안녕하세요
최근에 "생각하는 프로그래밍" 이라는 책을 읽게되었는데요
해당책을 읽으며 생각했던 내용들을 조금씩 정리해 보려고 합니다.
개요
챕터의 제목은 "아하! 알고리즘" 인데요, 이것은 특정 알고리즘을 명칭하는 것이 아니라,
문제를 해결하는 방법을 해결하는 알고리즘을 떠올리는 순간인 아하 모먼트를 의미합니다.
그리고 해당 순간은 깊은 연구가 아닌 문제에 대해 고민하는 개발자라면 누구든 해당 순간이 찾아올 수 있다고 합니다.
이번챕터는 어려운 문제를 간단하게 바라볼 수 있는 방법을 제시해줄 것 같습니다.
해당 칼럼에서는 세가지 문제를 던집니다.
해당 문제를 하나하나씩 살펴보겠습니다.
문제1: 빠진 수 찾기
최대 40억개의 32비트 정수가 랜덤한 순서로 들어있는 순차파일이 있을 때,
해당 파일에 포함되지 않은 임의의 32비트 정수를 찾아라.
우선 해당 문제에는 두가지 하위 문제가 있습니다.
※순차파일: 파일의 데이터가 물리적으로 연속된 파일을 의미합니다.
1-1: 빠진수가 존재할 수 있는가?
32비트는 생각보다 익숙한 수입니다. 바로 C언어의 정수 자료범위로
-2,147,483,648 ~ 2,147,483,647
의 범위를 가집니다.
약 42억개가 존재할 수 있음으로 파일의 정수들이 모두 서로다른 수라고 할지라도 빠진 수는 반드시 존재합니다.
1-2: 메모리가 넉넉하지 않다면 어떻게 해당문제를 해결할 수 있는가?
예를들어 비트맵을 이용하여 해당 범위의 수를 체크하는 경우
정수가 42억개 임으로 약 500MB정도의 공간이 필요하게 됩니다.
책에서는 몇백 키로바이트 정도의 공간이 있는 경우를 가정합니다.
정답은 이진탐색을 사용하는 방법입니다.
예를들어 최솟값이 1이고 최댓값이 10인 범위가 주어져 있습니다.
해당 범위의 중간지점을 기준으로 범위를 반으로 나누었을 때, 각각의 범위는 전체범위의 절반만큼의 범위를 가지게 됩니다.
만약 3이빠져있는 경우, 아래쪽 범위의 총 원소개수가 감소합니다.
결과적으로 아래쪽 범위 요소수와 위쪽 요소수의 차이가 발생하게 되고 그 수가 적은 쪽에 빠진 수가 있음을 알 수 있습니다.
(물론, 정수의 수가 홀수냐 짝수냐, 빠진수의 개수에 따라서 크고 작음에 따른 판단 기준이 달라질 수 있습니다.)
따라서 탐색해야할 영역이 절반으로 감소합니다.
해당 과정을 보면 한가지 의문점이 들었습니다. 중복된 수가 존재하야도 해당 접근 방식은 유효한가?
1, 1, 1, 4, 5, 6
1-3: 3개
4-6: 3개
이 경우 개수의 차이가 발생하지 않음으로 양쪽 범위를 모두 한번더 탐색해야 합니다.
1, 1, 1의 경우
1-2: 2개
3: 0개
3이 빠진 수 임을 알 수 있습니다.
해결해봅시다.
해당 인사이트를 가지고 문제를 해결해보겠습니다. 여기 부터는 단순히 제생각으로 추후에 수정될 수 있습니다.
현재 파일에 있는 정수들중 최대값과 최솟값을 도출합니다.
해당 값들을 사용하여 범위를 만들고 범위의 중간지점을 찾아 해당 값보다 큰 수와 작은 수들을 카운팅합니다.
카운팅 차이를 통해 탐색의 범위가 절반으로 재귀적으로 감소합니다.
따라서 빠진 수를 찾을 수 있게되며
시행은 logN 이고 각 시행마다 N번의 탐색이 이뤄짐으로 시간복잡도로 표현하면 O(logN * N)의 복잡도를 가지게됩니다.
※ 순차파일에 접근하긴 하지만 메모리에 접근하는 것이 아닌 디스크 I/O를 통해서 접근 함으로 메모리보다 훨씬 느린 접근이 이뤄지긴 합니다.
하지만 HDD기준 순차접근을 할때 150MB/s의 속도를 가지게되고 16GB를 읽어들일 때 약 109초가 소비된다고 합니다.
그리고 메모리는 범위를 표현하는 수인 최댓값 최솟값 중간지점 정도만 사용되며 거의 사용되지 않게 됩니다.
문제2: N개의 원소를 가지는 1차원 벡터를 i만큼 회전 시키기
벡터를 회전시킨다는 것은 다음을 의미합니다.
a b c d e를 3만큼 회전한다면
d e a b c
이렇게 동작합니다.
책에서는 i만큼 회전을 하는 경우 상대적으로 비효율적인 2가지 방법을 소개합니다.
첫번째 방법은 0..<i 위치의 요소들을 별도의 공간에 따로 저장하고
남은 배열을 앞으로 당깁니다.
복잡도는 O(N)이 지만 i만큼의 공간이 필요하게 됨으로 저장공간을 비효율적으로 사용합니다.
두번째 방법은 가장 앞자리를 T라는 공간에 저장하고 남은 배열을 앞으로 한칸씩 당깁니다.
그 후 T에 저장된 요소를 벡터의 마지막에 기입합니다.
이 방법은 저장공간에 낭비가 적지만, 해당 시행을 i번 반복해야 함으로, 시간 복잡도가 비효율적입니다.
해결법1: 문제를 분할하고 정복하기
이번 문제에서도 책에서는 분할을 강조합니다.
0..<i 까지의 벡터를 A, 그 이후에 벡터를 B라고 해봅시다.
A B
문제는 A와 B의 위치를 바꾸는 것이라고 말할 수 있습니다.
B A
해당 과정을 가능하게 하기 위해 문제는 다음과 같은 방법을 제시합니다.
A 벡터의 길이가 B보다 작다는 가정하에 B 벡터를 B1 B2로 나뉩니다.
여기서 중요한점은 B2의 길이와 A의 길이를 일치시킵니다.
A B1 B2
A의 위치와 B2의 위치를 뒤바꿉니다.
B2 B1 A
문제의 결과가 B A 라는 점에서 A영역은 확정된 위치를 가지게 되고
해결해야 하는 문제의 범위는 B2, B1의 위치를 바꾸는 것으로 좁혀지게 됩니다.
여기서는 재귀적 접근이 가능해지며, 복잡도와 저장공간 측면에서 모두 낭비가 거의 발생하지 않게 됩니다.
해결법2: 벡터를 뒤집기
앞선 해결법에 이어서 책에서는 또다른 해결법을 제시합니다.
A B의 위치를 바꾸는 것이 목표일 때 특정 벡터를 뒤집은(reverse) 것에 r을 붙이겠습니다.
Ar Br
(Ar Br)r
B A
특정 벡터를 뒤집는 동작은 벡터의 길이에 비례하는 복잡도를 가짐으로 시간복잡도, 저장공간에서 모두 낭비가 발생하지 않습니다.
그리고 짧고 간단하여 실수가 잘 발생하지 않는 접근법입니다.
텍스트 에디터의 줄 위치를 변경하는데 해당 방식이 사용된다고 합니다.
책에서는 연결리스트를 사용해서 해당 기능을 구현할 경우 버그가 많이 생긴다고 합니다.
실수 발생이 적은 접근법 역시 중요하다고 생각합니다.
문제3: 전철어구 찾기
전철어구라는 말을 처음 듣는데요, 같은 문자로 이루어졌지만 문자의 배치가 다른 단어를 만드는 것을 의미합니다.
사전에 있는 단어들에서 특정 전철어구 집합을 찾는다고 했을 때, 일일히 비교하는 경우 어마어마한 시간이 걸리게 됩니다.
책에서는 해당 문제역시 문제를 분할하려고 합니다.
1. 특정 단어가 어떤 전철어구 집합에 속하는지 표기하는 법
2. 표기를 따라 전철어구 집합을 구성하는 것
1번에 집중하여 문제점을 해석하다 보면 단어란 문자의 나열이고 문자는 순서를 가집니다.
따라서 abcde나 edcba를 정렬하면 같은 결과를 얻을 수 있습니다.
1번은 간단하게 해결되었습니다.
2번의 사전을 순회하면 특정 표기의 단어들을 수집하면 되겠지요.
해당 칼럼의 의의
포스팅으로 다루지 않았지만, "생각하는 프로그래밍" 챕터1에서는 해결하려는 문제가 정확히 무엇인지 인지하는 것을 주제로 합니다.
이번 칼럼은 문제를 정의하였을 때 어떻게 문제를 해결할 것인지?에 대해 제시합니다.
어려운 문제를 어떻게 간단하게 접근할 것인가?
제를 해결할 수 있는 쉬운문제로 잘게 쪼개나가는 예시를 앞의 세문제를 통해 확인할 수 있었습니다.
책에서는 어려운 문제 지나치게 오랜시간 빠져있는 것은 당연한 말이지만 안좋은 것이라고 합니다.
적절한 시점에 도출한 해법을 구현해 내는 것이 중요하며, 훌륭한 능력이라고 생각합니다.
해당 능력은 문제의 해법을 찾고 구현하는 경험치에서 나온다고 책에서는 말합니다.
개인적 감상
해결해야하는 문제를 잘 정의하였다면, 해당 문제를 해결할 수 있는 방법을 생각해야 한다.
해결법은 엄청난 발상이나 연구가 아닌 문제를 작은 영역으로 분할하는 것이 효율적이다.
문제를 분할할 줄 아는 능력은 훌륭하며, 경험에서 나온다.
그러니 앞으로는 의식적으로 분할을 통해 문제를 바라보는 습관을 들여보자.