2024/1/8 TIL

'오늘의 일에서 나는 어떤 것을 배웠는지' - 학습

알고리즘에 대해 학습했다.

 

알고리즘
-입력을 받아 원하는 출력을 생성하기 위한 절차

Big O 표기법
-알고리즘의 효율성을 나타내는 표기법
-얼마나 많은 시간(입력횟수) / 공간(메모리-입력 크기와 비교하여 산출 시 필요한 저장 공간의 양)를 필요로 하는지
-n번 반복할 경우 시간 복잡도 O(n)
-추가공간이 필요 없을 경우(입력된 공간을 그대로 사용할 경우) 공간 복잡도 O(1)

-Big O 표기법은 최악의 경우의 성능을 표기하는 것을 원칙으로 함 -> 알고리즘의 효율성을 과장하지 않음
-최고 상수만 남기고 나머지는 전부 생략하는 것으로 간소화할 수 있음.

정렬 알고리즘
-주어진 데이터 세트를 특정 순서로 배열하는 방법

선택 정렬
-배열에서 최소값(or 최대값)을 찾아서 그것을 맨 앞(or 맨 뒤) 속성과 교환하는 방법
-시간복잡도 O(n^2)
-공간복잡도 O(1)

삽입 정렬
-정렬되지 않은 부분에서 요소를 가져와 정렬된 부분에 적절한 위치에 삽입하는 방법
-시간 복잡도: 최악의 경우 O(n^2), 하지만 정렬되어 있는 경우에는 O(n)
-공간 복잡도: O(1)

 

예시)

주어진 배열: {5, 2, 4, 6, 1, 3}

1. 첫 번째 단계 (i = 1):
   • 현재 정렬된 부분: {5}
   • key 값은 2이므로 5와 비교하고, 2가 5보다 작으므로 5를 오른쪽으로 한 칸 이동합니다.
   • 정렬된 부분: {2, 5}
   • 배열 상태: {2, 5, 4, 6, 1, 3}
2. 두 번째 단계 (i = 2):
   • 현재 정렬된 부분: {2, 5}
   • key 값은 4이므로 5와 비교하고, 4가 5보다 작으므로 5를 오른쪽으로 한 칸 이동합니다.
   • 2와 비교하고, 4가 2보다 크므로 4를 현재 위치에 삽입합니다.
   • 정렬된 부분: {2, 4, 5}
   • 배열 상태: {2, 4, 5, 6, 1, 3}
3. 세 번째 단계 (i = 3):
   • 현재 정렬된 부분: {2, 4, 5}
   • key 값은 6이므로 5와 비교하고, 6이 5보다 크므로 정렬된 부분에서 멈춥니다.
   • 정렬된 부분: {2, 4, 5, 6}
   • 배열 상태: {2, 4, 5, 6, 1, 3}
4. 네 번째 단계 (i = 4):
   • 현재 정렬된 부분: {2, 4, 5, 6}
   • key 값은 1이므로 6과 비교하고, 1이 6보다 작으므로 6을 오른쪽으로 한 칸 이동합니다.
   • 5와 비교하고, 1이 5보다 작으므로 5를 오른쪽으로 한 칸 이동합니다.
   • 4와 비교하고, 1이 4보다 작으므로 4를 오른쪽으로 한 칸 이동합니다.
   • 2와 비교하고, 1이 2보다 작으므로 2를 오른쪽으로 한 칸 이동합니다.
   • 1을 현재 위치에 삽입합니다.
   • 정렬된 부분: {1, 2, 4, 5, 6}
   • 배열 상태: {1, 2, 4, 5, 6, 3}
5. 다섯 번째 단계 (i = 5):
   • 현재 정렬된 부분: {1, 2, 4, 5, 6}
   • key 값은 3이므로 6과 비교하고, 3이 6보다 작으므로 6을 오른쪽으로 한 칸 이동합니다.
   • 5와 비교하고, 3이 5보다 작으므로 5를 오른쪽으로 한 칸 이동합니다.
   • 4와 비교하고, 3이 4보다 작으므로 4를 오른쪽으로 한 칸 이동합니다.
   • 2와 비교하고, 3이 2보다 크므로 정렬된 부분에서 멈춥니다.
   • 3을 현재 위치에 삽입합니다.
   • 정렬된 부분: {1, 2, 3, 4, 5, 6}
   • 배열 상태: {1, 2, 3, 4, 5, 6}

