정해진 순서로 풀기

알고리즘은 '문제를 푸는 정해진 순서'예요. 단계를 밟으면 답이 나오고, 순서가 틀리면 결과도 틀려요. 같은 순서면 누가 해도 같은 답이 나와요. 그래서 컴퓨터에게 순서를 적어주면, 언제나 같은 일을 해줘요.

큰 문제는 한 입에 못 풀어요. 그래서 같은 꼴의 작은 문제로 쪼개고, 어떤 순서로 풀지 세우고, 조각 답을 다시 합쳐요. 이렇게 '쪼개고 - 순서 - 합치기'로 큰 문제를 다루는 게 바로 컴퓨팅 사고의 출발이에요. 어떤 어려운 문제를 만나도, 작게 나누면 손에 잡혀요.

정렬은 뒤섞인 것을 순서대로 줄 세우는 거예요. 옆끼리 견줘 큰 걸 뒤로 보내길 거듭하면, 줄이 차근차근 맞아요. 한 걸음마다 하나씩 제자리를 찾으니, 아무리 뒤죽박죽이어도 끝엔 줄이 맞아요. 정돈해두면 찾기도 쉬워져요.

한 칸씩 옆끼리 견주는 정렬은 줄이 길수록 비교가 폭증해 느려요. 더 똑똑한 길은 줄을 반으로 쪼개고, 각각을 정렬한 뒤, 정렬된 둘을 지퍼처럼 합치는 거예요. 반 쪼개기는 끝까지 가면 한 칸짜리만 남는데, 한 칸은 이미 정렬된 셈이죠. 합치기는 양쪽 맨 앞만 견주면 되니 빨라요. 반으로 쪼개니 층은 천천히 늘고, 각 층 비용은 줄 길이만큼이라, 전체는 한 칸씩보다 훨씬 빠르게 끝나요. 쪼개고 합치는 이 생각이 빠른 정렬의 비결이에요.

찾기는 원하는 걸 집어내는 거예요. 하나씩 보면 느리지만, 줄이 맞아 있으면 반씩 잘라가며 훨씬 빠르게 찾아요. 반씩 자르기는 정렬돼 있을 때만 통해요. 그래서 정렬과 찾기는 짝꿍이에요. 한 번 줄 세우면 두고두고 빨라져요.

빠르기는 초가 아니라 자라는 모양으로 재요. 입력 칸 n이 커질 때 일이 얼마나 늘까를 보는 거죠. log n은 거의 안 늘고, n은 칸만큼 늘고, n²은 폭발해요. 그리고 식이 복잡해도 가장 크게 자라는 항 하나만 남기면 돼요. 3n²+5n+9는 그냥 n²이에요. 이렇게 큰 항만 보는 표시가 빅오(O)예요. 그래서 큰 데이터에선 반씩 자르기가, 하나씩보다 비교가 안 될 만큼 빨라요.

알고리즘은 시간만 쓰는 게 아니라 자리(메모리)도 써요. 공간 복잡도는 답 말고 알고리즘이 추가로 쓰는 자리가 입력 크기에 따라 얼마나 늘어나는지를 재는 거예요. 시간을 잴 때 쓴 빅오의 렌즈를, 이번엔 자리에 그대로 갖다 대는 거죠. 추가 자리가 늘 한 칸이면 O(1), 입력만큼 같이 늘면 O(n)이에요. 그리고 시간과 공간은 자주 맞바꿔져요. 미리 표를 만들어 자리를 더 쓰면 빨라지고, 제자리에서 풀어 자리를 아끼면 느려지죠. 그래서 좋은 알고리즘을 고를 땐 빠르기뿐 아니라 자리값도 함께 봅니다.

큰 문제는 반으로 쪼개고, 각각 풀고, 다시 합쳐 정복해요. 핵심은 쪼갠 두 조각이 서로 겹치지 않는다는 거예요. 한쪽에서 한 일을 다른 쪽이 다시 안 해도 되니까요. 더 못 쪼갤 만큼 작아지면 바로 풀고, 풀린 조각들을 위로 합쳐 올리면 전체 답이 나와요. 이진 탐색도 병합 정렬도 다 이 틀이에요. 조각이 겹치지 않는 게 이 방식의 힘이에요.

재귀는 문제를 풀 때 자기 자신을 더 작은 입력으로 다시 부르는 방법이에요. 8강에서 큰 문제를 반으로 쪼개 정복했죠. 그 쪼개기가 바로 자기를 다시 부르는 일이에요. 그래서 분할정복과 재귀는 한 몸이에요. 꼭 필요한 건 멈추는 바닥이에요. 바닥이 없으면 끝없이 내려가요. 호출이 차곡차곡 쌓였다가, 바닥에 닿으면 거꾸로 올라오며 답이 하나로 합쳐져요. 자기 부름, 멈추는 바닥, 쌓였다 풀림. 이 셋이 재귀예요.

