2023년 1학기 알고리즘 출석수업 만점 받은 과제물

문서 내 토픽

1. 이진 탐색

이진 탐색은 정렬된 상태의 데이터 중 원하는 값을 탐색하는 알고리즘이다. 이진 탐색은 먼저 주어진 데이터 중 중앙값이 목표 값과 일치하는 지 비교한다. 그리고 데이터가 정렬되어 있음을 이용해, 중앙값이 목표 값보다 작다면 중앙값보다 큰 값을 지니는 쪽, 중앙값이 목표 값보다 크다면 중앙값보다 작은 값을 지니는 쪽에 대해 다시 중앙값과 목표 값을 비교하며 데이터를 절반씩 줄여가는 과정을 반복하며 원하는 값을 찾는다.
2. 퀵 정렬

퀵 정렬은 데이터 중 하나의 값을 피벗으로 뽑고 데이터를 그 값보다 큰 쪽과 작은 쪽으로 분할시키는 과정을 재귀적으로 반복함으로써 데이터를 정렬하는 알고리즘이다. 데이터 중에서 고른 피벗을 기준으로 분할하고 그 가운데에 피벗을 놓으면 피벗의 올바른 위치를 찾을 수 있다. 퀵 정렬에 있어 최악의 경우는 피벗을 고를 때 가장 크거나 작은 값을 뽑는 것이고, 최선의 경우는 중앙값을 뽑는 것이다.
3. 합병 정렬

합병 정렬은 주어진 배열을 절반의 크기를 가진 두 개의 하위 배열로 분할하는 것을 반복한다. 분할이 반복되면 각각의 하위 배열이 한 개의 요소만을 가지게 되고, 이 때 각각의 하위 배열은 정렬된 상태라고 할 수 있다. 정렬된 상태의 두 개의 배열을 새로운 정렬된 하나의 배열로 합치는 것은 배열에서 가장 앞에 있는 값을 서로 비교하고 제거하여 새로운 배열에 채워 넣는 과정을 반복함으로써 이루어질 수 있다.
4. 선택 문제

선택 문제는 임의의 순서로 저장된 데이터 중 x번째로 작거나 큰 값을 찾아내는 것에 관한 문제이다. 선택 문제를 해결하는 방법에는 퀵 정렬의 Partition 함수를 사용하는 방법과 주어진 데이터를 각 그룹마다 x개의 값을 가진 개의 하위 그룹으로 나누고, 각 하위 그룹의 중앙값을 찾는 방법이 있다.
5. 피보나치 수열

피보나치 수열 문제는 피보나치 수열의 임의의 순서, i번째 수를 구하는 문제이다. 피보나치 수열의 i번째 수는 (i–1)번째 수와 (i–2)번째 수의 합이다. 이처럼 피보나치 수열에서 i번째 수열은 그 이전 값들에 종속적이고, i번째 수를 구하기 위해서는 그 이전 값들은 또 다시 그것의 이전 값들에 종속적이기 때문에 동적 프로그래밍을 이용하면 효율적으로 이를 구할 수 있다.
6. 연쇄 행렬 곱셈 문제

연쇄 행렬 문제는 n개의 행렬이 주어졌을 때, 행렬들의 곱셈에 필요한 연산의 횟수를 가장 작아지도록 하는 연산 순서를 찾는 것에 관한 문제이다. C(i, j)를 i번째 행렬부터 j번째 행렬까지 곱셈할 때 필요한 최소 연산 횟수라고 정의하면, C(1, n), 즉 주어진 n개의 행렬을 모두 곱하는데 필요한 최소 연산 횟수를 구하는 것은 동적 프로그래밍을 이용해 효율적으로 구할 수 있다.
7. 스트링 편집 거리 문제

스트링 편집 거리 문제는 어떤 문자열 X를 또 다른 문자열 Y로 변환하는데 드는 최소 비용을 구하는 문제이다. E(i, j)를 X의 첫 번째 문자부터 i번째 문자를 Y의 첫 번째 문자부터 j번째 문자로 바꾸는 최소 비용이라고 정의하면, E(i, j)는 E(i-1, j)와 E(i, j-1), E(i-1, j-1)에 종속적으로 결정된다. 그러므로 동적 프로그래밍을 이용하면 효율적으로 편집거리를 구할 수 있다.
8. 플로이드 알고리즘

플로이드 알고리즘은 가중치의 합이 음수인 사이클이 존재하지 않는 가중 그래프에서 모든 정점 간의 최단 경로를 구하는 알고리즘이다. MC(x, y)를 정점 x에서 정점 y로 가는데 드는 최소 비용으로 정의하고, C(x, y)를 정점 x에서 정점 y로 직행으로 갈 때의 비용이라고 정의하면, 플로이드 알고리즘에서는 기준 정점 k를 고른 후 모든 MC(x, y)와 MC(x, k)+MC(k, y)를 비교한 후 더 작은 값을 MC(x, y)로 설정한다.
9. 저울 문제

