Let IT Begin

* Python을 기준으로 합니다 DFS (Depth-First Search), BFS (Breadth-First Search) - 개념 DFS (깊이 우선 탐색), BFS (너비 우선 탐색) : 그래프의 모든 노드를 한 번씩 방문하는 그래프 순회 작업을 위한 알고리즘 완전 탐색과 같이 탐색 방향을 결정하고, 다음 탐색의 유효성을 검사해야 하는 경우 사용 방문 처리 : 그래프에서 한번 처리되어 탐색된 노드가 다시 탐색되지 않게 체크하는 과정 DFS : 스택, 재귀로 주로 구현됨 그래프에서 더 이상 탐색할 노드가 없을 때까지 진행한 다음, 탐색할 노드가 없으면 가장 최근의 방문 노드로 돌아가 다른 노드를 탐색하는 방법 DFS의 동작 과정 스택에 시작 노드를 push 스택이 비어있다면 탐색을 종료 비어있지 ..

* Python을 기준으로 합니다 이진 탐색 (Binary Search), 파라메트릭 서치 (Parametric Search) - 개념 이진 탐색 : 정렬된 데이터가 있을 때, 검색 범위를 절반으로 줄여나가면서 값을 탐색하는 방식 반드시 정렬된 데이터에서만 사용 가능하지만, $O(\log n)$의 time complexity를 가짐 이진 탐색의 동작 배열의 시작점과 끝을 start, end로 정함 가운데를 mid로 정하고, mid에 해당하는 값이 탐색 값이면 탐색을 종료하고 값을 반환 mid에 해당하는 값이 탐색하려는 값보다 크면 mid의 오른쪽 배열에 대해 이진 탐색 수행, 작으면 mid 왼쪽 배열에 대해 이진 탐색 수행 위 2~3 과정을 반복 이진 탐색의 응용 - 이진 탐색은 탐색 범위를 계속해서 좁..

* Python을 기준으로 합니다 완전 탐색 (Brute-Force) - 개념 완전 탐색 : 모든 경우의 수를 확인해서 정답을 구하는 방법 완전 탐색의 적용 : 현재 위치에서 다음 위치로 이동할 수 있는 모든 조건들을 정의해야 함 - 반복적으로 적용되는 동일 조건으로 정답을 찾아야 하는 경우 - 입력 크기가 작을 때 최적해를 구해하는 경우 - 여러 조합들 중에서 최적해를 찾아야하는 경우 완전 탐색의 유형들 단순 완전 탐색 - 반복문, 조건문을 활용하여 단순하게 모든 경우의 수들을 확인하는 방법 순열, 조합 - 여러 데이터에서 경우의 수를 만들어서 활용하는 방법 - 순열 (Permutation) : 서로 다른 $n$개에서 $r$개를 선택할 때, 선택되는 순서가 중요한 경우 - 조합 (Combination)..

* 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..

* 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..

* Python을 기준으로 합니다 투 포인터 (Two Pointer) - 개념 투 포인터 : 배열에서 start, end를 나타내는 포인터를 이동시키면서 값의 위치를 탐색하는 알고리즘 배열에서 특정한 합을 가지는 수열이나 중복 값 등을 탐색할 때 사용할 수 있음 일반적으로 배열을 순차적으로 탐색하는 데에는 $O(n^{2})$이 소모되지만, 투 포인터를 사용하면 $O(n)$의 time complexity로 해결 가능하기 때문 - 구현 1. 양 끝에서 시작하는 투 포인터 현재 위치에서 일치 여부를 비교한 다음, 포인터를 옮기면서 탐색 범위를 줄이는 방식 배열의 양 끝에 포인터를 위치시킴 두 포인터의 합이 작으면 start 포인터를 오른쪽으로 이동, 크면 end 포인터를 왼쪽으로 이동 정답을 찾을 때까지 위 ..