코드 기록장

* 참고한 책 : 5장 | 알기 쉬운 알고리즘 | 양성봉 | 생능출판사

** 알고리즘은 위의 책에 있는 알고리즘을 사용했기 때문에 책이 있으시면 더 쉽게 이해할 수 있습니다.

*** 과제로 제가 작성했던 내용을 포스팅한 것입니다.

* 참고한 책 : 4장 | 알기 쉬운 알고리즘 | 양성봉 | 생능출판사

** 알고리즘은 위의 책에 있는 알고리즘을 사용했기 때문에 책이 있으시면 더 쉽게 이해할 수 있습니다.

퀴즈 ) 책에 있는 그리디 알고리즘으로 거스름돈 문제를 해결하려고 할 때, 반복문을 사용하지 않고 알고리즘을 구현하려면?

CoinChange(W)

입력: 거스름돈 액수 W 출력: 거스름돈 액수에 대한 최소 동전 수

1. change = W, n500 = n100 = n50 = n10 = n1 = 0 // n500, n100, n50, n10, n1은 각각의 동전 카운트

2. if ( (change / 500) ≥ 1 ) // 입력액수가 500 이상이라 몫이 1보다 크다면

change -= 500 * (change / 500), n500 = (change / 500) // 몫의 수 * 500원 금액만큼 돈을 감소, 500원 개수 = 몫의 수

3. if ( (change / 100) ≥ 1 ) // 입력액수가 100 이상이라 몫이 1보다 크다면

change -= 100 * (change / 100), n100 = (change / 100) // 몫의 수 * 100원 금액만큼 돈을 감소, 100원 개수 = 몫의 수

4. if ( (change / 50) ≥ 1 ) // 입력액수가 50 이상이라 몫이 1보다 크다면

change -= 50 * (change / 50), n50 = (change / 50) // 몫의 수 * 50원 금액만큼 돈을 감소, 50원 개수 = 몫의 수

5. if ( (change / 10) ≥ 1 ) // 입력액수가 10 이상이라 몫이 1보다 크다면

change -= 10 * (change / 10), n10 = (change / 10) // 몫의 수 * 10원 금액만큼 돈을 감소, 10원 개수 = 몫의 수

6. if ( (change / 1) ≥ 1 ) // 입력액수가 1 이상이라 몫이 1보다 크다면

change -= 1 * (change / 1), n1 = (change / 1) // 몫의 수 * 1원 금액만큼 돈을 감소, 1원 개수 = 몫의 수

7. return (n500 + n100 + n50 + n10 + n1) // 총 동전 수를 리턴한다.

* 퀴즈 출처 : 4장 | 알기 쉬운 알고리즘 | 양성봉 | 생능출판사

** 알고리즘은 위의 책에 있는 알고리즘을 사용했기 때문에 책이 있으시면 더 쉽게 이해할 수 있습니다.

그리디 알고리즘은 욕심 알고리즘이라고 하며 왜 욕심 알고리즘인지, 그리디 알고리즘의 예시를 들어 설명드리겠습니다.

그리디 알고리즘의 대표적인 예로는 동전 거스름돈 문제가 있습니다. 이 문제는 거스름 동전의 갯수가 최소가 되는 해를 찾는 문제입니다.

동전이 500원, 100원, 50원, 10원짜리가 있을 때 거스름돈이 560원이라면,

먼저, 560-500 = 60로 거스름돈이 60원 남게 되고 거스름 동전은 500원짜리 동전 1개입니다.

60-100은 불가능하기 때문에 넘어가고, 60-50 = 10로 거스름돈이 10원 남게 되고 500원짜리 동전 1개, 50원짜리 동전 1개로 총 2개 입니다.

마지막으로 10-10 = 0이므로 거스름돈이 0원이 되고 500원, 50원, 10원 동전 각각 1개씩 총 거스름돈의 동전 개수는 3개가 됩니다. 

