이것이 코딩테스트다

Greedy

• 현재 상황에서 가장 좋아 보이는 것 만을 선택해도 문제를 풀 수 있는지 파악할 수 있어야 한다
• 가장 큰 순서대로, 가장 작은 순서대로 와 같이 기준을 제시해 준다
• 정렬 알고리즘과 자주 짝을 이뤄 출제된다

예제

1. 거스름돈

   당신은 음식점의 계산을 도와주는 점원이다. 카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원 짜리 동전이 무한이 존재한다. 손님에게 거슬러 줘야 할 돈이 N원일 때 거슬러 줘야 할 동전의 최소 개수를 구하라. 단 거슬러 줘야 할 돈 N은 항상 10의 배수이다.

   해설

   • 그리디를 이용해 풀 수 있는 대표적인 문제로 간단한 아이디어만 떠올릴 수 있으면 문제를 해결할 수 있다.
   • 큰 돈 부터 먼저 거슬러 줄 수 있을 만큼 거슬러 준다.
   • 동전을 차례대로 거슬러 줄 수 있을 만큼 거슬러 주면 최소의 동전 개수로 모두 거슬러 줄 수 있다.

정당성

• 대부분의 문제는 그리디를 이용했을 때 최적의 해를 찾을 수 없을 가능성이 크다
• 그리디 알고리즘으로 문제의 해법을 찾았을 때는 그 해법이 정당한지 검토해야 한다
• 위의 예제에서는 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문에 그리디를 사용할 수 있는 것이다

구현

• 완전 탐색은 모든 경우의 수를 주저 없이 다 계산하는 해결 방법을 의미한다
• 시뮬레이션은 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행해야 하는 문제 유형을 의미한다
• 일반적으로 1초 = 2천만 ~ 1억 번 정도의 연산이라고 생각한다
• 시간 제한이 1초이고, 데이터의 수가 100만이라면 O(NlogN)이 되도록 수행해야 한다

DFS/BFS

• 스택과 큐를 활용한 알고리즘이다
• 스택은 단순 파이썬 리스트의 append, pop을 이용 할 수 있다
• 큐는 collections deque의 append와 popleft를 이용 할 수 있다

그래프

• 인접 행렬 방식과 인접 리스트 방식으로 표현할 수 있다

  • 인접 행렬은 2차원 배열에 노드가 연결된 형태를 기록한다
  • 인접 리스트는 각 노드가 연결된 정점을 배열에 저장하여 기록한다

• 예를 들어 0번 노드와 1번 노드가 7의 길이로 연결되어 있고, 0번 노드와 2번 노드가 5의 길이로 연결되어 있다면

• 인접 행렬은 [ [0, 7, 5], [7, 0, INF], [5, INF, 0] ]

• 인접 리스트 [[(1,7),(2,5)], [(0,7)], [(0,5)]]

• 메모리 측면에서는 인접 리스트가 더 효율적이다

• 하지만 연결 정보를 얻는 속도는 인접 행렬이 더 효율적이다

DFS

• 깊이 우선 탐색 기법으로 그래프의 깊은 부분을 먼저 탐색하는 기법이다
• 스택을 활용하여 각 노드에서 방문 되지 않은 인접 노드가 있으면 스택에 넣고 방문한다.
• 만약 방문 되지 않은 인접 노드가 없다면 스택에서 제거하고 이전 노드에서 다시 방문 되지 않은 인접 노드를 탐색한다
• 기본적으로 N개의 노드에 대해 O(N)의 복잡도를 가진다
• 스택을 사용하는 알고리즘이기 때문에 재귀로도 구현할 수 있다

Stack으로 구현

def solution(arr):
    stack = []
    visited = [0] * len(arr)
    # 시작점 stack에 넣기
    stack.append(1)
		visited[1] = 1
    # stack에 요소가 없을 때 까지 반복
    while len(stack) > 0:
				v = stack[-1]
        print(v)
        
				# 방문할 수 있는 인접 노드 확인
        flag = False
        for i in arr[v]:
            if visited[i] == 0:
								visited[i] = 1
                flag = True
                stack.append(i)
                break
        # 방문할 수 있는 인접 노드 없으면 pop
        if flag is False:
            stack.pop()

Recursive로 구현

def solution(start, arr):
    # Visited 정의
    visited = [False] * len(arr)
		visited[start] = True
		
    # 각 노드 별로 방문하는 DFS 함수 정의
    def DFS(loc, arr, visited):
				visited[loc] = True
        # 방문하지 않은 인접 노드 탐색
        for i in arr[loc]:
            # 발견 시 방문 
            if not visited[i]:
                DFS(i,arr, visited)
		
    DFS(start,arr, visited)

