본문 바로가기

분류 전체보기

 (894)
6-6장 퀵 정렬(1) 1. 퀵 정렬 살펴보기 퀵 정렬 (quick sort) - 각 그룹에 대해 피벗설정과 그룹 나눔을 반복하여 모든 그룹의 요소가 1개가 되면 정렬을 마침 - 피벗(pivot) : 그룹을 나누는 기준 2. 배열을 두 그룹으로 나누기 - x : 피벗 pl : 왼쪽 끝 요소의 인덱스 pr : 오른쪽 끝 요소의 인덱스 - 그룹을 나누기 위해 피벗 이하의 요소를 배열 왼쪽으로, 피벗 이상의 요소를 배열 오른쪽으로 옮겨야 함 1) a[pl] >= x 가 성립되는 요소를 찾을 때까지 pl을 오른쪽으로 옮김 a[pr] 피벗 이하의 값은 왼쪽으로 이동하고 피벗 이상의 값은 오른쪽으로 이동함 4) 2번,3번 과정을 pr과 pl이 교차할때까지 진행, pr과 pl이 교차하면 두 그룹으로 나눠짐 - 피벗 이하의 그룹 : a[0]..
6-5장 쉘 정렬 1. 단순 삽입 정렬의 특징 이해하기 - 정렬을 마쳤거나 정렬을 마친 상태에 가까우면 정렬 속도가 매우 빨라짐 (장점) - 삽입할 위치가 멀리 떨어져 있으면 이동(대입)해야 하는 횟수가 많아짐(단점) 2. 쉘 정렬 살펴 보기 - 단순 삽입 정렬의 장점은 살리고 단점은 보완한 알고리즘 - 정렬할 배열의 요소를 그룹으로 나눠 각 그룹별로 단순 삽입 정렬 수행 - 그 그룹을 합치면서 정렬을 반복하여 요소의 이동 횟수를 줄이는 방법 - ex) 배열 {8,1,4,2,7,6,3,5}을 4개의 배열로 나누기 - ({8,7},{1,6},{4,3},{2,5}) - 4- 정렬 - 2-정렬 ({7,3,8,4},{1,2,6,5}) - 1-정렬을 적용하면 정렬을 마치게 됨 - h-정렬 -> 쉘 정렬 과정에서 수행하는 각각의 정..
6-4장 단순 삽입 정렬 1. 단순 삽입 정렬 알아보기 단순 삽입 정렬 (straight insertion sort) - 선택한 요소를 그보다 더 앞쪽의 알맞은 위치에 '삽입'하는 작업을 반복하여 정렬 - 아직 정렬되지 않은 부분의 첫 번째 요소를 정렬된 열의 '알맞은 위치에 삽입'하는 작업을 n-1회 반복 - 배열 {6,4,1,7,3,9,8}의 단순삽입정렬과정 ex) 값이 3인 요소를 선택해 앞쪽의 알맞은 위치에 삽입하는 과정 - 3보다 작은 요소를 만날 때까지 이웃한 왼쪽의 요소를 대입하는 작업을 반복 - 멈춘 위치에 3을 대입 - 반복 제어용 변수 j에 i 대입 - tmp에 a[i] 대입 (a[i] = 정렬되지 않은 부분의 첫 번째 요소) - 종료 조건 중 하나를 만날 때까지 j를 1씩 감소하면서 대입하는 작업 반복 OR ..
6-3장 단순 선택 정렬 1. 단순 선택 정렬 알아보기 단순 선택 정렬 (straight selection sort) - 가장 작은 요소부터 선택해 알맞은 위치로 옮겨서 순서대로 정렬 - 교환 과정 1) 아직 정렬하지 않은 부분에서 가장 작은 키의 값 (a[min])을 선택 2) a[min]과 아직 정렬하지 않은 부분의 첫 번째 요소를 교환 ex) 배열 {6,4,8,3,1,9,7}을 선택 정렬 - 아직 정렬하지 않은 부분에서 값이 가장 작은 요소를 선택하고 - 아직 정렬하지 않은 부분의 첫번째 요소와 교환 - 단순 선택 정렬 프로그램 //단순 선택 정렬 #include #include #define swap(type,x,y) do {type t=x; x=y; y=t;} while(0) void selection(int a[],i..
6-2장 버블 정렬 1. 버블 정렬 알아보기 버블 정렬(bubble sort) - 이웃한 두 요소의 대소관계를 비교하여 교환을 반복 ex) 배열 {6,4,3,7,1,9,8} 오름차순 정렬 - 왼쪽에 있는 값이 오른쪽에 있는 값보다 작아야 함 - 요소의 개수가 n개인 배열에서 n-1회 비교, 교환을 하면 오름차순으로 정렬됨 - 패스(pass) : 일련의 과정(비교, 교환 과정) - 버블 정렬의 첫 번째 패스 - 버블 정렬의 두번째 패스 - 패스를 1회 수행할 때마다 정렬할 요소가 하나씩 줄어듬 - 패스를 k회 수행하면 앞쪽의 요소가 k개 정렬됨 - 모든 정렬이 끝나려면 n-1회의 패스가 수행되어야 함 - 버블정렬 프로그램 //버블 정렬 (버전1) #include #include #define swap(type,x,y) do ..
6-1장 정렬 1. 정렬 정의 하기 정렬(sorting) - 이름, 학번, 키 등 핵심 항목 (key)의 대소 관계에 따라 데이터 집합을 일정한 순서로 줄지어 늘어서도록 바꾸는 작업 - 키 값이 작은 데이터를 앞쪽에 놓으면 오름차순(ascending order) - 키 값이 큰 데이터를 앞쪽에 놓으면 내림차순(descending order) 정렬 알고리즘의 안정성 - 안정된(stable) 정렬 -> 같은 값의 키를 가진 요소의 순서가 정렬 전후에도 유지 -> 중복된 값을 입력 순서와 동일하게 정렬 -> 삽입 정렬, 병합 정렬, 버블 정렬 - 불안정(unstable) 정렬 -> 중복된 값을 입력순서와 동일하지 않게 정렬 -> 퀵 정렬, 선택 정렬 정렬 알고리즘의 핵심 요소 - 교환, 선택, 삽입 내부 정렬과 외부 정렬 ..
5-4장 8퀸 문제 1. 8퀸 문제 정의하기 - 서로 공격하여 잡을 수 없도록 8개의 퀸을 8x8 체스판에 놓으세요 - 퀸은 가로,세로, 대각선 방향으로 체스판 끝까지 이동 가능 - 규칙 1) 각 열에 퀸을 1개만 배치 2) 각 행에 퀸을 1개만 배치 2. 가지 뻗기(branching) - 가지를 뻗으며 퀸을 배치하는 조합 모두 나열 - 배열 pos는 퀸의 배치를 나타냄 - i열에 놓인 퀸의 위치가 j행이면 pos[i]의 값을 j로 함 - set함수 -> pos[i]에 0부터 7까지의 값을 순서대로 대입하여 'i열에 퀸을 1개만 배치하는 8가지 조합을 만드는 재귀함수' -> 0번째 열에 퀸을 배치 set(0); //0열에 퀸을 배치 -> for문에 의한 반복 구문에서는 i값을 0에서 7까지 증가시키면서 pos[i]에 j를 ..
5-3장 하노이의 탑 1. 하노이의 탑 살펴보기 하노이의 탑 (Towers of Hanoi) - 작은 원반이 위에, 큰 원반이 아래에 위치할 수 있도록 원반을 3개의 기둥 사이에서 옮기는 문제 - 모든 원반을 세번째 기둥으로 최소의 횟수로 옮김 - 원반은 1개씩만 옮길 수 있음 - 큰 원반을 작은 원반 위에 쌓을 수는 없음 - 원반이 3개일때 모든 과정 - 그룹 : 원반 1과 원반 2를 겹친 것 - 가장 큰 원반을 최소의 단계로 목표 기둥으로 옮기려면 먼저 '그룹'을 중간 기둥으로 옮겨야 함 - 원반 1과 원반 2가 겹친 '그룹'을 옮기는 단계 - 하노이의 탑 구현 프로그램 - move( 옮겨야 할 원반의 개수, 시작 기둥의 번호, 목표 기둥의 번호) //하노이의 탑 #include //원반[1] ~원반[no]를 x기둥에서 ..

티스토리툴바