퀵 정렬
-퀵 정렬은 피벗을 기준으로 작은 요소들은 왼쪽, 큰 요소들은 오른쪽으로 분할하고 이를 재귀적으로 정렬하는 방법입니다.
-시간 복잡도: 최악의 경우 O(n^2), 하지만 평균적으로 O(n log n)
-공간 복잡도: 평균적으로 O(log n), 최악의 경우 O(n) (재귀 호출에 필요한 스택 공간)

1. 피벗(Pivot) 선택:
배열에서 하나의 원소를 선택하여 피벗으로 지정합니다. 피벗은 일반적으로 배열의 중간 원소를 선택합니다.

2. 분할(Divide):
배열을 피벗을 기준으로 두 개의 부분 배열로 나눕니다.
피벗보다 작은 원소는 왼쪽 부분 배열로, 큰 원소는 오른쪽 부분 배열로 이동합니다.
피벗 자체는 정렬이 완료된 위치에 위치하게 됩니다.

3. 정복(Conquer):
왼쪽 부분 배열과 오른쪽 부분 배열에 대해 재귀적으로 퀵 정렬을 수행합니다.
각 부분 배열에서도 위의 두 단계를 반복하여 정렬을 수행합니다.

4. 결합(Combine):
정렬된 부분 배열들을 합쳐 전체 배열을 정렬된 상태로 만듭니다.


간단 요약: 피벗을 기준으로 2개 도막으로 토막내고, 
피벗보다 작은건 왼쪽으로, 큰건 오른쪽으로.
이걸 더 토막낼 수 없을 때까지 반복한 뒤 합친다.


병합 정렬
- 병합 정렬은 배열을 반으로 나누고, 각 부분을 재귀적으로 정렬한 후, 병합하는 방법입니다.
- 시간 복잡도: 모든 경우에 대해 O(n log n)
- 공간 복잡도: O(n)

1. 분할(Divide):
주어진 배열을 반으로 나눕니다.
배열을 나눌 때 중간 지점을 찾아 재귀적으로 왼쪽 부분과 오른쪽 부분을 각각 정렬합니다.
나누는 과정을 더 이상 나눌 수 없을 때까지 반복합니다.

2. 정복(Conquer):
분할된 부분 배열들을 정렬합니다.
정렬은 재귀적으로 이루어집니다.

3. 병합(Combine):
정렬된 부분 배열을 합병(merge)하여 하나의 정렬된 배열을 만듭니다.
두 부분 배열을 처음부터 비교해가며 작은(또는 큰) 원소를 새로운 배열에 복사합니다.
두 부분 배열 중 하나의 배열이 모두 복사되면, 나머지 배열의 나머지 원소들을 새로운 배열에 복사합니다.

4. 반복(Recursion):
위의 세 단계를 재귀적으로 반복하여 배열을 계속해서 나누고 정렬한 후, 병합하여 최종적으로 정렬된 배열을 얻습니다.

간단 요약: 가장 작은 두개 조각의 뭉치까지 쪼갠 뒤 그 뭉치들의 원소간의 크기를 비교하여 정렬한다.

이렇게 정렬된 더미를 다른 더미와 비교하여 새 더미를 생성하는데, 가장 작은 원소부터 차례대로 넣는다.

이 과정을 전체 배열이 될 때까지 반복한다. 

 

Sort 메서드
-`Sort` 메서드는 배열이나 리스트의 요소들을 정렬하는 메서드.
-정렬은 오름차순으로 수행되며, 요소들의 자료형에 따라 다양한 정렬 기준을 사용할 수 있음.
-`Sort` 메서드는 원래의 배열이나 리스트를 직접 수정하므로 반환값이 없음.

사용 예) 
int[] numbers = { 5, 2, 8, 3, 1, 9, 4, 6, 7 };
Array.Sort(numbers);


탐색 알고리즘
-주어진 데이터 집합에서 특정 항목을 찾는 방법

선형 탐색
-가장 단순한 탐색 알고리즘. 배열의 각 요소를 하나씩 차례대로 검사하여 원하는 항목을 찾는다.
-시간 복잡도: 최악의 경우 O(n)
-배열의 처음부터 끝까지 하나씩 비교하여 검색하는 알고리즘

이진 탐색
-정렬된 배열에서 빠르게 원하는 항목을 찾는 방법
-중간 요소와 찾고자 하는 항목을 비교하여 대상이 중간 요소보다 작으면 왼쪽을, 크면 오른쪽을 탐색.
-업다운 숫자 찾기 게임.
-시간 복잡도: 최악의 경우 O(log n)

