1. 문제 기술

1-1. 문제 설명

리스트가 주어질 때 리스트에서 k 번째로 작은 값을 반환하는 함수 selection()을 구현하여야 한다. 함수 selection의 인자로는 2가지가 주어지는데 하나는 숫자들의 리스트이고 또 다른 하나는 k이다. 또 selection()은 함수 partition()을 불러야 한다. 함수 partition()은 0번째 원소를 pivot으로 정하고 그 왼편에는 더 작은 값들을, 오른 편에는 더 큰 값들이 오도록 원소의 위치를 변경하는 함수이며, 원소들의 위치가 바뀐 후 pivot의 index를 반환한다.

1-2. 해결 방법

자세한 구현 방법은 2-1. 핵심 코드 리뷰에 기술하도록 하고 개략적으로 설명하겠다. 먼저 partition()을 구현해야 한다. partition() 함수를 구현하였다면 리스트 안에 원소들이 pivot을 기준으로 왼쪽에는 더 작은 값들을, 오른쪽에는 더 큰 값들을 오도록 위치를 변경하였을 것이고 pivot의 index를 반환하였을 것이다. 해당 값을 이용하여 k 값과 비교하며 k 값이 왼쪽에 있는지 아니면 오른쪽에 있는지 또 아니면 k 값과 동일한지(실제로는 k-1이다. 추후에 기술 예정) 비교한다. 만약 왼쪽 또는 오른쪽에 있다면 재귀 호출을 통해서 selection()으로 다시 들어간다. 만약 내가 찾는 값이라면 해당 값을 반환해 주고 종료한다.

2. 세부 구현사항

2-1. 핵심 코드 리뷰

• 함수 partition()은 0번째 원소를 pivot으로 정하고 그 왼편에는 더 작은 값들을, 오른편에는 더 큰 값들이 오도록 원소의 위치를 변경하는 함수이며, 원소들의 위치가 바뀐 후 pivot의 index를 반환한다.

처음부터 올라가는 변수와 마지막으로부터 내려오는 변수가 필요하다. 그래서 UP과 DOWN 변수를 만들어주었다. 그리고 partition() 함수는 0번째 원소를 pivot으로 정하기 때문에 UP 변수는 1로 지정하여 주고 DOWN 변수는 0부터 시작했기 때문에 리스트의 크기 –1로 지정하여 준다. 다음 과정부터는 이해를 돕기 위해 아래 사진을 이용하여 설명하겠다.

사진과 같이 인덱스가 1인 3은 pivot 값인 8보다 작으니 8번째 줄의 while 문에서 반복하게 된다. 그래서 UP 값이 1 증가하게 된다. 인덱스가 2인 11은 pivot 값인 8보다 크니 10번째 줄로 가게 된다. 그리고 인덱스가 11인 14는 pivot 값보다 크니 10번째 while 문에서 반복하게 된다. 그래서 DOWN이 1 감소하게 되고 인덱스가 10인 7은 pivot 값보다 작으니 12번째 줄로 내려오게 된다. 12번째 줄의 조건인 UP>=DOWN은 성립하지 않으므로 넘어가게 되고 14번째 줄을 이용하여 그림과 같이 인덱스가 2인 값과 인덱스가 10인 값이 swap 하게 된다. 그리고 UP 값과 DOWN 값을 움직여준다. 해당 과정을 7번째 줄의 while 문으로 반복하게 되면 아래 그림과 같은 결과가 나오게 된다.

그림에서 현재 UP은 5에 있을 것이고 DOWN은 4에 있을 것이다. 이때 12번째 조건문에 걸리게 된다. 그래서 7번째 줄의 while 문을 탈출하게 되고 17번째 줄을 통해서 pivot 값과 DOWN의 값이 아래 그림과 같이 swap 하게 된다.

그리고 문제에서 제시한 것과 같이 현재 pivot값의 인덱스인 DOWN을 반환한다.

• 함수 selection()은 함수 partition()을 불러야 한다.

selection()은 list의 한 원소를 랜덤으로 선택하게 한다. 그리고 partition()은 인덱스가 0인 값을 pivot으로 사용하기 때문에 partition()의 사용을 위해 랜덤으로 선택한 값과 인덱스가 0인 값을 swap 해준다.

