현지의 개발일지

CS/알고리즘

기수정렬   기수 정렬은 각 자릿수(자리 수가 높은 순서부터 낮은 순서로)마다 정렬을 수행하는 방식일반적으로 자리 수가 작고 데이터의 범위가 좁을 때 매우 효율적으로 작동  1. 자릿수별 정렬가장 낮은 자릿수부터 가장 높은 자릿수까지 차례로 정렬을 진행2. 각 자릿수를 정렬각 자릿수는 계수 정렬(Counting Sort)을 이용하여 정렬3. 자릿수 순으로 반복자릿수가 다 채워질 때까지 반복하여 정렬 복잡도O(d * (n + k)) d최대 자릿수(데이터의 자릿수)n배열의 크기k자릿수당 가능한 값의 범위 (예: 0~9인 경우 k=10)자릿수가 d일 때, 각 자릿수마다 계수 정렬을 사용하여 정렬을 수행하므로 O(n) 시간이 걸리고이를 d번 반복하기 때문에 최종적으로 O(d * (n + k))의 시간이 소요  ..

2025. 2. 3.

CS/알고리즘

힙(Heap)힙은 이진 트리로서 두 가지 조건을 만족해야 한다완전 이진 트리(Complete Binary Tree)모든 레벨이 꽉 차야 하며마지막 레벨은 왼쪽부터 채운다힙 속성(Heap Property)최대 힙(Max Heap)부모 노드의 값이 자식 노드의 값보다 크거나 같다.최소 힙(Min Heap)부모 노드의 값이 자식 노드의 값보다 작거나 같다.  힙 정렬 절차1. 힙 만들기주어진 배열을 힙 자료구조로 변환한다.일반적으로 최대 힙(Max Heap)을 사용하여 배열의 루트 노드가 가장 큰 값이 되게 한다.2. 정렬 과정①  루트 노드를 마지막 노드와 교환한다.②  배열의 크기를 1 줄이고, 루트부터 다시 힙 속성을 만족하도록 조정한다.③  이 과정을 배열 크기가 1이 될 때까지 반복한다.  특징시간 ..

2025. 2. 2.

CS/알고리즘

분할 정복(Divide and Conquer) 알고리즘의 한 종류안정적이고 효율적인 정렬 방식정렬 과정에서 배열을 점점 작게 나누고 다시 합치며 정렬된 상태로 병합 1. 분할(Divide)배열을 절반으로 나눈다.크기가 1 이하가 될 때까지 반복적으로 나눈다.2. 정복(Conquer)나눠진 배열을 정렬된 상태로 병합(Merge)한다.3. 병합(Merge)두 개의 정렬된 서브 배열을 하나의 정렬된 배열로 결합한다. 특징시간 복잡도최악, 최선, 평균O(n log n)분할에 O(log n), 병합에 O(n)이 걸리기 때문에 항상 O(n log n)공간 복잡도O(n)추가적인 병합 배열이 필요하므로, 입력 배열 크기만큼 추가 메모리가 필요안정 정렬동일한 값의 순서가 유지 장점안정 정렬동일한 값의 순서가 유지일관된 ..

2025. 1. 30.

CS/알고리즘

1. 피벗(Pivot) 선택배열에서 하나의 요소를 피벗으로 선택2. 분할(Partition)피벗보다 작은 요소는 왼쪽피벗보다 큰 요소는 오른쪽3. 재귀 호출:분할된 서브배열에 대해 위 과정을 반복4. 모든 재귀 호출이 끝나면 정렬된 배열이 완성 피벗 선택 기준1. 첫 번째 요소를 피벗으로 선택배열의 첫 번째 요소를 피벗으로 정한다.장점구현이 간단하다.단점이미 정렬된 배열에서는 최악의 경우가 발생해 시간 복잡도가 O(n²)로 떨어진다. 2. 마지막 요소를 피벗으로 선택배열의 마지막 요소를 피벗으로 정한다.장점구현이 간단하다.단점첫 번째 요소를 피벗으로 선택하는 방식과 동일하게, 이미 정렬된 배열에서 비효율적이다. 3. 중앙 요소를 피벗으로 선택배열의 가운데 인덱스에 위치한 요소를 피벗으로 선택한다.장점일반..