그리디 알고리즘을 사용하면 이처럼 최소한의 동전을 거슬러 받을 수 있을 것처럼 보이지만 사실 그리디 알고리즘이 무조건 최적의 해를 찾는 것는 아닙니다. 왜냐하면 그리디 알고리즘은 무조건 큰 수(금액이 큰 동전)부터 차감하기 때문인데, 참고한 책*에 나와있는 예시를 들어보겠습니다.

만약 200원을 거슬러줘야하고, 160원, 100원, 10원짜리의 동전이 있다고 가정하면 그리디 알고리즘은 160원 동전 1개, 10원 동전 4개를 거슬러줄것입니다. 하지만 직관적으로 100원짜리 동전 2개가 최소 동전 개수가 된다는 것을 알 수 있습니다.

* 참고한 책 : 4장 | 알기 쉬운 알고리즘 | 양성봉 | 생능출판사

** 알고리즘은 위의 책에 있는 알고리즘을 사용했기 때문에 책이 있으시면 더 쉽게 이해할 수 있습니다.

최근접점쌍 문제는 간단하게 말해, 주어진 점들 중 가장 가까운 두 점을 찾는 문제입니다.

예를 들어 (8, 8), (10, 15), (5, 15), (20, 3), (9, 7), (15, 9), (8, 15), (20, 14), (17, 13), (16, 11), (7, 12), (10, 10), (1, 19), (30, 9), (22, 4), (6, 1) 의 점들이 있을때 알고리즘을 이용하여 최근접점쌍을 찾는 과정은 다음과 같습니다.

먼저, 점들의 x 좌표와 y 좌표를 이용해 정렬합니다. 분할해서 문제를 해결하기 때문입니다.

점들을 정렬하고 나면 다음 알고리즘을 수행합니다.

분할 할 때 남아있는 점이 3개 미만일 때까지 분할하기 때문에 나누다보면 위의 그림처럼 각 부분에서 점이 2개씩 존재하게 되는 것 입니다.

분할한 부분의 점의 개수가 3개 미만이 될 경우, 각 점들 사이의 거리를 계산합니다. 점들의 거리 계산은 보통 수학에서 사용하는 점들 사이의 거리 식을 이용합니다. 거리를 구했다면 가장 가까운 점들의 쌍을 반환합니다.

또한 중간영역 최근접점의 상 구하기라는 부분에서는 (첫번째 그림 상에서) SL11 영역의 가장 오른쪽 점과 SL12영역의 가장 왼쪽 점의 거리를 비교했을 때 더 짧은 거리가 나올 수 있기 때문에 수행하는 과정입니다. 분할해서 다른 영역이 되어버렸지만 점의 거리가 더 짧을 수도 있습니다.

위의 표는 SL1의 점들의 거리비교를 한 것입니다. d는 중간 영역 최근접 점의 쌍을 구하기 전 각 세부영역의 점들의 거리를 계산해서 나온 가장 작은 거리의 수입니다. 현재 가장 가까운 점들의 거리가 5이므로 x좌표의 값을 비교하여 차이가 5이상이면 계산할 필요도 없으므로(어차피 더 거리가 크게 나옴) 제외하기 위해서 사용합니다. 표에서 SL11 영역의 가장 오른쪽 점과 SL12영역의 가장 왼쪽 점을 기준으로 x좌표가 5이상 차이나면 계산에서 제외하지만 5이상 차이나는 점이 없으므로 모든 점들과 거리를 계산해봐야 합니다. 

그래서 나온 SL1영역에서의 최근접 점의 쌍은 (5,15), (7,12)이며 거리는 3입니다. 다른 영역도 같은 방법으로 구하면 됩니다.

* 참고한 책 : 3장 | 알기 쉬운 알고리즘 | 양성봉 | 생능출판사

** 알고리즘은 위의 책에 있는 알고리즘을 사용했기 때문에 책이 있으시면 더 쉽게 이해할 수 있습니다.

***최근접점쌍 문제의 경우 순서쌍만 제시하기때문에 교수님이 과제로 내주신 문제(순서쌍)를 그대로 사용하였으며 그림 및 알고리즘 과정은 제가 작성하였습니다.