BFS

• 너비 우선 탐색 기법으로 가까운 노드부터 탐색하는 기법이다
• 큐에 시작점을 삽입한다
• 큐에서 노드를 꺼내 해당 노드의 방문 되지 않은 인접 노드를 모두 큐에 삽입한다
• 더 이상 수행할 수 없을 때 까지 위의 과정들을 반복한다
• BFS 역시 N개의 노드에 대해 O(N)의 복잡도를 가진다
• 일반적인 경우 BFS가 DFS 보다 실행 시간이 좋은 편이다

from collections import deque

def solution(start, arr):
    queue = deque([start])
    visited = [False] * len(arr)
		visited[start] = True

    while len(queue) > 0:
        v = queue.popleft()
        for i in arr[v]:
            if visited[i] == 0:
                queue.append(i)
				visited[i] = True

정렬

• 데이터를 정렬하면 이진 탐색 또한 가능해진다
• 선택 정렬, 삽입 정렬, 퀵 정렬, 계수 정렬

선택 정렬

• 정렬되지 않은 값 중 가장 작은 값을 선택 한다

arr = [7,5,9,0,3,1,6,2,4,8]
# i번째 전은 정렬되어 있다고 생각
# i번째 후의 값들 중 가장 작은 값을 '선택'해서 i번째로 이동
for i in range(len(arr)):
	min_index = i
	for j in range(i+1, len(arr)):
		if arr[min_index] > arr[j]:
			min_index = j
	# 가장 작은 값을 i번째로 이동
	arr[i], arr[min_index] = arr[min_index], arr[i] # swap

• N + N - 1 + … 1 = O(N^2)
• 효율적인 알고리즘은 아니나 코딩테스트에서 리스트에서 최소 값을 찾는 경우가 많기 때문에 익숙해질 필요가 있다

삽입 정렬

• 각 데이터를 적절한 위치에 ‘삽입’한다
• 필요할 때만 위치를 바꾸기 때문에 데이터가 거의 정렬되어 있을 때 더 효율적이다
• 첫 번째 데이터는 정렬이 되었다고 가정하고 두 번째 데이터부터 정렬을 시작한다
• 정렬된 데이터를 기준으로 어느 위치에 들어가야 할지 판단하여 해당 위치에 삽입한다

arr = [7,5,9,0,3,1,6,2,4,8]
# 0번은 정렬되어 있다고 생각
# i번째 값을 왼쪽 값들과 비교하며 적절한 위치에 '삽입'
for i in range(1, len(arr)):
	for j in range(i,0,-1):	
		if arr[j] < arr[j-1]:
			arr[j], arr[j-1] = arr[j-1], arr[j]
		else:
			break

• 삽입 정렬 역시 O(N^2)의 복잡도를 가진다
• 하지만 리스트가 거의 정렬되어 있는 경우 O(N)의 시간 복잡도를 가진다
• 보통 퀵 정렬이 더 효율적이지만 정렬이 거의 되어있는 경우 삽입정렬이 더 빠르기도 하다

퀵 정렬

• 병합 정렬과 함께 가장 빠른 알고리즘이다
• 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾼다
• 왼쪽에서 부터 시작하여 기준 데이터보다 큰 데이터를 찾고 오른쪽에서 부터 시작하여 기준 데이터보다 작은 데이터를 찾아 두 데이터의 위치를 바꾼다
• 위의 작업을 계속 반복하다 두 데이터의 위치가 엇갈린 경우 기준 데이터와 기준 데이터 보다 작은 데이터의 위치를 바꾼다
• 기준 데이터를 기준으로 오른쪽과 왼쪽이 나누어져 있기 때문에 왼쪽, 오른쪽에 대해 다시 퀵 정렬을 재귀적으로 적용한다
• 종료 조건은 리스트의 원소가 1개일 경우이다

arr = [5,7,9,0,3,1,6,2,4,8]

def quickSort(arr, start, end):
	pivot = start
	left = start + 1
	right = end
	while left <= right:
		while right > start and arr[right] >= arr[pivot]:
			right -= 1
		while left < end and arr[left] <= arr[pivot]:
			left += 1 
		if left > right:
			arr[right], arr[pivot] = arr[pivot], arr[right]
			break
		else:
			arr[left], arr[right] = arr[right], arr[left]
	quickSort(arr, right+1, end)
	quickSort(arr, start, right-1)

