DFS(깊이 우선 탐색)

• DFS는 스택 자료구조(혹은 재귀함수)를 이용한다.
• DFS 동작 과정
  1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.
  2. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문처리한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
  3. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복
• 

# 노드 정보
graph = [
    [], # 0번 인덱스는 비워둠
    [2, 3, 8],  # 1번 노드
    [1, 7],  # 2번 노드
    [1, 4, 5],  # 3번 노드
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7] # 8번 노드
]

visited = [False] * 9

# 반복
def dfs1(graph, start_node):
    visited, need_visit = list(), list()
    need_visit.append(start_node) 
    
    while need_visit:
        node = need_visit.pop() # 스택 
        if node not in visited: 
            visited.append(node)  
            need_visit.extend(graph[node])  # 스택
                                            # extend는 iterable 객체만 올 수 있음. 각 요소를 분리하여 끝에 삽입.
                                            # append였다면, 각 요소를 분리하지 않고 iterable 객체를 그대로 넣었음(2차원 형태)
    return visited

# 재귀
def dfs2(graph, v, visited):
    # 현재 노드 방문처리
    visited[v] = True
    print(v, end = ' ')
    
    for i in graph[v]:
        if not visited[i]:
            dfs2(graph, i, visited)
    

# 출력
print(dfs1(graph, 1))
print()
print(dfs2(graph, 1, visited))

[1, 8, 7, 6, 2, 3, 5, 4]

1 2 7 6 8 3 4 5 None

BFS(너비 우선 탐색)

• BFS는 큐 자료구조를 이용한다.
• 시작 노드에서 가까운 노드들부터 방문
• 구체적인 동작 과정은 다음과 같다
  1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.
  2. 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중 방문하지 않은 노드를 모두 큐에 삽입하고 방문처리한다.
  3. 더 이상 2번의 과정을 수행할 수 없을 떄까지 반복
• • 

# 노드 정보
graph = [
    [], # 0번 인덱스는 비워둠
    [2, 3, 8],  # 1번 노드
    [1, 7],  # 2번 노드
    [1, 4, 5],  # 3번 노드
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7] # 8번 노드
]

visited = [False] * 9

#1
def bfs1(graph, start_node):
    visited, need_visit = list(), list()
    
    need_visit.append(start_node)
    
    while need_visit:
        node = need_visit.pop(0) # 큐.   (스택이면 DFS)
        if node not in visited:
            visited.append(node)
            need_visit.extend(graph[node])
    
    return visited

#2
from collections import deque

def bfs2(graph, start, visited):
    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

def bfs(graph, start_node):
    visited, need_visit = list(), list()
    
    need_visit.append(start_node)
    
    while need_visit:
        node = need_visit.pop(0) # 큐.   IF 스택이면 DFS
        if node not in visited:
            visited.append(node)
            need_visit.extend(graph[node])
    
    return visited

print(bfs1(graph, 1))
print(bfs2(graph, 1, visited))

[1, 2, 3, 8, 7, 4, 5, 6]
1 2 3 8 7 4 5 6 None

주의

• 들린 곳을 체크할 땐 꼭 need_visit에 append 하는 곳에서 할 것(시간 초과)

정렬 알고리즘

• 정렬: 데이터를 특정한 기준에 따라 순서대로 나열하는 것
• 일반적으로 문제 상황에 따라서 적절한 정렬 알고리즘이 공식처럼 사용됨
  |정렬 알고리즘|평균 시간 복잡도|공간 복잡도|특징|
  |:--:|:--:|:--:|:--:|
  |선택 정렬|O(N2)|O(N)|아이디어가 매우 간단함 (,,)|
  |삽입 정렬|O(N2)|O(N)|데이터가 거의 정렬되어 있을 땐 가장 빠름|
  |퀵 정렬|O(NlogN)|O(N)|대부분의 경우에 가장 접합하며, 충분히 빠름|
  |계수 정렬|O(N+K)|O(N+K)|데이터의 크기가 한정되어 있는 경우에만 사용이 가능하지만 매우 빠르게 동작함|

