hong0708

Union-Find는 트리구조를 활용해 노드를 합치고 부모를 찾아서 이를 통해 서로소 집합을 찾아내는 알고리즘입니다. find 함수를 통해 부모 노드를 찾을 때 까지 재귀를 활용하여 호출합니다. 이때, 재귀적으로 호출 하면 파이썬의 경우 문제가 생기는 경우가 있는데 이에 대한 내용은 하단에 새로운 코드를 추가하겠습니다. union 함수는 두 노드의 부모노드를 찾고 이를 합치는데 이때 노드의 번호에 따라 합칠 수 있습니다. 두 함수를 수행하기 위해선 해당 노드의 부모노드를 저장하는 리스트를 가지고 있어야합니다. 아래는 위 함수들과 알고리즘을 구현한 예제 코드입니다. n, m = map(int, input().split()) parent = [i for i in range(n)] def find(x): if..

위상 정렬이란 순환(사이클)이 없는 방향 그래프의 모든 노드를 방향성에 위배 하지 않고 나열하는 정렬 알고리즘 입니다. 여기서 알 수 있는 점이 1. 순환이 없다 2. 방향성 즉 우선순위를 판단하여 정렬한다 두점을 알 수 있습니다. 그래프 내부에 사이클이 없다 방향성을 가진 간선으로 이뤄진 그래프이다. 이 점을 봐서 DAG(Direct Acyclic Graph)에서 실행 될 수 있다고 할 수 있습니다. 이 때 문제에서 방향성을 우선순위 즉, 어떠한 테스크에 대해 먼저 선행되어야 할 다른 테스크가 있을 때 활용된다고 생각하고 풀이를 진행하면 좋습니다. 위상 정렬 알고리즘 큐를 활용하여 진입 차수가 0인 노드를 지속적으로 추가합니다. 진입 차수를 측정합니다. 진입 차수는 특정 노드로 들어오는 간선의 수로 특..

근래 경로찾기 문제에서 자주 활용했던 알고리즘들을 코드만 정리하려한다. 다익스트라 - 기준점으로 나머지 지점으로의 최단 거리를 구할 때 사용, heapq를 사용 # 입력 arr = [[] for _ in range(n + 1)] for _ in range(m): s, e, w = map(int, sys.stdin.readline().split()) arr[s].append([e, w]) # 경로 찾기 hq = [[start, 0]] road[start] = 0 while hq: now = heapq.heappop(hq) x, w = now[0], now[1] # 현재 가중치가 이미 답으로 나온 가중치보다 크다면 볼 필요 없음 if w > ans[x]: continue for i in arr[x]: if ..

일반적인 문자열 탐색 즉, 이중 for문을 통한 반복문과는 다른 방식을 통해 시간복잡도를 줄이는 방식입니다. 이중 for문을 통해 반복문을 진행한다면 시간복잡도는 O(N**2)이라 문제 조건의 길이가 길다면 시간초과가 일어날 수 있습니다. 보이어-무어 알고리즘의 진행 방식은 아래와 같습니다. 패턴의 오른쪽 끝 문자와 문자열의 현재 위치 문자가 일치하는지 검사합니다. 만약 패턴의 오른쪽 끝 문자와 문자열의 현재 위치 문자가 일치한다면 왼쪽으로 검사를 이어나갑니다. 만약 검사 중 일치하지 않는 다면 패턴의 길이만큼을 넘어가 새로 검사를 시작합니다. 반대로 패턴의 오른쪽 끝 문자와 문자열의 현재 위치 문자가 일치 하지 않는다면 먼저 문자열의 현재 위치 문자가 패턴에 있는지 검사를 진행합니다. 만약 있다면 그만..

리스트의 특정 구간의 합을 빠르게 구할 수 있는 방법입니다. 리스트 안에 데이터의 변화가 없다면 누적된 합의 변동이 없기 때문에 이 점을 활용해 특정 구간의 부분합을 구할 수 있습니다. 이전의 값을 미리 저장하는데 이 점이 동적 계획법과 유사한 방법이라 할 수 있습니다. 크게 1차원, 2차원 배열에서 많이 활용됩니다. 먼저 1차원 배열입니다. prefix[i] 는 arr[0]+arr[1]...arr[i-1] 이라 할 수 있습니다. 6 3 2 9 1 5 해당 배열의 누적합은 아래와 같습니다. 0 6 9 11 20 21 26 0번째 인덱스는 배열의 0번째와 같은 값입니다. 현재 i 번째 배열의 값을 i-1번째 누적합 배열의 값을 더해 i 번째 누적합 배열에 저장합니다. 즉 prefix[i] = prefix[..

투 포인터(Two Pointer) 리스트에 순차적으로 접근을 할 때 일반적으로 한 개의 점을 바라보는것이 아닌 두 개의 점의 위치를 기록하면서 처리하는 알고리즘입니다. 리스트에 있는 데이터를 접근할 때 시작점과 끝점 즉, 2개의 점으로 접근할 데이터의 범위를 표현합니다. 시작점과 끝점을 활용한 특징을 통해 특정 문제에 사용됩니다. 가장 대표적인 예시로 아래 문제가 있습니다. 2 1 3 1 5 위와 같은 배열이 있을 때, 합이 5인 부분 연속 수열의 개수를 구하는 문제입니다. 완전탐색을 통해 해당 문제 풀이가 쉽게 가능하지만 O(N)이라는 시간 제한을 가진다면 다른 풀이 방법이 필요합니다. 이때, 투 포인터를 활용한다면 쉽게 풀이가 가능합니다. 시작점과 끝점을 1번째 인덱스를 가르킵니다.(start ,en..