ITE2039 알고리즘

총평

Assignment/ 아래 독립 .cpp 12개가 전부다. 공통 헤더도, 빌드 스크립트도, 테스트도, 입력 예제 파일도 없다. 각 파일은 main() 하나와 scanf 몇 줄로 끝나는 온라인 저지 제출물 형태이고, 12개 중 5개가 학기 마지막 날 커밋 하나에 한꺼번에 들어왔다. 이것은 설계 산출물이 아니라 수업 진도를 따라친 연습 기록이며, 그 기준으로 읽어야 공정하다.

그 기준에서 잘한 것은 분명하다. Heapsort.cpp의 sift-down은 l<n/r<n 경계까지 CLRS 그대로고, PriorityQueue.cpp는 STL priority_queue에 위임하지 않고 1-based 배열 힙에 sift-up/sift-down·increase-key를 직접 구현했다. MatrixChain.cpp는 CLRS 예제 p = <30,35,15,5,10,20,25>에 정확히 15125를 냈고, RodCutting.cpp는 값뿐 아니라 절단 위치 s[]까지 복원한다. 점화식과 인덱스 오프바이원이 맞다는 뜻이다.

가장 치명적인 것은 LongestCommonSubsequence.cpp다. 파일 전체가 5줄이고 내용은 printf("abcde") 하나다. LCS 구현이 존재하지 않는다. 그 옆의 dijkstra.cpp는 우선순위 큐를 거리가 아니라 정점 번호로 정렬하고 있어서 Dijkstra의 그리디 불변식이 성립하지 않는다. 두 파일 모두 2016-12-07 커밋 5f1409f에 들어왔고 이후 손대지 않았다.

안전성은 전반적으로 방치되어 있다. AddressSanitizer는 세 파일에서 즉시 터졌고(Counting.cpp:28, HuffmanCode.cpp:176, Insertion.cpp:35), 그중 Huffman의 힙 오버플로는 과제 예제 입력으로 매 실행마다 발생한다. 12개 파일 어디에도 입력 범위 검증이 없다.

파일	주제	핵심 판정	등급
Insertion	삽입 정렬	결과는 맞음. 겹치는 영역에 `memcpy` — ASan 확인	B-
Merge	병합 정렬	교과서대로. 표준 아닌 VLA로 보조 배열	B
Selection	선택 정렬	`m`회만 돌고 `n`개 전부 출력 — 부분 정렬 노출	C+
Heapsort	힙 정렬	sift-down 경계 정확. `k>n`이면 배열 밖을 읽어 출력	B+
PriorityQueue	최대 힙	직접 구현 정상. 죽은 코드 4덩어리, 빈 힙 추출 무방비	B-
FindingSameKeys	키 교집합	동작함. 값 범위 100001 하드코딩, 검사 없음	C+
Counting	구간 계수	답은 맞지만 힙 버퍼 오버플로 — ASan 확인	C
RodCutting	막대 자르기 DP	이 저장소에서 가장 깔끔. 해 복원까지 구현	A-
MatrixChain	행렬 곱 순서 DP	CLRS 예제 15125 정확. 괄호화 복원은 없음	B+
HuffmanCode	허프만 부호	비용은 맞음. 출처 없는 복사 + 매 실행 힙 오버플로	C-
dijkstra	최단 경로	우선순위 큐가 거리가 아닌 정점 번호로 정렬됨	C-
LongestCommonSubsequence	LCS DP	구현 없음. `printf("abcde")` 5줄	F

학기 마지막 커밋 — 5f1409f

2016-12-07 커밋 하나가 HuffmanCode·LongestCommonSubsequence·MatrixChain·RodCutting·dijkstra 다섯 개를 동시에 추가하고(+327), 완성되어 있던 AssemblyLine.cpp를 삭제한다(-91). 커밋 메시지는 Update dijkstra다. 이 저장소 문제의 절반이 이 한 커밋 안에 있다.

치명적

LCS는 구현되지 않았다. 파일은 하드코딩된 문자열을 출력한다

아래가 LongestCommonSubsequence.cpp의 전문이다. 5줄이고, DP 테이블도 입력 읽기도 없다. 어떤 입력을 주든 abcde를 출력한다. 실행해서 확인했다: printf "abc\nabd\n" | ./LongestCommonSubsequence → abcde.