선택(Selection) 정렬

• 처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복
  • 탐색 범위는 반복할 때마다 1개씩 줄어듦
  • 맨 마지막은 안 해도 됨
• 시간복잡도: $O(N^2)$
• 

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

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]  # 스왑

print(array)

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

삽입(Insert) 정렬

• 처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입
• 선택 정렬에 비해 구현 난이도가 높은 편이지만, 일반적으로 더 효율적으로 동작함
• 시간복잡도: $O(N^2)$
  • 삽입 정렬은 현재 리스트의 데이터가 거의 정렬되어 있는 상태라면 매우 빠르게 동작합
    • 최선의 경우(데이터가 다 정렬되어 있는 경우) $O(N)$
• 

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

for i in range(1, len(array)):
    for j in range(i, 0, -1): 
        if array[j] < array[j - 1]:
            array[j], array[j - 1] = array[j - 1], array[j]
        else:
            break
            
print(array)

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

퀵(Quick) 정렬

• 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법
• 일반적인 상황에서 가장 많이 사용되는 정렬 알고리즘 중 하나
• 가장 기본적인 퀸 정렬은 첫 번째 데이터를 기준 데이터(Pivot)로 설정함
• 시간복잡도: 퀵 정렬은 평균의 경우 $O(NlogN)$의 시간 복잡도를 가짐
  • 최악의 경우 $O(N^2)$의 시간복잡도를 가짐(분할이 잘 안되는 경우, (이미 정렬된 배열에 대해 퀵 정렬))
• 퀵 정렬 동작 예시
  • 왼쪽으로부터 pivot보다 큰 값을 찾고, 오른쪽으로부터 pivot보다 작은 값을 찾아서 스왑
  • 위치가 엇갈리는 경우 pivot과 왼쪽 데이터(오른쪽에서 오던)의 위치를 서로 변경
    

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

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):
            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

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

# ** 퀵 정렬2 - 파이썬의 장점을 살린 방식 **

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

def quick_sort(array):
    if len(array) <= 1:
        return array
    pivot = array[0]
    not_pivot = array[1:]
    
    left_side = [x for x in not_pivot if x <= pivot]
    right_side = [x for x in not_pivot if x > pivot]
    
    return quick_sort(left_side) + [pivot] + quick_sort(right_side)

print(quick_sort(array))

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

계수 정렬

• 특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠르게 동작하는 알고리즘
  • 계수 정렬은 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때 사용 가능
  • 계수 정렬ㅇ느 동일한 값을 가지는 데이터가 여러 개 등장할 때 효과적으로 사용할 수 있다.
• 시간 복잡도: 최악의 경우에도 수행시간 O(N + K)를 보장
• 계수 정렬은 때에 따라서 심각한 비효율성을 초래할 수 있음
  • 데이터가 0과 999,999만 존재하는 경우(공간 복잡도 증가)
• 계수 정렬 동작 예시
  1. 가장 작은 데이터부터 가장 큰 데이터까지의 범위가 모두 담길 수 있도록 리스트를 초기화(0)
  2. 데이터를 하나씩 확인하며 데이터의 값과 동일한 인덱스의 데이터를 1씩 증가시킴
  3. 결과를 확인할 땐 리스트의 첫 번쨰 데이터부터 하나씩 그 값만큼 반복하여 인덱스를 출력

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

# 모든 범위를 포함하는 리스트 선언 및 초기화
count = [0 for i in range(max(array) + 1)]
# 카운트
for i in range(len(array)):
    count[array[i]] += 1

# 출력
for i in range(len(count)):  
    for j in range(count[i]): # coubt[i]의 수만큼 반복
        print(i, end = ' ')

0 0 1 1 2 2 3 4 5 5 6 7 8 9 9 

이진 탐색 알고리즘

• 순차 탐색: 리스트 안에 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법
• 이진 탐색: 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 기법
  • 이진 탐색은 시작점, 끝점, 중간점을 이용하여 탐색 범위를 설정함|
