[Algorithm] 완전 탐색
* Python을 기준으로 합니다 완전 탐색 (Brute-Force) - 개념 완전 탐색 : 모든 경우의 수를 확인해서 정답을 구하는 방법 완전 탐색의 적용 : 현재 위치에서 다음 위치로 이동할 수 있는 모든 조건들을 정의해야 함 - 반복적으로 적용되는 동일 조건으로 정답을 찾아야 하는 경우 - 입력 크기가 작을 때 최적해를 구해하는 경우 - 여러 조합들 중에서 최적해를 찾아야하는 경우 완전 탐색의 유형들 단순 완전 탐색 - 반복문, 조건문을 활용하여 단순하게 모든 경우의 수들을 확인하는 방법 순열, 조합 - 여러 데이터에서 경우의 수를 만들어서 활용하는 방법 - 순열 (Permutation) : 서로 다른 $n$개에서 $r$개를 선택할 때, 선택되는 순서가 중요한 경우 - 조합 (Combination)..
[Algorithm] 정렬
* Python을 기준으로 합니다 정렬 (Sorting) - 개념 정렬 : 데이터를 순서대로 나열하는 것 정렬의 종류 Time Complexity $O(n^{2})$ 선택 정렬 (Selection Sort) : 가장 단순한 정렬 방식으로, 배열에서 가장 작은 수를 찾아 하나씩 순서대로 정렬하는 방법 삽입 정렬 (Insertion Sort) : 현재 위치의 수를 정렬된 영역의 적절한 위치로 이동시켜 정렬하는 방법 - 거의 정렬되어 있는 경우 $O(n)$을 소모하지만 대부분의 경우, $O(n^{2})$이 소모됨 버블 정렬 (Bubble Sort) : 현재 값과 다음 값을 비교하여 다음 값이 더 작다면 위치를 교환하는 방식으로 정렬 Time Complexity $O(n \log n)$ 퀵 정렬 (Quick S..
[Algorithm] 슬라이딩 윈도우
* Python을 기준으로 합니다 슬라이딩 윈도우 (Sliding Window) - 개념 슬라이딩 윈도우 : 고정 크기의 윈도우가 이동하면서 윈도우 내의 데이터를 이용해 문제를 해결하는 방법 투 포인터와 비슷하지만 슬라이딩 윈도우는 정렬 여부에 관계없이 사용 가능함 - 구간 합 계산에 주로 활용 Time complexity 측면에서 슬라이딩 윈도우는, 투 포인터와 마찬가지로 $O(n^{2})$ 이상 소모되는 배열 탐색을 $O(n)$ 내에 해결 가능함 - 구현 1. 슬라이딩 윈도우 움직이기 배열에서 고정 크기만큼의 데이터를 가져오기 위해서 slicing을 활용함 def sliding_window(arr, window_size): slide = [] for i in range(len(arr)-window_s..
[Algorithm] 투 포인터
* Python을 기준으로 합니다 투 포인터 (Two Pointer) - 개념 투 포인터 : 배열에서 start, end를 나타내는 포인터를 이동시키면서 값의 위치를 탐색하는 알고리즘 배열에서 특정한 합을 가지는 수열이나 중복 값 등을 탐색할 때 사용할 수 있음 일반적으로 배열을 순차적으로 탐색하는 데에는 $O(n^{2})$이 소모되지만, 투 포인터를 사용하면 $O(n)$의 time complexity로 해결 가능하기 때문 - 구현 1. 양 끝에서 시작하는 투 포인터 현재 위치에서 일치 여부를 비교한 다음, 포인터를 옮기면서 탐색 범위를 줄이는 방식 배열의 양 끝에 포인터를 위치시킴 두 포인터의 합이 작으면 start 포인터를 오른쪽으로 이동, 크면 end 포인터를 왼쪽으로 이동 정답을 찾을 때까지 위 ..
[Algorithm] 유니온 파인드, 서로소 집합
* Python을 기준으로 합니다 유니온 파인드 (Union Find), 서로소 집합 (Disjoint Set) - 개념 집합 : 순서와 중복이 없는 원소들을 가지는 자료구조 유니온 파인드 (=서로소 집합) : 교집합이 없는 두 집합 관계를 의미 해당하는 원소가 그래프에 연결되어 있는지를 판별하기 위한 자료구조로써, 일반적으로 트리를 통해 구현함 노드의 개수가 $V$이고 $V-1$개의 union 연산과 $M$개의 find 연산이 가능할 때, 유니온 파인드의 time complexity는 $O(V+M(1+\log_{2-M/V}V))$ 유니온 파인드의 연산 Find : 특정 노드의 root를 확인하는 연산 (노드가 같은 트리에 연결되어 있는지를 판별) 현재 노드의 parent를 찾는다 Parent가 root..
[Algorithm] 우선순위 큐
* Python을 기준으로 합니다 우선순위 큐 (Priority Queue) - 개념 우선순위 큐 : 우선순위가 높은 데이터를 가장 먼저 삭제하는 큐 즉, 우선순위 큐는 데이터를 우선순위에 맞게 정렬하고 순서대로 추출할 수 있어야 함 이때 배열이나 연결 리스트를 사용한 구현은, 우선순위에 따른 삽입과 삭제에 많은 비용이 소모됨 따라서 우선순위 큐는 힙 자료구조를 사용하여 삽입과 삭제를 $O(\log n)$ 내에 처리하도록 함 우선순위 큐에서 최소힙을 적용하면 값이 작을수록 높은 우선순위를 부여하도록 할 수 있음 반대로 최대힙을 적용하면 값이 클수록 우선순위를 부여함 - 힙은 일반적으로 최소힙으로 구현되므로, 삽입 시 음수를 취하고 추출 시 다시 -1을 곱하는 방식으로 처리 - 구현 1. heapq 라이브..