파일명이 과제명이고 내용이 정답처럼 보이는 리터럴이라는 조합은, 좋게 보면 자리만 잡아둔 껍데기이고 나쁘게 보면 하드코딩 제출이다. 어느 쪽이든 저장소에 남아 있는 것은 스텁이며, git log상 이 파일은 추가된 이후 한 번도 수정되지 않았다. 같은 학기에 RodCutting과 MatrixChain의 DP를 정확히 짜 놓고 LCS만 비워둔 것이라 실력 문제로 보기도 어렵다.

Assignment/LongestCommonSubsequence.cpp:1–6 (파일 전문)

#include <stdio.h>

int main(void)
{
	printf("abcde");   // ← LCS 구현 없음. 입력조차 읽지 않는다
}

치명적

dijkstra의 우선순위 큐는 거리가 아니라 정점 번호로 정렬된다

pair<t_index, t_cost>를 priority_queue에 그대로 넣으면 std::pair의 기본 비교자가 .first를 먼저 본다. .first는 정점 번호다. 즉 이 큐는 "가장 가까운 정점"이 아니라 "번호가 가장 큰 정점"을 꺼낸다. :30에서 비용을 음수로 뒤집어 넣는 min-heap 관용구는 .second에만 걸려 있어 동점일 때만 작동하는 장식이다.

같은 타입으로 독립 실험을 돌려 확인했다. {5,-1}(정점 5, 거리 1)과 {2,-99}(정점 2, 거리 99)를 넣으면 정점 5가 먼저 나온다 — 거리 순이었다면 순서가 같았겠지만, 정점 2가 더 가까운 경우에도 5가 먼저 나온다는 뜻이다. 그리디 불변식이 없으므로 이것은 Dijkstra가 아니라 label-correcting(Bellman–Ford 계열) 완화 반복이다. 큐가 빌 때까지 완화를 반복하므로 답은 수렴하지만, O((V+E)log V) 보장은 사라지고 정점이 여러 번 재확장된다. 방문 표시도, -now.second > dist[now.first] 같은 낡은 항목 건너뛰기도 없다.

부수적으로 dist[start]를 0으로 초기화하는 문장이 파일 어디에도 없다(grep으로 확인: dist[]에 쓰는 곳은 :29 하나뿐이다). main이 정점 2부터만 읽기 때문에 가려져 있을 뿐이다.

Assignment/dijkstra.cpp:18–19, 27–31

priority_queue<pair<t_index, t_cost> > pq;  // ← .first(정점 번호)로 정렬된다
pq.push({ start, 0 });                      // dist[start]=0 은 어디에도 없음
...
if (dist[next_index] > -now.second + map[now.first][i].second)
{
    dist[next_index] = -now.second + map[now.first][i].second;
    pq.push({ next_index, -dist[next_index] });  // 음수 뒤집기는 .second, 즉 무의미
}

실행 확인도달 불가 정점 / 음수 간선

$ printf "4\n1 1 2 5\n2 1 3 5\n3 0\n4 0\n" | ./dijkstra
987654321          ← 센티넬을 거리인 양 그대로 출력 (main:53-57, 도달 불가 처리 없음)

$ printf "3\n1 2 2 4 3 1\n2 1 3 -10\n3 0\n" | ./dijkstra
4                  ← 음수 간선을 거부하지 않는다. 음수 사이클이면 종료하지 않음

중대

Huffman: 예제 입력에서 매번 힙 버퍼 오버플로가 난다

arr은 심볼 하나당 char 1바이트로 input개만 잡아둔 버퍼인데, :176에서 %s로 읽는다. %s는 토큰이 한 글자여도 널 종료자까지 2바이트를 쓰므로 매 반복마다 arr[i+1]을 침범하고, 마지막 원소에서는 힙 밖으로 나간다. 이것은 이론적 위험이 아니라 확정적 동작이다. 교과서 예제 입력으로 ASan이 즉시 잡았다.

Assignment/HuffmanCode.cpp:172–178

char *arr = (char *)malloc(sizeof(char)*input);   // 심볼당 1바이트
int *freq = (int *)malloc(sizeof(int)*input);
for (int i = 0; i < input; ++i)
{
   scanf("%s", &arr[i]);                      // ← %s 는 널 종료자까지 2바이트를 쓴다. %c 였어야 함
   scanf("%d", &freq[i]);
}

