Flood Fill 알고리즘Flood Fill 알고리즘은 다차원 배열에서 특정 영역을 탐색하고 색을 채우기 위해 사용되는 알고리즘이다.이 알고리즘은 주어진 시작점에서 인접한 같은 색의 영역을 탐색하며 색을 채운다.탐색 과정에서 DFS나 BFS를 사용하여 인접 영역을 방문한다.주로 픽셀 기반의 이미지 처리나 그래프 탐색 문제를 해결하는 데 활용된다.시간복잡도: 배열의 행 수가 n, 열 수가 m 일때, O(n * m)Flood Fill 알고리즘 구현먼저 시작 위치와 목표 색을 입력받고, 시작 위치의 기존 색을 확인한다.만약 시작 위치의 색과 목표 색이 동일하다면, 동작을 종료한다.시작 위치와 목표 색과 다르다면 목표 색으로 변경하고 상하좌우 인접한 영역을 탐색한다.인접 영역의 색이 기존 색과 동일할 때, 해..
[알고리즘 / Python] 최소신장트리 (크루스칼 알고리즘)
1. 신장 트리 (Spanning Tree)신장 트리는 모든 노드끼리 연결되어 있는 (모든 노드 간에 경로가 존재하는) 연결 그래프가 주어졌을 때, 모든 노드가 연결되지만 사이클이 존재하지 않는 부분 그래프를 의미한다.그래프의 최소 연결 부분 그래프라고 할 수 있다.여기서 최소 연결이란, 간선의 수가 최소가 되는 부분 그래프를 의미한다.n개의 노드가 있을 때 간선의 수는 n-1이 된다.2. 최소 신장 트리최소 신장 트리는 연결 그래프가 주어졌을 때, 가능한 신장 트리 중 가중치 합이 가장 작은 트리이다.2.1. 최소 신장 트리의 특징간선의 가중치 합이 최소여야 한다.노드가 n 개일 때, 간선은 반드시 n-1 개다. (신장 트리 특징)사이클이 존재하지 않는다. (신장 트리 특징)3. 크루스칼 (Kruska..
[알고리즘 / Python] 분리집합 (Disjoint Set / 서로소 집합)
1. 분리집합 (Disjoint Set) 분리집합은 서로 겹치는 원소가 없는 상호 배타적인 집합들을 의미하며 서로소 집합이라고도 불린다. 전체 집합에 대하여 겹치지 않는 두 개 이상의 부분 집합이라 할 수 있다. 즉, 분리집합 알고리즘은 각 원소가 속하는 부분 집합을 찾아 분리를 하는 것이다. 예를 들어, 전체 집합 U에 대하여 짝수 집합 A와 홀수 집합 B는 서로 겹치는 원소가 없는 부분 집합들로 분리집합이라 할 수 있다. 2. Union-Find 알고리즘 시간복잡도: 평균적으로 O(logN)이며, 최악의 경우에는 O(n)이다. 트리구조를 사용한다. 하지만 이때, 자식노드가 부모노드 가리킨다는 것에 차이가 있다. 두 개 노드가 있을 때, 서로 같은 집합에 있는지 아닌지 판별하는 알고리즘이다. Find ..
[알고리즘 / Python] 누적합 (Prefix Sum)
배열의 일부 구간에 대한 합을 빠르게 구할 수 있는 알고리즘이다.배열의 값들이 변하지 않는다면 누적된 합 또한 변동이 없다는 점을 적용한다.미리 구해둔 누적합을 통해 배열 중 특정 구간의 부분합을 쉽게 구할 수 있다.값을 미리 저장해 두는 점이 DP와 유사하다.배열의 값들이 변하지 않음1. 1차원 누적합 알고리즘1.1. 1차원 누적합그림과 같이 앞에서부터 차례대로 누적된 합계를 prefixSum 배열에 저장한다.첫 번째(0) 값은 arr 값과 prefixSum 값이 동일하다.현재 위치(i)의 arr 값에 prefixSum 배열에 저장된 직전 위치(i-1)까지의 합을 더하여 현재 위치의 누적합을 구하여 prefixSum에 입력한다.점화식은 다음과 같다.prefixSum[i] = prefixSum[i-1] ..
[알고리즘] 이분 그래프 (Bipartite Graph)
인접한 노드(정점)끼리 서로 다른 색으로 칠해서 두 가지 색으로 분할할 수 있는 그래프를 이분 그래프라고 한다. 즉 각각의 집합에 속한 노드끼리는 서로 인접하지 않도록 분할하는 것이다. 시간복잡도: O(V+E) 1. 이분 그래프 알고리즘 BFS, DFS 를 사용하여 이분 그래프인지 여부를 확인 가능하다. 판단 방법 서로 인접한 노드가 같은 색이면 이분 그래프가 아니다. BFS, DFS로 노드를 방문할 때마다 두 가지 중 한가지 색으로 칠한다. (1 혹은 2) 이때 인접한 노드와는 서로 다른 색을 선택한다. 즉, 현재 노드의 색(1)과는 다른 색(2)으로 연결된 다음 노드를 칠한다. 여기서 0은 방문하지 않음을 뜻하고 1 혹은 2는 서로 다른 색을 뜻한다. $color_{next}= color_{befor..
[알고리즘 / Python] 동적프로그래밍 (DP, Dynamic Programming)
동적프로그래밍동적 프로그래밍은 큰 문제를 작은 문제로 나누어 푸는 방법이다.분할 정복과는 다르게 작은 문제를 푸는데서 답이 같은 문제가 중복적으로 일어날 경우 사용한다.보통 점화식을 만들 수 있다.1. 동적프로그래밍의 조건큰 문제는 작은 문제로 나눌 수 있고 작은 문제가 반복해서 나타난다.같은 문제라면 계산할 때마다 같은 답이 도출된다.2. 메모이제이션 (Memoization)메모이제이션은 한번 풀었던 작은 문제를 다시 반복해서 풀지 않기 위해 메모해두고 필요할 때 답만 꺼내 보는 것이다.담아 놓는 것이기 때문에 캐싱 (caching) 이라고도 불린다.메모이제이션을 통해 먼저 구한 결과를 담아 두면, 아래 피보나치 예시에서 점선으로 표시된 노드는 먼저 먼저 계산된 값을 사용하면 되기 때문에 반복해서 계산..
[알고리즘 / Python] 이분 탐색 / 이진 탐색 (Binary Search)
이분 탐색이란, 오름차순으로 정렬된 배열을 반복적으로 반으로 나누어 target이 선택될 때까지 탐색하는 알고리즘이다. 1. 이분 탐색의 조건 반드시 오름차순으로 정렬된 상태에서 시작해야 한다. 2. 이분 탐색 알고리즘 시간복잡도: O(logN) 반복문과 재귀 두 가지 방법을 사용할 수 있다. 자료를 오름차순으로 정렬한다. 자료의 중간값(mid)이 찾고자 하는 값(target)인지 비교한다. mid 값이 target과 다르다면 대소관계를 비교하여 탐색 범위를 좁히고, target과 mid 값이 같을 때까지 아래 조건에 따라 2번과 3번을 반복한다. ⓐ target이 mid 값 보다 작으면 end를 mid 왼쪽 값으로 바꿔준다. (절반의 왼쪽 탐색) ⓑ target이 mid 값 보다 크면 start를 mi..