• 평균 시간복잡도는 O(NlogN)이다
• 하지만 피봇을 잘못 설정할 최악의 경우 O(N^2)이다

계수 정렬

• 데이터의 크기가 범위 제한이 되어 정수로 표현할 수 있어야 사용할 수 있지만 가장 빠른 알고리즘이다
• 모든 데이터가 양수인 경우 데이터의 개수가 N, 최대값이 K이면 최악의 경우에도 O(N+K)를 보장한다
• 일반적으로 가장 큰 데이터와 가장 작은 데이터 차이가 1,000,000을 넘지 않을 때 효과적으로 사용 할 수 있다

arr = [7,5,9,0,3,1,6,2,9,1,4,8,0,5,2]
count = [0] * (max(arr) + 1)
for i in range(len(arr)):
	count[arr[i]] += 1

파이썬 정렬

• sorted()는 병합 정렬 방식으로 구현되어 있으며 퀵 정렬보다는 느릴 수 있지만 O(NlogN)을 보장한다

• 리스트 내부의 sort() 함수로도 사용 가능하다

• sorted(), sort()의 매개변수로 key를 줄 수 있는데 이는 정렬의 기준을 나타내는 함수를 입력받는다

• 코딩테스트에서는 3가지의 정렬 문제로 구분될 수 있다

  • 정렬 라이브러리로 풀 수 있는 문제
  • 정렬 알고리즘의 원리에 대해서 물어보는 문제
  • 더 빠른 정렬이 필요한 문제

이진 탐색

• 순차 탐색은 리스트 안에 있는 특정 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법이다

• 이진 탐색은 내부 데이터가 정렬되어 있어야만 사용할 수 있다

• 찾으려는 데이터와 중간 지점의 데이터를 반복적으로 비교하여 데이터를 찾는 방법이다

  def binSearch(arr, target, start, end):
  	if start > end:
  		return none
  	mid = (start + end) // 2
  	if arr[mid] == target:
  		return mid
  	elif arr[mid] > target:
  		return binSearch(arr, target, start, mid - 1)
  	else:
  		return binSearch(arr, target, mid+1, end)

• 탐색 범위가 2000만을 넘어가면 이진 탐색으로 접근하는 것이 좋다

이진 탐색 트리

• 부모 노드보다 왼쪽 자식 노드가 작다
• 부모 노드보다 오른쪽 자식 노드가 크다

다이나믹 프로그래밍

• 메모리 공간을 약간 더 사용하여 연산 속도를 비약적으로 증가시킬 수 있는 방법이다.
• 대표적인 예로 피보나치 수열이 있다
• 피보나치 수열을 점화식으로 나타내면 $a\_{n+2} = f(a\_{n+1}, a\_n) = a\_{n+1} + a_n$

dp = [0] * 100
def fibo(x):
	if x == 1 or x == 2:
		return 1
	if dp[x] != 0:
		return dp[x]
	dp[x] = fibo(x-1) + fibo(x-2)
	return dp[x]

• $O(2^N)$의 복잡도를 가진다

• 다이나믹 프로그래밍은 다음의 경우에 적용할 수 있다

  1. 큰 문제를 작은 문제로 나눌 수 있다
  2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다

  dp = [0] * 100
  def fibo(x):
  	if x == 1 or x == 2:
  		return 1
  	if dp[x] != 0:
  		return dp[x]
  	dp[x] = fibo(x-1) + fibo(x-2)
  	return dp[x]

• 다이내믹 프로그래밍을 활용하는 경우 O(N)의 복잡도를 가지게 된다

• 이는 탑 다운 방식으로 큰 문제를 해결하기 위해 작은 문제를 호출한다

  dp = [0] * 100
  dp[1] = 1
  dp[2] = 2
  n = 99
  for i in range(3, n+1):
  	dp[i] = dp[i-1] + dp[i-2]

• 이 방식은 바텀업 방식이다

최단 경로

• 최단 경로 알고리즘은 다양한 유형이 존재한다

  • 한 지점에서 다른 특정 지점까지의 최단 경로를 구해야하는 경우
  • 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우

• 보통 그래프를 이용해 표현한다

• 다익스트라와 프로이드 워셜 알고리즘 유형에 대해 알아보자

다익스트라

• 그래프에서 여러 개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘이다

• 다익스트라 최단 경로 알고리즘은 음의 간선이 없을 때 정상적으로 동작한다