AddressSanitizerclang 21, -fsanitize=address

ERROR: AddressSanitizer: heap-buffer-overflow on address 0x6020000000f6
WRITE of size 2 at 0x6020000000f6 thread T0
    #0 scanf_common(...)
allocated by thread T0 here:
    #1 in main HuffmanCode.cpp:172
SUMMARY: AddressSanitizer: heap-buffer-overflow HuffmanCode.cpp:176 in main

중대

Huffman이 비교 대상으로 삼는 고정길이 부호 비트수가 틀렸다

이 과제의 출력은 두 줄이다. 첫 줄은 고정길이 부호의 총 비트수, 둘째 줄은 허프만 부호의 총 비트수 — 즉 압축률을 보이는 것이 과제의 요점이다. 그런데 bitelength는 floor(log2(n))+1을 반환한다. 올바른 값은 ceil(log2(n))이며, 둘은 n이 2의 거듭제곱일 때 정확히 1씩 어긋난다.

결과적으로 심볼 수가 2·4·8·16개일 때 베이스라인이 부풀려진다. 심볼 4개일 때 고정길이는 심볼당 2비트면 충분한데 3비트로 계산한다. 허프만 쪽 계산(printArr에 누적되는 가중 경로 길이)은 정확하다 — 고전 예제 a5 b9 c12 d13 e16 f45에서 최적값 224를 정확히 냈다. 틀린 것은 비교 대상 쪽이다.

실행 확인심볼 4개, 빈도 모두 1, 메시지 길이 4

$ printf "4\na 1\nb 1\nc 1\nd 1\n4\n" | ./HuffmanCode
12   ← 고정길이 주장. 4심볼 × 2비트 × 4개 = 8 이 정답 (bitelength(4)가 3을 반환)
8    ← 허프만. 이쪽은 맞다

$ printf "6\na 5\nb 9\nc 12\nd 13\ne 16\nf 45\n100\n" | ./HuffmanCode
300
224  ← CLRS 고전 예제의 최적값과 일치

중대

Huffman은 출처 표기 없는 복사본이고, 그 과정에서 노드마다 메모리를 흘린다

MinHeapNode/MinHeap 구조체 배치, newNode·createMinHeap·extractMin·buildHuffmanTree·printCodes·HuffmanCodes라는 함수명 조합, 내부 노드 표식 '$', int arr[100]이라는 상수까지 — 널리 유포된 C 튜토리얼 구현과 식별자 단위로 일치한다. 대문자 Left/Right, is_sizeOne 같은 표기만 손댔다. 출처 주석이 없다. 같은 커밋의 dijkstra.cpp:5는 자기 저장소 링크를 붙여두었으므로, 출처를 밝히는 습관 자체가 없는 것은 아니다.

그리고 :105–106에는 원본에 없는 버그가 추가되어 있다. 노드를 malloc한 직후 같은 슬롯을 newNode() 결과로 덮어쓴다. 심볼 하나당 sizeof(MinHeapNode)가 확정적으로 누수된다. 트리·힙·arr·freq 모두 free되지 않는 것은 별개 문제다.

한편 printArr(:129)은 배열을 출력하지 않고 aFreq += freq*top만 누적하며, printCodes(:133)는 부호를 하나도 출력하지 않는다. :152의 int arr[100]은 채워지기만 하고 읽히지 않는다. 원본의 출력부를 도려내고 이름만 남긴 결과다.

Assignment/HuffmanCode.cpp:103–107

for (int i = 0; i < size; ++i)
{
   minHeap->array[i] = (struct MinHeapNode *)malloc(sizeof(struct MinHeapNode));
   minHeap->array[i] = newNode(data[i], freq[i]);   // ← 윗줄 포인터를 덮어씀. 노드마다 누수
}

커밋 위생

