왜 암기를 하죠?
물론 필자는 수학 공부를 그렇게 열심히 하지는 않았으나, 중고등학교 수학에 비유해 보도록 하겠다. 이 글을 읽는 사람들 대부분이 과정을 따라가면 피타고라스 정리의 공식을 구할 수 있다. 그러나 한 번 도출된 공식이 있으면 그것을 암기해서 사용하지 삼각형부터 그리고 보지는 않는다.
여기서 보통 사람들은 정석적인 유클리드의 방식을 따라가서 피타고라스 정리를 외운다.
그런 방식으로 외우는 것이 정석이니까 다들 그렇게 하였다. 그러나 필자는 수학에 아주 약하기 때문에 직관적으로 이해할 수 있는 방식으로 바스카라의 정리(바스카라에 정리되기 전부터 인도에 널리 퍼져 있던 방식이고, 후일 중국에서도 구고현의 정리가 같은 방식으로 이 공식을 증명한다)를 사용했다.
그러나 거시적인 내용은 비슷한 시기의 서로 다른 대륙들의 정리 역시 같고, 결국 a^2 + b^2 == c^2으로 귀결된다.
이것과 정확히 동일하게 여기서는 아주 쉽게 단일 소스 최소 경로(SSSP) 문제를 위한 벨만포드 알고리즘을 구현하고 외우도록 하겠다.
구조화해서 외우자
삼항연산자는 죄가 없다
의외로 한 번 정도의 간단한 조건을 암기할 때 삼항연산자는 크게 도움이 되고, 블럭 형태로 잘 들여쓰기하면 가독성도 무난하다.
예를 들어서, a+b < c일 때 c = a+b를 한다고 해 보자. 여기서 자연어에 대응하면서 비교해 볼 것이다.
If문
한국어로 하면 아래와 같다. 만약 a + b 가 c보다 작다면 c는 a+b이다.
너무 말을 풀어 쓰니 조건 반영이 눈에 띄게 구조적이지 못하다.
삼항연산자
c = (a + b) < c ?
(a + b) : c ;
c는 ** a + b 보다 c가 작을 때 a + b, 아니면 c값 그대로이다.
말이 길어 보이지만 확실히 구조적으로 인지 가능하고, 부등호 조건에서 min일 때 a < b꼴로, max일 때 a > b 꼴로 쓰면 아래가 기억이 안 나도 a : b;로 끝내 버리면 된다. 즉 외워야 할 포인트가 반토막난다.
삼항연산자 + 매크로
#define MIN(x, y) (((x) < (y)) ? \
(x) : (y))
#define MAX(x, y) (((x) > (y)) ? \
(x) : (y))
c = MIN(a + b, c);
상단에 매크로만 추가하고 나면 아주 명료하다,
c는 a + b와 c 중에 작은 것이다.
그야말로 더 불평할 것이 없는 수준에 이르렀다.
이제 이와 같이 코드 작성을 해 보자. 아래의 벨만포드는 최대한 암기하기 쉽게 정리했으니 잘 생각하고 외워야 한다.
##벨만 포드 알고리즘
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#define MIN(x, y) (((x) < (y)) ? (x) : (y))
typedef long long ll;
typedef struct {
int u, v;
ll w;
} Edge;
#define INF (LLONG_MAX / 4)
int bellman_ford_sssp(int n, int m, const Edge *edges, int src, ll *dist) {
for (int i = 0; i < n; i++) dist[i] = INF;
dist[src] = 0;
for (int i = 0; i < n - 1; i++) {
int updated = 0;
for (int j = 0; j < m; j++) {
if (dist[edges[j].u] == INF) continue;
int current_update = (int)((_Bool)((dist[edges[j].u] + edges[j].w) < dist[edges[j].v]));
updated |= current_update;
dist[edges[j].v] = MIN(
dist[edges[j].u] + edges[j].w,
dist[edges[j].v]
);
}
if (!updated) break;
}
// Negative cycle detection (usually unnecessary in coding tests)
for (int k = 0; k < m; k++) {
if (dist[edges[k].u] == INF) continue;
if (dist[edges[k].u] + edges[k].w < dist[edges[k].v]) {
return 0; // negative cycle reachable
}
}
return 1;
}
int main(void) {
int n, m;
if (scanf("%d %d", &n, &m) != 2) return 0;
Edge *edges = (Edge *)malloc((size_t)m * sizeof(Edge));
if (!edges) return 0;
for (int i = 0; i < m; i++) {
scanf("%d %d %lld", &edges[i].u, &edges[i].v, &edges[i].w);
}
int src;
scanf("%d", &src);
ll *dist = (ll *)malloc((size_t)n * sizeof(ll));
if (!dist) {
free(edges);
return 0;
}
if (!bellman_ford_sssp(n, m, edges, src, dist)) {
puts("NEGATIVE_CYCLE");
} else {
for (int i = 0; i < n; i++) {
if (dist[i] >= INF / 2) printf("INF\n");
else printf("%lld\n", dist[i]);
}
}
free(dist);
free(edges);
return 0;
}
이 방식대로 외우면 플로이드 워셜로 풀 수 없으나 다익스트라를 잊어먹어도 풀 수 있는 문제들에서 꽤 효율적이다. N이 500-800 사이인 그래프 탐색 문제에서 푼다면 아슬아슬하게 공간복잡도와 시간복잡도 역시 통과할 수 있다.