본문 바로가기

분류 전체보기407

4: 알고리즘-8(병합 정렬:Merge sort) 병합 정렬(Merge sort): 원소가 한 개가 될 때까지 계속해서 반으로 나누다가 다시 합쳐 나가며 정렬을 하는 방식 전화번호부의 분할 정복 탐색처럼 데이터를 반으로 나누어 간다는 것과 공통점이 있음 버블 정렬이나 선택 정렬보다도 빠는 알고리즘 병합 정렬의 세 단계: 왼쪽 정렬, 오른쪽 정렬, 이 두 배열의 병합 병합정렬의 의사코드 If only one item Return Else Sort left half of items Sort right half of items Merge sorted halves 임의의 숫자들을 오름차순으로 병합 정렬을 사용해 정렬하기 1) 7 4 5 2 6 3 8 1 2) 7 4 5 2 | 6 3 8 1 3) 7 4 | 5 2 | 6 3 8 1 4) 7 | 4 | 5 2 |.. 2021. 12. 1.
4: 알고리즘-7(재귀:Recursion) 재귀: 프로그램이나 알고리즘의 스스로를 계속 호출하는 것, 함수 내부에서 자기 자신을 호출함 함수가 초기에 주어진 입력보다 더 작은 입력을 가지고 계속해서 자신을 호출함 반복문을 사용하는 코드는 항상 재귀함수를 통해 구현하는 것이 가능하고 그 반대도 가능함 피라미드 모양을 출력하기 위한 코드 작성하기 # ## ### #### #include #include //draw 함수의 프로토타입 void draw(int h); int main(void) { //사용자로부터 피라미드의 높이를 입력 받아 저장 int height = get_int("Height: "); //draw 함수로 피라미드 그리기 draw(height); } //draw 함수 구현하기(값을 반환할 필요없이 출력만 하기 때문에 void draw.. 2021. 12. 1.
4: 알고리즘-6(정렬 알고리즘의 실행시간) 앞에 Big Ω 표기에서 버블정렬의 하한은 Ω(n^2)이지만 이것을 개선할 여지가 있음 원래 버블 정렬의 의사코드 Repeat n–1 times For i from 0 to n–2 If i'th and i+1'th elements out of order Swap them 여기서 안쪽 루프에서 만약 교환이 일어나지 않는다면 이미 정렬이 잘 되어 있는 상황 따라서 바깥쪽 루프를 ‘교환이 일어나지 않을 때’까지만 수행하도록 조건을 바꿀 수 있음 "만약 아무런 swap이 없다면 동작을 멈춘다" Repeat until no swaps For i from 0 to n–2 If i'th and i+1'th elements out of order Swap them 이렇게 되면 버블정렬은 n-1번의 과정만 필요하게 됨 .. 2021. 12. 1.
4: 알고리즘-5(선택 정렬:Selection Sort) 선택 정렬(selection sort) 배열 안의 자료 중 가장 작은 수(혹은 가장 큰 수)를 찾아 첫 번째 위치(혹은 가장 마지막 위치)의 수와 교환해주는 방식의 정렬 선택 정렬은 교환 횟수를 최소화하는 반면 각 자료를 비교하는 횟수는 증가함 정렬되지 않은 숫자들을 오름차순 정렬하기 3 5 1 6 4 8 7 1 5 3 6 4 8 7 1 3 5 6 4 8 7 1 3 4 6 5 8 7 1 3 4 5 6 8 7 1 3 4 5 6 7 8 아래 숫자 중에서 가장 작은 값을 찾고 첫 번째 값과 교환한 다음 작은 숫자부터 시작해서 계속 바꿔줌 첫 번째 자료를 두 번째 자료부터 마지막 자료까지 차례대로 비교하여 가장 작은 값을 찾아 첫 번째에 놓고, 두 번째 자료를 세 번째 자료부터 마지막 자료까지 와 차례대로 비교.. 2021. 11. 29.
4: 알고리즘-4(버블 정렬:Bubble Sort) 버블 정렬(bubble sort) 정렬 알고리즘 중 하나로 두 개의 인접한 자료 값을 비교하면서 위치를 교환하는 방식으로 정렬하는 방법 버블 정렬은 두 개의 요소만 정렬해주는 좁은 범위의 정렬에 집중하기 때문에 접근법은 간단하지만 단 하나의 요소를 정리하기 위해 너무 많이 교환하는 낭비가 발생할 수도 있음 임의의 순서로 나열되어 있는 6개의 숫자를 오름차순으로 정렬 6 3 8 5 2 7 3 6 8 5 2 7 3 6 5 8 2 7 3 6 5 2 8 7 3 6 5 2 7 8(1회전) 3 5 6 2 7 8 3 5 2 6 7 8(2회전) 3 2 5 6 7 8(3회전) 2 3 5 6 7 8(4회전) 마치 거품이(비교 및 교환)이 터지면서 위로 올라오는 (배열의 옆으로 이동하는) 방식 같아서 이러한 정렬 방식을 버.. 2021. 11. 29.
4: 알고리즘-3(선형 검색:Linear Search) 선형검색 찾고자 하는 자료를 검색하는 데 사용되는 다양한 알고리즘 중 하나 선형검색은 원하는 값이 발견될 때까지 처음부터 마지막 자료까지 차례대로 검색하는 방법 효율성과 비효율성 선형 검색 알고리즘은 정확하지만 효율적이지 못한 방법 리스트의 길이가 n일 때, 최악의 경우 리스트의 모든 값을 확인해야 해서 n번만큼 실행됨 최악의 상황(worst case)은 찾고자 하는 자료가 맨 마지막에 있거나 리스트 안에 없는 경우 최선의 상황은 처음 시도했을 때 찾고자 하는 값이 있는 경우 선형검색은 자료가 정렬되어 있지 않거나 어떤 정보도 없어 하나씩 찾아야 하는 경우에 유용함 정렬은 시간이 오래 걸리고 공간을 더 차지하지만 이 과정을 진행하면 여러 번 리스트를 검색해야 하거나 매우 큰 리스트를 검색해야 할 경우 시.. 2021. 11. 29.

티스토리툴바