• 재귀 호출 (recursive call)을 하는 경우 selection()을 다시 부른다. 여기서 구현하는 selection()은 강의에서 다룬 selection()과 인자가 다르다는 점을 주목해야 한다. 이 함수는 전체 배열에서 selection()이 담당할 시작 위치와 종료 위치를 인자로 주는 대신 리스트 자체를 주어야 한다.

해당 코드에서 중요한 점은 비교할 때 사용하는 k 값과 selection()을 재귀 호출할 때 사용하는 인자들이다. 먼저 29번째 줄은 줄에서 pivot 값보다 작은 그룹에 찾는 값이 있을 때이다. k가 아닌 k-1을 사용한 이유는 현재 배열로 데이터를 다루고 있으므로 0부터 시작한다. 하지만 인자로 받은 값은 1부터 시작하는 k 번째 값이기 때문이다. 만약 해당 조건이 부합할 경우 작은 그룹을 인자로 넘기는 selection()을 호출해야 한다. 이때 파이썬의 슬라이스 기능을 이용하였다. random_index를 사용한 이유는 범위를 지정하는 방법이 range랑 같기 때문이다. 그래서 random_index의 값보다 이전 값으로 슬라이싱된다. 그리고 k 값은 왼쪽 그룹이기 때문에 변함없이 k 값이다.
그다음으로 31번째 줄은 찾는 값일 때이다. 위에서 설명했던 것처럼 k 값이 아닌 k-1과 비교하여야 한다. 만약 해당 조건이 부합한다면 k 번째 작은 값을 찾은 것이므로 해당 값을 반환한다.

2-2. 구현하기 어려웠던 코드

partition()의 구현은 퀵 정렬에서 해보았기 때문에 쉽게 하였다. 하지만 selection()의 구현이 어려웠다. selection()에서 교수님께서 강조하신 큰 그룹에서 찾기 위해 재귀 호출로 넘겨줄 때 사용하는 인자들을 지정하는 것에서 시간을 소요한 것 같다. 하지만 수업을 열심히 들었기 때문에 혼자 힘으로 해결할 수 있었다.

2-3. 사용한 자료구조, 알고리즘

• 배열

위에서 본 것과 같이 함수를 구현하기 위해서는 데이터를 저장해야 한다. 데이터를 저장하는 자료구조로 배열을 선정하였다.
배열은 연속된 메모리 공간에 순차적으로 저장된 데이터 모음이다. 배열을 선정한 이유는 첫 번째로는 구현하기 쉽다는 이유이다. selection()을 구현하면서 많은 데이터 이동을 처리해야 한다. 그래서 최대한 오류가 적게 발생하는 배열을 이용하여 구현하고자 하였다. 두 번째로는 구현해야 할 프로그램은 데이터의 이동만 발생하여 데이터의 크기가 정해져 있다. 그래서 데이터의 추가적인 삽입이 필요가 없어 데이터의 크기를 바꿀 일이 없다. 그래서 다른 자료구조를 이용하지 않아도 되고 배열이 효율적이라고 판단했다. 세 번째로는 index를 이용하여 손쉽게 데이터에 접근할 수 있어 빠르게 데이터 간의 이동이 가능하기 때문이다.

• 이진 탐색

이진 탐색이란 데이터가 정렬돼 있는 배열에서 특정한 값을 찾아내는 알고리즘이다. 배열의 중간에 있는 임의의 값을 선택하여 찾고자 하는 값 X와 비교한다. X가 중간 값보다 작으면 중간 값을 기준으로 좌측의 데이터들을 대상으로, X가 중간값보다 크면 배열의 우측을 대상으로 다시 탐색한다. 해당 문제에서 정렬된 입력의 중간에 있는 숫자와 찾고자 하는 숫자를 비교함으로써, 입력을 1/2로 나는 두 부분 중에서 한 부분만을 검색한다는 점이 이진 탐색이 사용되었다.

• 퀵 정렬

