개요
연결 리스트 단원 후속 실습 두 문제를 파이썬으로 풀고 나서, 같은 문제를 C++로 다시 짰다. 문제는 절마다 다시 적어뒀으니 이 편만 읽어도 된다. 연결 리스트 개념 정리와 파이썬 쪽 설계는 Python - < 7 >에 있다.
로직은 이미 파이썬으로 맞춰놓은 상태였으니 옮기기만 하면 될 줄 알았다. 그런데 이번 편의 절반은 컴파일도 되고 실행도 되는데 화면에 아무것도 안 나오던 시간이다.
당근 — 첫 코드가 세 군데 어긋나 있었다
문제부터. 당근을 수확한 순서대로 크기를 적어둔 기록이 주어진다. 이 기록에서 연속으로 크기가 커지는 구간 중 가장 긴 것의 당근 개수를 구한다. 커지는 구간이 하나도 없으면 답은 1이다.
- 입력: 첫 줄에 테스트케이스 수
T. 케이스마다 첫 줄에 당근 개수N, 다음 줄에 크기CN개 - 제약:
5 ≤ N ≤ 1000,1 ≤ C ≤ 10 - 출력:
#테스트케이스번호 최대값
1 2 3 4 5면 5, 4 5 1 2 3이면 3( 뒤쪽 1 2 3 ), 5 4 3 2 1이면 1이다.
이웃한 둘을 비교하며 한 번 훑으면 끝나는 O(N) 문제다. 파이썬에서 이미 통과시킨 로직이라 옮기기만 하면 될 줄 알았는데, 빌드부터 안 됐다.
C4996 'freopen': This function or variable may be unsafe.
Consider using freopen_s instead. To disable deprecation,
use _CRT_SECURE_NO_WARNINGS. See online help for details.
algorithm.cpp 줄 9
MSVC가 freopen을 deprecated로 보고 막는 것이라, 에러 메시지가 알려준 대로 매크로를 정의하면 된다. 중요한 건 위치다. 이건 전처리기 지시문이라 <cstdio>가 들어오기 전에 정의돼 있어야 하고, 그러려면 어떤 #include보다도 위에 있어야 한다.
#define _CRT_SECURE_NO_WARNINGS // include보다 반드시 위
#include <iostream>
#include <cstdio>
빌드가 되게 만들어놓고 코드를 다시 보니, 세 군데가 어긋나 있었다. 위 스크린샷에 찍힌 게 그 코드다.
int T;
cin >> T;
for (int test_case = 0; test_case <= T; ++T) // (1) 증감식이 ++T
{
int N; // N = 당근 갯수
cin >> N;
int maxCount = 0, curCount = 0;
vector<int> carrots(N);
for (int i = 0; i < N; ++i)
{
cin >> carrots[i];
if (i == 0) continue;
if (carrots[i] < carrots[i + 1]) // (2) 아직 안 읽은 자리를 본다
++curCount;
else
{
maxCount = maxCount > curCount ? maxCount : curCount;
curCount = 0;
}
}
maxCount = maxCount > curCount ? maxCount : curCount;
cout << '#' << test_case << ' ' << maxCount << '\n'; // (3) +1이 없다
}
(1) 증감식이 ++test_case가 아니라 ++T다. 루프 변수는 0에 고정되고 상한만 계속 올라가니 test_case <= T가 영원히 참이다. 실제로 돌려보면 #0 0을 끝없이 뱉는다.
(2) carrots[i + 1]은 아직 값이 안 들어간 자리다. 이 루프는 읽으면서 바로 비교하는 구조라, i번을 방금 읽은 시점에 i + 1번은 아직 0이다. 게다가 i == N - 1일 때는 vector 범위 밖이라 무슨 값이 나올지 알 수 없다. 비교 방향도 뒤집혀 있어서, 이웃한 둘 중 뒤엣것과 비교하면서 앞엣것이 작은지를 묻고 있다. 봐야 할 건 이미 읽어둔 이전 값이다.
(3) +1이 빠졌다. curCount는 “이전보다 커졌다”가 참일 때만 올라가니 증가가 일어난 횟수다. 문제가 묻는 건 그 구간에 든 당근 개수다. 1 2 3 4 5는 커진 횟수가 4인데 당근은 5개다. 원소 사이에만 세는 자리가 있으니 언제나 하나가 적다( fencepost error ). 5 4 3 2 1의 답이 1인 것도 같은 규칙이다 — 커진 횟수가 0이니 당근은 1개다.
파이썬에서 출력이 네 줄 모두 1씩 작게 나와 한 번 고쳤던 자리인데, 옮기면서 또 빠뜨렸다.
vector를 통째로 버렸다
(2)를 고치려고 carrots[i + 1]을 carrots[i - 1]로 바꾸려다가, 그러고 보니 vector가 필요 없다는 걸 알았다. 이 문제에서 한 칸을 판단하는 데 필요한 건 직전 값 하나뿐이다. 다 읽어놓고 나중에 다시 볼 일이 없다.
그래서 배열을 없애고 읽는 족족 처리하고 버리는 방식으로 바꿨다. 공간 복잡도가 O(N)에서 O(1)이 된다.
// #define _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;
int main(int argc, char** argv)
{
// freopen("carrot_sample_in.txt", "r", stdin);
int T;
cin >> T;
for (int test_case = 1; test_case <= T; ++test_case)
{
int N; // N = 당근 갯수
cin >> N;
int maxCount = 0, curCount = 0;
int prevCarrot = -1;
for (int i = 0; i < N; ++i)
{
int curCarrot;
cin >> curCarrot;
if (prevCarrot == -1)
{
prevCarrot = curCarrot;
continue;
}
if (curCarrot > prevCarrot)
++curCount;
else
{
maxCount = maxCount > curCount ? maxCount : curCount;
curCount = 0;
}
prevCarrot = curCarrot;
}
maxCount = maxCount > curCount ? maxCount : curCount;
cout << '#' << test_case << ' ' << maxCount + 1 << '\n';
}
}
prevCarrot = -1은 “아직 직전 값이 없다”를 나타내는 sentinel이다. 당근 크기가 1 ≤ C ≤ 10이라 -1이 진짜 값으로 들어올 수 없으니 이 자리에 쓸 수 있다. 처음엔 여기 0을 뒀다가 -1로 바꿨는데, sentinel은 입력 값의 범위와 절대 겹치지 않는 값이어야 한다는 걸 뒤에 주차장에서 한 번 더 확인하게 된다.
그리고 prevCarrot = curCarrot이 루프 맨 끝에 있다. 처음엔 이 줄이 빠져 있어서 직전 값이 영원히 첫 당근에 머물러 있었다.
출력이 아예 안 나왔다
고친 코드를 돌렸다. 빌드 성공, 실행 성공, 그리고 콘솔이 비어 있었다.
에러가 뜨면 차라리 쉬운데 아무 일도 안 일어난 것처럼 보이니 어디를 봐야 할지가 막막했다. 그래서 의심 범위를 셋으로 잘랐다.
1단계 — 파일이 열리긴 했나. 먼저 입력 파일 위치부터 봤다. .vcxproj가 있는 폴더에 있었다. Visual Studio의 기본 작업 디렉터리는 $(ProjectDir)이고 exe가 놓이는 Debug 폴더가 아니니, 이 위치가 맞다. 구성(Debug/Release)마다 설정이 따로 있다는 것도 이때 알았다.
그래도 확실히 하려고 freopen의 반환값을 찍었다.
cout << freopen("carrot_sample_in.txt", "r", stdin) << '\n';
int T;
cin >> T;
cout << T;
7ABBCA40
0
7ABBCA40. null이 아니다 = 파일은 열렸다. 경로 문제는 여기서 지워졌다.
2단계 — 그런데 T가 0이다. 입력 파일 첫 줄은 4인데 읽은 값이 0이다. 파일은 열렸는데 값이 안 들어왔으니, 문제는 여는 쪽이 아니라 읽는 쪽이다.
여기서 cin의 동작 두 가지가 증상을 전부 설명해준다.
- C++11부터 정수 추출이 실패하면 변수에
0을 쓴다. 그래서 초기화 안 한 쓰레기값이 아니라 딱 0이 보인다 - 한 번 실패하면 failbit가 서고,
clear()를 부르기 전까지 이후 추출이 전부 무시된다
T가 0이니 test_case <= T 루프는 한 번도 안 돌고, 설령 돌았어도 뒤의 cin >> N은 이미 무시되는 상태다. 출력이 없는 게 아니라 출력할 루프가 한 바퀴도 안 돈 것이었다.
3단계 — 인코딩. 파일을 다시 저장했더니 그대로 됐다.
원인은 UTF-8 BOM이었다. 파일 맨 앞에 EF BB BF 세 바이트가 붙어 있었고, cin >> T는 첫 글자에서 숫자가 아닌 바이트를 만나 바로 실패한 것이다. 눈으로 열면 4로 보이니 파일만 봐서는 알 수가 없다.
재현해보면 증상이 그대로 나온다. 같은 실행 파일에 BOM만 붙은 입력을 주면 이렇다.
--- BOM 없는 파일 ---
freopen 반환값 : 0x7f8f498038e0
cin >> T 이후 T : 4
fail() : 0 eof() : 0
--- UTF-8 BOM 붙은 파일 ---
freopen 반환값 : 0x7fda03c038e0
cin >> T 이후 T : 0
fail() : 1 eof() : 0
clear() 전 다음 추출 : 변수가 그대로 남는다
세 단계를 거꾸로 읽으면 다음에 또 조용히 실패했을 때 쓸 순서가 된다.
- 리소스를 잡는 호출의 반환값을 확인한다 — 여기까지 됐는지
- 처음 읽은 값을 확인한다 — 들어오긴 했는지
- 그다음이 인코딩이다 — 눈에 보이는 게 파일에 든 바이트와 같은지
1번과 2번 사이에서 끊긴 걸 확인하고 나서야 3번을 볼 생각이 났다.
주차장 — for-else가 없는 언어에서
문제부터. 1번부터 n번까지 번호가 붙은 주차 공간이 있다. 차가 도착하면 번호가 가장 작은 빈 공간에 넣고, 빈 곳이 없으면 입구에서 자기 차례를 기다린다( 새치기는 없다 ). 주차요금은 차량 무게 × 그 공간의 단위 무게당 금액이고 이용시간은 안 본다. 하루치 총 수입을 구한다.
- 입력:
TC/ 케이스마다n m(1 ≤ n ≤ 100,1 ≤ m ≤ 2000) /n줄에 공간별 단가Ri(1 ≤ Ri ≤ 100) /m줄에 차량 무게Wi(1 ≤ Wi ≤ 10000) / 이후2m줄에 정수x -
x > 0이면x번 차가 들어오고,x < 0이면-x번 차가 나간다. 모든 차는 정확히 한 번 들어오고 한 번 나간다 - 출력:
#테스트케이스번호 총수입
칸마다 단가가 다르다는 게 이 문제의 전부다. 어느 차가 어느 칸에 들어갔는지를 끝까지 들고 있어야 요금이 나온다. 그래서 파이썬에서는 상태를 넷으로 갈라뒀었다.
| 상태 | 무엇을 담나 |
|---|---|
parking |
칸마다 지금 무엇이 있는지, 빈 칸 표시 포함 |
car_pos |
차마다 지금 어느 칸에 있는지 |
| 대기열 | 기다리는 차 번호, 앞에서 뺀다 |
| 누적 수입 | 정산한 요금의 합 |
로직은 그대로 두고 옮겼는데, 넷 중 둘이 C++에서 모양이 바뀌었다. 이 절은 파이썬에서 쓰던 문법과 표현이 없는 자리를 메운 기록이다.
for-else를 대신할 flag
입차 처리는 “앞에서부터 훑다가 빈 칸이 나오면 거기 넣고, 하나도 없으면 대기열로” 두 갈래다. 파이썬에는 이 두 갈래를 그대로 적는 문법이 있다. for에 else를 붙이면 break 없이 루프가 끝났을 때만 그 블록이 실행된다.
for i in range(len(parking)):
if parking[i] == 0: # 빈 칸을 찾았다
parking[i] = car_weights[cur_pos]
break # break 했으니 else는 안 돈다
else: # break 없이 끝났다 = 빈 칸이 하나도 없다
line.append(cur_car)
C++엔 이게 없으니 bool 하나로 바꿨다.
bool isEmpty = true;
for (int j = 0; j < N; ++j)
{
// 빈 공간을 찾았을 경우
if (parking[j] == -1)
{
parking[j] = carIdx;
break;
}
// 못찾은 경우
if (j == N - 1)
isEmpty = false;
}
if (!isEmpty)
line.push(carIdx);
“마지막 반복까지 왔으면 못 찾은 것”으로 판정하는 방식이다. 마지막 칸에서 찾은 경우에도 break가 j == N - 1 검사보다 먼저라 오작동하지 않는다.
걸리는 건 판정의 근거가 파이썬 쪽과 다르다는 점이다. for ... else는 “break 없이 끝났는가”를 보는데, 이 코드는 “마지막 인덱스까지 갔는가”를 본다. 결과는 같지만 뒤쪽은 읽을 때 루프 범위를 같이 따라가야 무슨 뜻인지 잡힌다.
found = false로 두고 찾았을 때만 true로 바꾸면 그 확인이 필요 없다. 이름도 그쪽이 맞다. 지금 쓴 isEmpty는 “주차장이 비었나”로 읽히는데 실제로 담고 있는 건 “빈 자리를 찾았나”다.
sentinel을 -1로 바꿔야 했던 이유
parking에 무엇을 담을지가 두 언어에서 갈렸다. 파이썬에서는 칸에 차의 무게를 바로 넣고 빈 칸을 0으로 표시했다. 무게가 1 ≤ Wi라 0이 실제 값으로 나올 수 없으니 이 표시가 안전했다.
C++에서는 칸에 차 인덱스를 넣기로 했다. 요금 계산에 어차피 차 번호가 필요하고, 무게는 carWeights[carIdx]로 언제든 꺼낼 수 있어서다. 그런데 여기서 같은 수가 안 통한다. 인덱스는 0부터 시작하니 0번 차가 주차된 칸과 빈 칸이 똑같이 0이 된다. 그래서 빈 칸 표시를 -1로 바꿨다. 당근에서 prevCarrot을 -1로 고쳤던 것과 똑같은 이유다.
sentinel은 “특별한 값”이 아니라 입력 값 범위와 안 겹치는 값이어야 한다. 0-based 인덱스를 담는 배열에서 0은 쓸 수 없다.
car_pos를 지우고 선형 탐색으로
출차 신호는 차 번호로 오는데 요금은 칸 번호를 알아야 나온다. 칸마다 단가가 다르기 때문이다. 파이썬에서는 이걸 위해 car_pos( 차 → 칸 ) 배열을 따로 두고 O(1)로 꺼냈다.
C++에서는 그 배열을 없앴다. 배열 하나로 충분해 보여서였다. 대신 출차할 때 parking을 앞에서부터 훑어 그 차 인덱스가 든 칸을 찾는다.
대신 O(1)이던 조회가 O(N)이 된다. n ≤ 100이고 출차가 m ≤ 2000번이라 최악 20만 번, 이 문제에서는 문제가 안 되는 크기다. 다만 이건 상태 하나를 줄이는 대가로 조회 비용을 낸 것이지 그냥 더 나은 선택은 아니다.
칸을 안 비웠더니 조용히 틀렸다
여기서 버그가 하나 나왔다. 출차 처리에서 요금만 정산하고 parking[j] = -1을 안 했다.
나간 차가 계속 그 칸을 차지하고 있는 상태가 된다. 그러면 빈 칸이 점점 줄고, 들어와야 할 차가 대기열로 밀리고, 뒤에 나가는 차를 찾을 때도 엉뚱한 칸이 잡힌다. 더 나쁜 건 탐색에 실패해도 carPos가 -1인 채로 흘러간다는 것이다. 그 뒤의 parking[carPos] = carIdx가 곧 parking[-1]에 쓰는 코드가 된다.
이 버그의 무서운 점은 터지지 않는다는 데 있다. 이 줄만 빼고 예제를 돌리면 이렇게 나온다.
#1 46 <- 기대값은 53
크래시도, 경고도, 이상한 숫자도 없다. 그냥 조용히 7만큼 적은 값이 나온다. 앞의 BOM 건과 증상이 닮았다 — 실패가 실패처럼 생기지 않은 것이 이번 문제 둘의 공통점이었다.
최종 코드
// #define _CRT_SECURE_NO_WARNINGS
#include <iostream>
// #include <cstdio>
#include <vector>
#include <queue>
using namespace std;
int main(int argc, char** argv)
{
// freopen("sample_input.txt", "r", stdin);
int TC;
cin >> TC;
for (int test_case = 1; test_case <= TC; ++test_case)
{
int N, M; // N = 주차장 수, M = 차량 수
cin >> N >> M;
vector<int> parkPrices(N); // parkPrices = 주차장 별 단위 요금
for (int& price : parkPrices)
cin >> price;
vector<int> carWeights(M); // carWeights = 자동차별 무게
for (int& weight : carWeights)
cin >> weight;
vector<int> parking(N, -1); // 실시간 주차장 공간
queue<int> line; // 주차 대기열
long long sumPrice = 0;
for (int i = 0; i < M * 2; ++i)
{
int carNumber; // 차량 번호
cin >> carNumber;
int carIdx = abs(carNumber) - 1; // 차량 index
// 차량이 출입하는 경우
if (carNumber > 0)
{
bool isEmpty = true;
for (int j = 0; j < N; ++j)
{
// 빈 공간을 찾았을 경우
if (parking[j] == -1)
{
parking[j] = carIdx;
break;
}
// 못찾은 경우
if (j == N - 1)
isEmpty = false;
}
if (!isEmpty)
line.push(carIdx);
}
// 차량이 나가는 경우
else
{
int carPos = -1;
for (int j = 0; j < N; ++j)
{
if (parking[j] == carIdx)
{
// 주차요금 정산
sumPrice += parkPrices[j] * carWeights[carIdx];
// 현재 위치 저장
carPos = j;
// 주차장 초기화
parking[j] = -1;
break;
}
}
if (line.empty()) continue; // 대기열이 비어있는 경우 early continue
carIdx = line.front();
line.pop();
parking[carPos] = carIdx;
}
}
cout << '#' << test_case << ' ' << sumPrice << '\n';
}
}
안쪽 루프 변수를 j로 쓴 건 바깥 루프가 이미 i를 쓰고 있어서다. 처음엔 안쪽도 i라 shadowing이 나 있었다. 컴파일은 되지만 바깥 i를 가려버리니 읽는 사람이 헷갈린다.
std::queue::pop()은 값을 안 준다
대기열에서 차를 꺼낼 때 걸렸다. 파이썬 deque.popleft()는 앞에서 빼면서 그 값을 돌려주는데, std::queue::pop()은 void를 반환한다. 값을 쓰려면 front()로 먼저 읽고 그다음에 pop()으로 지워야 한다.
carIdx = line.front(); // 값을 먼저 읽고
line.pop(); // 그다음에 지운다
빈 큐에 front()나 pop()을 부르면 검사 없이 undefined behavior라, 위 코드가 if (line.empty()) continue; 뒤에 있는 게 중요하다.
Python deque
|
C++ std::queue
|
|
|---|---|---|
| 꺼내기 |
popleft() — 값을 돌려준다 |
front() + pop() — 두 단계 |
| 비었을 때 | IndexError |
undefined behavior |
정수 하나가 넘칠 수 있을까
sumPrice를 long long으로 바꿔놓고 나서 걸리는 게 있었다. 저장할 변수만 넓히면 곱셈 결과도 넓게 계산되나?
아니다. C++에서 곱셈은 피연산자의 타입으로 먼저 계산되고, 그 결과가 대입된다. int * int는 int로 계산돼서 넘칠 값이면 넘친 뒤에 long long으로 옮겨진다. 실제로 돌려보면 이렇다.
int x = 2000000, y = 2000;
long long v1 = 1LL * x * y; // 4000000000
long long v2 = (long long)(x * y); // -294967296
v2는 이미 망가진 값을 뒤늦게 넓힌 것이다. 넓힐 타입은 첫 번째 곱셈에 참여해야 한다.
| 쓰는 법 | 안전한가 | 왜 |
|---|---|---|
1LL * a * b |
O | 왼쪽부터 계산하니 첫 곱이 long long * int
|
a * b * 1LL |
X |
a * b가 먼저 int로 끝난다 |
(long long)(a * b) |
X | 괄호 안이 이미 int 계산 |
그리고 1L이 아니라 1LL이어야 한다. Windows/MSVC는 LLP64라 long이 32bit다. 1L로는 넓혀지지 않는다.( Microsoft 문서 기준 long 4바이트, long long 8바이트 )
그래서 이 문제는 어디까지 위험한가를 계산해봤다. 최대 수입은 차 2000대 × 무게 10000 × 단가 100 = 2 × 10⁹이고, INT_MAX는 2,147,483,647이다. int로도 통과는 한다. 다만 여유가 7%쯤이라 long long으로 갔다.
위험이 어디 있었는지를 갈라 보면 이렇다.
-
단일 곱
parkPrices[j] * carWeights[carIdx]는 최대100 × 10000 = 10⁶이다.int로 넉넉하다 -
누적합
sumPrice는 최대2 × 10⁹이다. 여기가 좁은 쪽이다
그래서 최종 코드에는 곱셈 지점에 1LL *이 없고 sumPrice만 long long이다. 이 문제에서는 그게 맞다. 위험한 건 곱셈이 아니라 쌓이는 쪽이었다. 1LL *은 한 번의 곱만으로도 int를 넘을 때 쓰는 것이고, 이번엔 그 조건이 아니었다.
덧붙이면 부호 있는 정수의 오버플로는 wrap-around가 보장되는 게 아니라 undefined behavior다. 위의 -294967296은 내 환경에서 관찰된 값이지 표준이 약속하는 값이 아니다.
Python과 견줘 보면
두 문제를 두 언어로 짜면서 갈린 지점들이다.
| 하는 일 | Python | C++ |
|---|---|---|
| 대기열 꺼내기 |
deque.popleft() — 값이 나온다 |
front() 읽고 pop()
|
| “끝까지 못 찾음” | for ... else |
bool flag |
| 빈 칸 표시 | 무게를 담으니 0으로 충분 |
인덱스를 담으니 -1
|
| 큰 수 | 정수가 알아서 커진다 |
long long, 곱셈 지점은 1LL *
|
| 입력 읽기 실패 |
ValueError로 터진다 |
조용히 0이 들어오고 failbit |
| 직전 값만 필요할 때 | 리스트째 받아도 편하다 | 변수 하나로 O(1) 공간 |
다섯 번째 줄이 이번에 시간을 제일 많이 먹은 줄이다. 같은 BOM 붙은 파일을 파이썬 쪽에 주면 이렇게 나온다.
File "carrot.py", line 1, in <module>
T = int(input())
^^^^^^^^^^^^
ValueError: invalid literal for int() with base 10: '\ufeff4'
어느 줄에서 무슨 값 때문에 실패했는지가 메시지에 다 있다. '\ufeff4'라고 찍히니 BOM이라는 것까지 보인다. C++은 같은 상황에서 0을 조용히 넣고 그다음부터 입력을 무시한다. 언어가 실패를 알려주지 않으면 실패를 확인하는 순서를 내가 갖고 있어야 한다는 게 이번 차이의 값이었다.
소감
파이썬으로 이미 맞춰놓은 로직이라 옮기기만 하면 될 줄 알았는데, 정작 시간을 쓴 건 알고리즘이 아니라 빌드·입력·타입 쪽이었다. 빌드 오류는 메시지에 고칠 방법까지 적혀 있어서 금방 끝났고, 오래 붙잡은 건 아무 말도 없이 지나간 나머지 둘이다..
freopen 반환값 → 첫 값 → 인코딩 순서는 다음에도 그대로 쓸 수 있을 것 같다!