* 아래 문제 출처 : 3장 | 알기 쉬운 알고리즘 | 양성봉 | 생능출판사

** 알고리즘은 위의 책에 있는 알고리즘을 사용했기 때문에 책이 있으시면 더 쉽게 이해할 수 있습니다.

주어진 배열이 아래 표와 같고 5번째로 작은 숫자를 찾을 때, 알고리즘을 적용하여 선택 문제를 푸는 과정은 다음과 같습니다.

+ 직관적으로 사람은 답이 5라는 것을 알 수 있습니다. 답을 기억한 상태에서 알고리즘을 적용하며 결과가 맞게 나왔는 지 확인해 보겠습니다. +

먼저 Selection(ARRAY, left, right, k)에서 k를 설정합니다. 여기서 k는 n번째로 작은 숫자를 찾는 문제에서 n과 동일합니다.

문제에 적용하면 Selection(ARRAY, 0, 8, 5)로 설정할 수 있습니다. 

1단계

먼저 피봇을 설정합니다. 알고리즘 상 피봇은 랜덤으로 설정되게 되어 있는데 보통 중간 위치를 설정하는 것이 덜 번거롭기 때문에 INDEX 4를 피봇으로 선정하겠습니다.

피봇을 선정하고 나면 피봇의 값을 제일 왼쪽의 INDEX로 옮깁니다.

그 다음 ARRAY에서 작은 값이 왼편에 올 수 있도록 서로 자리를 교환합니다.

9, 2를 서로 교환하고

피봇을 작은 수들의 제일 마지막 INDEX인 INDEX 3과 자리를 바꿉니다.

그러면 피봇을 기준으로 피봇보다 작은 값들은 왼쪽에 위치하게 됩니다.

그 다음, 알고리즘에 따라 S = ( p -1 ) - left + 1에서 S값을 구합니다.

p는 피봇의 INDEX, left는 가장 왼쪽의 INDEX입니다.

따라서 S = ( p -1 ) - left + 1 는 S = (3-1) - 0 + 1 이고 계산하면 3이 됩니다.

S는 피봇보다 작은 값들의 개수입니다.

이제 5번째로 작은 값을 찾기 위해 조건문으로 넘어갑니다.

[만약 k가 S보다 작거나 같다면 Selection(ARRAY, left, p-1, k)로 설정하라] 라는 내용의 조건문입니다.

k는 5, S는 3이므로 위의 조건문은 거짓입니다. 따라서 다음 조건문으로 넘어갑니다.

[만약 k == S+1이라면, 피봇 값을 반환하라] 라는 내용입니다. 참일 경우, 피봇 값이 k번째로 작은 값이라는 뜻인데 5= 4 이므로 거짓이 됩니다.

위의 조건문 둘 다 거짓인 경우 Selection을 다음과 같이 다시 설정해줍니다.

Selction(ARRAY, p+1, right, k-S-1), 문제에 적용하면 Selction(ARRAY, 4, 8, 1)이 됩니다. INDEX 4부터 8까지, 1번째로 작은 숫자를 찾으라는 뜻입니다.

2단계

마찬가지로 피봇을 설정해줍니다. 저는 INDEX 6을 피봇으로 선정하겠습니다.

과정은 1단계와 동일합니다. 피봇 값을 제일 왼쪽으로 옮기고 피봇 값보다 작은 수가 왼편에 오도록 자리를 바꿔줍니다. 

그 다음 피봇 값보다 작은 수가 왼편에 오도록 자리를 바꿔줍니다. 피봇 값을 피봇보다 작은 수들의 제일 오른쪽 편에 있는 INDEX 7과 바꿔주면 됩니다.

이제 다시 S값을 구합니다.

S = ( p -1 ) - left + 1에서 p는 7, k는 1입니다.

S = ( p -1 ) - left + 1 는 S = (7-1) - 4 + 1 이고 계산하면 3이 됩니다.

이제 1번째로 작은 값을 찾기 위해 조건문으로 넘어갑니다.