그래프
- 정점(Vertex)과 간선(Edge)으로 이루어진 자료 구조
- 방향 그래프(Directed Graph)와 무방향 그래프(Undirected Graph)로 나뉨
- 가중치 그래프(Weighted Graph)는 간선에 가중치가 있음

그래프 탐색 방법
깊이 우선 탐색
-트리나 그래프를 탐색하는 알고리즘. 
-루트에서 시작하여 가능한 한 깊이 들어가서 노드를 탐색하고, 더 이상 방문할 노드가 없으면 이전 노드로 돌아가는 방식.
-시간 복잡도: 최악의 경우 O(V+E) (V는 노드 수, E는 간선 수)

너비 우선 탐색
-트리나 그래프를 탐색하는 알고리즘. 
-루트에서 시작하여 가까운 노드부터 방문하고, 그 다음 레벨의 노드를 방문하는 방식.
-시간 복잡도: 최악의 경우 O(V+E) (V는 노드 수, E는 간선 수)

최단 경로 알고리즘
최단 경로 알고리즘 개념과 종류
-다익스트라 알고리즘
하나의 시작 정점에서 다른 모든 정점까지의 최단 경로를 찾는 알고리즘입니다. 음의 가중치를 갖는 간선이 없는 경우에 사용됩니다.

-벨만-포드 알고리즘
음의 가중치를 갖는 간선이 있는 그래프에서도 사용할 수 있는 최단 경로 알고리즘입니다. 음수 사이클이 있는 경우에도 탐지할 수 있습니다.

-A* 알고리즘
특정 목적지까지의 최단 경로를 찾는 알고리즘입니다.
휴리스틱 함수를 사용하여 각 정점까지의 예상 비용을 계산하고, 가장 낮은 예상 비용을 가진 정점을 선택하여 탐색합니다.


동적 프로그래밍
-큰 문제를 작은 하위 문제로 분할하여 푸는 접근 방식.
-작은 하위 문제의 해결 방법을 계산하여 저장하고, 이를 이용하여 큰 문제의 해결 방법을 도출. 메모이제이션(Memoization)
-동적 프로그래밍은 중복되는 하위 문제들을 효율적으로 해결하기 위해 사용됨 (프랙탈)
-일반적으로 재귀적인 구조를 가지며, 하향식(Top-down)과 상향식(Bottom-up) 두 가지 방법으로 구현할 수 있음.
-동적 프로그래밍은 최적 부분 구조와 중복 부분 문제의 특징을 가진 문제들을 효과적으로 해결할 수 있음.

그리디 알고리즘
-각 단계에서 가장 최적인 선택을 하는 알고리즘.
-각 단계에서 가장 이익이 큰 선택을 하여 결과적으로 최적해에 도달하려는 전략을 따름.
-그리디 알고리즘은 지역적인 최적해를 찾는데 초점을 맞추기 때문에 항상 전역적인 최적해를 보장하지는 않음.
-그리디 알고리즘은 간단하고 직관적인 설계가 가능하며, 실행 시간이 매우 빠른 편.
-그리디 알고리즘은 최적해를 찾는 문제에 사용되는 경우가 많지만, 일부 문제에서는 최적해를 보장하지 않을 수 있음.

분할 정복
- 큰 문제를 작은 부분 문제로 분할하므로 문제의 크기에 따른 성능 향상이 가능.
- 재귀적인 구조를 가지므로 문제 해결 방법의 설계가 단순하고 직관적.
- 분할된 부분 문제들은 독립적으로 해결되므로 병렬 처리에 유리.
- 하지만 문제를 분할할 때 발생하는 부분 문제들 간의 중복 계산이 발생할 수 있음.
이런 경우에는 중복 계산을 피하기 위한 메모이제이션 등의 기법을 활용하여 성능을 향상시킬 수 있음.

알고리즘 문제 해결 전략
1. 문제 이해
문제를 정확히 이해하고 요구사항을 파악하는 것이 중요합니다. 
문제 설명을 꼼꼼히 읽고, 입력과 출력의 형식을 이해하고 분석해야 합니다.

2. 예제와 테스트 케이스
문제의 예제와 추가적인 테스트 케이스를 활용하여 문제를 이해하고 해결 방법을 검증해야 합니다. 
예제와 테스트 케이스는 문제의 조건과 제약을 이해하는 데 도움을 줄 수 있습니다.

3. 알고리즘 설계
문제를 해결하기 위한 알고리즘을 설계해야 합니다. 문제의 특성에 맞는 알고리즘을 선택하고, 
알고리즘의 구현 방법과 시간 복잡도를 고려해야 합니다.