퀵 정렬을 수행하는 과정에서 선택한 pivot을 기준으로 왼쪽, 오른쪽을 나누는데 해당 문제에서도 입력이 정렬되어 있지 않으므로, 선택한 pivot을 기준으로 왼쪽, 오른쪽을 나눈다는 점이 퀵 정렬과 비슷하다. 해당 과정에 대한 자세한 설명은 위에 2-1. 핵심코드 리뷰에 기술하였으므로 생략하겠다.

3. 체크 포인트

• 프로그램 테스트

• print(partition(list1))을 하였으므로 인덱스가 0인 값 2의 위치를 반환하여야 한다. 현재 요소들은 1, 2, 3, 4로 이루어져 있으므로 1의 위치에 2가 들어가면 맞다. 즉 1을 출력해야 한다.

• print(list1)을 하였으므로 위에서 2를 기준으로 작은 값은 왼쪽으로 갈 것이고 큰 값은 오른쪽으로 갈 것이다. 여기서 4, 3의 값이 정렬이 되지 않은 이유는 partition은 정렬을 해주지는 않기 때문이다. 해당 과정은 2-1. 핵심코드 리뷰에서 자세히 설명하였으므로 생략하겠다.

• print(selection(list1,2))을 하였으므로 list1에서 2번째로 작은 수를 출력하여야 한다. list1의 요소로는 1, 2, 3, 4가 있으므로 2번째로 작은 수는 2이다. 즉 2를 출력해야 한다.

3-1. 길이가 10개인 리스트를 만들고 3번째로 작은 원소를 출력하도록 selection() 함수를 호출하는 코드를 작성하고 그 실행 스크린샷을 포함하시오.

• print(selection(list1,3))을 하였으므로 list1에서 3번째로 작은 수를 출력하여야 한다. list1의 요소에서 2번째로 작은 수는 3이다. 즉 3를 출력해야 한다.

3-2. 랜덤 넘버 생성 함수를 이용하여 길이가 100개인 리스트를 만들고 selection() 함수를 이용하여 10번째로 작은 원소를 출력하시오. 그 실행 스크린샷을 포함하시오.

• random.randint를 이용하여 0에서 100까지 랜덤으로 선택하고 100번 반복한다. 그리고 해당 값들을 리스트에 저장해 준다.

• print(song)을 통해 실행이 잘 된 모습이다.

• print(selection(song, 10))을 하였으므로 song에서 10번째로 작은 수를 출력하여야 한다. song의 요소에서 10번째로 작은 수는 11이다. 즉 11을 출력해야 한다.

• song.sort()를 이용하여 10번째로 작은 수가 11이 맞는지 눈으로 확인할 수 있다.

4. 결론

• 전체 요약

리스트가 주어질 때 리스트에서 k 번째로 작은 값을 반환하는 함수 selection()을 구현하는 것에 성공하였고 함수 partition() 또한 0번째 원소를 pivot으로 정하고 그 왼편에는 더 작은 값들을, 오른 편에는 더 큰 값들이 오도록 원소의 위치를 변경하도록 하였고 원소들의 위치가 바뀐 후 pivot의 index를 반환하도록 하였다. 또한 여러 가지 테스트를 통해 구현한 코드가 잘 작동하는지 확인하였다.

• 성장 요소

수업을 들을 때는 정확히 이해하였다고 생각하였는데 막상 구현을 해보니 생각보단 어려웠다.
구현을 하면서 선택 문제 알고리즘에 대해서 완벽하게 이해하게 된 것 같다. 역시 알고리즘은 눈으로 보는 것보다는 직접 구현해 보는 것이 제일 좋다는 것을 다시 한번 깨닫게 되었다. 또한 partition()을 구현하면서 퀵 정렬에 대해서도 공부할 수 있어서 퀵 정렬 또한 완벽하게 이해한 것 같다. 평소 알고리즘 문제를 즐겨 풀고 있는데 수업을 듣기 이전에는 k 번째로 작은 숫자를 찾으라고 한다면 정렬을 이용하여 해결하였다. 하지만 수업과 과제를 통해 더 효율적인 방법을 알게 되어서 해당 알고리즘을 적용하여 여러 가지 문제에서 시간 복잡도를 줄일 수 있을 것 같다.