Selection Sort(선택정렬) & Bineary search(이진탐색)
목차
- 선택정렬 설명 & 코드
- 이진탐색 설명 & 코드
- 알고리즘 코딩을위한 팁
Selection Sort(선택정렬)
설명
선택정렬이란?: 선택 정렬은 전체배열에서 가장 작은 것(또는 큰것)들을 하나씩 선택하여 정렬을하는방법입니다.
선택정렬을위한 단계
- 주어진 리스트 중에 최솟값을 찾는다.
- 그 값을 맨 앞에 위치한 값과 교체한다(패스(pass)).
- 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다.
자 그럼 단계를 알았으니 이것을 C언어로 프로그래밍해보겠습니다.
프로그램은 배열의 크기와 배열을 입력받아서 이를 선택정렬후 출력하도록합니다.
시작하기전
어떻게 코딩을 할것인지 각주를 통해 구상을 해봅시다.
1. 배열을 입력받아야하니 우선 데이터를 받는부분을 구현합니다.
2. 선택정렬을합니다.
3. 정렬된 배열을 출력합니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
|
#include <stdio.h>
int main(void){
//1.make array
//1.get data
//2.loop for n
//2.loop for find min
//2.exchange
//3.print
}
| cs |
무턱대고 바로 코딩을 시작하는 것보단 전체적인 구상을 잡는게 실수를 줄이며 효율적인 코드를 만들 수 있습니다.
구상을 잡았으니 단계별 프로그래밍을 진행해보겠습니다.
1. 배열을 입력받아야하니 우선 데이터를 받는부분을 구현합니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
|
#include <stdio.h>
#include <stdlib.h>
int main(void){
//make array
int array_size,*array;
scanf("%d",&array_size);
array=(int*)malloc(sizeof(int)*array_size);
//get data
int i;
for(i=0;i<array_size;i++)
scanf("%d",&array[i]);
//loop for n
//loop for find min
//exchange
//print
}
| cs |
배열의 크기를 받고 동적할당(malloc)이용해 크기만큼 정수형 배열을 생성합니다.
그리고 반복문과 scanf()함수를 통해서 데이터를 입력받습니다.
2. 선택정렬을합니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
#include <stdio.h>
#include <stdlib.h>
#define swap(a,b,temp) {temp=a;a=b;b=temp;}
int main(void) {
//make array
int array_size, *array;
scanf("%d", &array_size);
array = (int*)malloc(sizeof(int)*array_size);
//get data
int i;
for (i = 0; i < array_size; i++)
scanf("%d", &array[i]);
//loop for n
for (i = 0; i < array_size; i++) {
//loop for find min
int smallesti = i, j;
for (j = i + 1; j < array_size; j++) {
if (array[smallesti] > array[j]) {
smallesti = j;
}
}
//exchange
int t;
swap(array[smallesti], array[i], t)
}
//print
}
| cs |
구상했던데로 이중 반복문을 입력해서 범위를 줄여가며 가장작은 부분을 앞에오도록합니다.
3. 정렬된 배열을 출력합니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
|
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#define swap(a,b,temp) {temp=a;a=b;b=temp;}
int main(void) {
//make array
int array_size, *array;
scanf("%d", &array_size);
array = (int*)malloc(sizeof(int)*array_size);
//get data
int i;
for (i = 0; i < array_size; i++)
scanf("%d", &array[i]);
//loop for n
for (i = 0; i < array_size; i++) {
//loop for find min
int smallesti = i, j;
for (j = i + 1; j < array_size; j++) {
if (array[smallesti] > array[j]) {
smallesti = j;
}
}
//exchange
int t;
swap(array[smallesti], array[i], t)
}
//print
for (i = 0; i < array_size; i++) {
printf("%d ", array[i]);
}
}
| cs |
Bineary search(이진탐색)
설명
이진탐색이란?
이진탐색은 배열중에서 어떤 수를 찾는 방법중 하나입니다.
전체 범위에서 가운데 숫자를 기준으로 그 숫자보다 큰 지 작은지 범위를 좁혀가며 숫자를 찾습니다. 이 방식은 순서대로 찾는것보다 훨씬 효율적입니다.
이진탐색은 오름차순으로 정렬된 배열에서만 사용이 가능합니다.
그럼이제 배열의 크기, 배열 그리고 찾고 싶은 수를 받아서 수의 위치를 반환하는 알고리즘을 작성해보도록 하겠습니다.
위와 마찬가지로 구상을 해봅시다.
1. 배열의크기, 배열 그리고 찾고 싶은 수를 입력받는다
2. 중간값이 찾고싶은 수인지 더 작은지, 큰지 비교하여 범위를 좁혀나가는걸 반복한다.
3. 찾고싶은 수가 있다면 위치를 출력하고 없다면 -1을 출력한다.
이번 구상은 위보다 조금 어려울수 있습니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
int main(void) {
//make array
//get data( array and target)
// loop while range > 0
// find midle value
//check value is target
//else if value < target
//else(target < value)
//check find
}
| cs |
구상한걸 우선 각주로 표현하고 하나씩 진행해봅시다.
1. 배열의크기, 배열 그리고 찾고 싶은 수를 입력받는다
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
int main(void) {
//make array
int array_size, *array, target;
scanf("%d", &array_size);
array = (int*)malloc(sizeof(int)*array_size);
//get data( array and target)
int i;
for (i = 0; i < array_size; i++)
scanf("%d", &array[i]);
scanf("%d",&target);
// loop while range > 0
// find midle value
//check value is target
//else if value < target
//else(target < value)
//check find
}
| cs |
이부분은 쉬우니 따로 설명하지 않습니다.
2. 중간값이 찾고싶은 수인지 더 작은지, 큰지 비교하여 범위를 좁혀나가는걸 반복한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
|
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
int main(void) {
//make array
int array_size, *array, target;
scanf("%d", &array_size);
array = (int*)malloc(sizeof(int)*array_size);
//get data( array and target)
int i;
for (i = 0; i < array_size; i++)
scanf("%d", &array[i]);
scanf("%d",&target);
int start=0,end=array_size-1, target_loc=0;
// loop while range >= 0
while(start<=end){
// find midle value
int mid=(start+end)/2
//check value is target
if(array[mid]==target){
target_loc=mid;
break;
}
//else if value < target
else if(array[mid] < target){
start=mid+1;
}
//else(target < value)
else{
end=mid-1;
}
}
//check find
}
| cs |
이 부분에서 범위를 start변수로 첫번째 지점, end변수로 마지막 지점을 정합니다.
그리고 int mid=(start+end)/2 를 이용해서 중간지점을 찾아 target과의 값을 비교하고 결과에 따라 범위를 새로 지정합니다.
3. 찾고싶은 수가 있다면 위치를 출력하고 없다면 -1을 출력한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
|
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
int main(void) {
//make array
int array_size, *array, target;
scanf("%d", &array_size);
array = (int*)malloc(sizeof(int)*array_size);
//get data( array and target)
int i;
for (i = 0; i < array_size; i++)
scanf("%d", &array[i]);
scanf("%d",&target);
int start=0,end=array_size-1, target_loc=0;
// loop while range >= 0
while(start<=end){
// find midle value
int mid=(start+end)/2
//check value is target
if(array[mid]==target){
target_loc=mid;
break;
}
//else if value < target
else if(array[mid] < target){
start=mid+1;
}
//else(target < value)
else{
end=mid-1;
}
}
//check find
if (start > end) {
printf("-1");
}
else {
printf("%d", target_loc);
}
}
| cs |
start > end인 경우가 못찾은 경우랑 같은이유는 다음과 같습니다.
위 반복문안에서는 범위가 점점줄어들고 있습니다. 범위가 줄어들어 start와 end가 같아질때의 위치에 있는 숫자가 없다면 end=mid-1; 이 실행되어 end는 start보다 작아지게 됩니다. 따라서 start > end == 못찾음이 성립됩니다.
알고리즘 코딩을위한 팁
두 개의 대표적인 알고리즘 코드를 짜보았습니다. 앞으로는 이보다 더 어렵고 복잡한 알고리즘을 짤 일이 많을 수 있습니다. 이 때 빠르고 정확하게 알고리즘을 짜는법은 절대 이해하지도 못하면서 빨리 시작부터하는것이 아닙니다.
1.복잡한 문제를 빠르게 짜기위해서는 항상 전체적인 구상을 생각해봐야 합니다.
2. 각주를 사용해 미리 코딩을 한다는 생각으로 살짝 적어주고 맞는지 판단합니다.
3. 그리고 코드를 짜면 자잘한 에러를 제외하고 거의 정확합니다.
코드를 짜기전에는 항상 이해를 해야하기 때문에 무턱대고 코드를 짜는것은 나중에 누더기옷같은 코드를 만들수 있습니 꼭 이해와 구상을 하고 짜시기 바랍니다.
'Computer Science > Data Structure' 카테고리의 다른 글
| Dive Data Structure with Java Collection (1) | 2022.03.10 |
|---|---|
| 2017 카카오페스티벌 예선 문제 1 - 카카오프렌즈 컬러링북 풀이 (0) | 2020.01.18 |
| 자료구조 3 - Transposing Sparse Matrix ( 희소행렬 대칭이동) (0) | 2020.01.18 |