데이터 과학 유망주의 매일 글쓰기 — 프로젝트 5–4
자주 나오는 알고리즘 패턴
# 알고리즘, # 패턴
오늘 한일:
어제는 코딩테스트에서 문제를 접했을 때, 어떻게 하면 효율적으로 해결할 수 있을지에 대해 정리해보았다. 문제 해결에 있어 전략적으로 접근하는 것이 중요하고, 더 철저히 계획할수록, 더 작게 문제를 나눌수록, 전체적인 문제 해결이 한 층 더 수월해진다는 것을 알았다.
그렇다면, 코딩테스트에서 자주 활용되는 알고리즘이 있지 않을까? 지금까지 배워온 다양한 기본적인 정렬 알고리즘, 예를 들어 삽입 정렬이나 선택 정렬, 또는 재귀와 분할정복 같은 개념들이 많은 문제에서 사용될 수 있지 않을까하는 생각을 해 보았다.
예상대로, 많은 알고리즘 및 데이터 구조관련 문제들이 비슷한 유형으로 분류될 수 있다고 한다. 따라서, 비슷한 기법으로 솔루션을 구현할 수 있을 것이라는 생각이 든다. 그렇다면, 우리가 알아두면 좋을 알고리즘 문제의 공통된 성질들은 어떤 것들이 있을까?
다수 포인터(Multiple Pointers)
알다시피, 리스트 같은 컬렉션 데이터를 순회할 때, 가장 낮은 인덱스 부터 높은 인덱스까지 포인터를 사용한다. 이는 주어진 데이터를 모두 조회해야할 때 해 볼 수 있는 가장 쉽고 직관적인 방법에는 틀림없다. 실제로, 상당수 정렬 문제는 이러한 방법으로 알고리즘을 구현할 수 있다. 그러나 다수의 아이템을 비교해야하는 문제가 주어질 경우, 특히 각각의 아이템이 갖는 위치 정보가 중요한 문제에서는, 하나의 포인터를 사용하여 배열을 순회하려면, 각 아이템을 모두 조회해야하기 때문에 시간복잡도는 제곱시간(O(n²))으로 늘어난다.
이러한 문제에서는 두 개 이상의 포인터를 사용하여, 시간복잡도를 선형시간(O(n))으로 줄일 수 있다. 대표적으로 2개의 포인터를 사용하거나, Sliding Window라는 도구를 활용할 수 있다.
2개의 포인터를 활용한다면, 배열을 양쪽 끝에서 시작해 안으로 들어오는 방향으로 순회를 할 수 있다. 또는, 배열의 중심에서 시작해 양쪽 끝으로 나가는 방향으로 순회를 할 수도 있고, 둘 다 한 방향에서 시작하여 반대 방향으로 나아가는 방법을 취할 수도 있다. 2개의 포인터는 컬렉션 데이터에서 가장 큰 값을 찾는데 적합하다.
2개의 포인터를 다룬다면, 서로 겹치지 않도록 순회 방식을 명확하게 해 주는 것이 좋다.
# Two Pointer예제
# 배열의 합이 "0"인 쌍을 리턴하는 프로그램def sumZero(arr):
left = 0 # 하나의 포인터는 인덱스 0부터 시작
right = len(arr) - 1 # 다른 포인터는 마지막 인덱스 부터 시작
while left < right: # 두 번째 인덱스보다, 첫 인덱스가 같거나 크면 종료
sum = arr[left] + arr[right] # 각 포인터의 아이템을 더하기
if sum == 0: # 합이 0 이면 그대로 아이템 쌍을 리턴
return [arr[left], arr[right]]
elif sum > 0: # 합이 0보다 크면 두 번째 인덱스를 왼쪽으로 이동
right -= 1
else:
left += 1 @ 합이 0보다 작으면 첫 번째 인덱스를 오른쪽으로 이동
return sum, [arr[left], arr[right]] # 반복문 종료시 합과 쌍을 리턴# 코드 테스트
arr = [0,0,0,1,1,1,2,2,3,3,4]sumZero(arr)>> (1, [0, 0])
Sliding Window
가장 외곽에 두 개의 포인트를 위치 시키고 좁혀나가는 방법을 쓸 수도 있지만, 두 포인터를 평행으로 같이 이동시킬 수도 있다. Window의 sliding 정도는 문제에 따라 조금 다를 수 있으나, 컬렉션에서 두 개의 포인터가 같은 방향으로 평행하게 이동한다면 Sliding Window라고 할 수 있다. 원하는 결과를 얻을 수 있는 가장 좋은 시퀀스에 대한 snapshot을 찍어 나가는 개념이다.
# Sliding Window예제# 주어진 배열의 n 만큼의 크기에 존재하는 아이템들의 합을 리턴
def maxSubarraySum(array, n):
if len(array) < n: # 배열의 길이가 n보다 낮으면 n은 배열의 크기와 같다.
n = len(array)
sum = 0 # 합을 구하기 위한 변수 초기화
for i in range(n): # 배열에 존재하는 아이템들에서, 하나의 포인터를 처음부터 n만큼 움직이며 합을 구하기
sum = sum + array[i]
maxSum = sum # 최대합은 현 시점까지의 합
for i in range(len(array)): # 배열에 존재하는 아이템들에서, 두 번째 포인터를 처음부터 배열의 크기만큼 움직이며 합을 구하기
sum = sum + array[i] - array[i - n] # 배열의 크기가 n보다 크면, 현재 위치에서 n을 뺀 값의 위치에 있는 값을 빼주어, 합이 중복되지 않도록하기
if sum > maxSum: # 만약 합이 최대합보다 크면, 최대합을 합으로 설정한다.
maxSum = sum
return maxSum # n까지의 합을 리턴# 코드 테스트
arr = [0,0,0,1,1,1,2,2,3,3,4]maxSubarraySum(arr, 7) # 주어진 배열의 '7'번째 위치에 있는 값까지의 합을 리턴>> 5
분할정복(Divide and Conquer)
분할정복은 문제를 작은 단위로 나누어, 같은 연산을 반복적으로 수행해, 모든 단위 문제를 풀고, 그 결과값을 합치는 방법으로 전체 문제에 대한 솔루션을 도출하는 방법을 말한다. 따라서 반복적으로 문제를 분할하여 해결해 나가야한다. 보통 이를 위해 반복문보다는, 가장 작은 단위 문제로 내려갈 때까지, 함수를 스스로 호출하는 재귀(Recursion)방법을 많이 활용하는 편이다.
이진검색(Binary Search)나 병합정렬(Merge Sort)는 재귀를 활용하여 문제를 해결하는 가장 대표적인 예라고 볼 수 있다.
추가 팁: 상수 시간(O(1)) 복잡도를 가지는 Hash Table
Hash Table은 쓰이는 언어에따라, 값(Value), 객체(Object), Dictionary, Hash등등을 저장한다. 특정값의 빈도수에 대한 정보를 저장하기에 매우 유용한 데이터 구조이며, 중복값을 점검할 때도 매우 유용하다. Key를 통해 값에 접근하는 구조이기 때문에, 원하는 값에 접근하는 속도가 상수시간(O(1))으로 매우 빠르다.
앞으로 할일:
오늘은 알고리즘 문제에서 많이 활용될 수 있는 유용한 도구들에 대해 알아보았다. 실제로 두 개 이상의 평행한 포인터를 사용하는 Sliding Window기법은, 특히 정렬 알고리즘을 구현할 때 내가 많이 사용했다. 하지만, 양쪽 끝에서부터 안으로 좁혀나간다거나, 중간에서 양쪽 끝으로 퍼져나가는 방법은 아직 활용하지 못했지만, 앞으로 필요시에 유용하게 쓸 수 있겠다는 생각이들었다.
결국, 많은 문제들은 서로 공유하는 교집합의 패턴을 가지고있다. 그 패턴을 잘 잡아낸다면, 그 어떤 복잡한 문제도 풀 수 있을 것이라는 생각이들었다. 그러자면, 모든 문제를 작은 단위로 나누어, 그 문제들 사이에 어떠한 규칙이 존재하는지 파악하는 것이 매우 중요할 것 같다. 마치, 모든 물질이 일정한 분자의 패턴으로 이루어진 것처럼 말이다. 이 세상에 특정한 패턴이 없는 것들은 아마 없을지도 모른다는 생각이 들었다.
또한, 이 세상 그 어떤 문제들도 더 작은 부분으로 나뉘어 질 수 없는 문제는 없는 것 같다. 그렇게 생각하면 복잡한 문제들도 결국 쉬운 여러 문제들의 합이니까. 나도 이 세상 모든 물질도 무수히 많은 작은 분자들로 이루어졌으니까. 그렇게 생각하면, 그렇게 복잡하거나 풀 수 없는 문제는 없을지도 모른다.
누가 그랬다. “당신이 풀 수 없는 문제는 당신 삶에 주어지지 않는다.”고. 지금 풀리지 않을 것만 같은 내 미래도 언젠가는 답이 보이게 될 것이라 믿는다. 아직 그게 분명히 보이지는 않지만, 어쨌든 희미하게나마 불 빛이 느껴진다고 생각한다. 그 불빛을 잘 따라서, 결국에는 동굴을 빠져나와, 나도 자유로운 세상에서 나의 가치를 실현하고 싶다. 그러기 위해 지금 노력하는 것이고, 반 이상이나 이 과정을 헤쳐나왔다. 나머지 절반의 과정을 극복해 나갈수록, 출구에 가까울 것이라 믿어 의심치 않는다. 물론, 또 새로운 세상에서 나는 더 큰 도전을 맞이할 수 있지만, 지금까지 유지해온 나의 삶의 태도를 지켜나간다면, 내가 노력해도 풀 수 없는 문제는 없지 않을까 생각한다. 모든 사람들이 자신의 삶의 문제를 하나씩, 천천히 해결해 나갈 수 있기를 바란다. 이 세상에서 가장 가치있는 사람들은 스스로 문제를 해결할 수 있는 사람이라는 생각이 자주 드는 요즘이다.
내일도 내 인생의 작지만 중요한 문제를 또하나 해쳐나갈 수 있기를.
참조:
(1) https://dev.to/moresaltmorelemon/algorithm-problem-solving-strategies-21cp
