강몬드의 프로그래밍 이야기

알고리즘 공부한 내용을 작성하겠습니다. 일단, 시험 준비를 위해 알고리즘에서 프로그래밍 언어는 C/C++언어만 사용합니다.

이진 탐색(Binary Search)이진 탐색은 정렬된 배열에서 원하는 값을 탐색하는 방법입니다.

버블 정렬(Bubble Sort)버블 정렬은 인접한 원소 간의 대소관계를 비교하여 주어진 규칙에 따라 인접한 원소를 교환하는 방법입니다. 맨 앞에 위치한 원소부터 순차적으로 인접한 원소 간의 대소관계를 비교하면, 배열의 원소 중 가장 큰 값이 마지막에 위치하게 됩니다. 이를 통해 마지막 원소가 정렬이 되고, 이를 N-1 번 반복을 하게 되면 정렬이 완료 됩니다.버블 정렬의 시간복잡도는 고려해야 할 반복문이 (정렬해야 할 원소의 개수 - 1) * (최대 교환 수)이므로 총 O(N^2)가 됩니다. 앞 글에서 설명한 선택 정렬과 삽입 정렬과 동일한 시간복잡도 이므로 자주 쓰이지는 않습니다. 아래는 버블 정렬의 이해를 도울 수 있는 의사코드와 예제를 보여 줍니다. 의사코드123456789bubbleSort(){..

삽입 정렬(Insertion Sort)삽입 정렬은 배열을 정렬된 부분, 정렬되지 않은 부분으로 나눈 후, 정렬 되지 않은 원소를 순차적으로 비교하면서 정렬이 된 부분에 끼워 넣는 방법입니다. 시간 복잡도는 선택 정렬(Selection Sort)와 동일하게 O(N^2)이다. 각 원소에 적당한 위치 찾는 복잡도: 총 원소의 개수 O(N), 순차적으로 삽입 위치를 찾는 복잡도: O(N)이다. 그림여기서는 위 방법을 그림을 통해 설명합니다.삽입 정렬은 정렬 부분(빨간 점선 박스), 정렬 되지 않은 부분(파란 점선 박스)을 나누고 정렬이 된 부분에 순차적으로 원소를 끼워 넣는 방법입니다. 1단계에서는 첫 번째 원소 '19'를 정렬된 부분에 끼워 넣습니다. 2단계에서는 두 번째 원소 '89'를 정렬 부분의 원소와 ..

선택 정렬(Selection Sort)선택 정렬은 매 차례마다 순차적으로 각 인덱스에 해당하는 원소의 값(최소값or 최댓값)을 찾고 해당 인덱스의 원소와 교환해주는 정렬입니다.매 차례마다 남은 원소들을 모두 확인해야 하기 때문에 알고리즘 상 시간 복잡도는 최악의 연산 횟수나 평균 연산 횟수나 O(N^2) 입니다. 그림크기가 5인, 배열을 예로 그림을 통해 설명하겠습니다. 순차적으로 각 인덱스마다(5단계) 해당하는 원소의 값(최소값)을 찾고 해당 인덱스(각 단계)에서 원소를 교환해주는 방법입니다. 1단계에서 첫 번째 인덱스의 값은 '19'를 가리키고, 이후 인덱스에서 최소값 '6'을 찾아서 교환합니다. 2단계에서 두 번째 인덱스는 '89'를 가리키고, 첫 번째 인덱스(이미 정렬이 된)를 제외한 인덱스에서 ..