알고리즘의 유래
-“알콰리즈미”라는 사람의 이름으로부터 유래
-최초의 알고리즘 = 유클리드의 최대공약수 알고리즘 (몫과 나머지의 성격을 이용하여)
알고리즘이란?
: 문제를 해결하기 위한 단계적인 절차
-효율적인 알고리즘 고안이 중요
= 최소한의 시간과 비용이 드는 것(시간 복잡도와 공간 복잡도를 최소화시키는 알고리즘)
알고리즘 기술 방법
-알고리즘이라는 것은 문제를 해결하는 방법을 고안하는 것뿐만 아니라 약속된 방법을 통해서 절차를 기술하는 것까지가 알고리즘이다.
기술 방법 = 자연어, flow chart, 의사코드 등
의사코드가 가장 일반적 (프로그래밍 코드와 매우 유사)
모든 문제를 그때 그때마다 구현까지 하려면 복잡한 문제는 구현하는데까지 드는 비용이 매우 높을 것이다. 그 전단계까지인 의사코드를 통해 표기하면 구현까지의 비용을 감소시킬 수 있다.
1.1 최대 숫자 찾기
(1) 의사코드 표현
Alg findMax(A) -- 알고리즘 이름 == int findMax(int A[])
input array A of size n -- 입력값으로 n사이즈의 배열이 들어간다. (자료형도 써도 된다)
output integer max
(순차적인 절차이기 때문에 순서를 부여한다)
1. max <- A[0] -- 처음 들어가는 input값이 max라고 가정하기 때문에 max라고 함, A의 배열 중 0번째를 max에 대입
2. for i <- 1 to n-1 -- 1`~ n-1까지 돌면서
if (A[i] > max) -- max값보다 해당 index가 더 크다면
max <- A[i] -- max에 해당 indec값을 대입한다.
3. return max
문제 = 정렬되지 않는 숫자들 중에서 최대값을 찾는다.
방법 = 숫자를 하나씩 비료하면서 본 숫자들 중에서 가장 큰 숫자를 기억해가며(임시 저장) 찾아보기
→ 순차탐색(이 방법밖에 없음)
1.2 임의의 숫자 찾기
Alg findKey(A, key) -- 알고리즘 이름 == int findMax(int A[])
input array A of size n, integer key -- 배열과 key 값 입력
output index of key or signal of failure (-1) -- key의 위치를 return 한다.(실패하면 -1 )
1. for i <- 0 to n-1 -- 1`~ n-1까지 돌면서
if (A[i] == key) -- key값과 같으면
return index of key (즉, i값을 의미)
2. return -1 --key값이 없는 경우 (failure)
문제 = 일차원적인 데이터(= 선형적)가 있고 이 중에서 입력된 key값을 찾기
방법 = 순차탐색 ( 1.1 최대값 찾기는 무조건 탐색에 성공하여 결과를 return하지만 1.2는 탐색에 실패할 수도 있다는 차이점이 있다)
문제
만약 오름차순으로 미리 정렬되어 있는 상태였다면?
⇒ 훨씬 더 효율적인 방법이 존재 = “이진 탐색”
[ 이진탐색 ]
- 정가운데를 찾기
- 중간 숫자와 key를 비교한 후
같으면 → 탐색 끝
다르면 → 크기 비교 후 비교 대상 범위 축소
방법
- 반복문
- 재귀
//이진탐색트리 템플릿
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
void selectionSort(int list[])
{
int min, temp;
for (int i = 0; i < 19; i++)
{
min = i;
for (int j = i + 1; j < 20; j++)
if (list[j] < list[min])
min = j;
temp = list[min];
list[min] = list[i];
list[i] = temp;
}
}
int main()
{
int A[20];
srand(time(NULL)); // 임의의 숫자(난수 발생)
for(int i = 0; i < 20; i++)
A[i] = rand() % 100; // 여기까지 임의의 숫자 난수 발생 후 배열
selectionSort(A); // 정렬 알고리즘
for(int i = 0; i < 20; i++)
printf("%d ", A[i]);
printf("\\n");
return 0;
}
이진탐색_반복문
// 이진 탐색 -> 상한과 하한을 줄여나가면서(공간을 줄이면서) key 값을 찾는다.
//예시 20개의 배열이며 인덱스는 0 ~ 19까지 라고 가정
int BinarySearchIter(int A[], int left, int right, int key )
{ // left = 하한, right = 상한
int mid, count = 0; // 중간값을 기억하기 위해 mid, 몇번만에 찾았는지 기록하기 위해 count
while (left <= right) // "탐색할 수 있는 공간이 있으면" -> 이에 만족하지 않는 경우는 상한과 하한이 크로스가 된 상황이기 때문에 찾을 공간이 없음
{
count++; // 탐색시도 횟수 증가
mid = (left + right) / 2; // 중간값 찾기 (예시 = 9)
if (key == A[mid]) //찾는 숫자가 중간 위치의 숫자와 같다면
return count;
else if (key < A[mid])// mid 위쪽에는 key값이 없을 것이므로 버린다
right = mid - 1; // 상한선을 줄이자 ( 0~8 인덱스에서 찾자)
else
left = mid + 1; //하한값을 증가한다 (10 ~ 19 사이)
}
return 0;
}
int main()
{
int A[20], k;
srand(time(NULL)); // 임의의 숫자(난수 발생)
for(int i = 0; i < 20; i++)
A[i] = rand() % 100; // 여기까지 임의의 숫자 난수 발생 후 배열
selectionSort(A); // 정렬 알고리즘
for(int i = 0; i < 20; i++)
printf("%d ", A[i]);
printf("\\n");
printf("key : ");
scanf("%d", %k); // key 값 입력받기
printf("%d\\n", binarySrearchIter(A, 0, 19, k)); //몇번만에 찾았는지
return 0;
}
이진탐색_재귀함수
// 이진 탐색 -> 상한과 하한을 줄여나가면서(공간을 줄이면서) key 값을 찾는다.
//예시 20개의 배열이며 인덱스는 0 ~ 19까지 라고 가정
int BinarySearchRecur(int A[], int left, int right, int key )
{
int mid = 0;
static int count = 0; // 재귀 함수할 때는 계속 함수를 호출하는 것이므로 지역함수일 경우
// 계속 초기화가 된다. -> 누적 불가, 따라서 정적 변수로 선언될 수 있기 때문에 함수가 계속 호출되어도 누적된 결과를 알 수 있음
if (left <= right) // 재귀 함수 빠져나가기 위해 필요한 조건
{
count ++;
mid = (left + right) / 2;
if (key == A[mid]){
return count;
}
else if (key < A[mid]){
return BinarySearchRecur(A, left, mid - 1, key) // 자신을 호출할 때 매개변수를 바꿔서 호출
}
else{
BinarySearchRecur(A, mid + 1, right, key)
}
return 0;
}
}
int main()
{
int A[20], k;
srand(time(NULL)); // 임의의 숫자(난수 발생)
for(int i = 0; i < 20; i++)
A[i] = rand() % 100; // 여기까지 임의의 숫자 난수 발생 후 배열
selectionSort(A); // 정렬 알고리즘
for(int i = 0; i < 20; i++)
printf("%d ", A[i]);
printf("\\n");
printf("key : ");
scanf("%d", %k); // key 값 입력받기
printf("%d\\n", binarySrearchIter(A, 0, 19, k)); //몇번만에 찾았는지
return 0;
}
1.3 동전 거스름돈
상황 = 거스름돈을 받을 때 “가장 적은 수"의 동전을 원한다. 현시점에서 가장 이득인 순으로 한다.
[ 그리디 알고리즘 (탐욕기법) ]
가장 이득인 것을 취하면서 결과를 낸다.
이 알고리즘을 통해 얻은 결과는 최상의 답이다. (하지만 문제에 따라서는 최선과 유사하지만 정확한 결과가 아닌 값인 경우도 있음)
1.4 한붓 그리기
상황 = 종이에서 연필을 떼지 않고 그래프를 그린다.
조건 = 모든 간선을 한 번만 지나야 함 + 종점이 출발점
-오일러 순환 = 정점과 정점 사이의 간선을 한 번만 지남, 시작점 = 종점
-오일러 경로 = 정점과 정점 사이의 간선을 한 번만 지난다(그래프 이론), 시작점 ≠ 종점( 오일러 순환을 포함)
-헤밀턴 = 간선은 몇번 지나도 상관없는데 모든 정점을 한 번씩만 가는 문제(외판원 문제, 51개주를 한 번만 방문하는 방법)
-참고 : 프로그래밍을 짤 때 오일러 순환이 되기 위해서는 모든 정점이 짝수여야 한다. 는 것을 반영하여 먼저 정점이 짝수인지 확인하고 그 다음 경로를 탐색하게 한다.
[ 그림 ]
6과 9의 특징을 찾아서 고안해내는 것이 알고리즘이며 그래프 이론과 관계된 알고리즘이다.
방법 : 현재 점으로 돌아오는 사이클이 있으면 진행한다.
각각 정점에서 선택을 할 때 자신의 선택 후 다시 자신을 지나서 원래의 정점으로 돌아갈 수 있어야 한다. 그렇지 못한다면 경우의 수에서 제거해 나가는 것이다.
1.5 미로 찾기
상황 = 미로 , 어두워서 표시를 볼 수 없음
해결 방안 = 오른손 법칙
출구가 있는 미로라면 무조건 오른손 법칙을 통해 출구를 찾을 수 있다.
벽에 오른손을 대고 걷기만하면 막히더라도 다시 오른쪽 벽을 타고 나오면 빠져나갈 수 있음
오른손 법칙이 해결 가능한 이유 = 오른손으로 대고 가는 과정 자체는 유연한 끈으로 이을 수 있고 이 벽들을 당긴다는 것이고 이것이 일자로 만들어질 수 있다.
백트래킹 기법의 하나의 예이다.
1.6 가짜 동전 찾기
이진 탐색에서 재귀호출했던 문제와 비슷하게 문제 해결 (분할정복 기법)
가정 = 동전의 개수 2의 거듭제곱(홀짝이 바뀌게 되면 프로그램으로 구현시 어려울 수 있음)
상황 = 동전 중 하나의 동전만 가짜이다.
조건 = 양팔 저울을 이용해서 찾는데 횟수를 최소화하여 찾아라
(1) 철수의 아이디어
한 개를 기준으로 나머지를 비교 (예를 들어 총 16개라면 1개를 올려놓고 15개를 비교)
최선 = 1번만에 가짜 동전 찾음
최악 = n -1 번째에 가짜 동전 찾음
(2) 영희 아이디어
n개를 두개씩 짝을 지어 쌍끼리 비교한다
최선 = 1번만에 가짜 동전 찾음
최악 = 마지막 “쌍"에서 가짜 동전 찾음 → 철수의 방법에 비해 1/2 로 저울 사용이 감소한다.
항상 철수의 방법보단 적음
(3) 광수 아이디어
방법 = 동전 전체를 2묶음으로 나누어 저울에 양편에 놓는다. 그 중 하나의 묶음에는 반드시 가짜 동전이 있다.
해당 묶음을 다시 2묶으로 나누어서 비교
비교횟수 = 2의 거듭제곱꼴에서 지수만큼만 하면된다(예를 들어 동전이 2의 10승개가 있다면 10번만 비교하면 된다)
장점 = 동전이 많아지면 많아질수록 더 효율적인 알고리즘이다. (빠르게 찾기 가능)
<광수 아이디어 직접해보기 → 이진탐색 재귀함수 버전과 비슷 , sum 함수를 이용해서 양쪽 무개를 비교 >
//동전이 전체 16개
int cheolsu(int A[])
{
int a = A[0];
int count = 0;
for(int i = 1; i < 16; i++)
{
count++;
if(a != A[i])
return count;
}
}
int yeonghui(int A[])
{
int count = 0;
for(int i = 0; i < 16; i += 2)
{
count++;
if(A[i] != A[i + 1])
return count;
}
}
int main()
{
int A[16];
srand(time(NULL));
for(int i = 0; i < 16; i++)
A[i] = 10;
A[rand() % 16] = 9;
for(int i = 0; i < 16; i++)
printf("%d ", A[i]);
printf("\\n");
printf("%d %d\\n", cheolsu(A), yeonghui(A));
}
int sum(int A[], int left, int right) //sum 함수를 통해 오른쪽과 왼쪽의 무개를 비교한다(무개의 합을 이용해서 비교 계산한다)
{
int result = 0;
for(int i = left; i <= right; i++)
result += A[i];
return result;
}
int kwangsu(int A[], int left, int right)
{
}
'CS > 알고리즘' 카테고리의 다른 글
| Chap3-4. 최근접 점의 쌍 찾기(Closest Pair) (0) | 2022.04.08 |
|---|---|
| Chap3-2 퀵정렬(QuickSort) (0) | 2022.04.05 |
| Chap3-1. 합병 정렬(MergeSort) (0) | 2022.04.04 |
| Chap 3. 분할 정복 알고리즘 (0) | 2022.04.02 |
| Ch2. 알고리즘 (0) | 2022.03.14 |
