🔥 저를 포함한 이직러들을 생각하며 만든 cheat sheet 입니다. 정리 및 리마인드겸 작성했습니다.
🔥 [23.10월 기준 미완성]
Coding Test Algorithm
빠른 찾기와 리마인드를 위한, python 코딩테스트 전용 cheat sheet
설명을 위한 글이 아닌점 유의 부탁드립니다.
1. 초중급 알고리즘 종류, intro
- PS분야 관점보다는 철저하게 코딩테스트 관점에서 나오는 자료구조, 알고리즘 종류들
- 사실 자료구조 자체가 기초 알고리즘을 기반으로 설계되었기 때문에 둘을 완전 분리하는 것은 어불성설 일 수 있으나, 기본적으로 바로 활용가능한 자료구조는 알고리즘과 구분했다.
1) Stack/Queue
- 알고리즘 종류라기 보단 자료구조다.
- Que는 python에서
deque쓰는게 좋음 - 괄호 없애기, 후위 연산 / 시계 방향의 배열 순환 거의 큐 (공주 구하기)
2) Hash
- 알고리즘 종류라기 보단 자료구조다.
- 중복 제거, 최적화,
- 완주하지 못한 선수
3) Heap (P.Q)
- 알고리즘 종류라기 보단 자료구조다.
- 완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조이다. / 여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조이다.
- insert 하는 순간에 대소비교를 하며 노드추가를 하니 최악은 O(logN) 이다. 그래서 P.Q를
for loop하나와 같이 응용하는 경우O(NlogN)이며 중첩for loop대신(O(N^2))최적화를 한다고 생각하자. - python P.Q는 기본라이브러리
heapq를 활용
4) Sorting
- 선택, 삽입, 버블, 합병(병합), 힙(tree), 퀵 까지는 기본 소양이다.
- n^2 / nlogn / 메모리 복잡도에 대한 개념은 있어야 한다.
- sorting 자체의 문제보다는 PS에 데이터 정렬이 필요한가? 정도를 알아차리는게 또 중요한 것 같다.
- 또 추가로 생각할 부분은, 메모리 복잡도가 크지 않다면, 계수 정렬 를 (index + counter) 사용하는 접근 법도 좋다.
O(N)
5) implementation, simulation
- Brute force / 완전 탐색의 형태가 많다. 단순 완탐의 접근법에 대해 기본적으로 다 알고 있어야 한다. 사실 단순 구현은 거의 보기 힘들고, 구현 + 다른 알고리즘 개념이 대부분이다.
- "simulation" 은 "문제에서 제시한 방법을 step by step 으로 직접 수행"하는 경우를 말한다.
- 어떻게 되었던 "구현"은 피지컬이 꽤 중요하다. 하지만 python에서는 자료형을 명시하지 않기 때문에 데이터 개수 - list 길이에 따라 얼마나 메모리 복잡도가 높은지 꼭 기억하고 있어야 한다.
- 1,000 - 약 4KB / 1,000,000 - 약 4MB / 10,000,000 - 약 40MB
- 나이트가 움직일 수 있는 경우의 수 /
6) Greedy (탐욕법)
- "그 순간 최선"을 다하는게 "최적"이라는, 내가 생각하기에 가장 어려운 개념을 가진 유형이다.
- 그리디 해결이 어떻게 항상 최적의 해를 보장할 수 있는지, "정당한지 검토할 수 있는 것" 이 핵심
- 거스름돈 (큰 단위가 항상 작은 단위의 배수 -> 작은 단위 종합해 다른 해가 나올 수 없기 때문) / 강의실 배정
7) DP
- 큰 문제를 작게 나누고, 같은 문제는 한 번만 풀자 / 최적화를 "메모리 관점"에서 가져가는 것, 중복되는 연산을 줄이는 것 / dynamic programing, 그리고 이를 위한 memoization(caching). 접근법은 top-down, bottom-up이 있다.
- 간단한 점화식 세우기는 쉬울지 몰라도 DP를 기본개념으로 상위 개념의 알고리즘까지 쭉 관통하는 개념이라 상대적으로 어렵다고 생각한다.
- 그리고 좀 더 복잡한 알고리즘 (완전탐색 + DP, 중복 방문-탐색에 대한 제한, DP) 을 나아가기위한 초석이다.
- 피보나치, 수열, n번째 수, 1로 만들기, 개미 전사, 바닥 공사 (타일링 문제), 효율적 화폐 구성(그리디 인척) 등
8) Graph
- 알고리즘 종류라기 보단 자료구조다.
- 그래프는 쉽게 말하자면 "노드와 노드를 연결하는 간선(edge)" 으로 이뤄진 자료구조다. 인접행렬과 인접 연결리스트 형태로 표현이 가능하다. 조금 더 상위 자료구조로 가기위한 첫 스탭.
- 종류가 워낙다양하고 그래프 자체만 문제로 나오진 않는다. 가장 흔하게는 그래프에서 [ DFS/BFS 탐색 + 조건 ] 정도 형태이다. 가중치가 있는 것은 탐색 순서에도 영향을 주니 기억!
- 주기(cycle, 경로의 시작과 끝 노드가 같은 경로)가 없는 연결된 그래프를 "트리(tree)"라고 한다.
9) DFS / BFS
- 깊이 우선 탐색 (stack, recursive)과 너비 우선 탐색 (queue, - deque) / "완전 탐색" 이 기본 원리임을 잊으면 안된다.
- 단순 탐색은 거의 안보이고 "map형태에서 상-하-좌-우 탐색 + 조건"의 문제가 가장 흔하다.
10) Binary Search
- 순서가 이미 있는, 즉 정렬되어 있는 배열(또는 object, list) 대상으로 해당 값을 가지는 Index를 찾는 알고리즘
- 검색 범위를 절반씩 줄여서 접근하여
O(N)이 걸릴 탐색을O(logN)으로 줄여준다. - Parametric Search 는 "주어진 범위 내에서 원하는 값 또는 원하는 조건에 가장 일치하는 값을 찾아내는 알고리즘" 이다. 최적화 문제를 결정 문제로 바꾸는 것. 이런 형태의 문제를 이진 탐색으로 해결한다.
- 떡볶이 떡 만들기
11) Binary Search Tree
- Tree중에 자식노드가 최대 두 개인 노드들로 구성된 트리를 "이진트리"라고 한다.
- 이진트리에는 정이진트리(full binary tree), 완전이진트리(complete binary tree), 균형이진트리(balanced binary tree) 등이 있다.
- 모든 왼쪽 자식의 값이 루트나 부모보다 작고, 모든 오른쪽 자식의 값이 루트나 부모보다 큰 값을 가지는 특징을 가지는 이진트리가 "이진 탐색 트리"
- 왼쪽 자식 노드 값 < 부모 노드 값 < 오른쪽 자식 노드 값
12) Backtracking
- 해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾아가는 기법
- 그 해를 찾는 과정 중에 어긋나면 아예 그 길로 가지 않는다는 원리다. 최적화 에서 중요하다. DFS의 예로, 깊이로 가는 중 하나라도 어긋나면 그 깊이까지 갈 이유가 전혀 없어진다. 이렇게 경우의 수를 확실하게 줄여 최적화를 한다. -> 모든 가능한 경우의 수 중에서 특정한 조건을 만족하는 경우만 살펴보는 것 / promising 이라고 표현한다.
- N번째 Queen
13) LIS / LCS
- Longest Increasing Subsequence(최장 증가 부분 수열) / Longest Common Subsequence(최장 공통 부분 수열) / 개념은 간단하지만 어떨때 해당 해법을 활용할지 판단하는게 쉽지않다.
- 기본적으로 부분 수열 구하기에 DP를 얹은 형태다. 하지만 그래도
O(N^2)이다. 그래서 이분탐색 을 활용해 최적화를 한다. - 반도체 설계
14) Dijkstra / Floyd-Warshall
- 보통 "최단거리"를 구하기 위해서 사용하는 알고리즘이다.
- 다익스트라는 한 지점에서 다른 특정 지점까지 최단 경로 인 반면, 플로이드워셜은 모든 지점에서 다른 모든 지점까지의 최단 경로 에 대해 알 수 있다.
- 다익스트라는 "그리디" 특성을 가지고, 플로이드워셜은 "DP"의 특성을 가진다.
15) Divide and Conquer
- 분할정복, 큰 부분을 작은 부분으로 나누어 해결하고, 작은 부분의 각 해결을 결합해 결국 전체 문제를 해결하는 방식, 아래 3가지 단계를 따른다. 알고리즘 분류의 큰 패러다임 중 하나다.
- 분할(
Divide): 원래 문제를 동일한 유형의 작은 하위 문제로 분할합니다. - 정복(
Conquer): 각 하위 문제를 재귀적으로 해결합니다. 하위 문제가 충분히 작으면 직접적인 방법으로 해결합니다. - 결합(
Combine): 하위 문제의 해결 방법을 결합하여 원래 문제의 해결 방법을 도출합니다.
- 퀵 정렬(Quick Sort), 이진 검색(Binary Search), 합병 정렬(Merge Sort), 최대 부분 배열 문제(Maximum Subarray Problem)
16) Topological Sort
- 사이클이 없는 방향 그래프에서, "순서가 정해져있는 작업"을 차례로 수행해야 할 때 그 순서를 결정해주기 위해 사용하는 알고리즘 / 유일해가 아님
17) Union-Find
- 부모 찾기
18) MST(Minimum Spanning Tree)
- Spanning Tree (신장트리)는 최소 연결 부분 그래프 이다. 최소 연결이란 말은 "간선의 수가 가장 적다"는 말이다. 한 그래프에서 다양한 신장트리가 존재한다.
- Kruskal Algorithm (그리디 특성) / Prim MST Algorithm 을 활용해서 최소 신장 트리를 찾는다.
19) 기타 (Trie)
2. Cheat Sheet
1) 복잡도 계산
시간 복잡도
공간 복잡도
a: list[int] = [0] * 1000 # >= 4KB
a: list[int] = [0] * 1000000 # >= 4MB
a: list[list[int]] = [[0] * 2000] * 2000 # >= 16MB2) 코테 테크니컬 python tip
직접 input 받을 때
- 일반적으로 list, map 을 활용
# 공백을 기준으로 구분된 데이터를 입력 받을 떄
data = list(map(int, input().split()))
# 공백을 기준으로 구분된 데이터가 많지 않다면
a, b, c = map(int, input().split())- sys stdin을 활용해 빠른 input 받기 (꼭 직접 입력을 받아야 한다면, 추천)
import sys
# 공백으로 구분된 2개 숫자 입력 받기
N, M = map(int,sys.stdin.readline().split())
# 2차원 리스트 입력 받기
board = [list(map(int,sys.stdin.readline().split())) for _ in range(N)]
# 문자열 입력 받기
data = sys.stdin.readline().rstrip()- 사실 빠른 입출력 (I/O)는 아래와 같이 print, input 함수를 새로운 함수로 바인딩해버리자
import sys
input = sys.stdin.readline
print = sys.stdout.write
# sys.stdin.readline()은 개행문자 "\n"까지 읽어들이기 때문에
# .rstrip()등으로 지워주어야 하고
n = input() # "1"을 입력 할 때,
print(list(n)) # ['1', '\n']
print([int(n)]) # [1]
print(list(n.rstrip())) # ['1']
# print()는 출력 방식이 다음과 같이 바뀌어 버린다.
print("%s\n" % "123") # 123
print("%s\n" % ("12" + "3")) # 123
print("%d + %d = %d\n" % (1, 2, 1 + 2)) # 1 + 2 = 3문자열 아스키코드, 대소 문자
import string
string.ascii_lowercase # 소문자 abcdefghijklmnopqrstuvwxyz
string.ascii_uppercase # 대문자 ABCDEFGHIJKLMNOPQRSTUVWXYZ
string.ascii_letters # 대소문자 모두 abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ
string.digits # 숫자 0123456789
# str method tip
str.isupper()
str.islower()- 파이썬에서는 ljust, center, rjust와 같은 string의 메소드를 사용해 코드를 획기적으로 줄일 수 있습니다.
s = '가나다라'
n = 7
s.ljust(n) # 좌측 정렬
s.center(n) # 가운데 정렬
s.rjust(n) # 우측 정렬ZIP 활용, 2차원 배열, 열과 행 뒤집기
mylist = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
new_list = [[], [], []]
for i in range(len(mylist)):
for j in range(len(mylist[i])):
new_list[i].append(mylist[j][i])
# 위와 동일 #
list(map(list, zip(*mylist)))
# +a zip으로 list 2개 각 key:value 만들기
animals = ['cat', 'dog', 'lion']
sounds = ['meow', 'woof', 'roar']
answer = dict(zip(animals, sounds)) # {'cat': 'meow', 'dog': 'woof', 'lion': 'roar'}
# zip 함수에 서로 길이가 다른 리스트가 인자로 들어오는 경우에는 길이가 짧은 쪽 까지만 이터레이션이 이루어집니다.
def solution(mylist):
answer = []
for number1, number2 in zip(mylist, mylist[1:]):
answer.append(abs(number1 - number2))
return answer
if __name__ == '__main__':
mylist = [83, 48, 13, 4, 71, 11]
print(solution(mylist))
map 활용하기
# list element 모두 int 로 형 변환
list1 = ['1', '100', '33']
list2 = list(map(int, list1))
a = list(map(str, range(10)))
# ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9']
# input에서 map object 활용하기
>>> a = map(int, input().split())
10 20 (입력)
>>> a
<map object at 0x03DFB0D0>
>>> list(a)
[10, 20]
2차원 배열 1차원으로 만들기
my_list = [[1, 2], [3, 4], [5, 6]]
# 방법 1 - sum 함수
answer = sum(my_list, [])
# 방법 2 - itertools.chain
import itertools
list(itertools.chain.from_iterable(my_list))
# 방법 3 - itertools와 unpacking
import itertools
list(itertools.chain(*my_list))
# 방법 4 - list comprehension 이용
[element for array in my_list for element in array]
# 방법 5 - reduce 함수 이용 1
from functools import reduce
list(reduce(lambda x, y: x+y, my_list))
# 방법 6 - reduce 함수 이용 2
from functools import reduce
import operator
list(reduce(operator.add, my_list))
# 각 원소 길이가 모두 동일한 경우, numpy 사용가능
# 방법 7 - numpy 라이브러리의 flatten 이용
import numpy as np
np.array(my_list).flatten().tolist()
list에서 문자 등장 개수 count
import collections
my_list = [1, 2, 3, 4, 5, 6, 7, 8, 7, 9, 1, 2, 3, 3, 5, 2, 6, 8, 9, 0, 1, 1, 4, 7, 0]
answer = collections.Counter(my_list)
print(answer[1]) # = 4
print(answer[3]) # = 3
print(answer[100]) # = 0
for - (break) - else 구문
- for와 함께 쓰는 else는, for문이 중간에 break 등으로 끊기지 않고, 끝까지 수행 되었을 때 수행하는 코드를 담고 있습니다.
- 코딩을 하다 보면 for문이 중간에 break 되었는지, 되어있지 않는지 판별해야 되는 경우가 많이 있습니다.
테스트 변수(flag)를 둬서 확인하는 등으로 처리합니다. - 파이썬에서는 else의 사용으로 간단하게 해결할 수 있습니다. if문에 else를 사용하듯이 else를 사용 하게 됩니다. else의 들여쓰기는 for와 일치해야 합니다.
import math
if __name__ == '__main__':
numbers = [int(input()) for _ in range(5)]
multiplied = 1
for number in numbers:
multiplied *= number
if math.sqrt(multiplied) == int(math.sqrt(multiplied)):
print('found')
break
else:
print('not found')수 swap 하기
a = 3
b = 'abc'
temp = a
a = b
b = temp
# 아래와 같이 사용가능
a = 3
b = 'abc'
a, b = b, a 무한대와 비교하게, 항상 가장 작게, 항상 가장 크게
- 파이썬이 제공하는 inf 를 사용해보세요. inf는 어떤 숫자와 비교해도 무조건 크다고 판정됩니다.
min_val = float('inf')
min_val > 10000000000
# inf에는 음수 기호를 붙이는 것도 가능합니다.
max_val = float('-inf')진수 변환기
tmp = string.digits + string.ascii_lowercase
def convert(num, base):
q, r = divmod(num, base)
if q == 0:
return tmp[r]
else:
return convert(q, base) + tmp[r]
# --------------------------------------------- #
def solution(n):
tmp = ''
while n:
tmp += str(n % 3)
n = n // 3
answer = int(tmp, 3)
return answerint(문자열, 진수)로 특정 "진수"로 되어있는 "문자열"을 10진수로 바꾼다.
3) 코테에 필요한 기본 수학 상식
약수: 어떤 수를 나누어떨어지게 하는 수
-
약수가 홀수개인 모든 수는 제곱수
-
제곱수가 아닌 수는 약수가 짝수개
-
소수: 1과 자기 자신만으로 나누어지는 수
# 소수 찾기 아라토테네스의 채
def solution(n):
MAX_NUM = 1_000_000
answer = 0
d = [True]*MAX_NUM
d[0] = False
d[1] = False
d[2] = True
for i in range(2, n + 1):
if d[i]:
answer += 1
for j in range(2, n + 1):
if (j * i) >= MAX_NUM:
break
d[j * i] = False
return answer최대공약수(GCD, Greateast Common Division)와 최소공배수(LCM, Least Common Multiple)
A,B 의 최대공약수를 G, 최소공배수를 L => AB=LG
- 최대 공약수 알면,
AB / G = L
소인수 분해
유클리드 호제법
- https://dimenchoi.tistory.com/46
- A를 B로 나눈 몫을 Q라 하고, 나머지를 R이라 하자. 이 때, gcd(A,B)=gcd(B,R)
- A와 B의 최대공약수를 구하기 위해서 A를 B로 나눈 나머지 R1을 구합니다.
- B를 R1으로 나눈 나머지 R2를 구합니다.
- R1을 R2로 나눈 나머지 R3를 구합니다.
- 이 과정을 계속 반복하여, 어느 한 쪽이 나누어떨어질 때까지 반복합니다.
- 이 직전 얻은 나머지가 최대공약수입니다.
등차 등비 수열
- 이때,
a != 0, r != 0이다. - 꼭 첫째 항이 아니더라도, 하나 이상의 항의 값, 몇 번째 항인지, 그리고 공비가 주어지거나 둘 이상의 항의 값, 각각 몇 번째 항인지가 주어지면 등비수열의 일반항을 정할 수 있다.
순열과 조합
https://ourcstory.tistory.com/414
items = ['1', '2', '3', '4', '5']
from itertools import permutations
list(permutations(items, 2))
# [('1', '2'), ('1', '3'), ('1', '4'), ('1', '5'), ('2', '1'), ('2', '3'), ('2', '4'), ('2', '5'), ('3', '1'), ('3', '2'), ('3', '4'), ('3', '5'), ('4', '1'), ('4', '2'), ('4', '3'), ('4', '5'), ('5', '1'), ('5', '2'), ('5', '3'), ('5', '4')]
from itertools import combinations
list(combinations(items, 2))
# [('1', '2'), ('1', '3'), ('1', '4'), ('1', '5'), ('2', '3'), ('2', '4'), ('2', '5'), ('3', '4'), ('3', '5'), ('4', '5')]
# 두 개 이상의 리스트에서 모든 조합
from itertools import product
items = [['a', 'b', 'c,'], ['1', '2', '3', '4'], ['!', '@', '#']]
list(product(*items))
# [('a', '1', '!'), ('a', '1', '@'), ('a', '1', '#'), ('a', '2', '!'), ('a', '2', '@'), ('a', '2', '#'), ('a', '3', '!'), ('a', '3', '@'), ('a', '3', '#'), ('a', '4', '!'), ('a', '4', '@'), ('a', '4', '#'), ('b', '1', '!'), ('b', '1', '@'), ('b', '1', '#'), ('b', '2', '!'), ('b', '2', '@'), ('b', '2', '#'), ('b', '3', '!'), ('b', '3', '@'), ('b', '3', '#'), ('b', '4', '!'), ('b', '4', '@'), ('b', '4', '#'), ('c,', '1', '!'), ('c,', '1', '@'), ('c,', '1', '#'), ('c,', '2', '!'), ('c,', '2', '@'), ('c,', '2', '#'), ('c,', '3', '!'), ('c,', '3', '@'), ('c,', '3', '#'), ('c,', '4', '!'), ('c,', '4', '@'), ('c,', '4', '#')]- (위에 이어서) 곱집합(Cartesian product) 구하기 - product
import itertools
iterable1 = 'ABCD'
iterable2 = 'xy'
iterable3 = '1234'
print(list(itertools.product(iterable1, iterable2, iterable3)))피보나치 DP
def solution(n):
answer = 0
dp = [0]*100_001
dp[0] = 0
dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i - 2] + dp[i - 1]
return dp[n] % 12345671로 만들기 DP
# 5로 나누어지면 /5
# 3으로 나누어지면 /3
# 2로 나우어지면 /2
# X = X -1
# 1로 만드는 최소 연산 수
# 답 = min(/5, /3, /2, -1) + 1 (각 경우의 수 의미)
def solution(n):
d = [0] * 30_001
for i in range(2, n + 1):
d[i] = d[i - 1] + 1
if i % 2 == 0:
d[i] = min(d[i], d[i // 2] + 1)
if i % 3 == 0:
d[i] = min(d[i], d[i // 3] + 1)
if i % 5 == 0:
d[i] = min(d[i], d[i // 5] + 1)
return d[n]2거듭 제곱과 비트 연산
-
특정 값 x를 log(n, 2)를 취하면 2의 거듭제곱인 것을 알 수 있다. 하지만 math.log() 함수는 부동소수점 계산을 수행
-
비트연산의 특이점을 활용한다. 2의 거듭제곱인 숫자는 이진수로 표현했을 때 한 비트만이 1이고, 나머지 비트는 모두 0인 패턴을 가진다.
class Solution:
def isPowerOfTwo(self, n: int) -> bool:
return n>0 and n&(n-1)==0digital root
-
음이 아닌 정수의 자릿수근(영어: digital root, 반복적 자릿수합(repeated digital sum)이라고도 함)은 자릿수를 더하는 과정을 방금 구한 그 값의 자릿수합에서 자릿수합을 구하도록 반복해서 얻어지는 (한 자리) 값이다. 이 과정은 한 자리 수가 될 때까지 계속된다.
-
예를 들어, 65,536의 자릿수근은 7이다. 왜냐하면 6 + 5 + 5 + 3 + 6 = 25이고 2 + 5 = 7이기 때문이다.
-
"어떤 수가 9의 배수라면, 그 수의 모든 자릿수의 합도 9의 배수" 라는 규칙을 통해 자릿수근을 쉽게 구할 수 있다.
class Solution(object):
def addDigits(self, num):
if num == 0:
return 0
return num % 9 or 94) 그래프
기본 개념과 구현
-
그래프는 정점(Vertex, 또는 노드(Node)라고도 함) 과 이들을 연결하는 간선(Edge)으로 구성된 자료구조
-
방향성이 있는 방향 그래프(Directed Graph) 와 방향성이 없는 무방향 그래프(Undirected Graph)로 나뉘며, 간선에 가중치(Weight) 가 있을 수도 있다.
- 그래프를 구현하는 방법으로는 인접 리스트(Adjacency List) 와 인접 행렬(Adjacency Matrix) 을 사용하는 방법이 있다.
-
[인접 리스트] 는 각 정점에 대해 연결된 모든 정점의 리스트를 저장하는 방식 으로, 특정 정점과 인접한 정점들을 바로 알 수 있다는 장점
-
[인접 행렬] 은 2차원 배열을 사용하여 노드 간의 연결 관계를 행렬 형태로 나타내는 방식.
-
노드 간의 연결 여부를 빠르게 확인할 수 있다는 장점이 있지만, 모든 각 정점에 관한 관계를 기록하기 때문에 메모리 소비가 더 크다는 단점이 있다.
-
따라서 인접 행렬은 그래프 간선이 많은 그래프에 주로 사용하고, 인접 리스트는 상대적으로 간선이 적은 그래프에서 주로 사용
DFS, BFS
- 얘들도 기본형태는 "완전탐색" 인 것을 잊지말자
- 보통 배열형태의 "길 찾기", "길 따라가기", "경우의 수" 계산 느낌이다.
from collections import deque
graph = dict(
A=['B', 'C'],
B=['A', 'D'],
C=['A', 'G', 'H', 'I'],
D=['B', 'E', 'F'],
E=['D'],
F=['D'],
G=['C'],
H=['C'],
I=['C', 'J'],
J=['I']
)
def bfs(graph, node, visited=[]):
'''
- deque를 활용한 bfs
'''
# 큐 구현을 위한 deque 라이브러리 활용
queue = deque([node])
if not visited:
visited = [False] * (len(graph) + 1)
visited[node] = True # 현재 노드를 방문 처리
# 큐가 완전히 빌 때까지 반복
while queue:
v = queue.popleft() # 큐에 삽입된 순서대로 노드 하나 꺼내기
sys.stdout.write(str(v)) # 탐색 순서 출력
# 인접한 행렬 체크 여부, 구현하기에 따라 달라짐
if isinstance(graph[v], int):
continue
# 현재 처리 중인 노드에서 방문하지 않은 인접 노드를 모두 큐에 삽입
for i in graph[v]:
if not (visited[i]):
queue.append(i)
visited[i] = True
def dfs_deque(graph, start_node):
'''
- deque 활용한 stack, DFS
'''
visited = []
need_visited = deque()
# 시작 노드 설정해주기
need_visited.append(start_node)
# 방문이 필요한 리스트가 아직 존재한다면
while need_visited:
# 시작 노드를 지정하고
node = need_visited.pop()
# 만약 방문한 리스트에 없다면
if node not in visited:
# 방문 리스트에 노드를 추가
visited.append(node)
# 인접 노드들을 방문 예정 리스트에 추가
need_visited.extend(graph[node])
return visited
def dfs_recursive(graph, start, visited=[]):
'''
- 재귀를 활용한 dfs
'''
sys.stdout.write(str(start))
visited.append(start)
# 인접한 행렬 체크 여부, 구현하기에 따라 달라짐
if isinstance(graph[start], int):
return visited
for node in graph[start]:
if node not in visited:
dfs_recursive(graph, node, visited)
return visited- python으로 기깔나게 DFS simple 순회 숏코드가 가능하다.
def preorder(root):
return [root.val] + preorder(root.left) + preorder(root.right) if root else []
def inorder(root):
return inorder(root.left) + [root.val] + inorder(root.right) if root else []
def postorder(root):
return postorder(root.left) + postorder(root.right) + [root.val] if root else []Binary Search / 이진 탐색
- 정렬이 되어 있어야 하고, 분할 탐색 형태, 데이터를 나누어서 접근하는 반복-높이가 logN
- 단순 반복문 (while)을 통해 구현하는게 편할 수 있지만, 제귀가 더 단순해진다.
def binary_search(arr, target, low=None, high=None):
low, high = low or 0, high or len(arr) - 1
if low > high:
return -1
mid = (low + high) // 2
if arr[mid] > target:
return binary_search(arr, target, low, mid)
if arr[mid] == target:
return mid
if arr[mid] < target:
return binary_search(arr, target, mid + 1, high)BST
class Node:
def __init__(self, value: int):
self.value = value
self.left: Node = None # 왼쪽 서브노드
self.right: Node = None # 오른쪽 서브노드
class BinarySearchTree:
def __init__(self, root: Node):
self.root = root # root node
def insert_node(self, value):
'''
- 왼쪽 자식 노드 값 < 부모 노드 값 < 오른쪽 자식 노드 값 규칙을 지키면서 append (추가) 하는 method
'''
curr: Node = self.root # 연산의 기준 노드 변수 선언
while True:
# 기준 노드 값이 삽입하고자 하는 값보다 큰 경우 (삽입 값은 좌측 노드로 내려간다)
if curr.value > value:
if curr.left: # 기준 노드의 좌측 자식노드가 존재한다면
curr = curr.left # 다음 연산을 위해 기준노드를 좌측 자식노드로 초기화
else: # 기준 노드의 좌측 자식노드가 존재하지 않는다면
curr.left = Node(value) # 좌측 자식노드에 값 삽입
break
# 기준 노드 값이 삽입하고자 하는 값보다 작은 경우
else:
if curr.right: # 기준 노드의 우측 자식노드가 존재한다면
curr = curr.right # 다음 연산을 위해 기준노드를 우측 자식노드로 초기화
else: # 기준 노드의 우측 자식노드가 존재하지 않는다면
curr.right = Node(value) # 우측 자식노드에 값 삽입
break
def search_node(self, value):
'''
- BST의 특성을 생각하면서 탐색하는 method
'''
curr = self.root # 연산의 기준 노드 변수 선언
while curr: # 기준 노드가 존재하는 동안
if curr.value == value: # 기준 노드의 값이 검색하고자 하는 값과 같다면
return True # True 반환
break
elif curr.value > value: # 기준 노드의 값이 검색하고자 하는 값보다 클 때
if curr.left: # 기준 노드의 좌측 자식노드가 존재한다면
curr = curr.left # 다음 연산을 위해 기준 노드를 좌측 자식노드로 초기화
else: # 기준 노드의 좌측 자식노드가 없다면
return False # False 반환(검색하고자 하는 값이 없음)
elif curr.value < value: # 기준 노드의 값이 검색하고자 하는 값보다 작을 때
if curr.right: # 기준 노드의 우측 자식노드가 존재한다면
curr = curr.right # 다음 연산을 위해 기준 노드를 우측 자식노드로 초기화
else: # 기준 노드의 우측 자식노드가 없다면
return False # False 반환(검색하고자 하는 값이 없음)
def debugPrint(self, start: Node, level: int) -> None:
'''
- 깊이 우선 탐색의 특성으로 그래프 출력하기
'''
print(f'Node: {start.value}, childs:')
for node in [start.left, start.right]:
if not node:
continue
print(' ' * level, end='')
self.debugPrint(node, level+1)LIS / LCS - DP
Dijkstra / Floyd-Warshall
Topological Sort
Union-Find
MST(Minimum Spanning Tree)
3. 참고하면 좋은 링크 모음
1) 20 of these coding problem patterns (leetcode 기준)
- Sliding Window
- Islands (Matrix Traversal)
- Two Pointers
- Fast & Slow Pointers
- Merge Intervals
- Cyclic Sort
- In-place Reversal of a LinkedList
- Tree Breadth-First Search
- Tree Depth First Search
- Two Heaps
- Subsets
- Modified Binary Search
- Bitwise XOR
- Top ‘K’ Elements
- K-way Merge
- Topological Sort
- 0/1 Knapsack
- Fibonacci Numbers
- Palindromic Subsequence
- Longest Common Substring
도메인 중심의 개발, 깊이의 가치를 이해하고 “문제 해결” 에 몰두하는 개발자가 되고싶습니다. 그러기 위해 항상 새로운 것에 도전하고 노력하는 개발자가 되고 싶습니다!