자료구조+알고리즘

스택/큐

스택(Stack) 가장 처음에 들어간 요소가 가장 나중에 나오는 자료구조 Last In First Out - LIFO라고 부른다! 시간 복잡도 삽입: O(1) 삭제: O(1) 파이썬에선 사실 스택을 사용할 때, 그냥 list를 사용하면 된다 하지만 큐는 다르다!!! 왜 둘다 linked list를 기반으로 한 자료구조인데 차이가 날까? 파이썬의 list는 사실 array이고 스택을 사용하려면 맨 뒤의 요소를 pop()해도 시간 복잡도는 똑같지만 큐 같은 경우는 맨 앞의 요소를 빼기 위해 pop(0)을 해야하는데 array에서 맨 앞의 요소를 빼는 것은 O(n)의 시간이 걸리기 때문이다!! # 한쪽 끝으로만 자료를 넣고 뺄 수 있는 자료구조 class Node: def __init__(self, item,..

연결리스트 LinkedList

Array vs LinkedList array 파이썬의 list 타입 공간을 미리 할당하고 메모리를 할당한다. 각 자리에 순서가 정해져 있고 확장하면 메모리 확보를 더 해서 쭉쭉 붙여나간다. 데이터를 추가하려면 새로운 메모리 공간을 할당받아야 한다 탐색: 해당 인덱스에 있는 요소를 찾으려면 바로 찾기가 가능해서 탐색에 O(1)시간이 걸린다. 모두 붙어있어서 삽입 삭제가 어렵다. O(N) → 1, 2, 4, 5 에서 2에 3을 넣으려면 기존에 있는 2는 앞으로 당기고 4, 5는 뒤로 밀어야 한다! 이는 직접 구현해야함 데이터에 접근(탐색)하는 경우가 잦으면 array를 사용! linked list 서로 다른 요소가 이어져 있다고 생각!! 탐색: linked list에서 n번재 요소를 탐색하려면 앞에있는 n..

최대공약수(GCD) / 최소공배수(LCD)

GCD 유클리드 호제법을 이용해서 간단히 구할 수 있다. 숫자 a와 b가 있을 때, a를 b로 나눈 나머지와 b 의 최대공약수 는 a와 b의 최대공약수가 같다는 것을 의미한다. def gcd(a, b): while b > 0: a, b = b, a % b return a LCD 두 수 a와 b가 있을 때 a와 b를 곱한 값에서 a와 b의 최대공약수를 나누면 된다! def lcm(a, b): return a * b / gcd(a, b)

deque로 BFS, DFS 구현

BFS DFS 소스코드 주의사항! 각 노드에 연결된 자식 노드들은 꼭 정렬이 되어 있어야 한다! bfs, dfs 둘 다 앞에서부터 빠져나가는 식으로 구현했으므로 popleft를 사용함 dfs의 경우 extendleft로 왼쪽에 자식 노드를 추가해서 맨앞부터 빠져나가기 편하게 구현! extendleft를 사용할 때 예를 들어 [1, 2, 3]을 extendleft하면 [3, 2, 1] 순으로 deque의 왼쪽에 붙으므로 한번 reversed 해서 붙여줌! graph = dict() graph['A'] = ['B', 'C'] graph['B'] = ['A', 'D'] graph['C'] = ['A', 'G', 'H', 'I'] graph['D'] = ['B', 'E', 'F'] graph['E'] = ['D..