컴퓨터프로그래밍I - 문제 풀이
경기과학고등학교 2026 직보 3주
배열
배열이 필요한 이유
변수 100,000개가 필요하다고 해 보자. 이름을 하나하나 다르게 짓는 건 쓸 수 없다.
int score1, score2, score3, ..., score100000; // 이건 말이 안 된다같은 이름에 번호를 붙여 쓰면 편하다. 이게 바로 배열(array)이다.
int score[100000]; // 한 줄이면 된다
score[0] = 95;
score[99999] = 87;배열은 같은 타입의 데이터를 연속된 메모리에 모아 놓은 자료 구조다. 대부분의 프로그래밍 언어가 기본으로 지원한다.
1차원 정수 배열
선언과 초기화
배열을 만드는 방법은 여러 가지다.
// 1. 선언과 동시에 초기화
int a[5] = {10, 20, 30, 40, 50};
// 2. 크기를 생략하면 초기화 값 개수로 결정
int b[] = {1, 2, 3, 4, 5, 6, 7, 8, 9}; // 크기: 9
// 3. 일부만 초기화 - 나머지는 0
int c[10] = {1, 2, 3}; // {1, 2, 3, 0, 0, 0, 0, 0, 0, 0}
// 4. 전부 0으로 초기화
int d[100] = {0};
// 5. 선언만 하고 나중에 값을 넣기
int e[5];
e[0] = 100;
e[1] = 200;지역 변수로 선언한 배열을 초기화하지 않으면 쓰레기값이 들어 있다. 반드시 초기화하거나 값을 넣은 뒤에 읽어야 한다.
int arr[5]; // 쓰레기값 - 뭐가 들었는지 알 수 없다
printf("%d", arr[0]); // 예측 불가능한 값이 나온다크기 초과 초기화
배열 크기보다 많은 값으로 초기화하면 컴파일 에러가 난다.
int arr[3] = {1, 2, 3, 4, 5}; // 에러: 크기 3인데 값이 5개여담: 배열은 왜 0부터 셀까
C에서 arr[i]는 내부적으로 *(arr + i)와 같다. arr이 시작 주소일 때, 첫 원소는 시작 주소에서 0칸 떨어져 있으므로 arr[0]이 된다.
Dijkstra도 1982년에 “Why numbering should start at zero”라는 글에서 0부터 세는 게 수학적으로 깔끔하다고 했다. 범위를 [0, n)으로 쓰면 원소 개수가 n - 0 = n으로 바로 나온다.
Pascal이나 Lua는 1부터 시작하지만, C 계열 언어(C++, Java, Python, JavaScript)는 전부 0부터다.
여담: C는 왜 배열 경계를 검사하지 않을까
Java에서 arr[100]에 접근하면 ArrayIndexOutOfBoundsException이 뜬다. Python도 IndexError를 낸다. 그런데 C는 아무 경고 없이 엉뚱한 메모리를 읽거나 쓴다.
이건 C의 설계 철학 때문이다. C를 만든 Dennis Ritchie와 Ken Thompson은 “프로그래머를 믿는다”는 원칙을 따랐다. 배열 접근마다 범위를 검사하면 느려지는데, 당시(1970년대) 컴퓨터는 지금보다 수천 배 느렸으므로 이런 오버헤드를 감수할 여유가 없었다.
덕분에 C는 빨라졌지만, 보안 문제의 불씨가 되기도 했다. 1988년 Morris Worm은 gets() 함수의 버퍼 오버플로우를 이용해 인터넷의 약 10%를 감염시켰다. 2014년 Heartbleed 취약점도 배열 경계 미검사가 원인이었다. OpenSSL이 클라이언트가 보낸 길이 값을 검증하지 않고 그만큼 메모리를 복사해 돌려보내서, 서버의 비밀 키나 비밀번호가 유출될 수 있었다.
Rust 같은 현대 언어는 컴파일 시점에 메모리 안전성을 보장하면서도 C에 가까운 성능을 내는 방향으로 이 문제를 풀려 하고 있다.
여담: off-by-one 에러
배열 프로그래밍에서 가장 흔한 실수가 off-by-one 에러다. 인덱스를 1 잘못 잡는 것이다.
// 틀린 코드: i <= n이면 arr[n]에 접근하는데, 이건 범위 밖이다
for (int i = 0; i <= n; i++)
arr[i] = 0;
// 맞는 코드
for (int i = 0; i < n; i++)
arr[i] = 0;이 에러에는 “울타리 기둥 문제”(fencepost problem)라는 별명이 있다. 100미터 울타리를 10미터 간격으로 세우면 기둥이 몇 개 필요할까? 10개가 아니라 11개다. 구간과 경계점의 개수가 1 차이나기 때문이다.
off-by-one은 경험 많은 개발자도 자주 저지른다. <와 <=, i = 0과 i = 1을 헷갈리기 쉬우니, 반복문을 쓸 때마다 경계값을 한 번 더 확인하는 습관이 좋다.
문제: 1차원 정수 배열
문제 1 - 배열 출력
다음 코드의 출력 결과를 구하라.
#include <stdio.h>
#define MAX 10
int main() {
int a[MAX] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
for (int i = 0; i < MAX; i++)
printf("%d ", a[i]);
return 0;
}a[0]부터 a[9]까지 순서대로 출력한다.
0 1 2 3 4 5 6 7 8 9#define MAX 10은 전처리기가 코드에서 MAX를 전부 10으로 바꾸는 것이다. 배열 크기를 매크로로 정의해 두면 나중에 크기를 바꿀 때 한 곳만 고치면 된다.
문제 2 - 역순 출력
다음 코드의 출력 결과를 구하라.
#include <stdio.h>
int main() {
int arr[] = {3, 1, 4, 1, 5, 9, 2, 6};
int n = sizeof(arr) / sizeof(arr[0]);
for (int i = n - 1; i >= 0; i--)
printf("%d ", arr[i]);
return 0;
}sizeof(arr) / sizeof(arr[0])은 배열 전체 바이트를 원소 하나의 바이트로 나눈 것이므로, 원소 개수 8을 구한다.
i가 7부터 0까지 줄어들며 역순으로 출력한다.
6 2 9 5 1 4 1 3문제 3 - 누적 합
다음 코드의 출력 결과를 구하라.
#include <stdio.h>
int main() {
int a[] = {2, 5, 1, 8, 3};
int sum = 0;
for (int i = 0; i < 5; i++) {
sum += a[i];
a[i] = sum;
}
for (int i = 0; i < 5; i++)
printf("%d ", a[i]);
return 0;
}첫 번째 반복에서 a[i]를 누적 합으로 덮어쓴다.
| i | a[i] (원래) | sum | a[i] (변경 후) |
|---|---|---|---|
| 0 | 2 | 2 | 2 |
| 1 | 5 | 7 | 7 |
| 2 | 1 | 8 | 8 |
| 3 | 8 | 16 | 16 |
| 4 | 3 | 19 | 19 |
출력:
2 7 8 16 19이런 누적 합(prefix sum) 배열은 구간 합을 빠르게 구할 때 자주 쓰인다. 예를 들어 원래 배열에서 a[2]부터 a[4]까지의 합은 prefix[4] - prefix[1] = 19 - 7 = 12로 한 번에 구할 수 있다.
문제 4 - 최댓값과 위치
다음 코드의 출력 결과를 구하라.
#include <stdio.h>
int main() {
int arr[] = {42, 17, 93, 65, 28, 93, 11};
int n = 7;
int max_val = arr[0];
int max_idx = 0;
for (int i = 1; i < n; i++) {
if (arr[i] > max_val) {
max_val = arr[i];
max_idx = i;
}
}
printf("%d %d\n", max_val, max_idx);
return 0;
}배열에서 가장 큰 값과 그 인덱스를 찾는 코드다.
| i | arr[i] | max_val | max_idx |
|---|---|---|---|
| 0 | 42 | 42 | 0 |
| 1 | 17 | 42 | 0 |
| 2 | 93 | 93 | 2 |
| 3 | 65 | 93 | 2 |
| 4 | 28 | 93 | 2 |
| 5 | 93 | 93 | 2 |
| 6 | 11 | 93 | 2 |
93이 인덱스 2와 5에 모두 있지만, >(초과)를 쓰므로 처음 나온 위치(2)가 남는다. >=(이상)를 쓰면 마지막 위치(5)가 나온다.
93 2문제 5 - 버블 정렬
다음 코드가 끝나면 배열 a의 내용은?
#include <stdio.h>
int main() {
int a[] = {5, 3, 8, 1, 2};
int n = 5;
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - 1 - i; j++) {
if (a[j] > a[j + 1]) {
int tmp = a[j];
a[j] = a[j + 1];
a[j + 1] = tmp;
}
}
}
for (int i = 0; i < n; i++)
printf("%d ", a[i]);
return 0;
}버블 정렬(bubble sort)이다. 인접한 두 원소를 비교해서 순서가 틀리면 바꾼다. 한 바퀴 돌 때마다 가장 큰 값이 뒤로 밀려나간다.
1회전 (i=0, j=0..3):
- j=0: 5 > 3 → 교환 → {3, 5, 8, 1, 2}
- j=1: 5 > 8? 아님 → 그대로
- j=2: 8 > 1 → 교환 → {3, 5, 1, 8, 2}
- j=3: 8 > 2 → 교환 → {3, 5, 1, 2, 8}
2회전 (i=1, j=0..2):
- j=0: 3 > 5? 아님
- j=1: 5 > 1 → 교환 → {3, 1, 5, 2, 8}
- j=2: 5 > 2 → 교환 → {3, 1, 2, 5, 8}
3회전 (i=2, j=0..1):
- j=0: 3 > 1 → 교환 → {1, 3, 2, 5, 8}
- j=1: 3 > 2 → 교환 → {1, 2, 3, 5, 8}
4회전 (i=3, j=0):
- j=0: 1 > 2? 아님
1 2 3 5 8버블 정렬의 시간복잡도는 \(O(n^2)\)이다. 원소가 10만 개면 약 100억 번 비교해야 하므로 데이터가 많으면 너무 느리다. 하지만 구현이 단순해서 정렬 알고리즘을 처음 배울 때 자주 등장한다.
문제 5.5 - 에라토스테네스의 체
1 이상 n 이하의 소수를 전부 출력하라. (n ≤ 1,000,000)
에라토스테네스의 체(Sieve of Eratosthenes)는 기원전 3세기 그리스 수학자 에라토스테네스가 고안한 알고리즘이다. 배열을 “체”처럼 써서, 소수가 아닌 수를 걸러낸다.
#include <stdio.h>
#include <stdbool.h>
#define MAX 1000001
bool is_prime[MAX];
int main() {
int n;
scanf("%d", &n);
// 처음에 전부 true로 놓고
for (int i = 2; i <= n; i++)
is_prime[i] = true;
// 2부터 시작해서 배수를 지운다
for (int i = 2; i * i <= n; i++) {
if (is_prime[i]) {
for (int j = i * i; j <= n; j += i)
is_prime[j] = false;
}
}
for (int i = 2; i <= n; i++)
if (is_prime[i])
printf("%d\n", i);
return 0;
}i * i부터 시작하는 이유: i의 배수 중 i * 2, i * 3, …, i * (i-1)은 이미 2, 3, …, i-1의 배수로 지워져 있다.
is_prime 배열을 전역으로 선언한 이유: 100만 칸짜리 배열은 지역 변수로 잡으면 스택이 넘칠 수 있다. 전역이면 데이터 영역에 잡히므로 안전하다.
시간복잡도는 \(O(n \log \log n)\)으로, 100만까지의 소수를 금방 구할 수 있다. 단순히 각 수마다 나눗셈을 해 보는 \(O(n\sqrt{n})\)보다 빠르다.
에라토스테네스는 소수뿐 아니라 지구의 둘레도 측정했다. 알렉산드리아와 시에네(현재 아스완) 사이의 거리와 태양 그림자 각도를 이용해 약 40,000km라는 답을 얻었는데, 실제 값(40,075km)과 거의 같다. 기원전 3세기에 이 정도 정밀도를 낸 건 놀라운 일이다.
문제 5.7 - 배열 왼쪽 회전
배열의 원소를 왼쪽으로 k칸 회전시킨 결과를 출력하라.
예: {1, 2, 3, 4, 5}를 왼쪽으로 2칸 회전 → {3, 4, 5, 1, 2}
임시 배열을 쓰면 간단하다.
#include <stdio.h>
int main() {
int arr[] = {1, 2, 3, 4, 5};
int n = 5, k = 2;
int tmp[5];
for (int i = 0; i < n; i++)
tmp[i] = arr[(i + k) % n];
for (int i = 0; i < n; i++)
printf("%d ", tmp[i]);
return 0;
}(i + k) % n이 회전의 핵심이다. 인덱스가 끝을 넘으면 %로 다시 앞으로 돌아온다.
임시 배열 없이 제자리(in-place)로 하는 방법도 있다. 배열 전체를 뒤집고, 앞쪽 n-k개를 뒤집고, 뒤쪽 k개를 뒤집는다.
// reverse(arr, l, r): arr[l]..arr[r]을 뒤집는 함수
reverse(arr, 0, n - 1); // {5, 4, 3, 2, 1}
reverse(arr, 0, n - k - 1); // {3, 4, 5, 2, 1}
reverse(arr, n - k, n - 1); // {3, 4, 5, 1, 2}이 “세 번 뒤집기” 기법은 문자열 회전 문제에서도 똑같이 쓸 수 있다.
여담: 정렬 알고리즘의 세계
정렬은 컴퓨터 과학에서 오래전부터 많이 연구된 주제다.
- 버블 정렬: \(O(n^2)\). 배울 때는 좋지만 데이터가 크면 느리다. Barack Obama이 Google 면접에서 “버블 정렬은 쓰면 안 된다”고 답해서 유명해졌다.
- 삽입 정렬: \(O(n^2)\)이지만 거의 정렬된 데이터에서는 \(O(n)\)에 가깝다. 카드 게임에서 손에 든 패를 정리하는 방식과 같다.
- 병합 정렬: \(O(n \log n)\). 분할 정복(divide and conquer) 기법으로 동작한다.
- 퀵 정렬: 평균 \(O(n \log n)\), 최악 \(O(n^2)\). C 표준 라이브러리의
qsort()가 보통 이 변형을 쓴다.
C 표준 라이브러리에는 qsort() 함수가 있어서, 직접 정렬을 구현할 필요가 없는 경우가 많다.
#include <stdlib.h>
int compare(const void *a, const void *b) {
return *(int *)a - *(int *)b;
}
int main() {
int arr[] = {5, 3, 8, 1, 2};
qsort(arr, 5, sizeof(int), compare);
// arr = {1, 2, 3, 5, 8}
}지역 변수와 전역 변수
개념
int main()같은 함수 안에서 선언한 변수는 지역 변수(local variable)다. 그 함수가 끝나면 사라진다.- 함수 바깥에서 선언한 변수는 전역 변수(global variable)다. 프로그램이 끝날 때까지 유지된다.
#include <stdio.h>
int global_arr[100]; // 전역: 자동으로 0으로 초기화
int main() {
int local_arr[100]; // 지역: 쓰레기값
printf("%d\n", global_arr[0]); // 0
printf("%d\n", local_arr[0]); // 예측 불가능
return 0;
}- 전역 배열: 초기값이 자동으로 0이 된다. 크기를 크게 잡을 수 있다 (데이터 영역에 저장).
- 지역 배열: 초기화하지 않으면 쓰레기값이다. 크기가 너무 크면 스택 오버플로우가 날 수 있다 (스택에 저장).
문제 6 - 전역 변수와 지역 변수
다음 코드의 출력 결과를 구하라.
#include <stdio.h>
int x = 10;
void foo() {
int x = 20;
printf("%d ", x);
x = 30;
printf("%d ", x);
}
int main() {
printf("%d ", x);
foo();
printf("%d\n", x);
return 0;
}main시작: 전역x는 10 → 출력10foo()호출: 지역x = 20선언 (전역x를 가림) → 출력20foo()안에서x = 30: 지역x만 바뀜 → 출력30foo()종료: 지역x사라짐main으로 돌아옴: 전역x는 여전히 10 → 출력10
10 20 30 10지역 변수가 전역 변수와 이름이 같으면 지역 변수가 우선한다. 이를 이름 가림(shadowing)이라 한다.
여담: 전역 변수를 피해야 하는 이유
전역 변수는 편리하지만, 프로그램이 커지면 문제가 된다.
- 어디서든 값을 바꿀 수 있어서 버그 원인을 찾기 어렵다.
- 함수가 전역 변수에 의존하면, 같은 함수를 다른 곳에서 재사용하기 어렵다.
- 멀티스레드 프로그램에서 동시에 접근하면 경쟁 조건(race condition)이 생긴다.
다만, PS(Problem Solving)에서는 큰 배열을 전역으로 선언하는 게 관례다. 스택 크기 제한(보통 1~8MB)을 피하려면 전역(데이터 영역)에 놓는 게 안전하기 때문이다.
int dp[1000001]; // PS에서 이렇게 전역으로 선언하는 건 괜찮다문자 배열
C 문자열의 구조
C에는 문자열 타입이 따로 없다. char 배열로 문자열을 표현하고, 끝에 널 문자('\0')를 붙여서 어디서 끝나는지 표시한다.
char s1[] = "Hello";
// 메모리: ['H']['e']['l']['l']['o']['\0']
// sizeof(s1) = 6 (문자 5개 + 널 문자 1개)
char s2[] = {'H', 'e', 'l', 'l', 'o'};
// sizeof(s2) = 5 (널 문자 없음 - 이건 "문자열"이 아니라 "문자 배열"이다)"Hello"처럼 큰따옴표로 쓰면 컴파일러가 자동으로 '\0'을 붙인다. 중괄호 초기화는 직접 '\0'을 넣어야 한다.
문제 7 - 문자 배열 조작
다음 코드의 출력 결과를 구하라.
#include <stdio.h>
int main() {
char s[100] = "A";
s[0] = 'H';
printf("%s", s);
s[1] = 'i';
s[2] = '\0';
printf("%s", s);
return 0;
}단계별로 메모리 상태를 보자.
char s[100] = "A"→ s ={'A', '\0', 0, 0, ...}(나머지 98칸은 0)s[0] = 'H'→ s ={'H', '\0', 0, 0, ...}printf("%s", s)→'\0'까지 읽으므로"H"출력s[1] = 'i'→ s ={'H', 'i', 0, 0, ...}(s[2]가 이미 0이므로'\0'역할)s[2] = '\0'→ s ={'H', 'i', '\0', 0, ...}(사실 바뀌는 게 없다)printf("%s", s)→"Hi"출력
HHi두 printf를 합치면 "H" + "Hi" = "HHi"다. printf에 \n이 없으므로 한 줄에 붙어 나온다.
문제 8 - 문자열 길이 구하기
널 문자를 이용해 문자열 길이를 구하는 함수를 작성하라.
int my_strlen(char s[]) {
// 여기를 채우시오
}int my_strlen(char s[]) {
int len = 0;
while (s[len] != '\0')
len++;
return len;
}'\0'이 나올 때까지 한 칸씩 세면 된다. 이 방식은 문자열 길이에 비례하는 시간이 걸린다 - \(O(n)\).
C 표준 라이브러리의 strlen() 함수도 원리는 같다. 그래서 반복문 안에서 strlen()을 매번 호출하면 느려질 수 있다.
// 느린 코드 - 매번 strlen() 호출 (O(n²))
for (int i = 0; i < strlen(s); i++) { ... }
// 빠른 코드 - 길이를 한 번만 구함 (O(n))
int len = strlen(s);
for (int i = 0; i < len; i++) { ... }C++의 std::string에서는 .size()와 .length()가 \(O(1)\)에 동작한다. 내부적으로 길이를 따로 저장하고 있기 때문이다.
문제 9 - 대소문자 변환
다음 코드의 출력 결과를 구하라.
#include <stdio.h>
int main() {
char s[] = "Hello, World!";
for (int i = 0; s[i] != '\0'; i++) {
if (s[i] >= 'A' && s[i] <= 'Z')
s[i] = s[i] + 32;
else if (s[i] >= 'a' && s[i] <= 'z')
s[i] = s[i] - 32;
}
printf("%s\n", s);
return 0;
}ASCII에서 대문자와 소문자의 차이는 32다. 'A'(65)에 32를 더하면 'a'(97)이 된다.
이 코드는 대문자를 소문자로, 소문자를 대문자로 바꾼다. 알파벳이 아닌 문자(,, , !)는 그대로 둔다.
hELLO, wORLD!32라는 숫자는 2진수로 00100000이다. 비트 5 하나만 다른 셈이다. 실제로 s[i] ^= 32로도 대소문자를 뒤집을 수 있다. ASCII가 이렇게 설계된 건 우연이 아니다 - 비트 연산 한 번으로 대소문자를 바꿀 수 있게 일부러 맞춘 것이다.
문제 9.5 - 시저 암호
시저 암호(Caesar cipher)는 각 알파벳을 일정한 칸수만큼 밀어서 암호화하는 방식이다. 예를 들어 3칸 밀면 A→D, B→E, …, X→A, Y→B, Z→C가 된다.
문자열과 밀 칸수 k가 주어질 때, 암호화된 문자열을 출력하라. 알파벳이 아닌 문자는 그대로 둔다.
#include <stdio.h>
#include <string.h>
int main() {
char s[] = "Hello, World!";
int k = 3;
int len = strlen(s);
for (int i = 0; i < len; i++) {
if (s[i] >= 'A' && s[i] <= 'Z')
s[i] = (s[i] - 'A' + k) % 26 + 'A';
else if (s[i] >= 'a' && s[i] <= 'z')
s[i] = (s[i] - 'a' + k) % 26 + 'a';
}
printf("%s\n", s); // Khoor, Zruog!
return 0;
}s[i] - 'A'로 0~25 범위의 수를 만들고, k를 더한 뒤 % 26으로 Z를 넘으면 A로 돌아오게 한다.
시저 암호의 이름은 Julius Caesar에서 왔다. 로마 시대에 Caesar가 군사 통신에 3칸 밀기를 썼다고 한다. 오늘날 기준으로는 26가지 경우를 다 시도하면 바로 풀리므로 암호로서 가치는 없지만, 암호학의 시작점으로 의미가 있다.
ROT13은 시저 암호에서 k=13인 특수한 경우다. 26글자의 절반이 13이므로, ROT13을 두 번 적용하면 원래 문장으로 돌아온다. 인터넷 초창기에 스포일러를 가리는 용도로 많이 쓰였다.
문제 9.7 - 아나그램 판별
두 문자열이 아나그램(anagram)인지 판별하라. 아나그램이란 한 단어의 글자를 재배열해서 다른 단어를 만들 수 있는 관계다.
예: "listen", "silent" → 아나그램 / "hello", "world" → 아나그램 아님
각 알파벳의 등장 횟수가 같으면 아나그램이다.
#include <stdio.h>
#include <string.h>
int is_anagram(char *a, char *b) {
if (strlen(a) != strlen(b)) return 0;
int count[26] = {0};
for (int i = 0; a[i]; i++) count[a[i] - 'a']++;
for (int i = 0; b[i]; i++) count[b[i] - 'a']--;
for (int i = 0; i < 26; i++)
if (count[i] != 0) return 0;
return 1;
}
int main() {
printf("%d\n", is_anagram("listen", "silent")); // 1
printf("%d\n", is_anagram("hello", "world")); // 0
return 0;
}첫 번째 문자열에서 각 글자를 세고, 두 번째 문자열에서 빼면, 아나그램이면 전부 0이 된다.
정렬로도 풀 수 있다. 두 문자열을 각각 알파벳순으로 정렬하면 아나그램은 같은 문자열이 된다. 하지만 정렬은 \(O(n \log n)\)이고 빈도 세기는 \(O(n)\)이므로 빈도 세기가 더 빠르다.
실제로 아나그램은 영어 단어 퍼즐에서 많이 쓰인다. “dormitory”와 “dirty room”, “astronomer”와 “moon starer” 같은 유명한 아나그램 쌍이 있다.
여담: ASCII 코드의 비밀
ASCII는 1963년에 만들어졌다. 겨우 7비트(128개 문자)로 영어 알파벳, 숫자, 기호를 담았다.
의도적으로 넣은 패턴이 몇 가지 있다.
- 숫자
'0'~'9'의 하위 4비트가 0~9다.'7' & 0x0F만으로 숫자값 7을 얻을 수 있다. - 대문자 A~Z는 65~90, 소문자 a~z는 97~122. 차이가 정확히 32(비트 5)다.
- 제어 문자(0~31)는 통신 장비 제어용이었다.
'\n'(10),'\t'(9),'\0'(0) 정도가 아직 쓰인다.
ASCII의 한계는 영어만 지원한다는 점이다. 한국어, 중국어, 일본어 같은 문자는 담을 수 없어서 나중에 유니코드(Unicode)가 나왔다. 유니코드는 15만 자 이상을 담을 수 있고, 이모지도 여기에 포함된다.
2차원 배열
선언과 초기화
2차원 배열은 표(행렬)처럼 생각하면 된다.
// 2행 3열 배열
int m[2][3] = {
{1, 2, 3},
{4, 5, 6}
};
// 중괄호 없이 써도 행 순서대로 채운다
int m2[2][3] = {1, 2, 3, 4, 5, 6};
// 일부만 초기화 - 나머지는 0
int m3[2][3] = {
{1, 2}, // {1, 2, 0}
{3} // {3, 0, 0}
};
// 행 수 생략 가능 (열 수는 반드시 써야 함)
int m4[][3] = {1, 2, 3, 4, 5, 6}; // 2행 3열열 수는 생략할 수 없다. 컴파일러가 메모리에 일렬로 배치할 때 한 행의 크기를 알아야 하기 때문이다.
메모리 배치
2차원 배열은 메모리에 행 우선(row-major)으로 일렬로 저장된다.
m[0][0] m[0][1] m[0][2] m[1][0] m[1][1] m[1][2]
┌──────┬──────┬──────┬──────┬──────┬──────┐
│ 1 │ 2 │ 3 │ 4 │ 5 │ 6 │
└──────┴──────┴──────┴──────┴──────┴──────┘m[i][j]의 실제 위치는 m + i * 열수 + j로 계산된다.
문제 10 - 2차원 배열 초기화
다음 각 선언 후 배열의 내용은?
// (a)
int a[2][3] = {0, 1, 2, 3};
// (b)
int b[3][2] = {{1}, {2}, {3}};
// (c)
char c[3][6] = {"hello", "world", "c"};(a) 값이 행 순서대로 채워지고 나머지는 0:
a = {{0, 1, 2},
{3, 0, 0}}(b) 각 행의 첫 원소만 지정하고 나머지는 0:
b = {{1, 0},
{2, 0},
{3, 0}}(c) 문자열은 널 문자('\0')를 포함해서 저장된다:
c[0] = {'h','e','l','l','o','\0'} // "hello" (5+1 = 6바이트, 딱 맞음)
c[1] = {'w','o','r','l','d','\0'} // "world" (5+1 = 6바이트)
c[2] = {'c','\0', 0, 0, 0, 0 } // "c" (1+1 = 2바이트, 나머지 0)문자열 "hello"는 길이가 5이지만 널 문자 포함 6바이트를 차지한다. 열 크기를 6으로 잡은 이유다. 5로 잡으면 널 문자가 들어갈 자리가 없어서 printf("%s", c[0])이 엉뚱한 결과를 낼 수 있다.
문제 11 - 행렬 전치
다음 코드의 출력 결과를 구하라.
#include <stdio.h>
int main() {
int m[3][3] = {
{1, 2, 3},
{4, 5, 6},
{7, 8, 9}
};
// 전치 (행과 열을 바꿈)
for (int i = 0; i < 3; i++) {
for (int j = i + 1; j < 3; j++) {
int tmp = m[i][j];
m[i][j] = m[j][i];
m[j][i] = tmp;
}
}
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++)
printf("%d ", m[i][j]);
printf("\n");
}
return 0;
}전치(transpose)는 행과 열을 바꾸는 연산이다. m[i][j]와 m[j][i]를 교환한다.
j = i + 1부터 시작하는 이유: 대각선 위쪽 원소만 아래쪽과 교환하면 된다. 전체를 다 돌면 두 번 교환해서 원래대로 돌아간다.
원래:
1 2 3
4 5 6
7 8 9전치 후:
1 4 7
2 5 8
3 6 9행렬 전치는 선형대수에서 기본 연산이다. 이미지 처리에서 90도 회전, 그래프의 인접 행렬 뒤집기 등에 쓰인다.
문제 12 - 2차원 배열 탐색
다음 코드가 “Found”를 출력하는가?
#include <stdio.h>
int main() {
int grid[4][4] = {
{ 1, 2, 3, 4},
{ 5, 6, 7, 8},
{ 9, 10, 11, 12},
{13, 14, 15, 16}
};
int target = 11;
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
if (grid[i][j] == target) {
printf("Found at (%d, %d)\n", i, j);
goto done;
}
}
}
printf("Not found\n");
done:
return 0;
}grid[2][2] = 11이므로 i=2, j=2일 때 조건이 참이 된다.
Found at (2, 2)goto done으로 이중 반복문을 한 번에 빠져나온다. break는 안쪽 반복문만 빠져나오므로, 이중 반복을 한 번에 빠져나올 때 goto가 쓸 만하다.
goto를 쓰기 싫다면 플래그 변수를 쓰는 방법도 있다:
int found = 0;
for (int i = 0; i < 4 && !found; i++)
for (int j = 0; j < 4 && !found; j++)
if (grid[i][j] == target) {
printf("Found at (%d, %d)\n", i, j);
found = 1;
}
if (!found) printf("Not found\n");여담: 행렬의 실생활 활용
행렬(2차원 배열)은 여러 분야에서 쓰인다.
- 이미지: 흑백 사진이 곧 2차원 배열이다. 각 칸에 0(검정)~255(흰색) 밝기값이 들어 있다. 컬러 사진은 RGB 3개 채널이므로 3차원 배열이다.
- 게임 맵: 체스판, 지뢰찾기, 미로 탐색 등 격자 위에서 동작하는 프로그램은 전부 2차원 배열을 쓴다.
- 그래프: 정점 n개짜리 그래프의 간선 정보를 n×n 인접 행렬(adjacency matrix)로 저장할 수 있다.
- 스프레드시트: Excel의 셀이 곧 2차원 배열이다.
행렬 곱셈은 딥러닝(deep learning)에서도 가장 많이 쓰는 연산이다. GPU가 빠른 것도 행렬 곱셈을 병렬로 처리하게 만들어졌기 때문이다.
여담: 지뢰찾기와 2차원 배열
Windows에 기본으로 들어 있던 지뢰찾기(Minesweeper)는 2차원 배열로 구현할 수 있는 대표적인 프로그램이다.
int board[R][C]: 각 칸에 지뢰 여부를 저장 (-1이면 지뢰, 아니면 주변 지뢰 수)- 한 칸을 열 때 주변 8방향을 검사해서 지뢰 수를 세야 한다
8방향 탐색은 방향 배열로 쓰면 깔끔하다:
int dr[] = {-1, -1, -1, 0, 0, 1, 1, 1};
int dc[] = {-1, 0, 1,-1, 1,-1, 0, 1};
int count_mines(int board[][C], int r, int c) {
int count = 0;
for (int d = 0; d < 8; d++) {
int nr = r + dr[d], nc = c + dc[d];
if (nr >= 0 && nr < R && nc >= 0 && nc < C)
if (board[nr][nc] == -1)
count++;
}
return count;
}이 “방향 배열 + 범위 검사” 패턴은 BFS, DFS, 시뮬레이션 등 격자 위에서 동작하는 거의 모든 알고리즘에서 쓰인다. 한 번 익혀 두면 두고두고 쓸 수 있다.
지뢰찾기가 Windows에 들어간 이유는 마우스 사용법을 알려주기 위해서였다. 왼쪽 클릭(열기)과 오른쪽 클릭(깃발 꽂기)을 자연스럽게 연습하게 만든 것이다. 솔리테어(Solitaire)도 마찬가지로, 드래그 앤 드롭을 연습시키려고 넣었다.
문제 12.5 - 행렬 덧셈
\(m \times n\) 행렬 두 개가 주어질 때 두 행렬의 합을 출력하라.
같은 위치의 원소끼리 더하면 된다.
#include <stdio.h>
int main() {
int m, n;
scanf("%d %d", &m, &n);
int a[100][100], b[100][100], c[100][100];
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
scanf("%d", &a[i][j]);
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
scanf("%d", &b[i][j]);
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
c[i][j] = a[i][j] + b[i][j];
printf("%d ", c[i][j]);
}
printf("\n");
}
return 0;
}행렬 덧셈은 같은 크기의 행렬에서만 정의된다. 곱셈은 왼쪽 행렬의 열 수와 오른쪽 행렬의 행 수가 같아야 한다. 3×2 행렬과 2×4 행렬을 곱하면 3×4 행렬이 나온다.
배열 심화
배열과 포인터
C에서 배열 이름은 첫 번째 원소의 주소와 같다. 그래서 배열과 포인터가 얽혀 있다.
int arr[5] = {10, 20, 30, 40, 50};
int *p = arr; // arr == &arr[0]
printf("%d\n", *p); // 10
printf("%d\n", *(p + 2)); // 30
printf("%d\n", p[3]); // 40 (p[i]는 *(p+i)와 같다)포인터에 정수를 더하면 sizeof(타입) 단위로 이동한다. p + 2는 주소가 p + 2 * sizeof(int) = p + 8바이트만큼 이동한다.
배열과 포인터가 비슷하게 동작하지만, 같은 것은 아니다.
int arr[5] = {1, 2, 3, 4, 5};
int *p = arr;
sizeof(arr); // 20 (5 × 4바이트)
sizeof(p); // 8 (포인터 크기, 64비트 시스템)
arr++; // 컴파일 에러 - 배열 이름은 상수
p++; // 가능 - 포인터는 변수sizeof에서 차이가 드러난다. 배열은 전체 크기를, 포인터는 주소의 크기를 돌려준다. 함수에 배열을 넘기면 포인터로 변환(decay)되므로 이 차이가 사라진다.
포인터 산술과 배열 순회
배열을 포인터로 순회하는 방식은 인덱스 방식과 결과가 같다.
// 인덱스 방식
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
// 포인터 방식
for (int *p = arr; p < arr + n; p++)
printf("%d ", *p);두 방식은 성능 차이가 거의 없다. 현대 컴파일러가 최적화해 주기 때문이다. 읽기 쉬운 쪽을 고르면 된다.
배열을 함수에 넘기기
배열을 함수에 넘기면 포인터로 변환된다. 함수 안에서 배열의 크기를 알 수 없으므로, 크기를 따로 넘겨야 한다.
// 이 셋은 전부 같은 의미다
void print_arr(int arr[], int n);
void print_arr(int *arr, int n);
void print_arr(int arr[100], int n); // 100은 무시된다void print_arr(int arr[], int n) {
// sizeof(arr)는 포인터 크기(8)이지, 배열 크기가 아니다
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
}
int main() {
int data[] = {3, 1, 4, 1, 5};
print_arr(data, 5);
return 0;
}함수에 배열을 넘기면 복사가 아니라 주소가 전달된다. 그래서 함수 안에서 배열 원소를 바꾸면 원본이 바뀐다.
void zero_fill(int arr[], int n) {
for (int i = 0; i < n; i++)
arr[i] = 0; // 원본이 바뀐다
}2차원 배열을 함수에 넘기기
2차원 배열을 함수에 넘길 때는 열 수를 명시해야 한다.
// 열 수 3을 반드시 적어야 한다
void print_matrix(int m[][3], int rows) {
for (int i = 0; i < rows; i++) {
for (int j = 0; j < 3; j++)
printf("%d ", m[i][j]);
printf("\n");
}
}
int main() {
int mat[2][3] = {{1,2,3},{4,5,6}};
print_matrix(mat, 2);
return 0;
}열 수가 컴파일 시점에 정해져 있어야 하므로, 열 수가 달라지는 함수를 만들기 어렵다. 이걸 해결하려면 1차원 배열로 펼쳐서 넘기거나, 동적 할당을 쓴다.
문제 A1 - 배열 뒤집기 함수
배열의 원소 순서를 뒤집는 함수 reverse를 작성하라. 함수 호출 후 원본 배열이 바뀌어야 한다.
양쪽 끝에서 안쪽으로 오면서 교환한다.
void reverse(int arr[], int n) {
for (int i = 0; i < n / 2; i++) {
int tmp = arr[i];
arr[i] = arr[n - 1 - i];
arr[n - 1 - i] = tmp;
}
}
int main() {
int a[] = {1, 2, 3, 4, 5};
reverse(a, 5);
// a = {5, 4, 3, 2, 1}
}n / 2번만 교환하면 된다. 짝수든 홀수든 동작한다. 홀수일 때 가운데 원소는 제자리이므로 건드릴 필요 없다.
동적 배열
malloc으로 1차원 동적 배열
크기를 실행 중에 정하려면 malloc을 쓴다.
#include <stdlib.h>
int n;
scanf("%d", &n);
int *arr = (int *)malloc(n * sizeof(int));
if (arr == NULL) {
printf("메모리 할당 실패\n");
return 1;
}
for (int i = 0; i < n; i++)
arr[i] = i * 10;
free(arr); // 다 쓰면 반드시 해제malloc이 돌려주는 포인터는 배열처럼 arr[i]로 접근할 수 있다. arr[i]는 *(arr + i)이므로, 포인터 산술이 그대로 적용된다.
malloc으로 2차원 동적 배열
2차원 배열을 동적으로 잡는 방법은 두 가지다.
방법 1: 포인터 배열 (행마다 따로 할당)
int rows = 3, cols = 4;
// 행 포인터 배열
int **mat = (int **)malloc(rows * sizeof(int *));
for (int i = 0; i < rows; i++)
mat[i] = (int *)malloc(cols * sizeof(int));
// 사용
mat[1][2] = 42;
// 해제 (할당 역순)
for (int i = 0; i < rows; i++)
free(mat[i]);
free(mat);방법 2: 1차원으로 펼치기 (한 번에 할당)
int rows = 3, cols = 4;
int *mat = (int *)malloc(rows * cols * sizeof(int));
// mat[i][j] 대신 mat[i * cols + j]로 접근
mat[1 * cols + 2] = 42;
free(mat); // 해제도 한 번방법 2가 메모리가 연속이라 캐시 효율이 좋고, 할당/해제도 간단하다. PS에서는 보통 전역 배열을 쓰므로 동적 할당을 잘 안 쓰지만, 실무에서는 자주 나온다.
CPU 캐시와 배열
캐시 계층 구조
CPU가 메모리에서 데이터를 가져오려면 시간이 오래 걸린다. 이 속도 차이를 줄이려고 CPU와 메모리 사이에 작고 빠른 저장소를 여러 단계로 둔다. 이게 캐시(cache)다.
CPU 레지스터 ← 1 사이클 (< 1ns)
↕
L1 캐시 ← ~4 사이클 (~1ns), 32~64KB
↕
L2 캐시 ← ~12 사이클 (~3ns), 256KB~1MB
↕
L3 캐시 ← ~40 사이클 (~10ns), 4~64MB (코어 공유)
↕
메인 메모리 ← ~200 사이클 (~60ns), 8~128GB
↕
SSD/디스크 ← ~수만~수십만 사이클L1에서 데이터를 찾으면(cache hit) 1나노초면 되지만, 메인 메모리까지 가야 하면(cache miss) 60나노초 이상 걸린다. 60배 차이다. 같은 코드라도 캐시를 잘 쓰느냐에 따라 성능이 크게 갈린다.
캐시 라인 (Cache Line)
캐시는 바이트 단위가 아니라 캐시 라인(cache line) 단위로 데이터를 가져온다. 대부분의 CPU에서 캐시 라인 크기는 64바이트다.
arr[0]을 읽으면 CPU는 arr[0] 하나만 가져오는 게 아니라, arr[0]이 속한 64바이트 블록을 통째로 캐시에 올린다. int가 4바이트이므로 한 캐시 라인에 int 16개가 들어간다.
메모리: ... | arr[0] arr[1] arr[2] ... arr[15] | arr[16] arr[17] ... | ...
└──── 캐시 라인 1 (64B) ────┘ └──── 캐시 라인 2 ────┘그래서 arr[0]을 읽은 뒤 arr[1], arr[2], …을 읽으면 이미 캐시에 있으므로 빠르다. 이걸 공간 지역성(spatial locality)이라 한다.
반대로 arr[0], arr[1000], arr[2000], …처럼 듬성듬성 접근하면 매번 새 캐시 라인을 가져와야 해서 느리다.
배열 접근 순서와 성능
2차원 배열에서 이 차이가 확실히 보인다.
// 빠른 코드 - 행 우선 접근 (메모리 순서대로)
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
sum += arr[i][j];
// 느린 코드 - 열 우선 접근 (메모리를 건너뛰며)
for (int j = 0; j < N; j++)
for (int i = 0; i < N; i++)
sum += arr[i][j];C의 2차원 배열은 행 우선(row-major)으로 저장되므로, arr[i][0], arr[i][1], arr[i][2], …이 메모리에 연속으로 놓인다.
행 우선 접근은 캐시 라인 하나를 가져오면 그 안의 원소 16개를 연달아 쓴다(int 기준). 열 우선 접근은 한 원소만 쓰고 N칸을 건너뛰므로, N이 크면 매번 캐시 미스가 난다.
N=10000이면 열 우선이 행 우선보다 10배 이상 느릴 수 있다.
참고로 Fortran은 열 우선(column-major)으로 저장한다. Fortran으로 짠 수치 계산 코드를 C로 옮길 때 반복문 순서를 바꿔야 성능이 나온다.
여담: 구조체 배열 vs 배열 구조체
캐시 라인을 의식하면 자료구조 설계도 달라진다.
// AoS (Array of Structures) - 구조체의 배열
struct Particle {
float x, y, z; // 위치
float vx, vy, vz; // 속도
float mass; // 질량
};
struct Particle particles[10000];x좌표만 전부 더하고 싶으면 particles[0].x, particles[1].x, … 을 접근해야 하는데, 사이에 y, z, vx, vy, vz, mass가 끼어 있어서 캐시 효율이 나쁘다. Particle 하나가 28바이트이므로 캐시 라인(64바이트)에 2개밖에 안 들어간다.
// SoA (Structure of Arrays) - 배열의 구조체
struct Particles {
float x[10000], y[10000], z[10000];
float vx[10000], vy[10000], vz[10000];
float mass[10000];
};
struct Particles p;이렇게 하면 p.x[0], p.x[1], p.x[2], …가 메모리에 연속이므로 캐시 라인 하나에 float 16개가 들어간다. x좌표만 순회할 때 훨씬 빠르다.
게임 엔진이나 물리 시뮬레이션에서는 이 차이가 프레임 레이트를 좌우하므로, SoA 쪽을 쓰는 경우가 많다. Unity의 ECS(Entity Component System)나 데이터 지향 설계(Data-Oriented Design)가 같은 생각에서 나왔다.
여담: 프리페치와 CPU의 예측
CPU는 프로그래머가 다음에 어떤 메모리를 읽을지 예측해서, 미리 캐시에 올려 두기도 한다. 이걸 하드웨어 프리페처(hardware prefetcher)라 한다.
배열을 순서대로 접근하면 패턴이 규칙적이라 프리페처가 잘 예측한다. 다음 캐시 라인을 미리 가져다 놓으므로 캐시 미스가 거의 안 난다. 하지만 연결 리스트(linked list)처럼 포인터를 따라가는 접근은 패턴이 불규칙해서 프리페처가 예측하기 어렵다.
그래서 이론적 시간복잡도가 같아도 배열 기반 자료구조가 포인터 기반보다 빠른 경우가 많다. 예를 들어 배열로 만든 이진 힙(binary heap)은 포인터로 만든 이진 탐색 트리(BST)보다 실측 성능이 좋은 경우가 흔하다.
GCC에서는 __builtin_prefetch() 함수로 프리페치를 명시적으로 요청할 수 있다. 하지만 대부분의 경우 하드웨어 프리페처가 알아서 처리하므로, 수동 프리페치가 도움되는 경우는 드물다.
여담: 비순차 실행과 Reorder Buffer
현대 CPU는 명령어를 프로그램에 적힌 순서대로 실행하지 않는다. 비순차 실행(out-of-order execution, OoOE)을 한다.
int a = arr[0]; // 캐시 미스 - 메모리 대기 (~200 사이클)
int b = x + y; // 이건 레지스터끼리 덧셈 - 1 사이클
int c = a + b; // a가 준비될 때까지 대기순차 실행이라면 a를 가져올 때까지 200 사이클을 기다리고 나서 b를 계산한다. 하지만 비순차 실행 CPU는 a를 기다리는 동안 b = x + y를 먼저 계산해 둔다. a가 도착하면 바로 c = a + b를 할 수 있으므로 시간이 절약된다.
이걸 관리하는 장치가 ROB(Reorder Buffer)다. ROB의 역할은:
- 명령어를 순서와 무관하게 실행되도록 허용한다
- 실행이 끝난 결과를 원래 프로그램 순서에 맞게 되돌려 놓는다(retire)
- 예외가 생기면 아직 retire하지 않은 명령어를 취소한다
ROB의 크기가 클수록 더 많은 명령어를 미리 내다볼 수 있다. Intel의 최신 CPU(Golden Cove 아키텍처)는 ROB가 512 항목이다. 즉, 최대 512개의 명령어를 동시에 “비행 중”으로 관리할 수 있다.
배열을 순차 접근하면 캐시 미스가 나더라도, CPU가 뒤쪽 명령어를 미리 실행하면서 대기 시간을 숨길 수 있다. 하지만 접근 패턴이 불규칙하면 다음에 실행할 명령어 자체를 예측하기 어려워서 ROB의 이점이 줄어든다.
여담: 분기 예측과 배열
CPU에는 분기 예측기(branch predictor)도 있다. if문을 만나면 조건을 평가하기 전에, 참일지 거짓일지 미리 예측하고 해당 방향의 코드를 실행해 둔다. 예측이 맞으면 시간을 아끼고, 틀리면(branch misprediction) 미리 실행한 결과를 버리고 다시 한다. 보통 15~20 사이클이 낭비된다.
유명한 예시:
// 정렬된 배열에서 - 분기 예측 잘 맞음 (빠르다)
int sorted[] = {1, 2, 3, ..., 99998, 99999, 100000};
int sum = 0;
for (int i = 0; i < n; i++)
if (sorted[i] >= 50000) sum += sorted[i];
// 정렬 안 된 배열에서 - 분기 예측 자주 틀림 (느리다)
int shuffled[] = {72841, 3, 99102, 451, ...};
int sum = 0;
for (int i = 0; i < n; i++)
if (shuffled[i] >= 50000) sum += shuffled[i];정렬된 배열에서는 앞쪽 절반이 전부 false, 뒤쪽 절반이 전부 true이므로 분기 예측기가 패턴을 쉽게 잡는다. 정렬되지 않은 배열에서는 true/false가 무작위로 섞여서 예측률이 50%에 가까워진다.
이 현상은 Stack Overflow에서 가장 많은 추천을 받은 질문 중 하나인 “Why is processing a sorted array faster than processing an unsorted array?”의 원인이다.
분기 없이 같은 결과를 내는 코드로 바꾸면 이 문제를 피할 수 있다:
// 분기 없는 버전 (branchless)
for (int i = 0; i < n; i++) {
int mask = -(arr[i] >= 50000); // 조건 참이면 -1(0xFFFFFFFF), 거짓이면 0
sum += arr[i] & mask;
}이런 걸 직접 최적화할 일은 잘 없지만, “같은 알고리즘인데 왜 속도가 다르지?”라는 의문이 들 때 원인을 찾는 데 쓸 수 있다.
여담: SIMD와 배열
CPU에는 SIMD(Single Instruction, Multiple Data) 명령어도 있다. 한 번에 여러 데이터를 동시에 처리하는 명령어다.
예를 들어 SSE 명령어는 128비트 레지스터를 써서 float 4개를 한 번에 더할 수 있다. AVX-512는 512비트이므로 float 16개를 동시에 처리한다.
// 일반 코드
for (int i = 0; i < n; i++)
c[i] = a[i] + b[i];
// 컴파일러가 SIMD로 바꾸면 (자동 벡터화)
// 내부적으로 4개씩 묶어서 한 번에 더함
// → 이론상 4배 빠름배열이 메모리에 연속으로 놓여 있으면 컴파일러가 자동으로 SIMD 코드를 만들어 주기도 한다(auto-vectorization). gcc -O2 이상이면 대부분 활성화된다. 연결 리스트 같은 비연속 자료구조에서는 SIMD를 쓰기 어렵다.
NumPy가 순수 Python 반복문보다 수십~수백 배 빠른 것도, 안에서 C로 짠 배열 연산에 SIMD를 쓰기 때문이다.
다차원 배열 심화
3차원 배열
3차원 배열은 “2차원 배열의 배열”이다.
int cube[2][3][4]; // 2 × 3 × 4 = 24칸
// 초기화
int cube[2][3][4] = {
{ // cube[0]
{1, 2, 3, 4},
{5, 6, 7, 8},
{9, 10, 11, 12}
},
{ // cube[1]
{13, 14, 15, 16},
{17, 18, 19, 20},
{21, 22, 23, 24}
}
};3차원 배열은 컬러 이미지(높이 × 너비 × RGB 채널), 3D 공간 데이터(x × y × z), 시계열 행렬(시간 × 행 × 열) 등에 쓰인다.
문제 A2 - 행렬 곱셈
\(A\)는 \(p \times q\) 행렬, \(B\)는 \(q \times r\) 행렬일 때 \(C = A \times B\) (\(p \times r\) 행렬)를 구하라.
행렬 곱셈의 정의: \(C[i][j] = \sum_{k=0}^{q-1} A[i][k] \times B[k][j]\)
#include <stdio.h>
#define MAXN 100
int A[MAXN][MAXN], B[MAXN][MAXN], C[MAXN][MAXN];
int main() {
int p, q, r;
scanf("%d %d %d", &p, &q, &r);
for (int i = 0; i < p; i++)
for (int j = 0; j < q; j++)
scanf("%d", &A[i][j]);
for (int i = 0; i < q; i++)
for (int j = 0; j < r; j++)
scanf("%d", &B[i][j]);
// 행렬 곱셈: C = A × B
for (int i = 0; i < p; i++)
for (int j = 0; j < r; j++) {
C[i][j] = 0;
for (int k = 0; k < q; k++)
C[i][j] += A[i][k] * B[k][j];
}
for (int i = 0; i < p; i++) {
for (int j = 0; j < r; j++)
printf("%d ", C[i][j]);
printf("\n");
}
return 0;
}3중 반복문이므로 시간복잡도는 \(O(pqr)\)이다. 정사각 행렬이면 \(O(n^3)\).
Strassen 알고리즘(1969)은 이걸 \(O(n^{2.807})\)로 줄였고, 이후로도 지수를 줄이는 연구가 계속되고 있다. 2024년 기준 이론적 하한은 \(O(n^{2.371})\) 근처다. 실제 구현에서는 BLAS 라이브러리가 CPU 캐시와 SIMD 명령어를 활용해 이론적 복잡도보다 훨씬 빠르게 동작한다.
문제 A3 - 90도 회전
\(n \times n\) 행렬을 시계 방향으로 90도 회전한 결과를 출력하라.
예: 입력 {{1,2,3},{4,5,6},{7,8,9}} → 출력 {{7,4,1},{8,5,2},{9,6,3}}
시계 방향 90도 회전은 “전치 + 각 행 뒤집기”로 할 수 있다.
#include <stdio.h>
int main() {
int n;
scanf("%d", &n);
int m[100][100];
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
scanf("%d", &m[i][j]);
// 1단계: 전치
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++) {
int tmp = m[i][j];
m[i][j] = m[j][i];
m[j][i] = tmp;
}
// 2단계: 각 행을 좌우 반전
for (int i = 0; i < n; i++)
for (int j = 0; j < n / 2; j++) {
int tmp = m[i][j];
m[i][j] = m[i][n - 1 - j];
m[i][n - 1 - j] = tmp;
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++)
printf("%d ", m[i][j]);
printf("\n");
}
return 0;
}임시 배열 없이 제자리에서(in-place) 회전할 수 있다.
회전 방향별 공식:
- 시계 90도: 전치 → 각 행 뒤집기
- 반시계 90도: 전치 → 각 열 뒤집기 (또는 각 행 뒤집기 → 전치)
- 180도: 각 행 뒤집기 → 각 열 뒤집기
이미지 편집기에서 사진을 회전하는 것도 같은 원리다.
배열 기반 자료구조
배열 하나로 스택, 큐 같은 자료구조를 만들 수 있다.
스택 (Stack)
“나중에 넣은 것을 먼저 꺼내는” 구조(LIFO: Last In, First Out).
#define MAX 10000
int stack[MAX];
int top = -1; // 비어 있으면 -1
void push(int x) { stack[++top] = x; }
int pop() { return stack[top--]; }
int peek() { return stack[top]; }
int is_empty() { return top == -1; }괄호 짝 맞추기, 후위 표기법 계산, DFS 등에서 쓰인다.
큐 (Queue)
“먼저 넣은 것을 먼저 꺼내는” 구조(FIFO: First In, First Out).
#define MAX 10000
int queue[MAX];
int front = 0, rear = 0;
void enqueue(int x) { queue[rear++] = x; }
int dequeue() { return queue[front++]; }
int is_empty() { return front == rear; }BFS, 프린터 대기열, 네트워크 패킷 처리 등에서 쓰인다.
위 구현은 rear가 계속 커져서 배열 끝에 다다르면 공간이 남아도 쓸 수 없다. 이걸 해결한 게 원형 큐(circular queue)다.
원형 큐 (Circular Queue)
#define MAX 10000
int queue[MAX];
int front = 0, rear = 0, count = 0;
void enqueue(int x) {
queue[rear] = x;
rear = (rear + 1) % MAX;
count++;
}
int dequeue() {
int val = queue[front];
front = (front + 1) % MAX;
count--;
return val;
}% MAX로 인덱스를 순환시킨다. 배열 끝에 가면 다시 0으로 돌아온다. 운영체제의 키보드 버퍼, 네트워크 소켓의 수신 버퍼 등이 원형 큐로 구현되어 있다.
문제 A4 - 괄호 짝 맞추기
문자열에 포함된 괄호 (, ), [, ], {, }의 짝이 올바른지 판별하라.
예: "({[]})" → 올바름 / "({[}])" → 올바르지 않음
스택을 쓴다. 여는 괄호는 push, 닫는 괄호는 pop해서 짝이 맞는지 확인한다.
#include <stdio.h>
#include <string.h>
int main() {
char s[100001];
scanf("%s", s);
char stack[100001];
int top = -1;
int valid = 1;
for (int i = 0; s[i] && valid; i++) {
char c = s[i];
if (c == '(' || c == '[' || c == '{') {
stack[++top] = c;
} else if (c == ')' || c == ']' || c == '}') {
if (top == -1) { valid = 0; break; }
char open = stack[top--];
if ((c == ')' && open != '(') ||
(c == ']' && open != '[') ||
(c == '}' && open != '{'))
valid = 0;
}
}
if (top != -1) valid = 0; // 여는 괄호가 남아 있으면 틀림
printf("%s\n", valid ? "YES" : "NO");
return 0;
}스택을 쓰면 딱 맞는 문제다. 컴파일러가 소스 코드의 괄호를 검사할 때도 같은 원리를 쓴다.
배열 알고리즘 심화
이진 탐색 (Binary Search)
정렬된 배열에서 값을 찾을 때, 가운데를 보고 반씩 줄여나가면 \(O(\log n)\)에 찾을 수 있다.
int binary_search(int arr[], int n, int target) {
int lo = 0, hi = n - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2; // (lo + hi) / 2는 overflow 위험
if (arr[mid] == target) return mid;
else if (arr[mid] < target) lo = mid + 1;
else hi = mid - 1;
}
return -1; // 못 찾음
}100만 개 배열에서 선형 탐색은 최악 100만 번 비교하지만, 이진 탐색은 최대 20번(= \(\log_2 1000000 \approx 20\))이면 끝난다.
(lo + hi) / 2 대신 lo + (hi - lo) / 2를 쓰는 이유: lo + hi가 INT_MAX를 넘으면 overflow가 난다. 이 버그는 Java의 Arrays.binarySearch()에도 있었는데, 2006년에야 고쳐졌다. Jon Bentley가 1986년에 쓴 “Programming Pearls”에서 이진 탐색을 설명했지만, 이 overflow 버그가 20년간 발견되지 않았다. “간단한” 알고리즘도 올바르게 구현하기는 쉽지 않다.
문제 A5 - lower_bound 구현
정렬된 배열에서 target 이상인 첫 번째 원소의 인덱스를 구하라. 없으면 n을 돌려줘라.
예: arr = {1, 3, 3, 5, 7}, target = 3 → 인덱스 1 (첫 번째 3의 위치)
이진 탐색의 변형이다. “값이 있는가”가 아니라 “경계가 어디인가”를 찾는다.
int lower_bound(int arr[], int n, int target) {
int lo = 0, hi = n;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (arr[mid] < target)
lo = mid + 1;
else
hi = mid;
}
return lo;
}lo < hi (등호 없음)와 hi = mid (mid - 1 아님)에 주의한다. 일반 이진 탐색과 조건이 미묘하게 다르다.
C++ STL의 std::lower_bound()가 같은 동작을 한다. upper_bound()는 target보다 큰 첫 번째 원소 위치를 돌려준다. 이 둘을 조합하면 “target이 몇 개 있는가”도 \(O(\log n)\)에 구할 수 있다.
카운팅 정렬 (Counting Sort)
값의 범위가 작으면 비교 없이 정렬할 수 있다. 각 값이 몇 번 나오는지 세고, 그 횟수만큼 순서대로 출력한다.
#include <stdio.h>
int main() {
int n;
scanf("%d", &n);
int arr[1000000];
int count[10001] = {0}; // 값의 범위: 1 ~ 10000
for (int i = 0; i < n; i++) {
scanf("%d", &arr[i]);
count[arr[i]]++;
}
for (int val = 1; val <= 10000; val++)
for (int j = 0; j < count[val]; j++)
printf("%d\n", val);
return 0;
}시간복잡도는 \(O(n + k)\) (k는 값의 범위). 비교 기반 정렬의 하한인 \(O(n \log n)\)을 깨는 정렬이다. 단, 값의 범위가 크면 메모리를 많이 쓰므로 범위가 작을 때만 쓸 만하다.
문제 A6 - 두 배열 병합
정렬된 두 배열을 합쳐서 하나의 정렬된 배열로 만들어라.
투 포인터(two pointer) 기법이다. 두 배열의 앞쪽을 가리키는 포인터를 하나씩 두고, 작은 쪽을 결과에 넣고 포인터를 전진시킨다.
void merge(int a[], int na, int b[], int nb, int result[]) {
int i = 0, j = 0, k = 0;
while (i < na && j < nb) {
if (a[i] <= b[j])
result[k++] = a[i++];
else
result[k++] = b[j++];
}
while (i < na) result[k++] = a[i++];
while (j < nb) result[k++] = b[j++];
}시간복잡도: \(O(n + m)\). 병합 정렬(merge sort)의 핵심 단계가 바로 이것이다.
투 포인터는 정렬된 배열에서 특히 강력하다. “두 수의 합이 target인 쌍 찾기”, “겹치는 구간 찾기” 등 다양한 문제에 쓰인다.
여담: 프로그래밍에서 자주 쓰는 배열 패턴 정리
배열 문제에서 자주 나오는 패턴을 모아 두면 문제를 보자마자 접근법이 떠오른다.
| 패턴 | 설명 | 시간 |
|---|---|---|
| 빈도 세기 | count[arr[i]]++ |
\(O(n)\) |
| 누적 합 | prefix[i] = prefix[i-1] + arr[i] |
\(O(n)\) |
| 투 포인터 | 양쪽 끝/두 배열에서 포인터 이동 | \(O(n)\) |
| 슬라이딩 윈도우 | 고정 길이 구간을 한 칸씩 밀기 | \(O(n)\) |
| 이진 탐색 | 정렬된 배열에서 반씩 줄여 찾기 | \(O(\log n)\) |
| 방향 배열 | dr[], dc[]로 4방향/8방향 탐색 |
- |
| 좌표 압축 | 값을 순위로 변환 | \(O(n \log n)\) |
이 패턴들은 단독으로도 쓰이지만, 조합해서 쓸 때가 더 많다. “정렬 + 이진 탐색”, “누적 합 + 투 포인터” 같은 조합이 대표적이다.
비트 연산 응용
비트마스크로 집합 나타내기
int 변수 하나는 32비트다. 각 비트에 정보를 담으면, 원소 32개짜리 집합을 정수 하나로 표현할 수 있다.
“i번 비트가 1이면 원소 i가 있다”는 약속을 쓰면 된다.
00000000 00000000 00000000 00000000 → 공집합
00000000 00000000 00000000 00001110 → {1, 2, 3}
00000000 00000000 11010001 00001110 → {1, 2, 3, 8, 12, 14, 15}집합 연산
| 연산 | 코드 | 설명 |
|---|---|---|
| i번 원소 추가 | S \|= (1 << i) |
i번 비트를 1로 켠다 |
| i번 원소 삭제 | S &= ~(1 << i) |
i번 비트를 0으로 끈다 |
| i번 원소 확인 | (S >> i) & 1 |
i번 비트가 1인지 본다 |
| i번 원소 토글 | S ^= (1 << i) |
i번 비트를 뒤집는다 |
| 합집합 | A \| B |
OR |
| 교집합 | A & B |
AND |
| 차집합 | A & ~B |
A에서 B 빼기 |
| 전체 집합 (0~19) | (1 << 20) - 1 |
하위 20비트 전부 1 |
| 공집합 | 0 |
문제 13 - 비트마스크 집합 (백준 11723번)
1부터 20까지의 정수를 다루는 집합 S에 대해 다음 연산을 구현하라.
add x: S에 x 추가remove x: S에서 x 삭제check x: S에 x가 있으면 1, 없으면 0 출력toggle x: S에 x가 있으면 삭제, 없으면 추가all: S를 {1, 2, …, 20}으로 바꾸기empty: S를 공집합으로 바꾸기
#include <stdio.h>
int main() {
int M;
scanf("%d", &M);
int S = 0;
while (M--) {
char cmd[10];
int x;
scanf("%s", cmd);
if (cmd[0] == 'a' && cmd[1] == 'd') { // add
scanf("%d", &x);
S |= (1 << x);
} else if (cmd[0] == 'r') { // remove
scanf("%d", &x);
S &= ~(1 << x);
} else if (cmd[0] == 'c') { // check
scanf("%d", &x);
printf("%d\n", (S >> x) & 1);
} else if (cmd[0] == 't') { // toggle
scanf("%d", &x);
S ^= (1 << x);
} else if (cmd[1] == 'l') { // all
S = (1 << 21) - 1;
} else { // empty
S = 0;
}
}
return 0;
}bool used[21] 같은 배열을 쓰는 것보다 정수 하나로 관리하는 게 메모리도 적게 쓰고 연산도 빠르다. int 하나가 4바이트인데, bool 배열 21칸은 최소 21바이트다.
입출력이 많으므로, C에서는 scanf/printf를 쓰는 게 좋다. C++에서는 ios::sync_with_stdio(false)와 cin.tie(NULL)을 쓰면 빨라진다.
문제 14 - XOR 응용
배열에서 하나만 홀수 번 나오는 원소를 찾아라. 나머지는 전부 짝수 번 나온다.
int arr[] = {4, 1, 2, 1, 2};
// 답: 4XOR의 성질을 이용한다.
a ^ a = 0(같은 값끼리 XOR하면 0)a ^ 0 = a(0과 XOR하면 원래 값)- 교환법칙과 결합법칙이 성립
int result = 0;
for (int i = 0; i < 5; i++)
result ^= arr[i];
// result = 4 ^ 1 ^ 2 ^ 1 ^ 2
// = 4 ^ (1 ^ 1) ^ (2 ^ 2)
// = 4 ^ 0 ^ 0
// = 4짝수 번 나온 원소는 서로 상쇄되고, 홀수 번 나온 원소만 남는다.
이 문제는 LeetCode 136번 “Single Number”로, 면접에서도 자주 나온다. \(O(n)\) 시간, \(O(1)\) 공간만 쓰면 되고, 정렬(\(O(n \log n)\))이나 해시맵(\(O(n)\) 공간)은 필요 없다.
문제 15 - 비트 시프트 계산
다음 각 식의 결과를 구하라.
// (a)
5 << 3
// (b)
100 >> 2
// (c)
-6 << 1
// (d)
(1 << 10) - 1(a) 5 << 3 = 5 × 2³ = 5 × 8 = 40
5 = 00000000 00000000 00000000 00000101
5<<3= 00000000 00000000 00000000 00101000 = 40(b) 100 >> 2 = 100 ÷ 4 = 25
100 = 00000000 00000000 00000000 01100100
100>>2= 00000000 00000000 00000000 00011001 = 25(c) −6 << 1 = −6 × 2 = −12
-6 = 11111111 11111111 11111111 11111010
-6<<1= 11111111 11111111 11111111 11110100 = -12(d) (1 << 10) - 1 = 1024 - 1 = 1023
이건 하위 10비트가 전부 1인 수다: 00000000 00000000 00000011 11111111. 비트마스크에서 “하위 n비트 전체”를 나타낼 때 자주 쓰는 패턴이다.
여담: 비트 연산은 어디에 쓸까
비트 연산은 생각보다 쓸 곳이 많다.
IP 주소와 서브넷 마스크: 네트워크에서
192.168.1.0/24는 IP 주소에 24비트 마스크를 AND 연산하는 것이다.색상 코드:
#FF8800은 R=0xFF, G=0x88, B=0x00이다. 32비트 정수에서 각 채널을 시프트로 꺼낸다.int color = 0xFF8800; int r = (color >> 16) & 0xFF; // 255 int g = (color >> 8) & 0xFF; // 136 int b = color & 0xFF; // 0파일 권한: Unix의
chmod 755는 소유자 rwx(7=111₂), 그룹 r-x(5=101₂), 기타 r-x(5=101₂)다.체스 엔진: 64칸 체스판을
unsigned long long하나(64비트)로 표현하는 비트보드(bitboard)를 쓴다. Stockfish 같은 강력한 체스 엔진이 이 방식을 쓴다.암호학: AES, SHA 같은 암호 알고리즘은 내부적으로 XOR, 시프트 연산을 반복한다.
문제 15.5 - 2의 거듭제곱 판별
양의 정수 n이 2의 거듭제곱(1, 2, 4, 8, 16, …)인지 판별하라.
2의 거듭제곱은 2진수로 쓰면 비트가 정확히 하나만 1이다.
1 = 00000001
2 = 00000010
4 = 00000100
8 = 00001000
16 = 00010000n & (n - 1)이 0이면 2의 거듭제곱이다.
int is_power_of_2(int n) {
return n > 0 && (n & (n - 1)) == 0;
}왜 동작할까? n이 2의 거듭제곱이면 비트가 하나만 1이다. n - 1은 그 1 아래 비트가 전부 1이 된다.
n = 00010000 (16)
n-1 = 00001111 (15)
n & (n-1) = 00000000 → 0 → 2의 거듭제곱2의 거듭제곱이 아니면:
n = 00010100 (20)
n-1 = 00010011 (19)
n & (n-1) = 00010000 → 0이 아님 → 2의 거듭제곱 아님n & (n - 1)은 “가장 아래쪽 1비트를 끄는” 연산이다. 이 트릭은 비트 조작 문제에서 자주 쓰인다.
여담: Y2K 버그와 데이터 표현
2000년이 가까워지면서 전 세계가 Y2K 버그를 걱정했다. 1960~70년대에 만든 프로그램들이 연도를 2자리(99)로만 저장해서, 2000년이 되면 00이 1900년으로 해석될 수 있었다.
메모리가 비싸던 시절이라 2바이트를 아끼려고 연도를 2자리로 줄인 건데, 그 절약이 수십 년 뒤에 수천억 원 규모의 수정 비용으로 돌아왔다.
비슷한 문제가 2038년에도 예고되어 있다. Unix 시간은 1970년 1월 1일부터 초를 세는 32비트 정수인데, 2038년 1월 19일에 int 최댓값(2,147,483,647)을 넘는다. 64비트로 바꾸면 약 2920억 년까지 버틸 수 있어서, 대부분의 시스템이 이미 전환했거나 전환 중이다.
데이터 타입 하나를 잘못 고르면 수십 년 뒤에 큰일이 날 수 있다는 교훈이다.
C++ 문자열 (std::string)
string 기본
C++에서는 std::string으로 문자열을 다루면 C보다 간결하다.
#include <iostream>
#include <string>
using namespace std;
int main() {
string s1 = "Hello"; // 문자열 생성
string s2("World"); // 같은 의미
string s3; // 빈 문자열
cout << s1.size() << endl; // 5 (O(1))
cout << s1.length() << endl; // 5 (size와 같음)
cout << s1[0] << endl; // 'H' (범위 검사 안 함)
cout << s1.at(0) << endl; // 'H' (범위 검사 함)
s1 += ", ";
s1 += s2;
cout << s1 << endl; // "Hello, World"
string sub = s1.substr(7, 5); // "World"
cout << sub << endl;
size_t pos = s1.find("World");
if (pos != string::npos)
cout << "Found at " << pos << endl; // Found at 7
return 0;
}std::string::size(): \(O(1)\) - 내부에 길이를 저장해 두므로 즉시 답을 준다.- C의
strlen(): \(O(n)\) - 널 문자까지 하나하나 세야 한다.
반복문 조건에서 이 차이가 크다.
문자열 비교
std::string은 비교 연산자(==, <, > 등)를 쓸 수 있다. 사전식(lexicographic) 비교다.
string a = "apple";
string b = "banana";
cout << (a < b) << endl; // 1 (apple이 banana보다 사전에서 앞)
string c = "abc";
string d = "abcd";
cout << (c < d) << endl; // 1 (앞 부분이 같으면 짧은 쪽이 작다)문자열 입출력
string s;
cin >> s; // 공백 전까지만 읽음
getline(cin, s); // 줄 전체를 읽음 (공백 포함)cin >> x 뒤에 getline(cin, s)를 쓰면, cin이 버퍼에 남겨둔 '\n'을 getline이 읽어서 빈 문자열이 된다.
int n;
cin >> n; // 입력: 42↵
cin.ignore(); // 버퍼의 '\n'을 버림
string line;
getline(cin, line); // 이제 정상 동작문제 16 - 단어의 개수
문자열 s에 포함된 단어의 개수를 구하라. 단어는 공백으로 구분되며, 연속된 공백이 있을 수 있다. 문자열 양쪽 끝에도 공백이 있을 수 있다.
예: " Hello World " → 2개
#include <stdio.h>
#include <string.h>
int main() {
char s[1000001];
fgets(s, sizeof(s), stdin);
int count = 0;
int in_word = 0;
for (int i = 0; s[i] != '\0' && s[i] != '\n'; i++) {
if (s[i] != ' ') {
if (!in_word) {
count++;
in_word = 1;
}
} else {
in_word = 0;
}
}
printf("%d\n", count);
return 0;
}공백이 아닌 문자가 나왔을 때, 직전이 공백(또는 시작)이었으면 새 단어의 시작이다. in_word 플래그로 현재 단어 안에 있는지 추적한다.
연속 공백이나 양 끝 공백이 있어도 정확히 세는 게 이 방법의 장점이다. 단순히 공백 개수를 세면 " Hello " 같은 입력에서 틀린다.
C++ 버전:
#include <iostream>
#include <sstream>
#include <string>
using namespace std;
int main() {
string line;
getline(cin, line);
istringstream iss(line);
string word;
int count = 0;
while (iss >> word) count++;
cout << count << endl;
}문제 17 - 뒤집은 문자열이 같은지
문자열이 앞뒤로 읽어도 같은지(팰린드롬인지) 확인하라.
예: "racecar" → 팰린드롬, "hello" → 아님
양쪽 끝에서 한 칸씩 안으로 오면서 비교한다.
#include <stdio.h>
#include <string.h>
int is_palindrome(char s[]) {
int left = 0;
int right = strlen(s) - 1;
while (left < right) {
if (s[left] != s[right])
return 0;
left++;
right--;
}
return 1;
}
int main() {
char s[100];
scanf("%s", s);
printf("%s\n", is_palindrome(s) ? "Yes" : "No");
return 0;
}시간복잡도: \(O(n/2) = O(n)\). 문자열 전체를 뒤집어서 비교하는 것보다 공간을 절약한다.
유명한 팰린드롬 문장: “A man, a plan, a canal: Panama” - 구두점과 공백을 무시하면 팰린드롬이다.
여담: 문자열 처리의 역사
문자열 처리는 단순해 보여도 컴퓨터 과학에서 오래전부터 깊이 연구되어 온 분야다.
- KMP 알고리즘 (1977): 텍스트에서 패턴을 찾을 때 \(O(n+m)\)으로 찾는 알고리즘. 이전에는 최악 \(O(nm)\)이었다.
- 정규 표현식: 1956년 수학자 Stephen Kleene이 정규 언어를 정의하면서 시작되었다.
grep명령어가 이것을 구현한 최초의 프로그램 중 하나다. - 접미사 배열(suffix array)과 접미사 트리(suffix tree): DNA 서열 분석, 전문 검색 엔진 등에 쓰인다. 인간 유전체(30억 글자) 안에서 특정 서열을 찾는 데도 쓸 수 있다.
- 유니코드: 처음에는 65,536자면 세계 모든 문자를 담을 수 있다고 생각했지만, 이모지와 고대 문자까지 포함하면서 지금은 15만 자 이상을 지원한다. UTF-8 인코딩은 영어는 1바이트, 한국어는 3바이트로 가변 길이를 쓴다.
Python 연습문제
연습문제 1: 수식 계산
\(x\), \(w\), \(z\)가 공백으로 구분되어 입력된다. 다음 수식의 값 \(y\)를 소수점 둘째 자리까지 출력하라.
\[y = \frac{8 \cdot \dfrac{2x^3 + 5x + 2}{7w - \dfrac{3}{z}} - z}{4 \cdot \dfrac{3 + x}{7}}\]
수식을 분자와 분모로 나눠서 쓰면 실수하기 어렵다.
x, w, z = map(float, input().split())
# 큰 분수의 분자 부분
inner_frac = (2 * x**3 + 5 * x + 2) / (7 * w - 3 / z)
numerator = 8 * inner_frac - z
# 큰 분수의 분모 부분
denominator = 4 * (3 + x) / 7
y = numerator / denominator
print(f"{y:.2f}")입력 예: 1 2 3
inner_frac= (2 + 5 + 2) / (14 - 1) = 9 / 13 ≈ 0.6923numerator= 8 × 0.6923 - 3 = 5.5385 - 3 = 2.5385denominator= 4 × 4 / 7 ≈ 2.2857y= 2.5385 / 2.2857 ≈ 1.11
출력: 1.11
복잡한 수식을 코드로 옮길 때는 한꺼번에 한 줄로 쓰기보다, 부분식을 변수에 담아 가면서 쓰는 게 읽기 좋고 디버깅하기도 쉽다.
연습문제 2: 놀이공원 입장 조건
놀이공원에서 아래 입장 조건이 있다.
- 조건 1 (탑승): 나이가 13세 이상이고, 티켓을 보유해야 한다.
- 조건 2 (입장): 키가 150cm 이상이거나 몸무게가 18kg 이상이면 입장 가능.
나이, 티켓 보유 여부(Y 또는 N), 키, 몸무게가 공백으로 구분되어 입력된다(숫자는 모두 정수). 조건 1과 조건 2를 모두 만족하면 True, 아니면 False를 출력하라.
단, if문과 for문을 쓰지 않고 풀어야 한다.
if/for 없이 논리 연산만으로 해결한다.
age, ticket, height, weight = input().split()
age, height, weight = int(age), int(height), int(weight)
ride = age >= 13 and ticket == 'Y'
entry = height >= 150 or weight >= 18
print(ride and entry)Python에서 비교 연산(>=, ==)의 결과는 True 또는 False이고, and/or로 합칠 수 있다. if문 없이도 조건 판단 결과를 변수에 담을 수 있다.
입력 예: 15 Y 160 20
ride= (15 >= 13) and (‘Y’ == ‘Y’) = True and True = Trueentry= (160 >= 150) or (20 >= 18) = True or True = Trueride and entry= True
출력: True
입력 예: 12 Y 160 20
ride= (12 >= 13) and (‘Y’ == ‘Y’) = False and True = Falseride and entry= False (단축 평가로 entry는 계산하지 않음)
출력: False
추가 Python 문제
문제 18 - 리스트 슬라이싱
다음 각 식의 결과를 구하라.
a = list(range(0, 100, 10)) # [0, 10, 20, 30, 40, 50, 60, 70, 80, 90]
# (1)
a[2:5]
# (2)
a[1:7:2]
# (3)
a[::-1]
# (4)
a[::3](1) a[2:5] = 인덱스 2, 3, 4 → [20, 30, 40]
(2) a[1:7:2] = 인덱스 1에서 시작해 2칸씩 건너뛰며 7 전까지 → [10, 30, 50]
(3) a[::-1] = 뒤에서부터 전부 → [90, 80, 70, 60, 50, 40, 30, 20, 10, 0]
(4) a[::3] = 처음부터 3칸씩 → [0, 30, 60, 90]
슬라이싱 문법은 a[start:stop:step]이다. start 생략 시 처음부터, stop 생략 시 끝까지, step 생략 시 1이다. step이 음수면 역방향으로 간다.
문제 19 - 딕셔너리 활용
다음 코드의 출력 결과를 구하라.
scores = {"Alice": 85, "Bob": 92, "Charlie": 78}
scores["Dave"] = 95
del scores["Bob"]
for name in scores:
print(f"{name}: {scores[name]}")
print(len(scores))
print("Eve" in scores)- 초기 딕셔너리:
{"Alice": 85, "Bob": 92, "Charlie": 78} scores["Dave"] = 95→{"Alice": 85, "Bob": 92, "Charlie": 78, "Dave": 95}del scores["Bob"]→{"Alice": 85, "Charlie": 78, "Dave": 95}- for문으로 순회:
Alice: 85
Charlie: 78
Dave: 95len(scores)→3"Eve" in scores→False
Python 3.7부터 딕셔너리는 삽입 순서를 유지한다. 그래서 Alice → Charlie → Dave 순서로 나온다.
문제 20 - f-string 포맷팅
다음 코드의 출력 결과를 구하라.
import math
x = math.pi
print(f"{x}")
print(f"{x:.2f}")
print(f"{x:10.4f}")
print(f"{x:<10.4f}")
print(f"{42:05d}")
print(f"{'hello':>10}")3.141592653589793
3.14
3.1416
3.1416
00042
hello포맷 문법 정리:
:.2f→ 소수점 아래 2자리:10.4f→ 전체 폭 10칸, 소수점 아래 4자리, 기본 오른쪽 정렬:<10.4f→ 왼쪽 정렬:05d→ 5칸, 빈 자리를 0으로 채움:>10→ 오른쪽 정렬, 폭 10
C의 printf와 비슷하지만 문법이 다르다:
| Python f-string | C printf | 의미 |
|---|---|---|
f"{x:.2f}" |
printf("%.2f", x) |
소수 2자리 |
f"{x:10.4f}" |
printf("%10.4f", x) |
폭 10, 소수 4자리 |
f"{n:05d}" |
printf("%05d", n) |
0 채우기 |
추가 Python 문제
문제 20.5 - Two Sum
정수 리스트 nums와 정수 target이 주어진다. 리스트에서 두 수를 골라 합이 target이 되는 인덱스 쌍을 구하라. 답은 반드시 하나 존재한다.
예: nums = [2, 7, 11, 15], target = 9 → (0, 1) (nums[0] + nums[1] = 2 + 7 = 9)
이중 반복문으로 모든 쌍을 시도하면 \(O(n^2)\)이다.
nums = [2, 7, 11, 15]
target = 9
for i in range(len(nums)):
for j in range(i + 1, len(nums)):
if nums[i] + nums[j] == target:
print(i, j)
break딕셔너리를 쓰면 \(O(n)\)으로 줄일 수 있다.
def two_sum(nums, target):
seen = {}
for i, x in enumerate(nums):
diff = target - x
if diff in seen:
return (seen[diff], i)
seen[x] = i
print(two_sum([2, 7, 11, 15], 9)) # (0, 1)각 수를 볼 때마다 “target - 현재 수”가 이미 나왔는지 딕셔너리로 확인한다. 딕셔너리의 in 연산은 평균 \(O(1)\)이므로 전체가 \(O(n)\)이다.
이 문제는 LeetCode 1번 문제로, 코딩 면접에서 가장 유명한 문제다. 배열 + 해시맵 조합의 기본이므로 꼭 알아 두면 좋다.
문제 20.7 - 리스트 컴프리헨션
다음 각 식의 결과를 구하라.
# (1)
[x ** 2 for x in range(1, 6)]
# (2)
[x for x in range(1, 21) if x % 3 == 0]
# (3)
[c.upper() for c in "hello" if c != 'l']
# (4)
[[i * j for j in range(1, 4)] for i in range(1, 4)](1) 1부터 5까지의 제곱 → [1, 4, 9, 16, 25]
(2) 1부터 20 중 3의 배수 → [3, 6, 9, 12, 15, 18]
(3) “hello”에서 ’l’을 빼고 대문자로 → ['H', 'E', 'O']
(4) 3×3 구구단 표:
[[1, 2, 3],
[2, 4, 6],
[3, 6, 9]]리스트 컴프리헨션은 for와 if를 한 줄에 담아서 새 리스트를 만드는 Python 문법이다. for를 중첩하면 2차원 리스트도 만들 수 있다.
여담: 10억 달러짜리 실수
Tony Hoare는 1965년에 null 참조(null reference)를 발명했다. 값이 없는 상태를 나타내기 위해서였는데, 그 뒤 수십 년간 null 참조로 인한 버그가 셀 수 없이 발생했다. Hoare 본인이 2009년 강연에서 이렇게 말했다:
“I call it my billion-dollar mistake. […] I couldn’t resist the temptation to put in a null reference, simply because it was so easy to implement.”
C에서 NULL 포인터를 역참조하면 segmentation fault로 프로그램이 죽는다. Java에서는 NullPointerException, Python에서는 None 관련 AttributeError가 이 문제의 변형이다.
이 문제를 아예 없애려는 시도도 있다. Rust는 Option<T> 타입으로 null을 아예 없앴고, Kotlin은 ? 연산자로 null 안전성을 보장한다. 어떤 값이 “없을 수 있다”는 것을 타입 시스템에서 표현하게 만든 것이다.
종합 문제
문제 21 - 빈도 세기
알파벳 소문자로만 이루어진 문자열이 주어질 때, 가장 많이 나온 문자와 그 횟수를 출력하라. 가장 많이 나온 문자가 여러 개면 알파벳 순서가 빠른 것을 출력한다.
배열을 카운터로 쓴다. 'a'~'z'는 26개이므로 크기 26 배열이면 충분하다.
#include <stdio.h>
#include <string.h>
int main() {
char s[100001];
scanf("%s", s);
int count[26] = {0};
int len = strlen(s);
for (int i = 0; i < len; i++)
count[s[i] - 'a']++;
int max_count = 0;
char max_char = 'a';
for (int i = 0; i < 26; i++) {
if (count[i] > max_count) {
max_count = count[i];
max_char = 'a' + i;
}
}
printf("%c %d\n", max_char, max_count);
return 0;
}s[i] - 'a'로 문자를 0~25 인덱스로 바꾸는 기법은 문자열 문제에서 아주 자주 쓰인다. 해시맵이 필요 없이 배열만으로 빈도를 셀 수 있다.
문제 22 - 달팽이 채우기
\(n \times n\) 배열을 시계 방향 달팽이(spiral) 순서로 1부터 \(n^2\)까지 채워서 출력하라.
입력 예: n = 4
출력:
1 2 3 4
12 13 14 5
11 16 15 6
10 9 8 7방향 배열을 쓰면 깔끔하게 풀 수 있다. 오른쪽 → 아래 → 왼쪽 → 위 순서로 돌면서, 벽이나 이미 채운 칸을 만나면 방향을 바꾼다.
#include <stdio.h>
int main() {
int n;
scanf("%d", &n);
int a[100][100] = {0};
// 방향: 오른쪽, 아래, 왼쪽, 위
int dr[] = {0, 1, 0, -1};
int dc[] = {1, 0, -1, 0};
int r = 0, c = 0, dir = 0;
for (int num = 1; num <= n * n; num++) {
a[r][c] = num;
int nr = r + dr[dir];
int nc = c + dc[dir];
// 범위 밖이거나 이미 채운 칸이면 방향 전환
if (nr < 0 || nr >= n || nc < 0 || nc >= n || a[nr][nc] != 0) {
dir = (dir + 1) % 4;
nr = r + dr[dir];
nc = c + dc[dir];
}
r = nr;
c = nc;
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++)
printf("%2d ", a[i][j]);
printf("\n");
}
return 0;
}여기서 중요한 건 방향 전환이다. dir = (dir + 1) % 4로 시계 방향으로 90도 회전한다. 이 “방향 배열” 패턴은 BFS/DFS 같은 그래프 탐색에서도 그대로 쓰인다.
문제 23 - 비밀번호 검증
문자열이 다음 조건을 모두 만족하면 "Valid", 아니면 "Invalid"를 출력하라.
- 길이가 8 이상
- 대문자가 하나 이상
- 소문자가 하나 이상
- 숫자가 하나 이상
#include <stdio.h>
#include <string.h>
int main() {
char pw[1001];
scanf("%s", pw);
int len = strlen(pw);
int has_upper = 0, has_lower = 0, has_digit = 0;
for (int i = 0; i < len; i++) {
if (pw[i] >= 'A' && pw[i] <= 'Z') has_upper = 1;
if (pw[i] >= 'a' && pw[i] <= 'z') has_lower = 1;
if (pw[i] >= '0' && pw[i] <= '9') has_digit = 1;
}
if (len >= 8 && has_upper && has_lower && has_digit)
printf("Valid\n");
else
printf("Invalid\n");
return 0;
}실제 비밀번호 검증에서는 특수문자, 연속된 문자, 사전 단어 포함 여부 등도 검사한다. NIST(미국 국립표준기술연구소)는 2017년 가이드라인에서 “길이가 가장 중요하고, 복잡성 규칙(대문자, 특수문자 등)은 오히려 비밀번호를 약하게 만들 수 있다”고 밝혔다. 사람들이 P@ssw0rd! 같은 예측 가능한 패턴을 쓰게 되기 때문이다.
문제 24 - 이진법 변환
10진수 정수 n을 입력받아 2진수 문자열로 출력하라. (0 이상의 정수)
2로 나누면서 나머지를 모으고, 역순으로 출력한다.
#include <stdio.h>
int main() {
int n;
scanf("%d", &n);
if (n == 0) {
printf("0\n");
return 0;
}
char bits[33]; // 32비트 + 널문자
int top = 0;
while (n > 0) {
bits[top++] = '0' + (n % 2);
n /= 2;
}
// 역순 출력
for (int i = top - 1; i >= 0; i--)
printf("%c", bits[i]);
printf("\n");
return 0;
}비트 연산으로도 풀 수 있다:
for (int i = 31; i >= 0; i--) {
if ((n >> i) & 1 || started) {
printf("%d", (n >> i) & 1);
started = 1;
}
}이 코드는 최상위 비트부터 하나씩 읽는다. (n >> i) & 1은 i번째 비트 값이다.
여담: 컴퓨터가 10진수를 쓰지 않는 이유
컴퓨터는 전기 신호로 동작한다. 전압이 높으면 1, 낮으면 0. 두 상태만 구분하는 게 가장 안정적이다.
10진수를 쓰려면 전압 레벨을 10단계로 나눠야 하는데, 노이즈 때문에 인접한 레벨을 구분하기 어렵다. 2진수는 “높다/낮다”만 구분하면 되므로 노이즈에 강하다.
초기 컴퓨터 중에는 10진수를 쓴 것도 있었다. IBM의 초기 메인프레임은 BCD(Binary-Coded Decimal) 방식으로 10진수 한 자리를 4비트에 담았다. 하지만 연산 효율이 2진수보다 떨어져서 지금은 거의 안 쓴다.
양자 컴퓨터는 큐비트(qubit)를 쓴다. 0과 1을 동시에 가질 수 있는 중첩(superposition) 상태라서, 특정 문제에서 기존 컴퓨터보다 훨씬 빠를 수 있다.
여담: 프로그래밍 대회 이야기
프로그래밍 대회(competitive programming)에서는 배열, 문자열, 비트 연산이 기본기로 항상 나온다.
대표적인 대회들:
- IOI(International Olympatics in Informatics): 고등학생 대상 국제 정보올림피아드. 한국은 매년 좋은 성적을 거둔다. 4~5시간 동안 3문제를 풀어야 하며, 부분 점수가 있다.
- ICPC(International Collegiate Programming Contest): 대학생 대상 팀 대회. 3명이 한 팀으로 컴퓨터 1대를 공유하며 10~13문제를 5시간 안에 푼다.
- Codeforces: 온라인 대회 플랫폼. 거의 매주 대회가 열리고, 레이팅 시스템으로 실력을 측정한다.
- 백준 Online Judge: 한국에서 가장 많이 쓰는 PS 플랫폼. 3만 문제 이상이 등록되어 있다.
대회에서 자주 쓰는 관용구(idiom)들:
// 빠른 입출력 (C)
#include <stdio.h>
// scanf/printf가 cin/cout보다 빠르다
// 빠른 입출력 (C++)
ios::sync_with_stdio(false);
cin.tie(NULL);
// 큰 배열은 전역에
int arr[1000001];
// 무한대 대용
#define INF 0x3f3f3f3f
// memset(arr, 0x3f, sizeof(arr))로 전부 INF로 채울 수 있다PS를 잘한다고 실무 능력이 높은 건 아니고, 실무를 잘한다고 PS를 잘하는 것도 아니다. 하지만 자료 구조와 알고리즘에 대한 감각, 코너 케이스를 생각하는 습관, 시간 복잡도를 의식하는 능력은 어디서든 쓸모가 있다.
실습 문제
문제 P1 - 피하자 (BOJ 25379)
문제 요약: 길이 N인 음이 아닌 정수 배열 A가 있다. 인접한 두 원소를 교환하는 연산으로, 홀수와 짝수가 인접한 쌍이 최대 1쌍이 되도록 만드는 최소 교환 횟수를 구한다.
제한: N ≤ 1,000,000, A_i ≤ 2×10^9, 시간 2초
예제: [4, 5, 1, 0] → 2, [1, 2, 3, 1] → 1
아이디어
“홀짝 인접 쌍이 최대 1쌍”이 되는 배열 형태를 생각한다. 짝수끼리, 홀수끼리 각각 연속하게 모아 두면 인접 쌍은 정확히 1쌍(두 그룹이 맞닿는 경계)이 된다. 즉 짝수를 모두 앞으로, 홀수를 모두 뒤로 모으거나 그 반대가 최적 후보다.
단순한 접근
모든 가능한 최종 배열을 직접 시도하면 O(N!)이므로 불가능하다.
최적화
“짝수를 앞, 홀수를 뒤”로 모을 때 필요한 교환 횟수를 생각한다.
- 짝수의 원래 위치를 순서대로 나열하면 p_0, p_1, …, p_{e-1} (e = 짝수 개수)
- 이들이 목표로 가야 할 위치는 0, 1, 2, …, e-1
- 필요한 교환 횟수는 각 짝수가 제자리로 가기 위해 넘어야 할 홀수 수의 합 = inversion 수
실제로는 짝수의 상대적 순서가 바뀌지 않는다고 가정하면, 짝수의 위치 목록에서 i번째 짝수의 현재 위치와 목표 위치(i)의 차이를 합산하면 된다.
단, 교환 횟수 공식은 다음과 같이 단순화된다: i번째 짝수(0-indexed)가 현재 p_i에 있다면, 앞에 홀수가 몇 개 있는지 세면 된다. 이는 p_i - i와 같다 (앞에 있는 원소 수 p_i 중 짝수가 i개이므로 홀수는 p_i - i개).
따라서 교환 횟수 = sum(p_i - i) for i = 0..e-1
마찬가지로 “홀수를 앞, 짝수를 뒤”로 모을 때도 같은 방식으로 계산하고, 두 경우 중 작은 쪽이 답이다.
시간복잡도 확인
배열을 한 번 순회해서 짝수 위치 목록과 홀수 위치 목록을 만들고, 각각 O(N)에 합산한다. 전체 O(N). N ≤ 10^6이므로 충분하다.
구현
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++) cin >> a[i];
// 짝수 위치 목록, 홀수 위치 목록
vector<int> even_pos, odd_pos;
for (int i = 0; i < n; i++) {
if (a[i] % 2 == 0) even_pos.push_back(i);
else odd_pos.push_back(i);
}
// 경우 1: 짝수 앞, 홀수 뒤
// i번째 짝수의 목표 위치 = i
// 교환 횟수 = sum(pos - i) for i-th even
long long cost1 = 0;
for (int i = 0; i < (int)even_pos.size(); i++) {
cost1 += even_pos[i] - i;
}
// 경우 2: 홀수 앞, 짝수 뒤
long long cost2 = 0;
for (int i = 0; i < (int)odd_pos.size(); i++) {
cost2 += odd_pos[i] - i;
}
cout << min(cost1, cost2) << "\n";
return 0;
}문제 P2 - 부여 궁남지 연꽃 키우기 1 (CodeUp 2405)
문제 요약: h×w 연못에 초기 연꽃이 (x, y)에 있다. 매일 연꽃은 인접 4방향으로 번식한다. 번식하지 못한 연꽃(주변이 모두 막힌 연꽃)은 사라진다. n일 후 남은 연꽃 수를 구한다.
제한: h, w ≤ 100, n ≤ 100
예제: 5×5 연못, (2, 2) 시작, 3일 후 → 21
아이디어
“번식하지 못하면 사라진다”는 조건을 정확히 읽는다. 번식한 꽃도 남고, 번식을 못 한 꽃(인접한 빈 칸이 하나도 없는 꽃)만 사라진다. 매일 시뮬레이션해서 꽃이 피는 과정과 사라지는 과정을 처리하면 된다.
단순한 접근
h, w, n이 모두 100 이하이므로 단순 시뮬레이션이 가능하다. 매일:
- 현재 꽃이 있는 칸을 순회해서 빈 인접 칸에 새 꽃을 심는다.
- 번식을 못 한 꽃(즉, 인접 4칸이 모두 꽃이거나 벽인 칸)을 제거한다.
시간복잡도: O(n × h × w) = O(100 × 100 × 100) = 10^6. 충분하다.
시간복잡도 확인
O(n × h × w) = 10^6으로 문제없다.
구현
#include <bits/stdc++.h>
using namespace std;
int h, w, n;
int grid[105][105]; // 0: 빈칸, 1: 꽃
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
int main() {
cin >> h >> w;
int sx, sy;
cin >> sx >> sy;
cin >> n;
grid[sx][sy] = 1;
for (int day = 0; day < n; day++) {
int next[105][105] = {};
// 번식: 현재 꽃에서 빈 인접 칸에 새 꽃
// 번식한 꽃은 남고, 번식 못 한 꽃은 사라짐
// 번식 여부 = 인접에 빈 칸이 하나라도 있는가
for (int i = 1; i <= h; i++) {
for (int j = 1; j <= w; j++) {
if (!grid[i][j]) continue;
bool bred = false;
for (int d = 0; d < 4; d++) {
int ni = i + dx[d], nj = j + dy[d];
if (ni < 1 || ni > h || nj < 1 || nj > w) continue;
if (grid[ni][nj] == 0) {
next[ni][nj] = 1; // 새 꽃
bred = true;
}
}
if (bred) next[i][j] = 1; // 번식한 꽃은 유지
// 번식 못 한 꽃은 next에 포함 안 됨 -> 사라짐
}
}
memcpy(grid, next, sizeof(grid));
}
int cnt = 0;
for (int i = 1; i <= h; i++)
for (int j = 1; j <= w; j++)
cnt += grid[i][j];
cout << cnt << "\n";
return 0;
}문제 P3 - 포도 수확하기 1 (BIKO 5132)
문제 요약: n그루 포도나무, 상자 한 개에 같은 나무의 포도를 최대 m개 담을 수 있고, 상자는 총 k개다. 판매 가능한 포도송이 수의 최댓값을 구한다.
제한: n ≤ 10000, m ≤ 10000, k ≤ 20000, c_i ≤ 10000
예제: - n=5, m=10, k=5, [15,19,10,9,8] → 48 - n=5, m=10, k=10, [15,19,10,9,8] → 61 - n=10, m=9, k=25, [15,19,10,9,8,7,31,54,73,26] → 224
아이디어
각 나무에서 c_i 개의 포도를 수확하려면 ceil(c_i / m)개의 상자가 필요하다. 상자가 충분하면 모든 포도를 담을 수 있다. 부족하면 k개 상자를 어떻게 배분해야 수확량이 최대가 될까?
단순한 접근
상자 k개를 각 나무에 할당하는 모든 경우를 시도하면 경우의 수가 너무 많다.
최적화
각 나무에 상자를 하나씩 배정할 때마다 포도를 얼마나 추가로 수확하는지 계산한다.
- 나무 i에 상자가 j개 배정되면, min(c_i, j × m)개의 포도를 수확한다.
- j번째 상자를 이 나무에 추가할 때의 증가량: min(c_i, j×m) - min(c_i, (j-1)×m)
- 이 값은 j가 커질수록 단조감소한다 (한계 효용 감소).
따라서 그리디: 매번 “지금 상자 한 개를 더 줬을 때 포도 증가량이 가장 큰 나무”에 상자를 준다. 이를 효율적으로 하려면, 각 나무별로 상자를 1개, 2개, …, ceil(c_i/m)개 줄 때의 증가량 목록을 만들고, 전부 합쳐 내림차순 정렬한 뒤 k개를 취하면 된다.
시간복잡도 확인
전체 증가량 목록의 크기: sum(ceil(c_i/m)) ≤ n × ceil(max_c/m). 최악의 경우 n=10000, c_i=10000, m=1이면 10^8이 되어 위험하다. 하지만 m이 1일 때는 각 상자가 1개씩 담으므로 증가량 목록 크기 = sum(c_i) ≤ n × 10000 = 10^8. 이 경우는 k도 커야 하므로 문제에서 k ≤ 20000이라는 점을 활용해야 한다.
실용적 접근: k ≤ 20000이므로, 각 나무에서 최대 k개 상자까지만 고려하면 된다. 또한 나무마다 ceil(c_i/m) 이상의 상자는 의미 없다. 증가량 목록을 만들되 최대 k개만 정렬해서 선택한다.
더 단순하게: 나무별 (상자 수, 수확량) 쌍을 직접 정렬하기 어려우면, 상자 1개당 수확량이 가장 큰 순서로 나무 전체에 상자를 배정하는 방식이다. 각 나무의 j번째 상자에서의 수확량을 모두 리스트에 넣고 정렬 후 상위 k개 선택.
n=10000, k=20000, ceil(c_i/m)의 최댓값은 k를 넘을 수 없으므로 총 항목 수 ≤ n×k가 아닌, 전체 필요 상자 수 ≤ k로 제한되지 않는다. 단, 실제로는 각 나무에서 ceil(c_i/m)개씩이고 c_i/m이 최대 10000이면 총 항목 수가 10^8. 제한을 다시 읽으면 문제에서 k ≤ 20000이므로 k개만 뽑으면 된다.
효율적 구현: 각 나무에서의 증가량 배열을 정렬해서 우선순위 큐에 넣고 k번 뽑는다. 또는 단순히 모든 (증가량, 나무번호, 상자번호) 쌍을 만들어 정렬. 총 쌍의 수 = sum(ceil(c_i/m))이 최대 n × (10000/m)이고, m=1이면 n×10000=10^8. 이건 TLE.
실용적으로: 각 나무에서 첫 번째 상자의 증가량은 min(c_i, m), 두 번째는 min(c_i, 2m) - min(c_i, m), … 즉 m씩 증가하다가 c_i에서 멈춘다. 마지막 상자 전까지는 모두 m이고 마지막 상자만 c_i mod m (0이면 m)이다. 따라서 각 나무에서 사용되는 상자 수 = floor(c_i/m) + (1 if c_i mod m > 0 else 0), 그 중 마지막 상자의 수확량만 m과 다르다.
이를 이용하면: 전체에서 증가량이 m인 상자와 m 미만인 상자를 분리해 처리할 수 있다. m인 상자를 최대한 쓰고 (남은 상자로 m 미만인 것을 처리). 구현을 단순화하면:
- 각 나무별 필요 상자 수 boxes_i = ceil(c_i / m)
- sum(boxes_i) ≤ k이면 전체 c_i의 합이 답
- 아니라면, 상자당 수확량이 높은 순으로 배정
상자당 수확량은 마지막 상자만 c_i mod m (0이면 m), 나머지는 m. 즉 m 미만인 상자들의 목록(각 나무당 최대 1개)을 내림차순 정렬하고, 나머지는 모두 m. 상자 k개를 배정할 때: 먼저 m인 상자들을 가능한 한 배정하고 남으면 m 미만 상자들을 배정한다.
구현
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
int n, m, k;
cin >> n >> m >> k;
vector<int> c(n);
for (int i = 0; i < n; i++) cin >> c[i];
// 각 나무별 필요 상자 수와 마지막 상자 수확량
long long total_full = 0; // m개 담는 상자들의 총 개수
vector<int> last_amount; // 마지막(부분) 상자 수확량
long long total_grapes = 0;
for (int i = 0; i < n; i++) {
int full_boxes = c[i] / m; // m개 꽉 찬 상자 수
int remainder = c[i] % m; // 나머지
total_full += full_boxes;
total_grapes += c[i];
if (remainder > 0) {
last_amount.push_back(remainder);
} else {
// c[i]가 m의 배수: 상자가 꽉 참, full_boxes에 이미 포함
}
}
// 총 필요 상자 = total_full + last_amount.size()
long long total_boxes_needed = total_full + (long long)last_amount.size();
if (k >= total_boxes_needed) {
// 상자가 충분: 전부 수확
cout << total_grapes << "\n";
return 0;
}
// 상자가 부족: 그리디
// m개 꽉 찬 상자 먼저, 그 다음 나머지 많은 순
sort(last_amount.rbegin(), last_amount.rend());
long long ans = 0;
long long boxes_left = k;
// m개 꽉 찬 상자에 먼저 상자 배정
long long use_full = min(boxes_left, total_full);
ans += use_full * m;
boxes_left -= use_full;
// 남은 상자로 부분 상자 배정 (큰 것부터)
for (int i = 0; i < (int)last_amount.size() && boxes_left > 0; i++) {
ans += last_amount[i];
boxes_left--;
}
cout << ans << "\n";
return 0;
}문제 P4 - 금산 인삼 수확하기 1 (BIKO 5116)
문제 요약: 10×10 밭에서 k년간 매년 심기(0) 또는 수확(1) 연산을 영역 (x1,y1)-(x2,y2)에 적용한다. 심기는 빈 칸에만 심는다. 수확은 4-6년근만 판매(7년 이상은 수확하되 판매 안 함, 0-3년근은 수확 안 함). 총 판매 금액을 구한다.
아이디어
10×10 배열에 각 칸에 심은 연도를 저장하고, 매년 나이를 계산해서 수확 가능 여부를 판단한다.
단순한 접근
k ≤ 100 (추정), 10×10 배열, 연도 추적. 매년 O(100)으로 시뮬레이션. 완전 시뮬레이션이 가능하다.
판매 금액: 4년근, 5년근, 6년근의 가격은 문제에서 직접 확인해야 하지만, 일반적으로 이런 문제에서는 연수별 가격이 입력으로 주어지거나 고정값이다. 여기서는 4년근 100만원, 5년근 150만원, 6년근 200만원으로 가정한다 (예제로 역추적 필요).
시간복잡도 확인
O(k × 100) = O(10000). 문제없다.
구현
#include <bits/stdc++.h>
using namespace std;
int field[11][11]; // 0: 빈칸, >0: 심은 연도
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
int k;
cin >> k;
// 가격: 4년근, 5년근, 6년근 (문제에 따라 조정)
int price[7] = {0, 0, 0, 0, 1000000, 1500000, 2000000};
long long total = 0;
for (int year = 1; year <= k; year++) {
int op, x1, y1, x2, y2;
cin >> op >> x1 >> y1 >> x2 >> y2;
if (op == 0) {
// 심기: 빈 칸에만
for (int i = x1; i <= x2; i++)
for (int j = y1; j <= y2; j++)
if (field[i][j] == 0)
field[i][j] = year;
} else {
// 수확
for (int i = x1; i <= x2; i++) {
for (int j = y1; j <= y2; j++) {
if (field[i][j] == 0) continue;
int age = year - field[i][j];
if (age >= 4 && age <= 6) {
total += price[age];
field[i][j] = 0;
} else if (age >= 7) {
// 수확하되 판매 안 함
field[i][j] = 0;
}
// 0~3년근은 수확 안 함
}
}
}
}
cout << total << "\n";
return 0;
}문제 P5 - 백제 문화제 0 (BIKO 5120)
문제 요약: 기념품 10개의 무게가 [13, 26, 31, 5, 8, 6, 7, 15, 40, 32]로 고정되어 있다. 상자 하나에 최대 40까지 담을 수 있다. 최소 상자 수를 구한다. 입력 없음.
아이디어
Bin Packing 문제다. NP-hard이지만 n=10으로 작아서 브루트포스도 가능하다. First Fit Decreasing(FFD) 휴리스틱이나 완전탐색으로 풀 수 있다.
단순한 접근
n=10이므로 모든 분할 방법을 시도하면 된다. 각 물건을 어느 상자에 넣을지 결정하는 방법: O(n^n)이지만 n=10이면 10^10으로 느리다.
더 효율적으로: 각 물건을 기존 상자 중 하나에 넣거나 새 상자에 넣는다. 이미 있는 상자 수가 최대 n개이므로 상태 공간이 훨씬 작다.
n=10이므로 정렬 후 백트래킹이나 FFD로 충분하다.
최적화
내림차순 정렬 후 각 물건을 처음 들어갈 수 있는 상자에 넣는 FFD를 시도한다. 정확한 최솟값이 필요하면 백트래킹을 쓴다.
구현
#include <bits/stdc++.h>
using namespace std;
int items[] = {13, 26, 31, 5, 8, 6, 7, 15, 40, 32};
int n = 10;
int best;
void solve(int idx, vector<int>& boxes) {
if (idx == n) {
best = min(best, (int)boxes.size());
return;
}
// 가지치기: 현재 상자 수가 이미 best 이상이면 중단
if ((int)boxes.size() >= best) return;
// 기존 상자에 넣기
for (int i = 0; i < (int)boxes.size(); i++) {
if (boxes[i] + items[idx] <= 40) {
boxes[i] += items[idx];
solve(idx + 1, boxes);
boxes[i] -= items[idx];
}
}
// 새 상자에 넣기
boxes.push_back(items[idx]);
solve(idx + 1, boxes);
boxes.pop_back();
}
int main() {
// 내림차순 정렬로 가지치기 효율 향상
sort(items, items + n, greater<int>());
best = n; // 최악: 각 물건을 상자에 하나씩
vector<int> boxes;
solve(0, boxes);
cout << best << "\n";
return 0;
}문제 P6 - 당일치기 전주 여행 1 (BIKO 1629)
문제 요약: 전주역과 5개 관광지, 6×6 이동시간 행렬이 주어진다. 전주역 도착 시각과 출발 시각이 주어질 때, 이동시간을 제외한 최대 체류시간을 구한다.
아이디어
전주역(0)에서 출발해 5개 관광지를 모두 방문하고 전주역으로 돌아오는 최단 이동 경로를 구한다. (총 시간) - (최소 이동시간) = 최대 체류시간.
단순한 접근
5개 관광지의 방문 순서를 모두 시도하면 5! = 120가지다. 각 순서에 대해 이동시간 합을 계산해 최솟값을 구한다.
시간복잡도 확인
O(5!) = O(120). 입력 읽기 포함해도 순식간에 끝난다.
구현
#include <bits/stdc++.h>
using namespace std;
int dist[6][6];
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
for (int i = 0; i < 6; i++)
for (int j = 0; j < 6; j++)
cin >> dist[i][j];
int arrive, depart; // 분 단위로 입력받는다고 가정
cin >> arrive >> depart;
int total_time = depart - arrive;
// 관광지 순서: 1~5번 노드
vector<int> order = {1, 2, 3, 4, 5};
int min_travel = INT_MAX;
do {
int travel = dist[0][order[0]];
for (int i = 0; i < 4; i++)
travel += dist[order[i]][order[i+1]];
travel += dist[order[4]][0];
min_travel = min(min_travel, travel);
} while (next_permutation(order.begin(), order.end()));
cout << total_time - min_travel << "\n";
return 0;
}문제 P7 - 흑백 이미지 생성 1 (BIKO 1639)
문제 요약: h×w 그리드가 0으로 초기화되어 있다. n번 직사각형 영역 (x1,y1)-(x2,y2)를 반전(0↔︎1)한다. 최종 상태를 출력한다.
제한: h, w ≤ 1000, n ≤ 10000
아이디어
단순 시뮬레이션은 O(n × h × w) = 10^10으로 TLE다. 2D 차분 배열(2D imos법)을 쓰면 O(n + h × w)로 해결된다.
단순한 접근
매 반전마다 영역 내 모든 칸을 뒤집으면 O(n × h × w) = 10^10으로 2초 내 불가능하다.
최적화
2D 차분 배열을 쓴다. diff[x1][y1] += 1, diff[x1][y2+1] -= 1, diff[x2+1][y1] -= 1, diff[x2+1][y2+1] += 1로 기록하고, 2D 누적합을 구한 뒤 홀수이면 1, 짝수이면 0으로 최종 값을 결정한다.
시간복잡도 확인
O(n) + O(h × w) = O(10000) + O(10^6) = O(10^6). 충분하다.
구현
#include <bits/stdc++.h>
using namespace std;
int diff[1005][1005];
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
int h, w, n;
cin >> h >> w >> n;
for (int i = 0; i < n; i++) {
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
// 1-indexed 가정
diff[x1][y1]++;
diff[x1][y2+1]--;
diff[x2+1][y1]--;
diff[x2+1][y2+1]++;
}
// 2D 누적합
for (int i = 1; i <= h; i++)
for (int j = 1; j <= w; j++)
diff[i][j] += diff[i-1][j] + diff[i][j-1] - diff[i-1][j-1];
for (int i = 1; i <= h; i++) {
for (int j = 1; j <= w; j++) {
cout << (diff[i][j] % 2 != 0 ? 1 : 0);
if (j < w) cout << " ";
}
cout << "\n";
}
return 0;
}문제 P8 - 스케이트 연습 (BIKO 207)
문제 요약: N개의 중간 지점이 있고 각 지점의 속력 제한이 V_i다. 시작과 끝 속력은 0이다. 속력을 올리는 건 자유지만 내리는 건 1씩만 줄일 수 있고 속력은 0이 될 수 없다(시작/끝 제외). 속력 합의 최댓값을 구한다.
제한: N ≤ 500,000, V_i ≤ 10^9
예제: [2,3,1] → 5, [23,7,1,5] → 7
아이디어
각 지점 i에서의 실제 속력 s_i = min(V_i, 왼쪽에서 가능한 최대, 오른쪽에서 가능한 최대).
왼쪽에서 가능한 최대: 시작(속력 0)에서 점점 올릴 수 있으므로 i번째(1-indexed) 지점은 최대 i. 즉 left[i] = i.
오른쪽에서 가능한 최대: 끝에서 0이 되어야 하므로, 끝에서 j번째 지점은 최대 j. 즉 right[i] = N+1-i.
따라서 s_i = min(V_i, i, N+1-i), 답은 sum(s_i).
단순한 접근
그냥 위 공식대로 O(N)에 계산한다.
시간복잡도 확인
O(N). N ≤ 500,000이므로 충분하다.
구현
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
int n;
cin >> n;
vector<long long> v(n+1);
for (int i = 1; i <= n; i++) cin >> v[i];
long long ans = 0;
for (int i = 1; i <= n; i++) {
long long s = min({v[i], (long long)i, (long long)(n+1-i)});
ans += s;
}
cout << ans << "\n";
return 0;
}문제 P9 - 대피소 (BOJ 28215)
문제 요약: N개 집과 K개 대피소(K ≤ 3). 대피소 위치를 격자 점 중에서 골라 “가장 먼 집까지의 맨해튼 거리”를 최소화한다.
제한: K ≤ 3, N ≤ 50, 좌표 ≤ 100000, 시간 3초
예제: 집 5개, 대피소 2개 → 5
아이디어
대피소 K개를 N개 집 중에서 고른다. 각 집은 가장 가까운 대피소까지의 거리를 구하고, 그 최댓값을 최소화한다.
단순한 접근
대피소 위치를 N개 집 위치 중에서 고르는 것이 최적임을 이용한다(대피소를 집이 아닌 위치에 두면 최적이 아닐 수 있다는 보장은 없지만, 이 문제에서는 후보가 집 위치로 제한된다고 보는 것이 일반적이다). C(50, 3) = 19600가지를 모두 시도한다.
K=1: C(50,1) = 50 K=2: C(50,2) = 1225 K=3: C(50,3) = 19600
각 경우에 N개 집까지의 맨해튼 거리 최솟값을 구하고 최댓값을 취한다. O(C(N,K) × N).
시간복잡도 확인
O(19600 × 50) = O(980,000). 충분하다.
구현
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
int n, k;
cin >> n >> k;
vector<pair<long long,long long>> houses(n);
for (int i = 0; i < n; i++) cin >> houses[i].first >> houses[i].second;
auto manhattan = [](pair<long long,long long> a, pair<long long,long long> b) {
return abs(a.first - b.first) + abs(a.second - b.second);
};
long long ans = LLONG_MAX;
if (k == 1) {
for (int i = 0; i < n; i++) {
long long worst = 0;
for (int h = 0; h < n; h++)
worst = max(worst, manhattan(houses[i], houses[h]));
ans = min(ans, worst);
}
} else if (k == 2) {
for (int i = 0; i < n; i++) {
for (int j = i+1; j < n; j++) {
long long worst = 0;
for (int h = 0; h < n; h++) {
long long d = min(manhattan(houses[i], houses[h]),
manhattan(houses[j], houses[h]));
worst = max(worst, d);
}
ans = min(ans, worst);
}
}
} else { // k == 3
for (int i = 0; i < n; i++) {
for (int j = i+1; j < n; j++) {
for (int l = j+1; l < n; l++) {
long long worst = 0;
for (int h = 0; h < n; h++) {
long long d = min({manhattan(houses[i], houses[h]),
manhattan(houses[j], houses[h]),
manhattan(houses[l], houses[h])});
worst = max(worst, d);
}
ans = min(ans, worst);
}
}
}
}
cout << ans << "\n";
return 0;
}문제 P10 - 반품 회수 (BOJ 31964)
문제 요약: 직선 도로 위 위치 0에서 출발한 트럭이 N개 집을 방문해 반품을 회수한 뒤 0으로 돌아오는 최소 시간을 구한다. 집 i는 위치 X_i에 있고 시각 T_i에 물건이 준비된다.
제한: N ≤ 3000, X_i ≤ 10^8, T_i ≤ 10^8, 시간 1초
예제: 위치 [2,5,7,10], 준비 시각 [20,4,16,11] → 23
아이디어
트럭은 직선 위를 움직인다. 오른쪽 끝까지 갔다가 왼쪽으로 돌아오거나, 왼쪽으로 갔다가 오른쪽으로 가는 식이다. 특정 순간 트럭의 위치는 구간 [L, R]을 커버했을 때 결정된다. 이를 DP로 모델링한다.
집을 위치 순으로 정렬한다. dp[i][j] = 집 i~j를 모두 커버한 상태에서 트럭이 i 쪽 끝에 있을 때 최소 시간, dp2[i][j] = j 쪽 끝에 있을 때 최소 시간.
단순한 접근
N ≤ 3000이므로 O(N^2) DP가 가능하다.
최적화
위치 순으로 정렬 후 dp[i][j][side] = 집 i~j를 처리했을 때 side(0=왼쪽, 1=오른쪽)에 있는 최소 시간. 전이: [i,j]에서 [i-1,j] 또는 [i,j+1]로 확장.
구체적으로, 정렬된 집 배열 x[0..N-1] (x[0] < x[1] < … < x[N-1]): - dp_l[i][j] = 구간 [i,j] 처리 후 왼쪽(x[i])에 있을 때 최소 시간 - dp_r[i][j] = 구간 [i,j] 처리 후 오른쪽(x[j])에 있을 때 최소 시간
집에 도착할 때 준비가 안 됐으면 기다려야 한다: 실제 도착 시각 = max(도착 시각, T[i]).
시간복잡도 확인
O(N^2). N=3000이면 9×10^6. 1초 내 가능하다.
구현
#include <bits/stdc++.h>
using namespace std;
const long long INF = 1e18;
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
int n;
cin >> n;
vector<pair<long long,long long>> houses(n);
for (int i = 0; i < n; i++) cin >> houses[i].first >> houses[i].second;
// x, t 쌍으로 정렬
sort(houses.begin(), houses.end());
vector<long long> x(n), t(n);
for (int i = 0; i < n; i++) {
x[i] = houses[i].first;
t[i] = houses[i].second;
}
// dp_l[i][j]: [i,j] 구간 커버, 현재 위치 x[i]에서 최소 경과 시간
// dp_r[i][j]: [i,j] 구간 커버, 현재 위치 x[j]에서 최소 경과 시간
vector<vector<long long>> dp_l(n, vector<long long>(n, INF));
vector<vector<long long>> dp_r(n, vector<long long>(n, INF));
// 초기화: 단일 집
for (int i = 0; i < n; i++) {
dp_l[i][i] = max(x[i], t[i]); // 0에서 x[i]까지 이동, t[i]까지 대기
dp_r[i][i] = dp_l[i][i];
}
// 구간 길이 늘려가며 DP
for (int len = 2; len <= n; len++) {
for (int i = 0; i + len - 1 < n; i++) {
int j = i + len - 1;
// [i+1,j]에서 왼쪽(x[i+1])으로 오고, x[i]로 확장
if (dp_l[i+1][j] < INF) {
long long arrive = dp_l[i+1][j] + (x[i+1] - x[i]);
arrive = max(arrive, t[i]);
dp_l[i][j] = min(dp_l[i][j], arrive);
}
if (dp_r[i+1][j] < INF) {
long long arrive = dp_r[i+1][j] + (x[j] - x[i]);
arrive = max(arrive, t[i]);
dp_l[i][j] = min(dp_l[i][j], arrive);
}
// [i,j-1]에서 오른쪽(x[j-1])으로 오고, x[j]로 확장
if (dp_r[i][j-1] < INF) {
long long arrive = dp_r[i][j-1] + (x[j] - x[j-1]);
arrive = max(arrive, t[j]);
dp_r[i][j] = min(dp_r[i][j], arrive);
}
if (dp_l[i][j-1] < INF) {
long long arrive = dp_l[i][j-1] + (x[j] - x[i]);
arrive = max(arrive, t[j]);
dp_r[i][j] = min(dp_r[i][j], arrive);
}
}
}
// 전체 [0, n-1] 커버 후 0으로 돌아오는 시간
long long ans = INF;
if (dp_l[0][n-1] < INF) ans = min(ans, dp_l[0][n-1] + x[0]);
if (dp_r[0][n-1] < INF) ans = min(ans, dp_r[0][n-1] + x[n-1]);
cout << ans << "\n";
return 0;
}문제 P11 - 가로등 (BOJ 32069)
문제 요약: 수직선 0~L 위 N개 가로등이 있다. 각 점의 “어두운 정도”는 가장 가까운 가로등까지의 거리다. K번째로 작은 어두운 정도 값들을 순서대로 출력한다.
제한: L ≤ 10^18, N ≤ 300,000, K ≤ 500,000, 시간 2초
예제: L=10, 가로등=[1,4,8], K=4 → 0, 0, 0, 1
아이디어
가로등 위치에서 어두운 정도는 0이다. 두 인접 가로등 사이 거리가 d이면, 그 구간 중간 점에서 어두운 정도가 가장 크고(floor(d/2)), 양 끝은 0이다. 각 구간의 어두운 정도 분포를 계산해서 K번째 작은 값을 구한다.
단순한 접근
이진 탐색: “어두운 정도가 v 이하인 점의 수”를 계산해서 K번째를 찾는다.
가로등이 정렬되어 있다면, 인접 가로등 사이 거리 d인 구간에서 어두운 정도가 v 이하인 정수 좌표 점의 수를 계산할 수 있다.
구체적 분포
- 인접 가로등 위치 a, b (b = a + d, d > 0)
- 이 구간 내 정수 점 중 어두운 정도 = min(x-a, b-x)
- min(x-a, b-x) ≤ v인 x의 수: x-a ≤ v이거나 b-x ≤ v, 즉 x ≤ a+v 또는 x ≥ b-v
- 구간 [a, b] 내에서: [a, a+v]의 점 수 + [b-v, b]의 점 수 - 중복
이를 이용해 이진 탐색으로 K번째 값을 찾는다.
구체적으로: 어두운 정도 v 이하인 점의 총 수 f(v)를 구하고, f(v) >= K인 최소 v를 이진 탐색.
그 다음 f(v-1)부터 K까지의 값들을 출력(모두 v).
시간복잡도 확인
이진 탐색 O(log L), 각 단계에서 N개 구간 처리 O(N). 전체 O(N log L). N=300,000, log L = 60이면 1.8×10^7. 충분하다.
구현
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
ll L;
int n, k;
cin >> L >> n >> k;
vector<ll> pos(n);
for (int i = 0; i < n; i++) cin >> pos[i];
sort(pos.begin(), pos.end());
// f(v) = 어두운 정도가 v 이하인 정수 점의 수
auto count_le = [&](ll v) -> ll {
ll cnt = 0;
// 왼쪽 끝 [0, pos[0]] 구간
{
ll d = pos[0]; // 가장 가까운 가로등은 pos[0]
// x in [0, pos[0]], 어두운 정도 = pos[0] - x (가장 가까운 가로등)
// pos[0] - x <= v => x >= pos[0] - v
ll lo = max(0LL, pos[0] - v);
ll hi = pos[0];
cnt += hi - lo + 1;
}
// 오른쪽 끝 [pos[n-1], L] 구간
{
ll lo = pos[n-1];
ll hi = min(L, pos[n-1] + v);
cnt += hi - lo + 1;
}
// 인접 가로등 사이 구간 [pos[i], pos[i+1]]
for (int i = 0; i + 1 < n; i++) {
ll a = pos[i], b = pos[i+1];
// x in (a, b), 어두운 정도 = min(x-a, b-x)
// min(x-a, b-x) <= v
// x-a <= v => x <= a+v
// b-x <= v => x >= b-v
ll lo1 = a + 1, hi1 = min(b - 1, a + v);
ll lo2 = max(a + 1, b - v), hi2 = b - 1;
ll covered = 0;
if (hi1 >= lo1) covered += hi1 - lo1 + 1;
if (hi2 >= lo2) covered += hi2 - lo2 + 1;
// 중복: [max(lo1,lo2), min(hi1,hi2)]
ll olo = max(lo1, lo2), ohi = min(hi1, hi2);
if (ohi >= olo) covered -= ohi - olo + 1;
cnt += covered;
}
return cnt;
};
// 이진 탐색으로 K번째 값 찾기
ll lo = 0, hi = L;
while (lo < hi) {
ll mid = (lo + hi) / 2;
if (count_le(mid) >= k) hi = mid;
else lo = mid + 1;
}
ll ans_val = lo;
ll prev_cnt = (ans_val > 0) ? count_le(ans_val - 1) : 0;
// prev_cnt+1 ~ k번째까지 출력 (모두 ans_val)
// 1~prev_cnt번째는 0~ans_val-1, prev_cnt+1~k번째는 ans_val
for (ll i = 1; i <= k; i++) {
if (i <= prev_cnt) {
// 재귀적으로 구해야 하지만, 문제에서 오름차순 출력이므로
// 0, 1, ..., ans_val-1 값들을 각 개수만큼 출력
// 여기서는 단순히 이진탐색을 각 값에 대해 반복
}
}
// 실용적 구현: 0부터 ans_val까지 각 값의 개수를 구해 출력
ll printed = 0;
for (ll v = 0; v <= ans_val && printed < k; v++) {
ll cnt_v = count_le(v) - (v > 0 ? count_le(v-1) : 0);
ll to_print = min(cnt_v, k - printed);
for (ll j = 0; j < to_print; j++) {
cout << v << "\n";
printed++;
}
}
return 0;
}문제 P12 - 먼 카드 (BOJ 34115)
문제 요약: 2N장 카드, 1~N이 각 2장씩 있다. k가 적힌 두 카드 사이의 카드 수를 “k 사이 카드 수”라 할 때, 모든 k에 대한 최댓값을 구한다.
제한: N ≤ 2000
예제: [1, 2, 2, 4, 3, 1, 3, 4] → 4
아이디어
각 숫자 k의 첫 번째 위치와 두 번째 위치를 기록해서 차이 - 1을 계산한다.
단순한 접근
배열을 한 번 순회하면서 각 숫자의 첫 등장 위치를 기록하고, 두 번째 등장 시 차이 - 1을 계산한다. O(N).
시간복잡도 확인
O(N). N ≤ 2000이므로 O(N^2)도 충분하지만 O(N)으로 바로 풀린다.
구현
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
int n;
cin >> n;
vector<int> a(2*n);
for (int i = 0; i < 2*n; i++) cin >> a[i];
vector<int> first(n+1, -1);
int ans = 0;
for (int i = 0; i < 2*n; i++) {
int v = a[i];
if (first[v] == -1) {
first[v] = i;
} else {
int gap = i - first[v] - 1;
ans = max(ans, gap);
}
}
cout << ans << "\n";
return 0;
}