• 다익스트라는 기본적으로 그리디 알고리즘으로 분류할 수 있다

  1. 출발 노드를 설정
  2. 최단 거리 테이블을 초기화
  3. 방문하지 않은 노드중에서 최단 거리가 가장 짧은 노드를 선택한다
  4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신한다
  5. 위의 과정에서 3과 4번을 반복한다

• 다익스트라 알고리즘은 최단 경로를 구하는 과정에서 각 노드에 대한 현재까지의 최단 거리 정보를 항상 1차원 리스트에 저장하며 리스트를 계속 갱신한다는 특징이 있다

• 구현하기 쉽지만 느린 코드와 구현하기 어렵지만 빠른 코드 두 가지 방식으로 구현 가능하다

쉬운 버전 : O(V^2)

def dijkstra(arr):
    cur = 1
    visited = [0] * (N+1)
    costs = [INF] * (N+1)
    costs[1] = 0
    def getSmallest():
        minValue = INF
        index = -1
        for idx in range(1,N+1):
            if costs[idx] < minValue and visited[idx] == 0:
                minValue = costs[idx]
                index = idx
                
        return index
    
    for i in range(1,len(costs)-1):
        cur = getSmallest()
        visited[cur] = 1
        for j in range(1,N+1):
            # cur에서 j 까지 가리
            if j != cur:
                for k in arr:
                    if k[0] == cur and j == k[1]:
                        costs[j] = min(costs[j], costs[cur]+k[2])

• 노드의 수가 5000개 이하면 위의 방법을 사용해도 좋다

개선된 다익스트라 @ : O(ElogV)

• 힙을 사용하여 최단거리 테이블을 정렬한 상태로 유지한다
• heapq 라이브러리를 활용할 수 있다
• heapq는 기본적으로 min heap 방식이나 -를 붙여 max heap으로도 활용 가능하다
• 우선순위 큐를 구현하는데 가장 많이 사용된다

def dijkstr(arr):
    start = 1
    costs = [INF] * (N+1)
    costs[1] = 0
    q = []
    heapq.heappush(q,(0,start))
    while q:
        dist, cur = heapq.heappop(q)
        if distance[cur] < dist:
            continue
        for j in arr:
            if j[0] == cur:
                if costs[j[1]] > (dist + j[2]):
                    costs[j[1]] = dist + j[2]
                    heapq.heappush(q,(dist + j[2], j[1]))

플로이드 워셜

• 모든 지점에서 다른 모든 지점까지의 최단 경로를 구해야 하는 경우 사용할 수 있다

• 단계마다 해당 노드를 거쳐가는 경로를 확인하며 최단 거리 테이블을 갱신한다

• 따라서 현재 노드를 제외한 N-1개의 노드 중 두 노드를 선택하여 두 노드 사이에 현재 노드를 거쳐 가는 비용을 계산한다

• 따라서 전체 N개의 노드에 대해 N-1 P 2번의 연산이 수행 되기에 O(N^3)의 복잡도를 가진다

• K 번 단계에 대한 점화식은 다음과 같다

  $D\_{ab} = min(D\_{ab}, D\_{ak} + D\_{kb})$

def floydWarshall(arr):
    dist = [[INF for j in range(N+1)] for i in range(N+1)]
    # 거리 테이블 초기화
    for i in range(1,N+1):
        dist[i][i] = 0
        for k in arr:
            if k[0] == i:
                dist[i][k[1]] = k[2]
    for i in range(1,N+1):
        # i번 노드를 거쳐가는 경우
        for start in range(1,N+1):
            if start == i:
                continue
            for end in range(1,N+1):
                if end == i or end == start:
                    continue
                print(start,"에서",end,"까지",i,"를 거침 :",dist[start][end],dist[start][i]+dist[i][end])
                dist[start][end] = min(dist[start][end], dist[start][i] + dist[i][end])
    print(dist)

그래프 이론

• 그래프와 트리로 기본 자료구조를 나눠 볼 수 있다
• 표현 방식은 인접 행렬과 인접 리스트 방식이 있다
• 플로이드 워셜 방식의 경우 인접 행렬을 사용하는 방식으로 노드 수가 적을 때 사용 가능할 것이다
• 노드 수가 너무 많아 메모리가 부족하다면 다익스트라 같은 알고리즘을 고려할 수 있다

서로소 집합

• 공통 원소가 없는 집합

• 서로소 자료구조는 union, find 연산으로 구성된다