저울 문제는 각각 w0, w1, …, wi의 무게를 가지는 i개의 추가 있을 때, 저울에 t의 무게를 가지는 물체와 추를 함께 달아 저울이 평행하도록 만들 수 있는지를 알아내는 것에 관한 문제이다. 이 문제는 추의 부분집합으로 (t-부분집합에 포함되지 않은 추의 무게)를 만들 수 있는지에 종속적이기 때문에, 동적 프로그래밍 방법으로 이를 풀 수 있다.
10. 동전 거스름돈 문제

동전 거스름돈 문제는 주어진 액수의 거스름돈을 최소한의 개수의 동전으로 만드는 것에 관한 문제이다. 주어진 동전의 모든 액면가가 각 액면가보다 더 작은 액면가 각각의 정수배로 이루어진 경우에는 욕심쟁이 방법을 적용해 쉽게 풀 수 있다.
11. 최소 신장 트리

최소 신장 트리는 가중 그래프에서 모든 정점을 포함하는 연결된 트리 중 가중치의 합이 최소로 되는 트리를 구하는 문제이다. 이 문제는 간선을 가중치 오름차순으로 정렬한 후, 앞 순서의 간선부터 해당 간선을 트리에 추가했을 때 사이클을 만들지 검사한 후, 사이클을 만들지 않는다면 트리에 추가하는 것을 반복함으로써 해결할 수 있다.

Easy AI와 토픽 톺아보기

1. 이진 탐색

이진 탐색은 정렬된 배열에서 특정 값을 빠르게 찾을 수 있는 효율적인 알고리즘입니다. 이진 탐색은 배열의 중간 값을 확인하고, 찾고자 하는 값이 중간 값보다 크면 오른쪽 부분을, 작으면 왼쪽 부분을 재귀적으로 탐색합니다. 이를 통해 시간 복잡도를 O(log n)으로 줄일 수 있어 큰 데이터 집합에서도 빠르게 동작합니다. 이진 탐색은 다양한 알고리즘과 자료 구조에서 핵심적인 역할을 하며, 알고리즘 설계와 분석에 있어 중요한 개념입니다.
2. 퀵 정렬

퀵 정렬은 분할 정복 기법을 사용하는 효율적인 정렬 알고리즘입니다. 퀵 정렬은 배열에서 임의의 pivot 원소를 선택하고, 이를 기준으로 배열을 두 부분으로 나눕니다. 그 후 각 부분을 재귀적으로 정렬하여 전체 배열을 정렬합니다. 평균적으로 퀵 정렬의 시간 복잡도는 O(n log n)으로, 다른 정렬 알고리즘과 비교했을 때 매우 빠릅니다. 또한 추가 메모리 공간이 필요 없어 공간 효율성도 높습니다. 퀵 정렬은 정렬 알고리즘 설계와 분석에 있어 중요한 기법이며, 실제 응용 프로그램에서도 널리 사용되고 있습니다.
3. 합병 정렬

합병 정렬은 분할 정복 기법을 사용하는 또 다른 효율적인 정렬 알고리즘입니다. 합병 정렬은 배열을 반으로 나누어 각 부분을 재귀적으로 정렬한 뒤, 두 부분을 병합하여 전체 배열을 정렬합니다. 합병 정렬의 시간 복잡도는 O(n log n)으로, 퀵 정렬과 마찬가지로 매우 효율적입니다. 또한 안정 정렬 알고리즘이므로 동일한 값을 가진 원소의 상대적 순서가 유지됩니다. 이러한 특성으로 인해 합병 정렬은 외부 정렬이나 병렬 처리에 적합하며, 다양한 응용 분야에서 활용되고 있습니다.
4. 선택 문제

선택 문제는 주어진 n개의 원소 중에서 k번째로 작은 원소를 찾는 문제입니다. 이는 정렬 알고리즘을 사용하여 해결할 수 있지만, 더 효율적인 해결 방법이 있습니다. 대표적인 알고리즘으로는 퀵 선택 알고리즘이 있는데, 이는 퀵 정렬과 유사한 방식으로 동작합니다. 퀵 선택 알고리즘은 평균적으로 O(n) 시간 복잡도를 가지며, 최악의 경우에도 O(n^2)의 시간 복잡도를 가집니다. 선택 문제는 다양한 응용 분야에서 중요하게 사용되며, 효율적인 해결 방법을 찾는 것이 알고리즘 설계와 분석에 있어 중요한 과제입니다.
5. 피보나치 수열

피보나치 수열은 수학과 컴퓨터 과학에서 매우 중요한 개념입니다. 이 수열은 첫 두 항이 0과 1이고, 이후의 항은 바로 앞의 두 항의 합으로 정의됩니다. 피보나치 수열은 재귀적으로 정의되어 있어 효율적인 알고리즘 설계에 활용될 수 있습니다. 또한 이 수열은 자연계에서 다양한 형태로 관찰되며, 수학적 특성으로 인해 많은 응용 분야에서 활용됩니다. 피보나치 수열은 알고리즘 분석, 동적 계획법, 수학적 모델링 등 다양한 주제에서 중요한 역할을 하므로, 이에 대한 깊이 있는 이해가 필요합니다.
6. 연쇄 행렬 곱셈 문제