2025. 1. 29.

CS/알고리즘

1. 배열의 두 번째 요소부터 시작한다.2. 현재 요소를 정렬된 부분과 비교하며 올바른 위치를 찾아 삽입한다.3. 위 과정을 배열의 끝까지 반복한다. 특징시간 복잡도최악O(n²) (역순 정렬일 경우)평균O(n²)최선O(n) (이미 정렬된 경우)모두 정렬이 되어있는 경우(Optimal)한 경우 한번씩만 비교공간 복잡도O(1) (추가 메모리가 필요하지 않음)주어진 배열 안에서 교환(swap)을 통해 정렬이 수행 장점알고리즘이 단순이미 정렬된 데이터에는 O(n)의 시간 복잡도안정 정렬동일한 값의 순서가 유지작은 데이터셋에서는 효율적 단점최악과 평균 시간 복잡도가 O(n²)큰 데이터셋에는 비효율적데이터가 많을수록 실행 시간이 급격히 증가 JAVAimport java.util.Arrays;public class ..

2025. 1. 28.

CS/알고리즘

1. 리스트에서 가장 작은 값을 찾는다.2. 가장 작은 값을 리스트의 첫 번째 위치와 교환한다.3. 첫 번째 위치를 제외한 나머지 리스트에 대해 위 과정을 반복한다.4. 리스트가 모두 정렬될 때까지 반복한다. 특징시간 복잡도:최악O(n²)평균O(n²)최선O(n²) (항상 동일한 비교를 수행하므로 입력 상태와 무관)공간 복잡도O(1) (추가 메모리가 필요하지 않음) 장점구현이 간단하다.작은 데이터셋에서는 동작 가능하다. 단점시간 복잡도가 O(n²)로 매우 비효율적이다.안정 정렬이 아니므로, 동일한 값의 순서가 변경될 수 있다.데이터가 많아지면 실무에서 사용하기 어렵다. JAVAimport java.util.Arrays;public class BubbleSort { public static void b..

2025. 1. 27.

CS/알고리즘

1. 배열을 순회하면서 인접한 두 요소를 비교한다.2. 두 요소의 순서가 잘못되었으면 교환한다.3. 배열 끝까지 한 번 순회하면 가장 큰 요소가 배열의 끝으로 이동한다.4. 위 과정을 반복하면서 정렬되지 않은 부분을 점차 줄여나간다. 특징시간 복잡도:최악O(n²) (배열이 역순으로 정렬된 경우)평균O(n²)(n-1) + (n-2) + (n-3) + .... + 2 + 1 => n(n-1)/2최선O(n) (이미 정렬된 경우)공간 복잡도 O(1) (추가 메모리가 필요하지 않음)주어진 배열 안에서 교환(swap)을 통해 정렬이 수행단순성구현이 쉽다.효율성이 낮아 실무에서는 잘 사용하지 않는다. 장점구현이 매우 간단하다.작은 데이터셋에서는 작동이 가능하다.추가 메모리가 필요하지 않다. 단점시간 복잡도가 매우 높..

2025. 1. 26.

CS/알고리즘

1. DFS(깊이 우선 탐색)DFS 정의 및 개념그래프나 트리에서 한 번에 가능한 한 깊은 노드까지 탐색을 진행한 뒤, 더 이상 갈 곳이 없으면 돌아가서 다른 경로를 탐색한다.자식 노드를 먼저 탐색하고, 자식 노드가 더 이상 없으면 부모 노드로 돌아가서 다른 자식 노드를 탐색한다.기본적으로 재귀적으로 구현한다.스택(Stack)을 이용하여 비재귀적으로도 구현한다.  동작 방식① 시작 노드를 방문하고 스택에 넣는다.② 스택에서 노드를 꺼내며, 그 노드와 연결된 인접 노드를 방문한다.③ 더 이상 방문할 노드가 없으면 스택에서 가장 최근에 방문했던 노드로 돌아가 다른 경로를 탐색한다.④ 이 과정을 더 이상 탐색할 노드가 없을 때까지 반복한다.   구현 방법1. 재귀적 구현재귀 호출을 사용하여 DFS를 구현한다...

2025. 1. 11.