길벗출판사 취업과 이직을 위한 프로그래머스 코딩테스트 문제풀이 전략 파이썬 편 정리 및 리뷰
- 문제를 읽고 스스로 풀어보는 시간을 갖습니다.
- 시간 초과가 발생하거나 해결 방법이 생각나지 않아도 괜찮습니다. 알고 있는 모든 지식을 동원해 충분한 시간과 노력을 들여 문제를 풀어보세요
- 문제를 모두 풀었다면, 과정을 되짚으면서 해설을 읽어봅니다.
- 모법 답안을 보고 문제를 어떻게 이해하고 접근했는지 살펴보고 여러분의 풀이와 어떤 점이 다른지, 어떤 점이 부족했는지를 생각해 봅니다.
- 설명이 이해되지 않는 부분은 체크하고 과감히 넘어가세요
- 뒷장에서 다시 설명하는 개념도 있기 때문에 한 번 책을 읽고 나서 돌아오면 의외로 쉽게 이해할 수 있습니다.
- 풀이법을 모두 이해했다면 한 문제를 푼 겁니다. 하지만 꼭 한 가지 방법으로만 문제를 풀 필요는 없습니다.
- 가능하다면 책에서는 여러 가지 방법으로 문제를 풀어볼 것입니다. 똑같은 문제를 다르게 해석하고 푸는 과정을 되짚으면서 문제에서 제시한 키워드를 어떻게 풀어나가는지 고민해보세요.
작가가 생각하는 코딩테스트에서의 잘 짠 코드
길벗출판사의 책 "취업과 이직을 위한 프로그래머스 코딩테스트 문제풀이 전략 파이썬 편"에서는 코딩테스트에서 잘 짠 코드를 작성하기 위한 여러 가지 요소들을 설명하고 있습니다. 그 중에서도 시간 복잡도, 공간 복잡도, 가독성, 그리고 유지보수성이 가장 중요한 요소로 소개되고 있습니다.
시간 복잡도는 알고리즘 문제에서 가장 기본적인 요소 중 하나입니다. 적절한 시간 복잡도를 가진 알고리즘을 선택하지 않으면, 코딩테스트에서 시간 초과로 인해 제한 시간 안에 문제를 푸는 것이 불가능해질 수 있습니다.
또한, 공간 복잡도도 중요한 요소 중 하나입니다. 메모리를 많이 사용하는 알고리즘은 대용량 데이터를 다루는 문제에서는 효율적이지 않을 수 있습니다.
가독성은 코드의 가독성을 높이는 것입니다. 다른 사람이 작성한 코드를 읽을 때, 코드의 구조와 의미를 파악하기 쉽도록 작성해야 합니다. 이를 위해서는 변수명, 주석 등을 적절히 활용하여 코드를 작성해야 합니다.
마지막으로, 유지보수성은 코드가 수정되거나 업데이트되더라도 기존 코드를 유지보수하기 쉽도록 작성되어야 합니다. 이를 위해서는 코드의 일관성을 유지하고, 중복 코드를 제거하며, 함수나 모듈 등을 적절히 분리하여 작성해야 합니다.
따라서, 코딩테스트에서는 이러한 요소들을 고려하여 잘 짠 코드를 작성해야 합니다.
코드를 짤 때 흔히 하는 실수
- 존재하지 않는 요소에 접근하는지 확인합니다. 만약 접근하려는 요소가 존재하지 않으면 새로운 값을 할당하거나 예외 처리를 해야 합니다.
- 파이썬에서는 배열 슬라이싱 기능을 사용할 때 [시작 위치(포함), 종료 위치(포함 안함), 간격]이라는 걸 항상 기억하여, 슬라이싱 결과가 예상한 대로 나오도록 합니다.
- ‘~보다 크다/작다’조건으로 조건식을 만들 때, 조건식의 경계값을 제대로 체크하지 않으면 의도하지 않은 결과가 나올 수 있습니다. 따라서 조건식을 만들 때, 경계값도 항상 고려해야 합니다.
- 연산자의 우선순위 문제도 빠질 수 없으므로, 코드를 작성할 때 우선순위를 명확하게 하거나 괄호로 묶어서 우선순위를 지정합니다.
- 자료형 변환도 항상 유념해야 합니다. 자료형을 변환할 때, 정확한 변환 방법을 사용하여 원하는 결과를 얻습니다.
- 최대치나 최소치 설정을 제대로 했는지 검사하는 습관도 중요합니다. 최대치나 최소치를 설정할 때, 예외 상황도 고려하여 적절한 값을 설정합니다.
- 반복문이나 재귀 함수에서 종료 조건이 어긋나 영원히 프로그램이 끝나지 않는 일도 종종 일어납니다. 따라서 반복문이나 재귀 함수를 작성할 때, 종료 조건도 항상 확인합니다.
- 절대 0으로 곱하거나 나누지 마세요. 이는 예외 상황을 발생시킵니다. 대신, 0으로 나누는 경우 예외 처리를 해야 합니다.
디버깅과 시행착오를 줄일 수 있는 몇가지 방법
- 기능을 모듈화하는 것은 코드를 더욱 체계적으로 작성할 수 있는 방법 중 하나입니다. 모듈화를 통해, 코드를 더욱 쉽게 분리하고 관리할 수 있습니다. 예를 들어, 각각의 기능을 함수로 만들어서 작성하면, 코드를 더욱 쉽게 분리하고 관리할 수 있습니다. 이를 통해, 코드의 유지보수성을 높일 수 있습니다. 또한, 모듈화를 통해 코드의 재사용성을 높일 수 있습니다. 여러 번 사용되는 기능을 함수로 만들어서 모듈화하면, 다른 프로그램에서도 쉽게 사용할 수 있습니다.
- 변수를 사용할 때는 선언 위치와 초기화 위치를 명시하는 것이 좋습니다. 또한, 변수 이름을 의미 있는 이름으로 만들어서 가독성을 높일 수 있습니다. 예를 들어, 상수는 대문자로 명명하고, 지역 변수와 전역 변수는 구분하여 사용하는 것이 좋습니다. 변수의 타입도 명시적으로 표시하는 것이 좋습니다. 이를 통해, 코드의 가독성을 높일 수 있고, 변수의 사용이 잘못되는 오류를 방지할 수 있습니다. 변수의 스코프와 생명주기를 이해하고, 변수의 사용을 적절하게 제어하는 것도 중요합니다.
- 코드의 가독성을 높이기 위해서는 주석을 적극적으로 활용하는 것이 좋습니다. 주석은 코드를 읽는 사람에게 코드의 구조와 의미를 파악하기 쉽도록 도와줍니다. 또한, 코드를 작성할 때, 변수 이름을 잘 지어서 코드의 의미를 더 나타나게 하는 것도 중요합니다. 변수의 의미를 파악하기 쉽도록 변수 이름을 지으면, 코드를 이해하기 쉬워집니다. 함수를 작성할 때도 함수의 기능을 정확하게 설명하는 docstring을 작성하면 가독성을 높일 수 있습니다.
- 내부 라이브러리를 적극적으로 활용하여, 코드를 더욱 간결하고 효율적으로 작성할 수 있습니다. 내부 라이브러리는 파이썬에서 기본적으로 제공되는 라이브러리로, 사용하기 쉽고, 디버깅이 용이합니다. 외부 라이브러리를 사용하는 경우에는 디버깅이 어려울 수 있으므로, 가능한 내부 라이브러리를 사용하는 것이 좋습니다. 내부 라이브러리를 잘 활용하면, 코드의 길이도 줄일 수 있습니다. 또한, 파이썬에서 기본적으로 제공되는 라이브러리의 기능을 잘 파악하고, 적절히 활용하는 것도 중요합니다.
- 파이썬에서 지원하지 않는 기능을 대체할 수 있는 다른 기능을 찾아보는 것도 중요합니다. 예를 들어, if-else 문을 사용하여 삼항 연산자를 대체할 수 있습니다. 또한, 증감 연산자를 대체할 수 있는 다른 방법도 고려해 보는 것이 좋습니다. 이를 통해, 코드의 가독성을 높일 수 있고, 더욱 효율적인 코드를 작성할 수 있습니다. 또한, 파이썬에서 제공하는 다양한 라이브러리와 함수들을 잘 파악하고 사용하는 것도 중요합니다. 이를 통해, 코드를 더욱 효율적으로 작성할 수 있습니다.
시간 복잡도란?
시간 복잡도는 알고리즘을 수행하는 데 걸리는 시간을 나타내는 개념입니다. 알고리즘의 시간 복잡도를 나타내는 데에는 보통 빅오(Big-O)표기법을 사용합니다. 이 기호는 최악의 경우의 시간 복잡도를 의미합니다. 즉, 알고리즘이 어떤 입력에 대해서도 항상 일정한 시간 내에 종료된다면, 이 알고리즘의 시간 복잡도는 O(1)입니다.
1.빅오(Big-O)표기법
빅오(Big-O)표기법은 알고리즘의 시간 복잡도를 나타낼 때 사용하는 기호입니다. 이 기호는 알고리즘의 시간 복잡도를 대략적으로 알 수 있게 도와줍니다.
2. 시간 복잡도 그래프
시간 복잡도를 시각화하기 위해서는 시간 복잡도 그래프를 사용할 수 있습니다. 이 그래프는 입력 크기와 연산 횟수가 어떤 관계를 가지는지를 나타냅니다. 그림에서 볼 수 있듯이, 입력 크기가 증가하면서 연산 횟수도 증가함을 알 수 있습니다.
3. 시간 복잡도 선택 시 참고할 만한 사항
시간 복잡도를 선택할 때는 여러 가지 요소를 고려해야 합니다. 예를 들어, 알고리즘의 입력 크기가 작다면, 시간 복잡도가 크게 중요하지 않을 수 있습니다. 또한, 알고리즘이 수행하는 작업이 간단하다면, 시간 복잡도가 낮은 알고리즘을 선택하는 것이 좋습니다.
시간 복잡도 계산하기
1. 어림짐작해보기
시간 복잡도를 계산하기 위해서는 우선 알고리즘의 각 단계에서 수행되는 연산의 횟수를 파악해야 합니다. 이를 위해서는 알고리즘의 구성요소를 자세히 분석해야 합니다. 그러나 이렇게 계산하는 것 만으로는 충분하지 않을 때가 있습니다.
2. 시간 복잡도 줄이기
시간 복잡도를 줄이기 위해서는 다양한 기술을 사용할 수 있습니다. 예를 들어, 입력 데이터를 정렬하는 것이 시간 복잡도를 줄이는 데에 효과적일 수 있습니다. 또한, 반복문을 최적화하거나, 중복 연산을 제거하는 것도 시간 복잡도를 줄이는 데에 도움이 됩니다. 이러한 기술들을 사용하면, 기존에는 시간 복잡도가 높았던 알고리즘을 더욱 효율적으로 개선할 수 있습니다.
3. 여러 상황에서의 시간복잡도 생각해보기
프로그래밍에서 알고리즘을 선택할 때는, 여러 상황에서의 시간 복잡도를 고려해야 합니다. 예를 들어, 알고리즘이 대용량 데이터를 다룰 때는 시간 복잡도가 큰 알고리즘을 선택하면 안됩니다. 또한, 알고리즘이 동시에 여러 가지 작업을 수행하는 경우에는 시간 복잡도가 높은 알고리즘을 선택하면 안됩니다. 이러한 상황에서도 적절한 시간 복잡도를 선택하려면, 알고리즘의 특징을 잘 파악하고, 가능한 모든 상황을 고려해야 합니다.
시간복잡도 선택 시 참고할 만한 사항
대충 1억번 연산이 1초라는 것을 알고
입력값 최대크기가 10만개라면 O(n^2)은 시간초과가 날 가능성이 매우 높다.
A. 1,000개라면 —>O(n^2)이하
B. 10,000개라면 —>O(n^2)미만(최대한 적게 사용하는 방향으로)
C. 100,000개라면 —> O(nlogn) 이하
D. 1,000,000이라면—>입력 데이터 수가 백만 개 이사이라면 문제의 조건을 유심히 살펴보세요 특정 알고리즘을 사용하도록 요구할 가능성이 큽니다.
- heapq: 이진 트리 기반의 최소 힙 자료 구조입니다. 항상 정렬된 상태로 값의 추가/삭제가 이루어집니다. 우선순위 큐나 최단거리 알고리즘을 구현할 때 많이 사용됩니다.
- collections: 연속되 자료를 가지고 있는 자료형에서 동일한 원소가 몇 개 있는지 확인 가능한 counter가 있기 때문에 해시 문제르 풀 때 유용합니다. 추가로 덱(dequeue) 자료 구조를 구현하는 데 사용하는 deque도 있습니다.
- itertools: 경우의 수 문제에 사용하며 순열(pernutations), 조합(combination), 중복순열(permutations_with_replacement), 중복조합(combinations_with_replacement) 등에 사용합니다.
- math: 복잡한 수학 연산을 대신하는 라이브러리입니다. 최대공약수, 최소공배수, 팩토리얼, 제곱근, 로그 등을 계산하며, 파이, 자연상수와 같은 상수도 존재해 수학 문제가 나온다면 이것만 있으면 됩니다.
- bisect: 이진 탐색 기능을 제공합니다. 정렬된 데이터가 필요하며, 특정 범위 안에 원소가 있는지 검사하거나 몇 개가 존재하는지 확인하는 데 유용합니다.
제너레이터를 만드는 방법 2가지
- return대신 yield 문구를 넣거나
- 컴프리헨션 문구를 소괄호로 감싸주는 방식으로 표현식을 생성합니다.
- (i for i in range(11))
- 이 함수는 한 번에 1부터 10까지 진행하지 않고, 직접 next()를 호출해야 1,2,3의 값이 반환됩니다 이때, 이전 값은 갖지 않으며, 필요하다면 따로 list()같은 함수를 통해 실행되는 값을 저장해야 합니다.
리스트 컴프리헨션 대신 제너레이터를 사용하는 이유:
메모리 관리 때문이다.
문제 1 교점에 별 만들기
문제 풀이
또 다른 문제 풀이
—> 내가 생각핮 못한 풀이법이 나온다.
내가 처음 생각한 풀이 방법:
참고사항에 적혀있느 두 직선의 교점이 유일하게 존재할 경우, 그 교점은 다음과 같다.
- 주어진 직선의 교점을 구한다.
- 그중 정수 교점만 따로 변수로 지정한다.
- 교정을 모두 표현할 수 있는 최소한의 사각형을 알아냅니다.
- 모든 교점을 *로 찍어서 표현합니다.
- 배열을 거꾸로 뒤집어 반환합니다.
다른 풀이 방법 : 5. 배열을 거꾸로 뒤집어 반환
reversed로 배열 역순 or 처음부터 역순
주의할 점 : 문자열을 2~3개 이상 합칠 때에는 join 사용 + 는 내부 처리 비용 high
주의할 점 2 : 리스트 컴프리헨션으로 이차원 배열을 생성할 때, 리스트의 곱셈은 동일한 데이터의 주소를 복사하는 얕은 복사이기 때문에 리스트의 곱셈을 2번 해서 [[v]n]n] 처럼 2차원 배열을 생성하면, [v]n 원본 하나에 바로가기 n-1개 생기는 느낌이다. 따라서 1차원 배열을 각각 10개 만들려면 [[v]n for i in range(n)]와 같이 1차원 배열 만드는 놈을 10번 실행 시켜 주어야 한다.
전체 코드:
def solution(line):
meet = list()
x_max = y_max = -float('inf')
x_min = y_min = float('inf')
for i in range(len(line)):
a, b, e = line[i]
for j in range(i + 1, len(line)):
c, d, f = line[j]
if ((a * d) - (b * c)) == 0:
continue
x = ((b * f) - (e * d)) / ((a * d) - (b * c))
y = ((e * c) - (a * f)) / ((a * d) - (b * c))
if x.is_integer() and y.is_integer():
x = int(x)
y = int(y)
meet.append([x, y])
x_max, y_max = max(x_max, x), max(y_max, y)
x_min, y_min = min(x_min, x), min(y_min, y)
meet = sorted(meet, key = lambda i: -i[1])
width = abs(x_max - x_min) + 1
height = abs(y_max - y_min) + 1
answer = [['.'] * width for _ in range(height)]
for x, y in meet:
ny = y_max - y
nx = x - x_min
answer[ny][nx] = '*'
return list(map(''.join, answer))취업과 이직을 위한 프로그래머스 코딩 테스트 문제풀이 전략 파이썬편을 읽으며…
이 책을 읽으며 알고리즘의 시간복잡도와 공간복잡도를 2장에 걸쳐 설명할 만큼 효율적으로 문제를 해결하는 부분에 집중했고, 사용되는 알고리즘이 부각되어 쉽게 설명할 수 있는 문제들만 뽑아서 만들었다고 느꼈다.
내가 이 책을 읽은 목적이자, 추천하는 이유는 ‘또 다른 풀이’이다. 책의 첫 번째 문제의 다른 풀이는 그저 배열의 역순부분만 다르게 풀어 아쉬움이 생길 뻔 했지만, 다른 문제들, 특히 dfs에서는 재귀와 스택으로 다르게 풀이하고 시간복잡도와 그래프의 디테일을 알려주는 것을 보고 시간을 들여 읽을 가치가 있는 책이라고 생각하게 되었다.
혼자 코테 문제를 풀다보면 익숙해지고, 지금까지 됐었던 방법들을 계속 쓰게 된다. 그때마다 드는 경험에서 우러나오는 불안한 생각, “제한시간이 조금이라도 줄었다면, 입력값이 1,000,000이 넘었더라도 이 문제를 통과할 수 있었을까? 더 좋은 풀이방법이 존재하지는 않을까?” 이 책은 문제를 더욱 더 효율적으로 해결하기 위한 다른 방법을 찾는다는 핑계로 여러 블로그를 전전하다 유튜브로 빠져버리는 나에게 씌어주는 차안대이다.
'도서리뷰' 카테고리의 다른 글
| [길벗 개발자 리뷰]이펙티브 엔지니어 (0) | 2022.07.28 |
|---|
