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

소개

2023년 1학기 알고리즘 출석수업 과제 만점 받은 리포트입니다.

문제는 아래와 같았습니다.

1. 다음은 입력 크기 n에 대한 빅오 함수들이다. 알고리즘의 성능 관점에서 가장 나쁜 것부터 차례대로 나열하시오.
2. 다음 4가지 경우에 해당하는 점화식과 폐쇄형을 쓰시오.
3. 대표적인 알고리즘 설계 기법이 적용된 문제들을 모두 나열하고, 해당 문제의 정의/개념에 대해서 간단히 설명하시오.
4. 주어진 배열에 대해서 퀵 정렬의 분할 함수 Partition()을 적용한 후의 결과 배열을 구하시오.
5. 물체를 쪼갤 수 있는 배낭 문제에 대해서 욕심쟁이 방법을 적용해서 최대 이익을 구하시오.
6. 다음 그래프에 대한 최소 신장 트리와 해당 트리의 가중치의 합을 구하시오.

문제는 다르더라도 교수님이 선호하시는 작성 방향을 파악하는데 도움이 되리라 생각합니다.

목차

없음

본문내용

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

2) 퀵 정렬
퀵 정렬은 데이터 중 하나의 값을 피벗으로 뽑고 데이터를 그 값보다 큰 쪽과 작은 쪽으로 분할시키는 과정을 재귀적으로 반복함으로써 데이터를 정렬하는 알고리즘이다. 데이터 중에서 고른 피벗을 기준으로 분할하고 그 가운데에 피벗을 놓으면 피벗의 올바른 위치를 찾을 수 있다(이런 일을 하는 함수를 보통 Partition 함수라고 명명함). 이 과정을 큰 쪽과 작은 쪽으로 분할된 각각의 부분의 크기가 1개 이하가 될 때까지 반복하면, 데이터를 정렬할 수 있다.
퀵 정렬에 있어 최악의 경우는 피벗을 고를 때 가장 크거나 작은 값을 뽑는 것이다. 그렇게 하면 데이터를 큰 쪽과 작은 쪽으로 분할할 때, 둘 중 한 쪽에 포함되는 개수는 0개가 되고, 한 쪽에 뽑은 값을 제외한 모든 값이 포함되게 된다. 반대로, 퀵 정렬에 있어 최선의 경우는 값을 뽑을 때 중앙값을 뽑는 것이다.

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

참고자료

· 없음