5f1409f "Update dijkstra"는 새 파일 다섯 개를 추가하면서 Assignment/AssemblyLine.cpp 91줄을 조용히 삭제한다. 이 파일은 258a3bc → 19de1eb → 6aade28 "Finish AssemblyLine"로 세 커밋에 걸쳐 완성된 것이었고, 삭제 이유는 메시지 어디에도 없다. 실제로 읽어보면 result1/result2 점화식과 역추적 배열 r1/r2가 들어간 멀쩡한 조립 라인 DP였다. 이 저장소에서 여러 커밋에 걸쳐 다듬은 유일한 파일이 최종 상태에서는 사라져 있다.

잘한 것

RodCutting.cpp는 34줄짜리 bottom-up DP인데 값 r[]과 선택 s[]를 함께 채우고, :28–32에서 n -= s[n]으로 절단 위치를 복원해 출력한다. CLRS 가격표 1 5 8 9 10 17 17 20, n=8에 22와 절단 2 6을 정확히 냈다. "최적값만 구하고 끝내지 않는다"는 점에서 같은 커밋의 MatrixChain(s 테이블 없음)보다 한 걸음 앞서 있다.

정렬과 자료구조 — week1–2

9~10월에 커밋된 7개 파일이다. 여기까지는 매주 한두 개씩 꾸준히 올라왔고, 세 정렬 파일은 input/print/printr/process라는 동일한 뼈대를 공유한다. 이 구간의 코드가 학기 후반보다 오히려 낫다.

중대

삽입 정렬이 겹치는 메모리 영역에 memcpy를 쓴다

원소를 한 칸씩 미는 대신 memcpy로 블록 이동하는 영리한 변형인데, 원본 v+i+1과 목적지 v+i가 (j-i)개 구간에서 겹친다. memcpy는 겹치는 영역에 대해 정의되지 않은 동작이며, 여기 필요한 것은 memmove다. 실제로는 대부분의 구현이 앞에서부터 복사해 우연히 맞는 답을 내지만(5 3 9 1 7 2 8 6 → 9 8 7 6 5 3 2 1, 정상), ASan은 첫 실행에서 바로 잡는다.

Assignment/Insertion.cpp:31–36

k = v[(j=i)];
while ( ++j < n && k > v[j] );

if ( --j == i ) continue;
memcpy ( v+i, v+i+1, sizeof(*v) * (j-i) );   // ← 겹침. memmove 였어야 함
v[j] = k;

AddressSanitizer입력 n=8

ERROR: AddressSanitizer: memcpy-param-overlap: memory ranges
  [0x603000001c70,0x603000001c78) and [0x603000001c74,0x603000001c7c) overlap
SUMMARY: AddressSanitizer: memcpy-param-overlap Insertion.cpp:35 in process(int*)

중대

Counting: 접두합 루프가 할당 범위를 한 칸 넘어간다

calloc(++M, ...)는 M을 먼저 증가시키므로 유효 인덱스는 0..M-1이다. 그런데 바로 아래 루프는 i <= M까지 돈다. 이미 증가한 M을 상한으로 다시 쓰면서 한 칸을 초과한다. ++M의 부수효과를 같은 변수의 경계값으로 재사용한 전형적인 오프바이원이다.

덧붙여 :22–23은 scanf의 반환값을 도수의 증가분으로 쓴다. 정상 입력에서는 항상 1이라 동작하지만, 입력이 짧거나 형식이 틀리면 증가분이 0 또는 -1(EOF)이 되어 도수가 조용히 줄어든다. :31의 s[--q[i].first]도 A=0인 질의에서 s[-1]을 읽는다(실행 확인: 0 2 질의가 종료 없이 2를 출력).

Assignment/Counting.cpp:13, 22–28

int * s = (int*)calloc(++M, sizeof(int));   // 유효 인덱스 0..M-1
...
while (N--) {
   int temp = scanf("%d", &k);              // ← 반환값을 도수 증가분으로 사용
   s[k] += temp;                            // k 범위 검사 없음
}
s[0] = 0;
for (int i = 1; i <= M; ++i)                 // ← i=M 은 할당 범위 밖
   s[i] += s[i - 1];

AddressSanitizerN=5 M=5 K=2

ERROR: AddressSanitizer: heap-buffer-overflow
READ of size 4 ... #0 in main Counting.cpp:28
allocated by thread T0 here: #1 in main Counting.cpp:13

경미

PriorityQueue에 죽은 코드가 네 덩어리 남아 있다

