코드를 쓰기 전에, 먼저 계산하던 것들

예전에 C를 공부할 때는 포인터나 배열이 재미있었다. 값 하나가 어디에 들어가 있는지, 배열을 크게 잡아도 되는지, 재귀를 한 번 더 돌리면 얼마나 느려질지 같은 걸 계속 보게 됐다.

시간이 꽤 지나서 당시 생각을 전부 정확하게 기억하지는 못한다. 그래서 예전에 풀었던 백준 코드를 다시 열어 봤다. 코드를 보니 그때 제가 문제를 풀기 전에 어떤 것을 먼저 계산했는지는 어느 정도 보였다.

문제를 받으면 바로 구현부터 하기보다는 대략 이런 순서로 봤던 것 같다.

입력 크기가 얼마지?
이 배열을 잡으면 메모리가 얼마나 들지?
반복문은 최대 몇 번 돌지?
이미 계산한 것을 또 계산하고 있지는 않나?
전체 상태를 들고 있어야 하나, 지금 필요한 것만 남겨도 되나?

지금은 프레임워크와 AI가 많은 구현을 대신해 준다. 그래도 이 질문들은 아직 남아 있다.

500 × 500 배열을 두 개 잡아도 될까

내리막 길을 풀 때는 지도와 DP 배열을 이렇게 잡았다.

int map[500][500];
int dp[500][500];

int가 4바이트라고 보면 배열 하나는 약 1MB, 두 개를 합쳐도 약 2MB다. 입력의 최대 크기를 보고 이 정도는 메모리에 올려도 된다고 판단했던 것 같다. 큰 2차원 배열을 함수 안이 아니라 전역으로 둔 것도, 재귀 호출이 이어지는 동안 스택을 불필요하게 크게 쓰지 않으려는 선택으로 볼 수 있다.

여기서 더 중요한 건 dp에 어떤 값을 남길지 정한 부분이다.

if (dp[y][x] != -1)
    return dp[y][x];

dp[y][x] = 0;

-1은 아직 계산하지 않은 칸이고, 0 이상은 이미 계산을 끝낸 경로 수다. 처음에는 모든 길을 따라가 보게 되지만, 한 번 도착한 칸의 결과는 다음 호출에서 다시 계산하지 않는다.

당시에는 시간 초과를 피하려고 썼을 것이다. 지금 다시 보면 이건 결과를 저장하는 것만이 아니라, 계산 전 상태와 계산 후 상태를 구분하는 약속을 만든 일이다. 지금도 캐시를 붙이거나 비동기 상태를 다룰 때 비슷한 질문을 한다. 아직 없는 값인지, 계산 중인 값인지, 이미 쓸 수 있는 값인지 먼저 구분해야 한다.

문제: 1520 내리막 길 · 코드: GitHub에서 보기

전부 저장하지 않아도 되는 결과가 있다

로봇 조종하기는 한 행을 지날 때 왼쪽에서 온 경우와 오른쪽에서 온 경우를 모두 봐야 하는 문제였다. 처음에는 2차원 DP 테이블을 전부 만들어야 할 것처럼 보인다.

그런데 코드에는 결과용 배열이 이렇게만 남아 있다.

int dp[1000];
int rl[1000][2];

dp[1000][1000]을 만들면 결과만 약 4MB가 된다. 반면 이 코드는 이전 행의 결과를 담는 dp와, 현재 행을 양방향으로 훑는 rl만 둔다. 각각 약 4KB와 8KB 정도다.

물론 지도 자체는 map[1000][1000]에 그대로 저장했다. 지금 보면 입력도 한 행씩 받으며 더 줄일 수 있었을지도 모른다. 그래도 DP 결과까지 같은 크기로 한 번 더 복사해 두지는 않았다.

여기에는 이런 생각이 들어 있다.

다음 행을 계산할 때, 정말 모든 이전 행의 모든 과정이 필요한가? 아니면 최종 결과 한 줄이면 되는가?

완벽하게 적게 쓰는 것보다 먼저, 무엇이 다음 단계까지 살아 있어야 하는지를 구분한 것이다. 지금 화면 상태를 설계할 때도 마찬가지다. 모든 응답과 중간 상태를 전역에 넣기보다, 다음 화면에 필요한 값이 무엇인지부터 본다.

문제: 2169 로봇 조종하기 · 코드: GitHub에서 보기

숫자의 크기가 아니라, 내가 확인할 구간의 크기

제곱 ㄴㄴ 수는 입력 숫자 자체가 커서 처음에는 배열을 어떻게 잡아야 할지부터 생각하게 되는 문제다. 모든 수를 처음부터 끝까지 저장하는 대신, 필요한 구간만 따로 표시했다.

check[i - a] = 1;

a부터 b까지의 수를 0부터 b - a까지의 배열 인덱스로 옮긴 것이다. 숫자의 절댓값이 아무리 커도, 내가 확인해야 할 구간 길이만큼만 check 배열을 쓰면 된다.

이 코드도 지금 다시 보면 prime과 check 배열을 둘 다 크게 잡고 있다. 무조건 최소 메모리를 쓴 코드는 아니다. 하지만 “큰 숫자 전체를 배열로 만들면 안 된다”는 문제는 구간의 좌표를 바꾸는 방식으로 해결했다.

이런 생각은 알고리즘 문제에서만 쓰이지 않는다. 긴 목록을 한 번에 다 받아오지 않고 페이지 단위로 자르거나, 특정 기간의 데이터만 조회하거나, 화면에 필요한 정보만 API로 요청할 때도 결국 같은 질문을 한다.

데이터 전체가 아니라, 지금 내가 다뤄야 하는 범위는 어디까지인가?

문제: 1016 제곱 ㄴㄴ 수 · 코드: GitHub에서 보기

C를 공부하며 남은 것은 포인터 하나가 아니었다

예전 코드에는 malloc과 free를 직접 다루는 구현이 많이 남아 있지는 않다. 대신 전역 배열을 어떻게 잡을지, 인덱스를 어디서부터 셀지, 재귀가 끝난 뒤 어떤 상태를 남길지 같은 선택이 그대로 남아 있다.

그래서 제가 C를 공부하며 얻은 것은 포인터 문법 하나가 아니었던 것 같다. 눈에 보이지 않는 자료의 크기와 위치, 계산이 반복되는 횟수, 그리고 상태가 살아 있어야 하는 범위를 먼저 생각하는 습관이었다.

요즘은 구현 속도가 훨씬 빨라졌다. AI에게 기능을 부탁하고, 라이브러리 하나를 설치하면 많은 것이 바로 동작한다. 그래도 저는 새로운 도구를 만날 때 한 번은 다시 묻는다.

이 값은 어디에 남는가?
이 작업은 몇 번 반복되는가?
지금 전부 들고 있어야 하는가?

편리한 도구를 잘 쓰는 것과, 그 아래에서 일어나는 일을 아는 것은 서로 반대가 아니다. 오히려 구조를 어느 정도 알고 있어야 필요한 도구를 더 정확하게 고를 수 있다. 예전 C 코드들을 다시 보며, 지금도 제가 붙잡고 있는 기초가 무엇인지 조금 더 분명하게 알게 됐다.