• 시간 복잡도: $O(logN)$
• 큰 탐색 범위를 보면 가장 먼저 이진 탐색을 떠올려야 함

def binary_search(array, target, start, end):
    if start > end:
        return False
    mid = (start + end) // 2
    
    if array[mid] == target:
        return mid    
    elif array[mid] > target:
        return binary_search(array, target, start, mid - 1)
    else:
        return binary_search(array, target, mid + 1, end)

array = [5, 7, 9, 0, 3, 1, 6, 2, 4, 8]
array.sort()

result = binary_search(array, 6, 0, len(array) - 1)
print(result)

6

파이썬 이진 탐색 라이브러리(bisect)

• bisect_left(a, x): 정렬된 순서를 유지하면서 배열 a에 x를 삽입할 가장 왼쪽 인덱스를 반환
• bisect_right(a, x): 정렬된 순서를 유지하면서 배열 a에 x를 삽입할 가장 오른쪽 인덱스를 반환
• 참고 : 값이 특정 범위에 속하는 데이터 개수 구할 때
  • bisect_left결과와 bisect_left결과의 차이를 통해 할 수 있음

from bisect import bisect_left, bisect_right

a = [1, 2, 4, 4, 8]
x = 4

print(a)
print(bisect_left(a, x))  # 인덱스 반환
print(bisect_right(a, x))  # 인덱스 반환

[1, 2, 4, 4, 8]
2
4

파라메트릭 서치(Parametric Search)

• 파라메트릭 서치란 최적화 문제를 결정 문제(예 혹은 아니오)로 바꾸어 해결하는 기법
  • ex) 특정한 조건을 만족하는 가장 알맞은 값을 빠르게 찾는 최적화문제
• 일반적으로 코딩 테스트에서 파라메트릭 서치 문제는 이진 탐색을 통해 해결할 수 있음.
• 큰 탐색 범위를 보면 가장 먼저 이진 탐색을 떠올려야 함

다이나믹 프로그래밍(동적 계획법)

• 다이나믹 프로그래밍은 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법
  • 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 한다.
• 다이나믹 프로그래밍의 구현은 일반적으로 두 가지 방식(탑 다운과 바텀 업)으로 구성됨
• 다이나믹 프로그래밍의 조건
  1. 최적 부분 구조(optimal substructure)
     • 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있다.
  2. 중복되는 부분 문제(overlapping subproblem)(여러 번 등장)
     • 동일한 작은 문제를 반복적으로 해결해야 한다
• 시간 복잡도
  • 메모이제이션을 이용하는 경우: $O(N)$

피보나치 수열

• 특정 k번째 피보나치 수는 앞 두 개의 피보나치 수를 더한 값임(1, 1, 2, 3, 5, 8, 13, 21, 34, ..., inf)
• 점화식이란 인접한 항들 사이의 관계식을 의미함
  • 피보나치 수열의 점화식 : an = an-1 + an-2 |||| a1 = 1, a2 = 1

피보나치 - 단순 재귀

# 피보나치 - 단순 재귀
def fibo(x):
    if x == 1 or x == 2 : 
        return 1
    return fibo(x - 1) + fibo(x - 2)

fibo(10)

55

• 
• 재귀함수 피보나치의 비효율성
  • 위 그림을 보면, 3번째 피보나치 수를 구하는 fibo(3)가 4번 발생한 것을 볼 수 있음
  • 시간 복잡도: O(2N)
  • 빅오 표기법을 기준으로 fibo(30)을 계산하기 위해선 약 10억 가량의 연산을 수행해야 함

피보나치의 효율적인 해법 : 다이나믹 프로그래밍

• 다이나믹 프로그래밍의 사용 조건을 만족하는지 확인
  1. 최적 부분 구조: 큰 문제를 작은 문제로 나눌 수 있다.
     • fibo(4)를 구하려면 fibo(3)과 fibo(2)로 해결할 수 있음
  2. 중복되는 부분문제: 동일한 작은 문제를 반복적으로 해결한다.
     • 같은 fibo(n)이 여러번 사용됨

피보나치는 다이나믹 프로그래밍의 사용 조건을 만족함

