개념 서로소 집합 : 공통 원소가 없는 두 집합 서로소 집합 자료구조 : 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조 스택, 큐가 pop, push 연산을 사용하는 것 처럼 서로소 집합은 union, find 연산을 이용함 find - 속한 집합이 어떤 집합인지 찾기 union - 두 개의 집합을 합치기 싸이클인지 구하기 find해서 같다면 cycle 다르면 union 코드 # find - 부모 찾기 def find_parent(parent, x): if parent[x] != x: parent[x] = find_parent(parent, parent[x]) return parent[x] # union 두 집합의 부모를 비교, 더 작은 쪽을 부모로 대입 def union_par..
ps, cp/코딩테스트 cheatsheet
개념 한 지점에서 다른 모든 지점까지의 최단거리를 구하는 알고리즘 현재 노드에서 가장 가까운 노드를 계속 탐색하며 최단거리를 그리디하게 업데이트해나감 힙을 사용하지 않으면 다음 노드를 선택하는 과정에서 연결된 노드를 모두 살펴야 함으로 비효율적 주의 : 가중치가 음일 경우 불가능함 => 벨만 포드 알고리즘을 사용해야함 시간복잡도 : O(ElogV) E : 간선의 개수, V : 노드의 개수 (힙 사용시) 코드 import heapq # 입력값은 인접리스트 형식으로 graph = [[] for _ in range(n + 1)] # 거리테이블을 무한으로 초기화 INF = int(1e9) distance = [INF] * (n + 1) # (거리, 노드)로 힙에 추가 -> 가장 가까운 거리를 바로 알 수 있음 ..
개념 자주 나오는 유형은 아니지만 간간이 나오기 때문에 꼭 알고 있어야 된다고 생각한다. 시간복잡도 : O(n^3) 언제 써야하는가? 모든 정점에서 모든 정점까지의 거리를 알고 싶을 때 쓴다. 시간복잡도가 O(n^3)으로 굉장히 느려 정점의 개수가 500이하일 경우에 고려해볼만 하다. 500 * 500 * 500 = 125,000,000 인데 500은 진짜 삐끗하면 시간초과가 날 가능성이 높다. 아예 플로이드 워셜을 의도로 하는 문제는 n이 100~200정도이다. 코드 # 처음은 graph를 큰 수로 초기화 INF = int(1e9) graph = [[INF] * (n + 1) for _ in range(n + 1)] # 자기자신에게 가는 경로가 0일 경우에만 for x in range(1, n + 1)..
개발자로 취업하기 위한 관문 중 하나는 코딩테스트이다. 코딩테스트 문제는 사람이 내는 것이고, 무한히 참신한 문제를 낼 수 없기 때문에 시중에 나와있는 문제들과 비슷하거나 조금씩 바꾼 문제가 출제되기 마련이다. 결국 문제은행 방식과 유사하다고 생각한다. 그럼 시중에 나와있는 문제들을 모두 푼다면 되겠지만 그건 비효율적이고 시간적으로도 모자르다. 이런 문제은행 시험을 통과하는 법 중 가장 효율적인 것은 최대한 많은 문제의 답지를 계속 보면서 외워버리는 것이라고 생각한다. 마치 문제와 답을 데이터로 하는 머신러닝을 우리 뇌로 돌리는 것 같다고 생각한다. 모든 문제의 답을 보는 것 역시 비효율적이므로 적절한 문제를 골라서 풀어보고, 답을 보고 주의할 점이 뭔지, 어떤 유형인지를 알아가면 될 것이다. 그럼 적절..