연쇄 행렬 곱셈 문제는 행렬 곱셈의 순서를 최적화하여 연산 비용을 최소화하는 문제입니다. 이는 동적 계획법을 사용하여 해결할 수 있는데, 이 방법은 부분 문제들의 최적 해를 저장하여 전체 문제의 최적 해를 구하는 방식입니다. 연쇄 행렬 곱셈 문제는 알고리즘 설계와 분석, 최적화 문제 해결 등에 있어 중요한 개념이 됩니다. 또한 이 문제는 다양한 응용 분야에서 발생하며, 효율적인 해결 방법을 찾는 것이 중요합니다. 동적 계획법을 통한 연쇄 행렬 곱셈 문제의 해결은 알고리즘 설계 및 분석 능력을 향상시키는 데 도움이 될 것입니다.
7. 스트링 편집 거리 문제

스트링 편집 거리 문제는 두 개의 문자열 사이의 최소 편집 거리를 찾는 문제입니다. 이 문제는 동적 계획법을 사용하여 해결할 수 있으며, 문자열 처리, 자연어 처리, 생물정보학 등 다양한 분야에서 활용됩니다. 스트링 편집 거리 문제는 문자열 간의 유사도를 측정하는 데 사용되며, 이는 텍스트 마이닝, 문서 클러스터링, 철자 교정 등의 응용 분야에서 중요한 역할을 합니다. 또한 이 문제는 알고리즘 설계와 분석, 동적 계획법 등 핵심 알고리즘 개념을 이해하는 데 도움이 됩니다. 스트링 편집 거리 문제의 효율적인 해결은 다양한 문자열 처리 문제에 대한 통찰력을 제공할 것입니다.
8. 플로이드 알고리즘

플로이드 알고리즘은 그래프 이론에서 중요한 알고리즘 중 하나입니다. 이 알고리즘은 가중치 그래프에서 모든 노드 쌍 간의 최단 경로를 찾는 문제를 해결합니다. 플로이드 알고리즘은 동적 계획법을 사용하여 효율적으로 동작하며, 시간 복잡도가 O(n^3)으로 매우 빠릅니다. 이 알고리즘은 네트워크 라우팅, 교통 계획, 사회 네트워크 분석 등 다양한 분야에서 활용됩니다. 또한 플로이드 알고리즘은 그래프 이론, 동적 계획법, 알고리즘 설계와 분석 등 핵심 컴퓨터 과학 개념을 이해하는 데 도움이 됩니다. 이 알고리즘에 대한 깊이 있는 이해는 복잡한 그래프 문제를 해결하는 데 필수적입니다.
9. 저울 문제

저울 문제는 주어진 무게 집합에서 모든 무게를 측정할 수 있는 최소 개수의 저울을 찾는 문제입니다. 이 문제는 그리디 알고리즘을 사용하여 해결할 수 있으며, 최적의 해를 찾는 데 동적 계획법도 활용될 수 있습니다. 저울 문제는 알고리즘 설계와 분석, 최적화 문제 해결 등에 있어 중요한 개념입니다. 또한 이 문제는 실생활의 다양한 응용 분야에서 발생하며, 효율적인 해결 방법을 찾는 것이 중요합니다. 저울 문제에 대한 이해는 그리디 알고리즘과 동적 계획법의 활용 능력을 향상시키는 데 도움이 될 것입니다.
10. 동전 거스름돈 문제

동전 거스름돈 문제는 주어진 동전 집합을 사용하여 특정 금액을 거슬러 주는 최소 동전 개수를 찾는 문제입니다. 이 문제는 그리디 알고리즘을 사용하여 해결할 수 있으며, 동적 계획법을 활용하여 최적의 해를 찾을 수도 있습니다. 동전 거스름돈 문제는 알고리즘 설계와 분석, 최적화 문제 해결 등에 있어 중요한 개념입니다. 또한 이 문제는 실생활의 다양한 응용 분야에서 발생하며, 효율적인 해결 방법을 찾는 것이 중요합니다. 동전 거스름돈 문제에 대한 이해는 그리디 알고리즘과 동적 계획법의 활용 능력을 향상시키는 데 도움이 될 것입니다.
11. 최소 신장 트리

최소 신장 트리 문제는 가중치 그래프에서 모든 노드를 연결하는 최소 비용의 트리를 찾는 문제입니다. 이 문제는 크루스칼 알고리즘이나 프림 알고리즘을 사용하여 해결할 수 있습니다. 최소 신장 트리 문제는 네트워크 설계, 통신 시스템 구축, 전력 배전망 설계 등 다양한 응용 분야에서 중요하게 활용됩니다. 또한 이 문제는 그래프 이론, 탐욕 알고리즘, 우선순위 큐 등 핵심 알고리즘 개념을 이해하는 데 도움이 됩니다. 최소 신장 트리 문제에 대한 깊이 있는 이해는 복잡한 그래프 문제를 해결하는 데 필수적이며, 알고리즘 설계와 분석 능력을 향상시키는 데 기여할 것입니다.