• 메모이제이션(하향식, 탑다운)
  • 한 번 계산한 결과를 메모리 공간에 메모하는 기법
    • 같은 문제를 다시 호출하면 메모했던 결과를 그대로 가져옴
    • 값을 기록해 놓는다는 점에서 캐싱(caching)이라고도 함

탑다운(하향식) vs 바텀업(상향식)

• 다이나믹 프로그래밍의 전형적인 형태는 바텀업 방식임(반복문)
  • (결과 저장용 리스트는 DP테이블이라고 부름)
• 엄밀히 말하면 메모이제이션은 이전에 계산된 결과를 일시적으로 기록해놓는 넓은 개념을 의미
  • 따라서 메모이제이션은 다이나믹 프로그래밍에 국한된 개념은 아님
  • 한 번 계산된 결과를 담아 놓기만 하고 다이나믹 프로그래밍을 위해 활용하지 않을 수도 있음

# 피보나치 - 탑다운 다이나믹 프로그래밍(재귀)

# 한 번 계산된 결과를 메모이제이션 하기 위한 리스트 초기화 0 ~ 99
d = [0] * 100

# 피보나치 함수를 재귀함수로 구현(탑다운 다이나믹 프로그래밍)
def fibo(x):
    if x == 1 or x == 2:
        return 1
    
    # 이미 계산한 적 있는 문제라면 그대로 반환(메모이제이션)
    if d[x] != 0:
        return d[x]
    
    # 계산하지 않은 문제는 점화식에 따라 피보나치 결과 반환
    d[x] = fibo(x - 1) + fibo(x - 2)
    return d[x]

print(fibo(99))

218922995834555169026

# 피보나치 - 바텀업 다이나믹 프로그래밍(반복문)

d = [0] * 100

# 첫 번째 피보나치 수와 두 번쨰 피보나치 수는 1
d[1], d[2] = 1, 1

n = 99
# 피보나치 함수 반복문으로 구현(바텀업 다이나믹 프로그래밍)
for i in range(3, n + 1):
    d[i] = d[i - 1] + d[i - 2]

print(d[n])

218922995834555169026

다이나믹 프로그래밍 VS 분할 정복

• 분할 정복
  • 문제를 나눌 수 없을 때까지 나누어서 각각을 풀면서 다시 합병하여 문제의 답을 얻는 알고리즘
  • 하향식 접근법으로, 상위의 해답을 구하기 위해, 아래로 내려가면서 하위의 해답을 구하는 방식
    • 일반적으로 재귀 함수로 구현
  • 문제를 잘게 쪼갤 때, 부분 문제는 서로 중복되지 않음
    • ex) 병합 정렬, 퀵 정렬 등
• 다이나믹 프로그래밍과 분할 정복은 모두 최적 부분 구조를 가질 떄 사용할 수 있다.
  • 큰 문제를 작은 무제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있는 상황
• 다이나믹 프로그래밍과 분할 정복의 차이점은 부분 문제의 중복이다.
  • 다이나믹 프로그래밍 문제에서는 각 부분 문제제들이 서로 영향을 미치며 부분 문제가 종복된다.
  • 분할 정복 문제에서는 동일한 부분 문제가 반복적으로 계산되지 않는다

다이나믹 프로그래밍 문제에 접근하는 방법

• 주어진 문제가 다이나믹 프로그래밍 유형임을 파악하는 것이 중요
• 가장 먼저 그리디, 구현, 완전 탐색 등의 아이디어로 문제를 해결할 수 있는지 검토
  • 다른 알고리즘으로 풀이 방법이 떠오르지 않으면 다이나믹 프로그래밍을 고려
• 일단 재귀 함수로 비효율적인 완전 탐색 프로그램을 작성한 뒤에(탑다운) 작은 문제에서 구한 답이 큰 문제에서 그대로 사용될 수 있으면, 코드를 개선하는 방법을 사용
• 일반적인 코딩 테스트 수준에서는 기본 유형의 다이나믹 프로그래밍 문제가 출제되는 경우가 많음