재귀는 종종 같은 작은 문제를 몇 번이고 다시 풀어요. 피보나치 트리만 봐도 fib(2)가 곳곳에 또 나오죠. 한 번 푼 답을 메모에 적어두고 다시 쓰면, 같은 걸 두 번 풀 일이 없어요. 이게 메모이제이션이에요. 거꾸로 맨 아래 작은 값부터 표를 채워 올라가도 같은 생각이고요. 그러면 지수적으로 느리던 것이 선형으로, 확 빨라져요. 분할정복은 쪼갠 조각이 겹치지 않아 적어둘 게 없었지만, 겹칠 때는 적어두는 한 수가 모든 걸 바꿔요.

탐욕 알고리즘은 매 순간 '지금 가장 좋아 보이는 것'을 고르는 방법이에요. 전체를 안 보고 한 걸음씩 고르니 빠르고 간단해요. 거스름돈을 큰 동전부터 내주거나, 일찍 끝나는 회의부터 잡는 것처럼, 어떤 문제에선 이게 진짜 정답이에요. 하지만 동전 종류가 이상하거나 길이 꼬여 있으면, 눈앞의 최선이 전체의 최선이 아니라 함정이 되기도 해요. 그래서 탐욕은 빠르고 자주 맞지만, 늘 맞는 건 아니에요.

어떤 풀이는 주사위를 굴려 무엇을 할지 무작위로 골라요. 퀵 정렬에서 늘 끝값을 기준으로 삼으면 나쁜 입력에 느려지지만, 기준을 무작위로 고르면 그런 함정을 피해 평균적으로 빨라져요. 또 정사각형 안에 점을 마구 찍어 원 안에 든 비율을 보면 넓이를 어림할 수 있어요. 많이 던질수록 어림이 정확해지죠. 무작위 풀이는 매번 똑같은 답을 장담하진 못하지만, 그 대신 빠르고 간단해요. 확실성을 조금 내주고 속도를 얻는 거예요.

그래프는 '점(대상)과 선(관계)으로 그린 그림'이에요. 점은 무엇이든 될 수 있고, 선은 둘 사이의 관계예요. 지하철, 친구망, 웹이 다 그래프죠. 트리는 그중에서 고리(순환)가 없는 특별한 경우예요. 그러니까 트리도 그래프의 한 종류예요. 세상을 점과 선으로 보면, 복잡해 보이던 것이 한눈에 들어와요.

한 점에서 출발해 그래프 전체를 도는 두 걸음이 있어요. 너비 우선은 가까운 곳부터 한 겹씩 물결처럼 퍼지고, 깊이 우선은 한 길을 끝까지 갔다가 막히면 되돌아와요. 둘 다 모든 점을 빠짐없이 밟지만 차례가 달라요. 그리고 선에 거리 차이가 없을 때는, 너비 우선이 밟는 차례가 곧 최단 거리예요.

선마다 거리가 다르면, 갈림길이 적은 길이 곧 가장 빠른 길은 아니에요. 그래서 가까운 순으로 세는 방법만으론 안 돼요. 출발점에서 가까운 점부터 거리를 하나씩 확정하고, 확정된 영역의 경계를 한 점씩 바깥으로 넓혀가요. 매 순간 아직 확정 안 된 점 중 가장 가까운 것을 고르는, 눈앞의 최선이에요. 경계가 다 퍼지면 모든 점까지의 가장 빠른 거리를 알게 돼요.

어떤 문제는 입력이 조금만 커져도 따져볼 경우의 수가 폭발해서, 빠른 풀이가 아직 알려져 있지 않아요. 외판원이 모든 도시를 한 번씩 도는 가장 짧은 길 같은 거예요. 그런데 이런 문제들은 답을 찾는 건 어려워도, 누가 준 답이 맞는지 확인은 쉬운 경우가 많아요. 그렇다면 확인이 빠른 문제는 푸는 것도 빠를까요? 이걸 P 대 NP 문제라고 부르는데, 아직 아무도 답을 몰라요. 풀리지 않은 큰 수수께끼예요.

완벽한 답을 빨리 못 구하는 어려운 문제라도, '충분히 좋은 답'은 빨리 구할 수 있을 때가 많아요. 어떤 방법은 한 발 더 나아가서, 그 답이 '최적의 몇 % 안'이라는 보장까지 줘요. 정확도를 조금 내주고 시간을 얻는 타협이죠. 시간을 더 쓰면 더 정확해지고, 덜 쓰면 덜 정확해지고. 어디서 멈출지는 우리가 골라요. 이게 이 영역 전체의 마무리예요. 모든 문제를 완벽하게 풀 수는 없지만, 빠른 방법으로, 똑똑한 전략으로, 한계를 알고 현명하게 타협하면, 어려운 문제 앞에서도 쓸 만한 답을 손에 쥘 수 있어요.