힙 연산 자체는 정상 동작한다(5,3,9,1 삽입 후 두 번 추출 → 9 5, 잔여 3 1). 문제는 그 주변이다.

:19–24의 손수 짠 swap(int*, int*)는 한 번도 호출되지 않는다. :40과 :60의 swap(v[i], v[i/2])는 값을 넘기므로 :7의 using namespace std; 때문에 std::swap으로 결정된다.
:11 #define NIL -987654321 — 정의만 되고 어디에도 쓰이지 않는다.
:17 전역 int idx = 0; — 쓰이지 않는다.
:117–121 void input(__container__ container, int size) — vector를 값으로 받아 채우므로 설령 호출되어도 결과가 버려진다. 호출되지 않는다.

동작 면에서는 case 2(:87–95)에 빈 힙 검사가 없다. 원소 없이 추출을 요청하면 v[1]로 벡터 범위 밖을 읽는다 — 실행 확인: printf "2 0" | ./PriorityQueue는 죽지 않고 0을 출력한다. case 3의 v[x] = y도 x를 검사하지 않는다.

경미

Heapsort의 알고리즘은 정확하지만 k 검증이 없다

sift-down(:37–54)은 l = 2i+1, r = 2i+2, 경계 l < n·r < n까지 CLRS와 동일하고, 힙 구축은 n/2-1부터 내려온다. 중복 값(4 4 4 4 4)에서도 정상이다. 이 저장소에서 자료구조 정확성이 가장 확실한 파일이다.

다만 main이 k를 검증하지 않아 k > n이면 i >= n-k가 음수까지 내려가 배열 밖을 읽는다. n=3, k=10: 9 5 1 0 0 0 0 0 0 0 — 뒤의 0 일곱 개가 힙 밖이다. 또 :17의 if (*first - *second)는 뺄셈 결과의 참/거짓으로 같음을 판정하므로 INT_MIN 근처에서 오버플로한다. *first != *second면 충분하다.

경미

Selection은 m회만 정렬하고 n개를 전부 출력한다

:31의 바깥 루프가 i < m이므로 앞 m개만 확정되는 부분 선택 정렬인데, :22는 print(v)로 배열 전체를 찍는다. n=8, m=3: 1 2 3 5 7 9 8 6 — 앞 3개는 정렬, 뒤 5개는 중간 상태다. 과제가 "가장 작은 m개"를 요구했다면 출력 범위를 m으로 잘랐어야 한다.

:39의 v[k] ^= v[i] ^= v[k] ^= v[i];는 같은 객체를 한 표현식에서 세 번 수정한다. C++17 이전 규칙에서는 정의되지 않은 동작이지만, 정직하게 적자면 clang 21에 -std=c++14 -Wall -Wextra -Wunsequenced -Wsequence-point를 줘도 아무 경고가 나오지 않았고, 실행 결과도 정상이었다. 안전성 문제라기보다 읽히지 않는 코드 문제다.

경미

FindingSameKeys는 값 범위 100001을 하드코딩하고 검사하지 않는다

:9의 vector<bool> v(100001, false)는 문제에서 준 제약을 그대로 박아 넣은 것으로, :13·:18에서 t가 그 범위 안인지 확인하지 않는다. 해시 없이 직접 주소 지정으로 푼 선택 자체는 O(n+k)로 타당하지만, 키 공간이 커지는 순간 무너진다. 또 :10·:15의 while(--n + 1)은 while(n-- > 0)과 같은 뜻을 일부러 읽기 어렵게 쓴 것이다. 두 집합의 교집합 크기 계산 자체는 맞다({1..5} ∩ {3,4,5,9} → 3).

경미

Merge는 보조 배열을 표준 아닌 VLA로 스택에 잡는다

병합 로직 자체는 L[i] <= R[j]로 안정성까지 지킨 교과서 구현이다. 다만 :28의 int L[n1], R[n2];는 C++ 표준에 없는 가변 길이 배열로, clang이 -Wvla-cxx-extension으로 경고한다. 최상위 호출에서 n/2개를 스택에 잡으므로 입력이 커지면 힙이 아니라 스택이 먼저 터진다. MSVC에서는 아예 컴파일되지 않는다.

반복되는 패턴

