자주 사용하는 정렬 알고리즘들을 정리해보려 한다. 버블 정렬(Bubble Sort)정의: 인접한 원소들을 비교하여 큰 값을 뒤로 보내는 정렬시간복잡도: O(n²) - 삽입/삭제 후 재정렬 필요, 검색 O(n) 의사코드for i = 0 to n-2: for j = 0 to n-2-i: if arr[j] > arr[j+1]: swap(arr[j], arr[j+1]) 선택 정렬(Selection Sort)정의: 최솟값을 찾아 앞쪽부터 차례로 배치하는 정렬시간복잡도: O(n²) - 삽입/삭제 후 재정렬 필요, 검색 O(n)의사코드for i = 0 to n-2: min_idx = i for j = i+1 to n-1: if arr[j] 삽입 정렬(In..
핵심 개념완전 탐색(Brute Force)은 가능한 모든 경우의 수를 전부 탐색하여 정답을 찾는 방법이다. 최적화 없이 모든 경우를 시도하기 때문에 구현이 간단하지만, 경우의 수가 많아지면 비효율적일 수 있다. 시간 복잡도완전 탐색의 시간 복잡도는 일반적으로 \( O(N!) \) 또는 \( O(2^N) \) 등 매우 높은 편이다. 예를 들어, n개의 요소가 있을 때 가능한 모든 순열을 탐색하는 경우 \( O(N!) \)이 된다. 따라서 입력 크기가 커질수록 실행 시간이 급격히 증가한다. 동작방식 & 구현완전 탐색은 보통 다음과 같은 방식으로 동작한다.가능한 모든 경우의 수를 생성한다.각 경우가 문제의 조건을 만족하는지 확인한다.원하는 결과를 찾으면 반환하거나 최적의 해를 갱신한다. 활용 가능한 문제 유..
핵심 개념DFS(Depth-First Search, 깊이 우선 탐색)와 BFS(Breadth-First Search, 너비 우선 탐색)는 그래프 탐색 알고리즘이다. DFS는 한 방향으로 끝까지 탐색한 후 돌아오는 방식이며, BFS는 가까운 노드부터 탐색하는 방식이다. 시간 복잡도두 탐색 방법의 시간 복잡도는 일반적으로 \( O(V + E) \)이다. 여기서 \( V \)는 vertex(or 노드) 개수, \( E \)는 edge(간선) 개수이다. DFS와 BFS 모두 모든 노드를 방문하기 때문에 그래프의 크기에 따라 탐색 시간이 결정된다. 동작방식 & 구현 DFS시작 노드에서 한 방향으로 갈 수 있는 만큼 탐색한다.더 이상 이동할 곳이 없으면 이전 노드로 돌아가 다른 경로를 탐색한다.모든 노드를 방문할..
핵심 개념투 포인터(Two Pointer)는 배열이나 리스트에서 두 개의 포인터를 활용해 문제를 해결하는 기법이다. 주로 정렬된 배열에서 특정 조건을 만족하는 부분을 찾거나, 두 개의 배열을 병합할 때 사용된다. 탐색 범위를 줄여 효율적으로 동작하기 때문에 많은 알고리즘 문제에서 활용된다. 시간 복잡도Two Pointer 기법의 시간 복잡도는 일반적으로 \( O(N) \)이다. 각 포인터가 배열을 한 번씩만 훑고 지나가기 때문에 불필요한 중복 연산이 줄어든다. 반면, Brute Force 접근법은 \( O(N^2) \)인 경우가 많아 투 포인터를 사용하면 성능을 크게 향상시킬 수 있다. 동작방식 & 구현 투 포인터는 보통 다음과 같은 방식으로 동작한다.시작점과 끝점을 설정: 두 개의 포인터를 배열의 시..