• 서로소 자료구조는 트리를 이용하여 구현된다

  Ex) 전체 집합 : {1,2,3,4,5,6}

  • union 1, 4
  • union 2, 3
  • union 2, 4
  • union 5, 6

  여기서 각 원소는 노드, 각 union 연산은 간선으로 표현한다

  union A,B
   1. A와 B의 부모노드 A`, B` 을 각각 찾는다
   2. A`을 B`의 부모노드로 설정한다 (값이 더 작은 루트가 루트가 되도록 한다)
  
      1       5
    2   4        6
  3

• 부모 테이블을 유지하여 각 원소마다의 부모를 저장한다

  parentTable = [i for i in range(1,N+1)]
  
  def findParent(a, parentTable):
  	if parentTable[a] != a:
  		parentTable[a] = findParent(parentTable[a], parentTable)
  	return parentTable[a]
  
  def union(a,b):
  	aParent = findParent(a)	
  	bParent = findParent(b)
  	if aParent > bParent:
  		parentTable[aParent] = bParent
  	else:
  		parentTable[bParent] = aParent

• 각각의 원소의 최종 루트를 찾게 되면 서로소를 판단할 수 있다

• 각 원소의 루트를 찾는 알고리즘의 시간 복잡도는 O(V)이다

• 따라서 union연산이 M이라고 할 때 전체 복잡도는 O(VM)이다

• 압축 기법을 통해서 findParent를 재귀적으로 사용할 때 parentTable을 업데이트하여 개선할 수 있다

서로소를 통한 사이클 판별

• 서로소 판별법은 무방향 그래프에서 사이클을 판별하는데 사용할 수 있다

• 방향 그래프에서 사이클은 DFS를 사용할 수 있다고 한다

• 간선을 하나씩 확인하면서 두 노드가 포함되어 있는 집합을 합치는 과정을 반복하면 사이클을 판별할 수 있다

  1. 각 간선을 확인하며 두 노드의 루트 노드를 확인한다
  2. 루트 노드가 서로 같다면 사이클이 발생한 것이다

신장 트리

• 하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 의미한다

• 최소한의 비용으로 신장 트리를 찾아야하는 경우 크루스칼 알고리즘을 사용할 수 있다

  • ex) 최소 비용으로 모든 도시를 연결

• 가장 적은 비용으로 모든 도시를 연결하는 그리디 알고리즘으로 분류할 수 있다

• 모든 간선을 비용순으로 정렬하고 가장 비용이 적은 간선 부터 포함한다

• 이때, 사이클이 생기는 간선은 포함하지 않는다

• 크루스칼 알고리즘은 O(ElogE)의 복잡도를 가진다

def find_parent(x, parent):
	if parent[x] != x:
		parent[x] = find_parent(parent[x], parent)
	return parent[x}

def union(parent, a, b):
	aParent = find_parent(a, parent)
	bParent = find_parent(b, parent)
	if aParent < bParent:
		parent[bParent] = aParent
	else:
		parent[aParent] = bParent

def kruskal(n, edges):
	# 비용이 적은 순서로 방문
	parent = [i for i in range(n+1)]
	edges.sort()
	total = 0
	for cost, a, b in edges:
		# 사이클이 생기는 경우 포함하지 않음
		if find_parent(a, parent) != find_parent(b,parent):
			union(parent, a, b)
			total += cost

위상 정렬

• 위상 정렬은 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것이다

  • ex) 선수과목을 고려한 학습 순서 설정

• 위상 정렬에서 진입 차수는 해당 노드로 들어오는 간선의 수를 의미한다

  1. 진입차수가 0인 노드를 큐에 넣는다

  2. 큐가 빌때 까지 다음 과정을 반복한다

     • 큐에서 원소를 꺼내 해당 노드에서 출발하는 간선을 그래프에서 제거한다
     • 새롭게 진입 차수가 0인 노드를 큐에 넣는다

from collections import deque

# arr는 인접리스트
def topology_sort(arr):
	result = []
	q = deque()
	indegree = [0 for i in range(n+1)]
	graph = [[] for i in range(n+1)]
	# 진입 차수 테이블, 그래프 초기화
	for a, b in arr:
		indegree[b] += 1
		graph[a].append(b)
	
	for i in range(1, n+1):
		if indegree[i] == 0:
			q.append(i)
	
	while q:
		cur = q.popleft()
		result.append(cur)
		# 현재 노드의 간선 제거
		for adj in graph[cur]:
			indegree[adj] -= 1
			if indegree[adj] == 0:
				q.append(adj)
	
	return result