이것이 취업을 위한 코딩 테스트다 with 파이썬
이것이 취업을 위한 코딩 테스트다 with 파이썬의 내용
탐색: 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정
자료구조: 데이터를 표현하고 관리하고 처리하기 위한 구조
Stack: 박스 쌓기, 선입후출 or 후입선출 구조
Queue: 대기 줄, 선입선출 구조
큐의 구현을 위해 deque 라이브러리 사용
DFS / BFS
DFS
DFS(Depth-First Search): 깊이 우선 탐색, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘
프로그래밍에서 그래프는 크게 2가지 방식으로 표현할 수 있다.
인접 행렬: 2차원 배열로 그래프를 표현하는 방식
인접 리스트: 리스트로 그래프의 연결 관계를 표현하는 방식, 연결 리스트 사용
메모리 측면에서 인접 행렬 방식은 모든 관계를 저장하므로 메모리가 낭비된다.
속도 측면에서 인접 리스트 방식은 특정한 두 노드가 연결되어 있는지에 대한 정보를 얻는 속도가 느리다.
1. 탐색 시작 노드를 스택에 삽입하고 방문 처리
2. 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리를 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
3. 2번 과정을 더 이상 수행할 수 없을 때까지 반복한다.
# 방문 처리는 처리된 노드가 다시 삽입되지 않게 체크하는 것.
# 방문 처리를 함으로써 각 노드를 한 번씩만 처리할 수 있다.N개의 데이터를 탐색하는데 O(N)의 시간이 소요된다.
재귀 함수를 이용했을 때 구현이 매우 간결
#DFS
graph = [[]] # 그래프를 2차원 리스트
visited = [False] * 9
def dfs(graph, v, visited):
# 현재 노드 방문 처리
visited[v] = True
print(v, end=' ')
# 현재 노드와 연결된 다른 노드를 재귀적으로 방문
for i in graph[v]:
if not visited[i]: # 방문되지 않았다면
dfs(graph, i, visited) # 재귀BFS
BFS는 너비우선탐색
DFS: 최대한 멀리 있는 노드를 우선 방문
BFS: 가까운 노드부터 탐색
deque 라이브러리를 사용하여 구현하는 것이 좋다
1. 탐색 시작 노드를 큐에 삽입 후 방문 처리
2. 큐에서 노드를 꺼내 인접 노드 중 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리
3. 2번의 과정을 수행할 수 없을 때까지 반복DFS와 같이 O(N)의 시간이 소요되지만 실제 수행 시간은 DFS보다 좋은 편
코딩 테스트에서는 보통 DFS보다는 BFS 구현이 조금 더 빠르게 동작한다
from collections import deque
#BFS
graph = [[]]
print(len(graph))
visited = [ False * len(graph)]
def bfs(graph, start, visited):
# 큐 구현을 위해 deque 라이브러리 사용
queue = deque([start])
# 현재 노드 방문 처리
visited[start] = True
# 큐가 빌 때까지 반복
while queue:
# 큐에서 하나의 원소를 뽑아 출력
v = queue.popleft()
print(v, end='')
# 해당 원소와 연결되고 아직 방문하지 않은 원소들 삽입
for i in graph[v]:
if not visited[i]:
queue.append(i)
visited[i] = True코딩 테스트에서 2차원 배열에서의 탐색 문제를 만나면 그래프 형태로 바꿔서 생각하면 풀이 방법을 조금 더 쉽게 떠올릴 수 있다.!
실전 문제
음료수 얼려먹기
미로탈출
dfs, bfs 관련 문제는 처음이라 생각해도 감이 안와서 책의 코드를 봤다
추후에 문제를 다시 풀어보고 코드를 올리겠다.정렬
정렬이란 데이터를 특정한 기준에 따라서 순서대로 나열하는 것
정렬 알고리즘으로 데이터를 정렬하면 이진 탐색이 가능해지니 제대로 알고 넘어가자.
정렬 알고리즘은 굉장히 다양하지만 많이 사용하는 선택 정렬, 삽입 정렬, 퀵 정렬, 계수 정렬만 이 책에서 언급함.
리스트를 뒤집는 연산은 O(N)의 복잡도로 간단히 수행할 수 있으므로 이 책에서는 오름차순 소스코드만 다룸
선택 정렬
가장 작은 데이터를 맨 앞에 있는 데이터와 바꾸고, 그 다음 작은 데이터를 앞에서 두 번째 데이터와 바꾸는 과정 N-1번 반복
동작 과정은 잘 정리된 블로그가 많으니 참고
array = []
for i in range(len(array)):
min_index = i # 가장 작은 원소의 인덱스
for j in range(i+1, len(array)):
if array[min_index] > array[j]:
min_index = j
array[i], array[min_index] = array[min_index], array[i] # swap선택 정렬의 시간 복잡도는 O(n^2)
삽입 정렬
두 번째 데이터부터 n번째 데이터까지 돌며 정렬된 데이터에 넣는다.
삽입 정렬은 선택 정렬에 비해 실행 시간측면에서 더 효율적인알고리즘
동작 과정은 잘 정리된 블로그가 많으니 참고
array = [4,2,1,6,8]
for i in range(1, len(array)):
for j in range(i, 0, -1): # 인덱스 i부터 1까지 감소하며 반복하는 문법
if array[j] < array[j-1]: # 한 칸씩 왼쪽으로 이동
array[j], array[j-1] = array[j-1], array[j]
else: # 자기보다 작은 데이터를 만나면 그 위치에서 멈춤
break
삽입 정렬의 시간 복잡도는 O(n^2)지만 데이터가 거의 정렬되어 있는 상태라면 매우 빠르게 동작한다.
최선의 경우 O(n)으로 동작한다.
보통 삽입 정렬이 퀵 정렬보다 비효율적이나 정렬이 거의 되어 있다면 퀵 정렬보다 더 강력하다.
퀵 정렬
퀵 정렬은 분할 정복 알고리즘의 하나로 매우 빠르게 동작한다.
퀵 정렬은 기준(피벗)을 설정한 다음 큰 수와 작은 수를 교환한 후 리스트를 반으로 나누는 방식으로 동작한다.
이 책에서는 가장 대표적인 분할 방식인 호어 분할 방식(리스트의 첫 번째 데이터를 피벗으로 설정)을 기준으로 설명함
퀵 정렬은 재귀 함수 형태로 작성했을 때 구현이 매우 간결해진다
동작 과정은 잘 정리된 블로그가 많으니 참고
널리 사용되고 있는 가장 직관적인 형태의 퀵 정렬 소스코드
array = []
def quick_sort(array, start, end):
if start >= end: # 원소가 1개인 겨우 종료
return
pivot = start
left = start + 1
right = end
while left <= right:
# 피벗보다 큰 데이터를 찾을 때까지 반복
while left <= end and array[left] <= array[pivot]:
left += 1
# 피벗보다 작은 데이터를 찾을 때까지 반복
while right >= start and array[right] >= array[pivot]:
right -= 1
if left > right: # 엇갈렸다면 작은 right -= 1 데이터와 피벗을 교체
array[right], array[pivot] = array[pivot], array[right]
else: # 엇갈리지 않았다면 작은 데이터와 큰 데이터를 교체
array[left], array[right] = array[right], array[left]
# 분할 이우 왼쪽 부분과 오른쪽 부분에서 각각 정렬 수행
quick_sort(array, start, right-1)
quick_sort(array, right+1, end)
quick_sort(array, 0, len(array) - 1)파이썬의 장점을 살려 짧게 작성한 퀵 정렬 소스코드
피벗과 데이터를 비교하는 연산 횟수가 증가하므로 시간 면에서는 비효율적
더 직관적이고 기억하기 쉽다는 장점
array = []
def quick_sort(array):
# 리스트가 하나의 원소만을 담고 있다면 종료
if len(array) <= 1:
return array
pivot = array[0] # 피벗은 첫 번째 원소
tail = array[1:] # 피벗을 제외한 리스트
left_side = [x for x in tail if x <= pivot] # 분할된 왼쪽 부분
right_side = [x for x in tail if x > pivot] # 분할된 오른쪽 부분
# 분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 정렬을 수행하고, 전체 리스트를 반환
return quick_sort(left_side) + [pivot] + quick_sort(right_side)파이썬의 장점을 살려 작성한 퀵 정렬 코드를 보니 앞의 직관적 형태의 코드가 머리속에서 사라졌다.
퀵 정렬의 평균 시간 복잡도는 O(NlogN)이지만 최악의 경우 시간 복잡도는 O(n^2)이다.
이 책에서의 퀵 정렬처럼 리스트의 가장 왼쪽 데이터를 피벗으로 삼을 때, '이미 데이터가 정렬되어 있는 경우'에는 매우 느리게 동작한다.
코딩 테스트를 목적으로 하는 경우 퀵 정렬의 시간 복잡도 증명에 대하여 자세히 알지 못해도 큰 무리가 없다.
계수 정렬
계수 정렬 알고리즘은 특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠른 정렬 알고리즘이다.
계수 정렬은 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때만 사용할 수 있다.
데이터의 값이 무한한 범위를 가질 수 있는 실수형 데이터가 주어지는 경우 사용하기 어렵다.
가장 큰 데이터와 가장 작은 데이터의 차이가 1,000,000을 넘지 않을 때 효과적으로 사용할 수 있다.
계수 정렬은 앞서 다루었던 3가지 정렬 알고리즘(비교 기반의 정렬 알고리즘)처럼 직접 데이터의 값을 비교한 뒤에 위치를 변경하며 정렬하는 방식이 아니다.
계수 정렬은 별도의 리스트를 선언하고 그 안에 각 데이터가 몇 번 등장했는지 그 횟수가 기록된다.
데이터의 크기가 한정되어 있고, 데이터의 크기가 많이 중복되어 있을수록 유리하며 항상 사용할 수는 없다. 데이터가 0과 999,999 단 2개만 존재한다면 심각한 비효율성 초래
동작 과정은 잘 정리된 블로그가 많으니 참고
# 모든 원소의 값이 0보다 크거나 같다고 가정
array = []
# 모든 범위를 포함하는 리스트 선언(모든 값은 0으로 초기화)
count = [] * (max(array) + 1) # 0부터 max(array)까지는 max(array) + 1개의 수가 존재
result = []
for i in range(len(array)):
count[array[i]] += 1 # 각 데이터에 해당하는 인덱스의 값 증가
for i in range(len(count)): # 리스트에 기록된 정렬 정보 확인
for j in range(count[i]):
result.append(i)모든 데이터가 양의 정수인 상황에 데이터의 개수가 N, 데이터 중 최댓값이 K일 때, 계수 정렬은 최악의 경우에도 수행 시간 O(N+K)를 보장한다.
계수 정렬의 공간 복잡도는 O(N+K)
보통 알고리즘 원리나 소스코드가 더 복합한 기수 정렬은 계수 정렬에 비해서 느리지만, 처리할 수 있는 정수의 크기는 더 크다. 다행히 반드시 기수 정렬을 이용해야만 해결할 수 있는 문제는 코딩 테스트에서 거의 출제되지 않으므로 책에서 자세히 다루지는 않음
파이썬의 정렬 라이브러리
파이썬은 기본 정렬 라이브러리인 sorted() 함수를 제공
sorted()는 병합 정렬을 기반으로 만들어졌는데, 병합 정렬은 일반적으로 퀵 정렬보다 느리지만 최악의 경우에도 O(NlogN)을 보장
sorted() 함수는 리스트, 딕셔너리 자료형 등을 입력받아서 정렬된 결과를 출력
sorted 소스코드
array = []
result = sorted(array)
print(result)sort 소스코드
array = []
array.sort()
print(array)key를 활용한 소스코드
람다함수를 사용할 수도 있다.
array = []
def setting(data):
return data[1]
result = sorted(array, key=setting)
print(result)정렬 라이브러리는 최악의 경우에도 O(NlogN)을 보장한다.
정렬 실전문제
위에서 아래로
n = int(input())
result = []
for i in range(n):
result.append(int(input()))
result.sort(reverse=True)
for i in range(len(result)):
print(result[i], end=' ')쉬운 문제였다.
성적이 낮은 순서로 학생 출력하기
n = int(input())
result = []
for i in range(n):
data = input().split()
result.append((data[0], int(data[1])))
result.sort(key=lambda x: x[1])
for name in result:
print(name[0], end=' ')lambda가 point
두 배열의 원소 교체
n, k = map(int, input().split())
list_A = list(map(int, input().split()))
list_B = list(map(int, input().split()))
list_A.sort()
list_B.sort()
for i in range(k):
if list_A[i] < list_B[n-1-i]:
list_A[i] = list_B[n-1-i]
else:
break
print(sum(list_A))코딩 테스트에서 정렬 알고리즘이 사용되는 경우
일반적으로 3가지 문제 유형으로 나타낼 수 있다
- 정렬 라이브러리로 풀 수 있는 문제: 단순히 정렬 기법을 알고 있는지 물어보는 문제로 기본 정렬 라이브러리의 사용 방법을 숙지하고 있으면 어렵지 않게 풀 수 있다.
- 정렬 알고리즘의 원리에 대해서 물어보는 문제: 선택 정렬, 삽입 정렬, 퀵 정렬 등의 원리를 알고 있어야 문제를 풀 수 있다.
- 더 빠른 정렬이 필요한 문제: 퀵 정렬 기반의 정렬 기법으로는 풀 수 없으며 계수 정렬 등의 다른 정렬 알고리즘을 이용하거나 문제에서 기존에 알려진 알고리즘의 구조적인 개선을 거쳐야 풀 수 있다.