4. 코드 작성
알고리즘을 기반으로 코드를 작성해야 합니다. 코드는 가독성이 좋고, 
문제의 요구사항을 정확히 반영해야 합니다. 변수명을 명확하게 지어 가독성을 높이고, 
주석을 추가하여 코드를 설명하는 것도 좋은 습관입니다.

5. 효율성
문제의 제약 조건과 입력 크기에 따라 알고리즘의 효율성을 고려해야 합니다. 
최적화 기법을 사용하고, 시간 복잡도와 공간 복잡도를 최대한 줄이는 방향으로 코드를 작성해야 합니다.

6. 디버깅과 테스트
코드를 작성한 후에는 디버깅을 통해 오류를 찾고 수정해야 합니다. 
테스트 케이스를 활용하여 코드의 정확성을 검증하고, 예외 상황을 고려하여 코드를 완성해야 합니다.

7. 시간 관리
코딩 테스트는 제한된 시간 안에 문제를 해결해야 하는 것이 특징입니다. 
따라서 시간을 효과적으로 관리하고, 문제에 맞는 효율적인 접근 방법을 선택하는 능력이 필요합니다.

8. 연습과 경험
코딩 테스트는 많은 연습과 경험이 필요한 분야입니다. 다양한 유형의 문제에 노출되고, 
해결 방법을 익히며 자신의 실력을 향상시켜야 합니다.
코딩 테스트 관련 문제를 많이 풀고 다른 사람들의 풀이를 학습하는 것도 좋은 방법입니다.


코딩 테스트나 알고리즘 문제의 종류
1. 탐색과 정렬
배열, 리스트, 문자열 등의 데이터에서 특정 값을 찾거나 정렬하는 문제입니다. 
선형 탐색, 이진 탐색, 퀵 정렬, 병합 정렬 등의 알고리즘이 주로 활용됩니다.

2. 그래프
그래프 구조를 활용하여 문제를 해결하는 문제입니다. 
최단 경로, 신장 트리, 네트워크 연결 등의 문제가 있을 수 있으며, 
대표적인 알고리즘으로는 DFS(Depth-First Search), BFS(Breadth-First Search), Dijkstra, 크루스칼, 프림 등이 있습니다.

3. 동적 프로그래밍
큰 문제를 작은 하위 문제로 분할하여 해결하는 동적 프로그래밍 알고리즘을 활용하는 문제입니다. 
피보나치 수열, 최장 공통 부분 수열, 0-1 배낭 문제 등이 있습니다.

4. 그리디 알고리즘
각 단계에서 가장 최적인 선택을 하는 알고리즘으로, 지역적 최적해를 찾는 문제입니다.
거스름돈 문제, 회의실 배정, 작업 스케줄링 등이 있습니다.

5. 분할 정복
문제를 작은 부분으로 분할하여 해결하는 분할 정복 알고리즘을 사용하는 문제입니다.
퀵 정렬, 병합 정렬, 이진 탐색 등이 있습니다.

6. 동적 그래프
그래프 구조에서 동적인 변화를 다루는 문제입니다. 
플로이드-와샬 알고리즘, 벨만-포드 알고리즘 등이 있습니다.

7. 문자열 처리
문자열에 대한 다양한 처리를 다루는 문제입니다.
문자열 압축, 회문 판별, 문자열 매칭 등이 있을 수 있습니다.

8. 기타
그 외에도 수학적인 문제, 비트 연산 문제, 시뮬레이션 문제,
동적 계획법과 그래프의 결합 문제 등 다양한 유형의 문제가 출제될 수 있습니다.


'오늘의 나는 무엇을 잘했는지' - 성취

알고리즘에 대해 학습했다.

이해하기 쉽게 정리 요약하고 쉬운 말로 풀어 쓰려고 노력했다.

'오늘의 나는 어떤 문제를 겪었는지, 앞으로 어떻게 해결할 것인지' - 개선

가장 큰 문제점은 배열을 끼고 있는 겹쳐진 반복문을 봤을 때 한눈에 이해하는 것이 쉽지 않다는 것이다.

주어진 정답을 해석하는 것으로도 벅찬데 문제를 보고 어떤 알고리즘을 사용할 지 판단하고 제한된 시간 안에 해결 할 수 있을지 걱정이 앞선다.

당장은 뾰족한 개선안이 떠오르지 않는데, 문제를 많이 접하고 풀어본다면 능률이 오를까?

그러기를 희망해야겠다.