[만약 k가 S보다 작거나 같다면 Selection(ARRAY, left, p-1, k)로 설정하라] 라는 내용의 조건문입니다.

k는 1, S는 3이므로 위의 조건문은 참입니다. 따라서 Selection을 다음과 같이 설정합니다.

Selection(ARRAY, 4, 6, 1)이 되고 INDEX 4부터 6까지, 1번째로 작은 숫자를 찾으라는 뜻입니다.

3단계

마찬가지로 가운데 있는 INDEX 5를 피봇으로 선정하고, 5보다 작은 ARRAY값이 없기 때문에 값을 왼편으로 이동시키는 과정은 표현하지 않겠습니다. 알고리즘 상 실행은 됩니다.

이제 다시 S값을 구합니다.

S = ( p -1 ) - left + 1에서 p는 4, k는 1입니다.

S = ( p -1 ) - left + 1 는 S = (4-1) - 4 + 1 이고 계산하면 0이 됩니다.

이제 1번째로 작은 값을 찾기 위해 조건문으로 넘어갑니다.

[만약 k가 S보다 작거나 같다면 Selection(ARRAY, left, p-1, k)로 설정하라] 라는 내용의 조건문입니다.

k는 1이고 S는 0이므로 거짓입니다. 따라서 다음 조건문으로 넘어갑니다.

[만약 k == S+1이라면, 피봇 값을 반환하라] 라는 내용입니다. 1 = 0 + 1 이므로 참입니다. 즉, 피봇값이 찾던 값이라는 뜻입니다.

따라서 답은 5가 됩니다. 

가짜 동전 문제 설명

가짜 동전 찾기 문제는 n개의 동전 중에서 1개의 가짜 동전을 찾는 문제입니다.

가짜 동전은 진짜 동전과 무게가 더 가볍기 때문에 저울을 이용해 찾으려합니다.

먼저 n개의 동전을 반으로 나누어 양쪽 동전의 무게를 잽니다.

그러면 가짜 동전이 포함된 쪽이 더 가벼운 것을 찾아낼 수 있습니다.

이 과정을 반복하면 마지막에는 저울의 양 쪽에 각각 1개씩 남게될 테고 끝내 가짜 동전을 찾을 수 있습니다.

이러한 방법으로 이 문제를 해결하면 시간복잡도는 log2n이 걸립니다.

그렇다면 처음 n개의 동전이 둘로 나눌 수 없는 짝수개일 경우에는 어떻게 해야 할까요?

아니면 동전들을 나누다 보니 동전의 개수가 홀수개가 되어 완벽히 둘로 나눈 수 없을 때는 어떻게 해야 할까요?

가짜 동전  찾기 문제에서 만일 동전의 수가 홀수 개이거나 2로 나누다 보니 한쪽이 홀수개 다른 한쪽이 짝수개가 되는 경우를 처리하는 방안을 제시하라.

① 주어진 n개의 동전이 홀수일 때(2로 나누기 전)는 1개의 동전을 제외하고 2로 나누어 무게를 잰다. 운이 좋을 경우 가짜 동전을 1번 만에 찾을 수 있고 그렇지 않다고 하더라도 2로 나누어 무게를 잴 수 있다.

② 2로 나누다보니 한쪽이 홀수 개, 다른 한쪽이 짝수 개가 되는 경우에는 ①번과 동일하게 동전 1개를 제외하고 무게를 잰다. 예를 들어, 2로 나누어진 결과 동전의 개수가 15가 되었을 때 7개와 8개로 나눌 수 있는 데 이 때 동전 1개를 제외하고 무게를 잰 후, 양쪽의 무게가 같지 않다는 결과가 나왔을 때, 7개의 동전과 아까 제외했던 동전 1개가 남으므로 총 8개의 동전이 된다. 이를 또 2로 나누어 무게를 잴 수 있다.

문제 출처 : 1장 연습문제 15번 | 알기 쉬운 알고리즘 | 양성봉 | 생능출판사