입력은 항상 신뢰된다. 12개 파일 전부 scanf 반환값을 무시하거나(Counting.cpp는 오히려 도수로 쓴다) 범위 검사를 하지 않는다. Heapsort의 k>n, PriorityQueue의 빈 힙 추출, FindingSameKeys의 t>100000, Counting의 A=0 — 네 가지 모두 실행으로 범위 밖 접근을 확인했다. 온라인 저지 제출 습관이 그대로 굳은 것이다.
주석과 이름이 실제 동작보다 앞서간다. printCodes는 부호를 출력하지 않고, printArr는 배열을 출력하지 않으며, dijkstra는 Dijkstra가 아니고, LongestCommonSubsequence는 LCS를 계산하지 않는다. README도 마찬가지로 week1·week2의 6항목에서 멈춰 있고 나머지 6개 파일은 한 줄도 언급되지 않는다(README 마지막 수정 2016-09-11, 코드 마지막 추가 2016-12-07).
영리함이 정확성보다 앞선다. memcpy로 블록 이동(Insertion:35), XOR 3연쇄 교환(Selection:39, Heapsort:18), while(--n+1)(FindingSameKeys:10), scanf 반환값을 증가분으로(Counting:23), 뺄셈으로 같음 판정(Heapsort:17). 전부 "더 짧게 쓰는 법"의 실험인데, 그중 둘은 실제로 미정의 동작이거나 오버플로 경로다. 같은 학생이 RodCutting·MatrixChain에서는 이런 장난을 전혀 하지 않고 평범하게 짰다는 점이 대비된다.
정리·해제는 하지 않는다. 정렬 3종은 free(v)를 하는데, 그 뒤에 나온 HuffmanCode는 트리·힙·arr·freq 무엇도 해제하지 않고 :105에서 노드마다 누수까지 추가한다. MSVC용 #pragma warning (disable : 4996)이 RodCutting:4·MatrixChain:6에 남아 clang에서 unknown pragma를 띄우고(후자는 뒤에 불필요한 ;까지 붙어 있다), dijkstra:6에는 헤더에서 떼어 온 #pragma once가 .cpp 최상위에 남아 있다.
커밋이 작업 단위를 반영하지 않는다. 커밋 12개 중 코드가 든 것은 6개, 그중 하나(5f1409f)가 전체 코드의 40%를 옮긴다. 메시지 Update dijkstra 아래에 새 과제 5개 추가와 완성된 과제 1개 삭제가 함께 들어 있다. 마지막 커밋(2021-08-09)은 5년 뒤의 사용자명 변경으로, 코드 변경이 아니다.

지금 손본다면

LongestCommonSubsequence.cpp를 실제로 구현하거나 지운다. 30분. 하드코딩된 printf("abcde")가 과제명 파일로 남아 있는 한, 이 저장소의 나머지 11개 파일에 대한 신뢰도 같이 깎인다. RodCutting 수준의 bottom-up 테이블 하나면 끝난다.
dijkstra.cpp:18의 큐 원소를 pair<cost, index>로 뒤집는다. 한 줄. 여기에 dist[start] = 0 한 줄과 pop 직후 if (-now.second > dist[now.first]) continue; 한 줄을 더하면 그때부터 진짜 Dijkstra가 되고 복잡도 보장이 생긴다.
HuffmanCode.cpp:176의 %s를 %c(또는 " %c")로 바꾸고 :105의 잉여 malloc을 지운다. 두 줄. 실행마다 나는 힙 오버플로와 심볼당 누수가 동시에 사라진다. 이어서 bitelength를 ceil(log2 n)로 고쳐야 과제가 비교하려던 숫자가 맞아떨어진다.
Counting.cpp의 ++M을 풀어 쓴다. int size = M + 1;로 분리하고 루프를 i < size로 두면 오프바이원이 사라진다. Insertion.cpp:35의 memcpy → memmove도 같은 성격의 한 단어 수정이다.
README를 실제 파일 목록과 맞춘다. week1·week2에서 멈춘 목록에 Counting 이후 6개를 채우고, 각 파일의 입력 형식(Counting은 N M K 다음에 질의가 먼저, 값이 나중이다)을 한 줄씩 적어야 이 코드를 다시 돌려볼 수 있다. 지금은 입력 형식을 소스에서 역추적해야만 실행된다.