문제를 푼 날짜: 2025. 06. 27

#graphs #shortest_path #dijkstra

내 풀이(C++)

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;
const int INF = 1000000000 / 3;

// N: 정점의 개수, E: 간선의 개수
int N, E;

// (to, weight)
vector<vector<pair<int, int>>> graph;

// Return: depart부터 arrival 까지 최단경로
int dijkstra(int depart, int arrival);

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> N >> E;
    graph.assign(N+1, vector<pair<int, int>>());

    for(int i = 0; i < E; i++){
        int src, dst, w;
        cin >> src >> dst >> w;
        graph[src].push_back({dst, w});
        graph[dst].push_back({src, w});
    }

    // 경유 지점
    int stop1, stop2;
    cin >> stop1 >> stop2;

    // 경우의 수는 1->stop1->stop2->N 또는 1->stop2->stop1->N
    int dist_two_stop = dijkstra(stop1, stop2);
    int ans = min(dijkstra(1, stop1) + dist_two_stop + dijkstra(stop2, N), dijkstra(1, stop2) + dist_two_stop + dijkstra(stop1, N));
    if(ans >= INF) cout << -1;
    else cout << ans;
    return 0;
}

int dijkstra(int depart, int arrival){
    vector<int> distance(N+1, INF);
    // (거리, 노드번호)
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;

    distance[depart] = 0;
    pq.push({0, depart});

    while(!pq.empty()){
        auto [cost, now] = pq.top();
        pq.pop();

        // 이미 더 짧은 경로 존재하면 skip
        if(distance[now] < cost) continue;

        for(auto [next, weight] : graph[now]){
            int new_cost = cost + weight;
            if(new_cost < distance[next]){
                distance[next] = new_cost;
                pq.push({new_cost, next});
            }
        }
    }
    return distance[arrival];
}

🔎 문제 설명

• 정점 1번에서 N번까지 가는데, 주어진 두 정점(stop1, stop2)을 반드시 경유해야 한다.
• 경로 순서는 다음 두 가지가 가능:
  • $1 \rightarrow \text{stop1} \rightarrow \text{stop2} \rightarrow N$
  • $1 \rightarrow \text{stop2} \rightarrow \text{stop1} \rightarrow N$
• 이 두 경우 중 최단 경로의 길이를 구하라.

⛔ 내가 틀렸던 부분

1. INF 값 오버플로우 주의

• 처음엔 INF = 10^9로 설정했는데,
• 최단거리끼리 3번 덧셈을 하면 $10^9 \times 3 = 3 \times 10^9$ 이 되어 int 오버플로우가 발생할 수 있었다.
• → 수정 : INF = 10^9 / 3 로 설정해서 여러 번 더해도 안전하도록 했다.

2. 무방향 간선 입력 실수

• 입력을 받을 때 아래처럼 한 방향만 추가했음:

  graph[src].push_back({dst, w});

• 그러나 무방향이므로 반드시 반대 방향도 추가해야 한다:

  graph[dst].push_back({src, w});

  3. dijkstra 호출 최적화

• 내 풀이는 다익스트라를 5번 호출했음:
  • dijkstra(1, stop1)
  • dijkstra(stop1, stop2)
  • dijkstra(stop2, N)
  • dijkstra(1, stop2)
  • dijkstra(stop1, N)
• 그러나 아래처럼 하면 3번만 호출해도 모든 정보를 얻을 수 있다:
  • 다익스트라(1) → stop1, stop2, N까지 거리 얻음
  • 다익스트라(stop1) → stop2, N까지 거리 얻음
  • 다익스트라(stop2) → N까지 거리 얻음

이 문제에서는 시간 제한이 엄청 빡빡하지는 않아 다익스트라 5번 호출을 해도 문제가 없었으나, 더 타이트한 조건이라면 위와 같이 최적화할 수 있다.

최초 풀이 날짜: 2025. 06. 01

재풀이 날짜: 2025. 06. 06

#math #implementation #arithmetic

최초 풀이 (C++)

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    cin >> N;

    int cha = N - 2013;

    // 지 구하기
    int ji = (5 + cha) % 12;
    if(ji < 0) ji += 12;
    cout << char(ji + 'A');

    // 간 구하기
    int gan = (9 + cha) % 10;
    if(gan < 0) gan += 10;
    cout << gan;

    return 0;
}

재풀이 (C++)

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    cin >> N;

    int cha = N - 2013;

    // 지 구하기
    int ji = ((5 + cha) % 12 + 12) % 12;
    cout << char(ji + 'A');

    // 간 구하기
    int gan = ((9 + cha) % 10 + 10) % 10;
    cout << gan;

    return 0;
}

코멘트

• 분명히 중1 때 수월히 풀었던 문제인데..지금 보니 생각할 부분이 많은 문제
• 첫째로, 1년이 갑자년이 아니라는 점을 헷갈리지 말아야 함!
  • 문제에서도 2013년이 F9년 인 점을 이용해서 계산하라고 힌트를 주고 있음.
• 간지를 구해야 하는 입력 N과 간지를 알고 있는 2013년과의 차이를 통해 N년의 간지를 계산하면 되는데, 코드를 잘 짜놓고 나중에 내 코드를 다시 보니 나머지 연산이 헷갈리는 것이다!
  • 이 기회를 통해 나머지 연산을 잘 정리해보기로 했다.

나머지 연산 기초

• a % b 연산을 할 때, C와 Python 간에 연산의 결과에 차이가 생길 때가 있다. 바로 a 나 b의 부호가 음수일 때다. 아래의 예시를 통해 확인해보자.

1. a > 0 , b>0

   10 // 3
   10 % 3

Python: 3, 1 C++: 3, 1

당연하게도 a와 b가 모두 양수인 경우 두 언어 모두 우리가 아는 결과와 같다.

2.  **a < 0 ,  b>0**
```python
-10 // 3
-10 % 3
- - - - - - -
Python: -4, 2
C++: -3, -1

이 문제에서 등장하는 케이스가 되겠다. (N < 2013) Python의 경우 나머지가 양수, C++의 경우 나머지가 음수가 나왔다.

3. a > 0 , b<0

   10 // -3
   10 % -3

Python: -4, -2 C++: -3, 1

이번에는 반대로 나머지가 Python이 음수, C++이 양수였다.

4.  **a < 0 ,  b<0**
```python
-10 // -3
-10 % -3
- - - - - - -
Python: 3, -1
C++: 3, -1

이번에는 두 언어 모두 똑같이 나머지가 음수로 나왔다.

음수 나머지에 대한 이해 + 코드 작성 팁

• 위 예시들을 보면 알 수 있듯이, 언어에 따라 동일한 a, b에 대해서도 % 연산 결과가 다를 수 있다.
• 보통 우리는 나머지 연산 결과가 0 이상이길 기대하지만, a와 b 중 하나가 음수이면 나머지가 음수가 될 수 있음에 유의해야 한다.

🎯 간지 문제 적용 예시

• 2013년을 기준으로 어떤 해의 간지(간, 지)를 구하려 할 때,
  • 기준 연도와의 차이를 계산하고,
  • 이를 10과 12로 나눈 나머지를 통해 간과 지를 결정하는 아이디어를 사용했다.
• 2013년의 ‘지’가 F(5)이므로
  • 차이가 +1인 2014년은 G(6),
  • 차이가 -5인 2008년은 A(0)이 된다.
• 그런데 차이가 -6인 2007년의 경우,
  • (5-6) % 12는 Python에서는 11, C++에서는 -1이 되며,
  • 지는 0부터 11까지 존재하므로, 음수가 나오면 인덱스 오류가 발생할 수 있다.
  • Python 연산의 결과로 나온 11은 우리가 원하는 2007년의 ‘지‘이며, C++ 연산의 결과로 나온 -1은, 0번 인덱스보다 1칸 이전이라고 생각할 수 있다.

💡 그래서 해결책은?

• 나머지 연산 결과가 음수일 가능성을 제거하기 위해,

  (a % b + b) % b

를 사용하면 된다.

• 이 식은 a % b가 음수일 경우 b를 더해서 양수로 만들고, 혹시나 b 이상이 되었을 경우 다시 % b로 조정해준다.
• a % b의 결과가 이미 음이 아닐 경우(0 이상 b미만), b를 더해도 2b 미만이기 때문에 이 식의 결과는 여전히 a % b와 동일하다.
• 결과적으로 이 표현은 항상 0 이상 b 미만의 값을 만들어 준다.

문제를 푼 날짜: 2025. 06. 04

#binary_search #parametric_search

Parametric Search란?

(https://ialy1595.github.io/post/parametric-search/ 의 내용을 참고하였습니다.)

• Parametric Search는 최댓값/최솟값을 구하는 최적화 문제를, "어떤 값 x가 조건을 만족하는가?"라는 결정문제로 바꾼 뒤,
• Binary Search*를 이용해 답을 빠르게 찾는 문제 해결 기법이다.
• 실생활에서 정확한 값을 한 번에 구하지 않고 "이 정도면 되나?"를 반복해서 조금씩 조정하며 원하는 값을 찾는 식(예: 저울에 고기를 여러 번 올리며 200g 맞추기)의 사고라고 생각할 수 있다.
• 파라메트릭 서치를 쓸 수 있으려면,

1. 최댓값/최솟값을 구하는 문제여야 하고,
2. 조건을 만족하는 값들의 구간이 연속적이어야 하며,
3. 답의 범위가 이산적이거나(정수), 허용 오차가 있어야 한다.

아이디어

이 문제는 "최댓값을 구하는 문제"이고, 그 값을 직접 계산하기엔 복잡하다. 따라서 조건을 만족하는지 확인하는 결정 문제로 바꾼 후, 이분 탐색을 이용하는 Parametric Search 기법을 사용한다.

✔️ H 높이로 잘랐을 때, 나무 길이의 합이 M 이상인가?를 판단하는 결정 문제로 변형하고
✔️ 만족한다면 더 높이 자를 수 있는지 탐색
✔️ 만족하지 못한다면 톱 높이를 낮추는 방향으로 탐색

내 코드 (C++)

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
using ll = long long;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, M;
    cin >> N >> M;

    vector<int> trees(N);

    for(int i = 0; i < N; i++){
        cin >> trees[i];
    }

    int low = 0, high = 1000000000;
    int ans;

    while(low <= high){
        int mid = (low + high) / 2;

        ll sum = 0;
        for(auto &tree: trees){
            sum += max(0, tree - mid);
        }

        // 높이를 mid로 설정했을 때 요건을 만족 -> 정답 후보로 저장하고, 높이를 올리기
        if(sum >= M) {
            ans = mid;
            low = mid + 1;
        }

        // 요건 만족 x -> 높이를 낮춰봄
        else high = mid - 1;
    }

    cout << ans;
    return 0;
}

분석

• 시간복잡도: $O(N logH)$ -> $H$는 나무의 최대 높이인 $10^9$. -> 시간 내에 충분히 들어옴!
• 처음에 sum을 int형으로 선언해서 WA가 떴고, 원인을 찾지 못했음. -> sum은 $10^6 \times 10^9 = 10^{15}$으로 int 범위 충분히 초과 가능! -> 항상 변수의 범위에 유의할 것
• 톱 높이는 최소 0부터, 최대는 문제에 주어진 나무 높이의 최댓값(= $10^9$)까지 가능하다. → 따라서 low = 0, high = 1,000,000,000으로 탐색 범위를 설정한다.

• 최댓값을 $10^9$ 대신 입력된 나무 중 제일 높은 나무의 높이로 잡아도 된다. (조금 더 최적화된 코드)

문제를 푼 날짜: 2025. 06. 03

#dp

아이디어

• 각 인덱스를 기준으로 "증가"하는 부분 수열과, "감소"하는 부분 수열을 각각 계산해서 합치는 방식.
• DP(동적 프로그래밍)를 두 번 적용!
• DP1[i] : i번째 원소까지 고려했을 때, 해당 원소를 끝으로 하는 가장 긴 증가 부분 수열의 길이
• DP2[i] : i번째 원소부터 시작해서, 해당 원소를 시작으로 하는 가장 긴 감소 부분 수열의 길이 (뒤에서부터 거꾸로!)
• DP2를 '뒤에서부터 센 가장 긴 증가 부분 수열'로 생각.
• 각 인덱스 i에 대해 DP1[i] + DP2[i] - 1 (-1 하는 이유는 i가 중복 포함되니까!)
• 이 값의 최댓값이 곧 가장 긴 바이토닉 부분 수열의 길이

내 풀이(C++)

#include <iostream>

using namespace std;

int A[1010];
int DP1[1010];
int DP2[1010];

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    int max;
    cin >> N;

    for(int i = 0; i < N; i++){
        cin >> A[i];

        max = 0;
        for(int j = 0; j < i; j++){
            if(A[j] < A[i] && DP1[j] > max) max = DP1[j];
        }
        DP1[i] = max + 1;
    }

    for(int i = N-1; i >= 0; i--){
        max = 0;
        for(int j = N -1; j > i; j--){
            if(A[i] > A[j] && DP2[j] > max) max = DP2[j];
        }
        DP2[i] = max + 1;
    }

    max = 0;

    for(int i = 0; i < N; i++){
        if(DP1[i] + DP2[i] > max) max = DP1[i] + DP2[i];
    }

    cout << max - 1;
    return 0;
}

문제를 푼 날짜: 2024. 01. 11

#dp #lis

아이디어

$DP[i] =$ $i$번째 원소가 마지막이 되도록 추가했을 때 최대 길이

#### Substring vs Subsequence 헷갈리지 말기!!

• 이 문제는 Subsequence를 구하는 문제

내 풀이(C++)

#include <iostream>

using namespace std;

/*
DP + Backtracking
DP[i] : i번 쨰 원소를 추가했을 때의 최대 길이(이전까지의 원소들 중 자기보다 작은 값의 최대 DP값 + 1)
*/
int A[1010];
int DP[1010];

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    int max;
    cin >> N;

    for(int i = 0; i < N; i++){
        cin >> A[i];

        max = 0;
        for(int j = 0; j < i; j++){
            if(A[j] < A[i] && DP[j] > max){
                max = DP[j];
            }
        }
        DP[i] = max + 1;
    }

    max = 0;

    for(int i = 0; i < N; i++){
        if(DP[i] > max) max = DP[i];
    }

    cout << max;
    return 0;
}

(a) 집합: ${ z \in \mathbb{C} \mid |z| < 1 }$

• Closed: X
  → $|z| = 1$에 있는 점들은 이 집합의 limit point이지만 포함되지 않음.

• Open: O
  → 임의의 점 $p$에 대해, 반지름 $\varepsilon = 1 - |p|$인 neighborhood $N_\varepsilon(p)$가 집합에 완전히 포함됨.
  → 모든 점이 interior point.

• Perfect: X
  → closed가 아니므로 perfect일 수 없음.

• Bounded: O
  → 모든 점 $z$에 대해 $|z| < 1$이므로, 중심 0, 반지름 1인 ball 안에 포함됨.

(b) 집합: ${ z \in \mathbb{C} \mid |z| \le 1 }$

• Closed: O
  → 극한값이 $|z| = 1$인 수열들이 모두 이 집합 안에 수렴함. 모든 limit point 포함.

• Open: X
  → 경계점 $z$ such that $|z| = 1$는 interior point가 아님.

• Perfect: O
  → 집합은 닫혀 있고, 모든 점이 limit point.
  → 예: 원판 내부의 점들 근처에는 언제나 다른 점들이 있음. 경계의 점도 limit point.

• Bounded: O
  → 모든 $z$에 대해 $|z| \le 1$이므로 유계.

(c) 집합: 유한 집합, 예: ${(1, 0), (2, 0)}$

• Closed: O
  → 유한 집합은 limit point가 없음. (2.20 Corollary) 따라서 vacuously closed(공허하게 닫힘; 가정이 거짓이므로 항상 참).

• Open: X
  → 어떤 점 $p$에 대해 반지름 $\varepsilon > 0$인 근방은 집합의 다른 점을 포함하지 않음.
  → 즉, interior point가 없음.

• Perfect: X
  → limit point가 존재하지 않으므로, perfect 아님.

• Bounded: O
  → 유한 집합은 항상 어떤 유한한 반지름의 ball 안에 포함될 수 있음.

(d) 집합: $\mathbb{Z} \subset \mathbb{R}$

• Closed: O
  → Limit Point가 없으므로(모든 점이 isolated) vacuously closed

• Open: X
  → 정수 $n$에 대해 아무리 작은 neighborhood $N_\varepsilon(n)$도 실수 $n + \delta \in \mathbb{R} \setminus \mathbb{Z}$ 포함함. (Interior Point의 정의: $E$에 대해 정의된 $p$에 대하여 $N \subset E$ 인 neighborhood $N$ 이 존재하는 $p$) → Interior point 없음

• Perfect: X
  → 집합 내 어떤 점도 limit point가 아님. (Every point is isolated)

• Bounded: X
  → $\mathbb{Z}$는 음의 무한대로도, 양의 무한대로도 발산 → 유계 아님.

(e) 집합: $E = {1/n \mid n \in \mathbb{N} }$

• Closed: X
  → 0은 limit point이지만 집합에 포함되지 x

• Open: X
  → 어떤 $1/n$의 neighborhood도 다른 원소들을 포함하지 않음.

• Perfect: X
  → 애초에 not closed여서 안 됨.

• Bounded: O
  → $0 < 1/n \le 1$ → 반지름 1인 ball 안에 전부 포함됨.

(f) 집합: 전체 공간 $\mathbb{R}^2$

• Closed: O
  → 전체 공간은 limit point 포함 조건을 자동으로 만족.

• Open: O
  → 모든 점에 대해 어떤 반지름의 neighborhood도 전체 공간 안에 있음.

• Perfect: O
  → 닫혀 있고, 모든 점이 limit point. 즉, interior에도 점이 있고, 극한 접근 가능.

• Bounded: X
  → 어떤 반지름의 ball도 전체 공간을 포함할 수 없음 → 유계 아님.

(g) 집합: 실수 구간 $(a, b) \subset \mathbb{R}$

• Closed: X
  → 경계점 $a$, $b$는 limit point이지만 포함되어 있지 않음.

• Open:

  • O (in $\mathbb{R}^1$)
    → 모든 점 $x \in (a, b)$에 대해 $N_\varepsilon(x) \subset (a, b)$
  • X (in $\mathbb{R}^2$)
    → $x = 0$ 위에 있는 1차원 집합일 뿐이므로 2차원 열린 집합이 아님.

• Perfect: X
  → 닫혀 있지 않음 → perfect일 수 없음

• Bounded: O
  → 유한 길이의 구간은 항상 bounded

✅ 2.22 De Morgan’s Law for Complements (드 모르간 법칙)

Theorem
Collection ${E_\alpha}$ 에 대해 다음이 성립한다: $$ \left( \bigcup_\alpha E_\alpha \right)^c = \bigcap_\alpha E_\alpha^c $$

설명 및 증명

• 좌변을 $A = \left( \bigcup_\alpha E_\alpha \right)^c$,
  우변을 $B = \bigcap_\alpha E_\alpha^c$ 라 하자.
• 이제 $A \subset B$, $B \subset A$ 임을 모두 보이면 $A = B$임을 알 수 있다.

(1) $A \subset B$
$x \in A$ 라면, $x \notin \bigcup_\alpha E_\alpha$
→ 모든 $\alpha$에 대해 $x \notin E_\alpha$
→ 모든 $\alpha$에 대해 $x \in E_\alpha^c$
→ $x \in \bigcap_\alpha E_\alpha^c = B$

(2) $B \subset A$
$x \in B$ 라면, 모든 $\alpha$에 대해 $x \in E_\alpha^c$
→ 모든 $\alpha$에 대해 $x \notin E_\alpha$
→ $x \notin \bigcup_\alpha E_\alpha$
→ $x \in \left( \bigcup_\alpha E_\alpha \right)^c = A$

결론
$$ \left( \bigcup_\alpha E_\alpha \right)^c = \bigcap_\alpha E_\alpha^c $$

✅ 2.23 열린 집합과 닫힌 집합의 여집합 관계

Theorem

집합 $E$는 open $\Leftrightarrow$ $E^c$는 closed

📝 Proof

(⇒ 방향) $E$가 open이면, $E^c$는 closed

• $x$가 $E^c$의 limit point라고 하자.
• 그러면 모든 $x$의 neighborhood는 $E^c$의 점을 하나 이상 포함.
• 이는 곧 $x$가 $E$의 interior point가 아님을 의미.
• 그런데 $E$는 open이므로 모든 점은 interior point이어야 함 → $x \notin E$
• 즉 $x \in E^c$ → limit point가 포함됨 → $E^c$는 closed

(⇐ 방향) $E^c$가 closed이면, $E$는 open

• $x \in E$ 라고 하자 → $x \notin E^c$
• $x$는 $E^c$의 limit point가 아니므로, 어떤 neighborhood $N$이 존재해서 $N \cap E^c = \emptyset$
• 따라서 $N \subset E$ → $x$는 $E$의 interior point
• 모든 $x \in E$에 대해 interior point이므로 $E$는 open

📌 Corollary

$F$가 closed ⇔ $F^c$가 open

✅ 2.24 Theorem: Open/Closed 집합의 연산

다음이 성립한다:

1. (a) 임의의 open set들의 collection ${G_\alpha}$에 대해,
   $$\bigcup_\alpha G_\alpha$$
   는 open set이다.

2. (b) 임의의 closed set들의 collection ${F_\alpha}$에 대해,
   $$\bigcap_\alpha F_\alpha$$
   는 closed set이다.

3. (c) 유한 개의 open set $G_1, \dots, G_n$에 대해,
   $$\bigcap_{i=1}^n G_i$$
   는 open set이다.

4. (d) 유한 개의 closed set $F_1, \dots, F_n$에 대해,
   $$\bigcup_{i=1}^n F_i$$
   는 closed set이다.

📝 Proof Sketch

• (a) $x \in \bigcup G_\alpha$ 이면 어떤 $\alpha$에 대해 $x \in G_\alpha$이고, $x$는 그 $G_\alpha$의 interior point → $x$는 전체 합집합의 interior point.
• (b) 드 모르간 법칙:
  $$\left( \bigcap_\alpha F_\alpha \right)^c = \bigcup_\alpha F_\alpha^c$$
  우변은 open이므로, $\bigcap_\alpha F_\alpha$ 는 closed.
• (c) $x \in \bigcap G_i$ 에 대해 각 $G_i$는 open이므로, 반지름 $r_i$의 neighborhood $N_i \subset G_i$ 존재.
  $$r = \min(r_1, \dots, r_n)$$
  으로 잡은 neighborhood $N$은 모든 $G_i$에 포함되므로 $x$는 interior point.
• (d) (c) 의 여집합을 취해 적용.

✅ 2.25 Examples: 유한성과 무한성의 차이

• (c), (d) 조건은 유한한 경우에만 성립하며, 무한한 경우엔 깨진다.

❗ 반례: 무한 교집합

• $G_n = (-1/n, 1/n)$ 은 각각 open이다.
• $$\bigcap_{n=1}^\infty G_n = {0}$$
• 하지만 ${0}$ 은 open이 아니다.

👉 따라서 무한히 많은 open set들의 교집합은 open이 아닐 수 있음.

❗ 반례: 무한 합집합

• 마찬가지로, 무한히 많은 closed set들의 합집합은 closed가 아닐 수 있음.
• 예: $$F_n = \left[ -1 + \frac{1}{n},\ 1 - \frac{1}{n} \right] \quad \text{for } n = 2, 3, 4, \dots$$ 은 각각 closed 이다.
• 하지만 $$ F = \bigcup_{n=2}^{\infty} F_n = (-1, 1) $$ 은 open이다. 👉 따라서 무한히 많은 closed set들의 합집합은 closed가 아닐 수 있음.

문제를 푼 날짜: 25. 05. 27.

#greedy

아이디어

• 꽤 오래 고민한 문제였지만 쉽지 않아 Editorial 및 GPT의 도움을 받았다.
• 병사의 수를 최소화해야 하므로, 왼쪽부터 탐색하며 가능한 한 긴 유효 조각(최대 3자리)을 만든다.
• 현재 위치(pos)에서 3자리까지 조각을 시도하며, 유효하지 않으면 길이를 줄인다.
  • 유효 조건: 조각은 0으로 시작하지 않고, 정수 값이 1 이상 641 이하.
  • 0으로는 시작할 수 없으므로 이전 유효 조각의 마지막 숫자로 현재 위치(pos)를 이동 (이전 유효조각은 길이가 1만큼 줄어도 여전히 유효)
• 가장 긴 유효 조각을 찾으면 그만큼 이동(pos += len), 병사 수 +1
• 이를 문자열 끝까지 반복하여 총 병사 수를 구한다.

Pseudocode (Greedy)

pos ← 0
cnt ← 0
n ← |s|   # 문자열 길이

while pos < n do
    cnt ← cnt + 1
    len ← min(3, n − pos)

    loop  # 이 안에서 “한 조각”을 확정할 때까지 반복
        # 1) 새 조각이 '0'으로 시작하면 → 잘못 끊어진 경계이므로
        if s[pos] == '0' then
            pos ← pos − 1
            len ← min(3, n − pos)
            continue    # 다시 같은 조각에서 재시도
        end if

        # 2) s[pos..pos+len−1] 을 숫자로 변환
        num ← 0
        for i in 0 … len−1 do
            num ← num * 10 + (s[pos+i] − '0')
        end for

        # 3) 1 ≤ num ≤ 641 이면 이 길이로 확정하고 다음 조각으로
        if num ≤ 641 then
            pos ← pos + len
            break      # while‐loop 빠져나가서 다음 조각 시작
        else
            len ← len − 1  # 너무 크면 한 글자 줄여 다시 검사
        end if
    end loop
end while

print cnt

C++ 풀이 (Greedy)

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    cin >> N;

    string s;
    cin >> s;

    int pos = 0;
    int cnt = 0;



    while(pos < int(s.length())){
        cnt++;
        int len = min(3, N - pos);

        while(1){
            int num = s[pos] - '0';
            if(num == 0){
                pos--;
                len = min(3, N - pos);
                continue;
            }

            for(int i = pos + 1; i < pos + len; i++){
                num = num * 10 + (s[i] - '0');
            }

            if(num <= 641){
                pos += len;
                break;
            } else len--;
        }
    }

    cout << cnt;
    return 0;
}

최초 풀이: 2025. 06. 01.

#sliding_window #string

아이디어

• 전형적인 'sliding_window' 문제이다.
• 0번째 index부터 시작하는 길이 |P|의 window를 잡아서 A, C, G, T 의 개수를 기록하고, 한 칸씩 이동하며 없어지는 문자와 새로 들어오는 문자를 확인하여 개수를 변화시켜주자.

Substrings vs Subsequences

• Substring: 원래의 문자열에서 연속된 구간을 떼어낸 부분 문자열이다.
  • 예: "abcdef"에서 "bcd"는 substring이다.
• Subsequence: 원래의 문자열에서 일부 문자를 선택하여 순서만 유지한 채 나열한 부분 문자열이다. 연속적일 필요는 없다.
  • 예: "abcdef"에서 "acf"는 subsequence이다. (연속되지 않아도 됨)

이 문제에서는 Substring을 요구한다는 점에 주의하자! (Subsequence가 아님!)

최초 풀이(C++)(내 풀이)

#include <iostream>
#include <string>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int S, P;
    cin >> S >> P;

    string DNA;
    cin >> DNA;

    int A, C, G, T;
    cin >> A >> C >> G >> T;

    int num_A = 0, num_C = 0, num_G = 0, num_T = 0;
    int ans = 0;
    for(int i = 0; i < P; i++){
        if(DNA[i] == 'A') num_A++;
        else if(DNA[i] == 'C') num_C++;
        else if(DNA[i] == 'G') num_G++;
        else if(DNA[i] == 'T') num_T++;
    }

    if(num_A >= A && num_C >= C && num_G >= G && num_T >= T) ans++;

    for(int i = P; i < S; i++){
        if(DNA[i - P] == 'A') num_A--;
        else if(DNA[i - P] == 'C') num_C--;
        else if(DNA[i - P] == 'G') num_G--;
        else if(DNA[i - P] == 'T') num_T--;

        if(DNA[i] == 'A') num_A++;
        else if(DNA[i] == 'C') num_C++;
        else if(DNA[i] == 'G') num_G++;
        else if(DNA[i] == 'T') num_T++;

        if(num_A >= A && num_C >= C && num_G >= G && num_T >= T) ans++;
    }

    cout << ans;
    return 0;
}

개선된 풀이(by GPT)

#include <iostream>
#include <string>
using namespace std;

// 문자 인덱스 매핑 함수
int idx(char c) {
    if (c == 'A') return 0;
    if (c == 'C') return 1;
    if (c == 'G') return 2;
    return 3; // 'T'
}

// 현재 윈도우의 카운트가 조건을 만족하는지 검사
bool is_valid(int count[], int required[]) {
    for (int i = 0; i < 4; ++i) {
        if (count[i] < required[i]) return false;
    }
    return true;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int S, P;
    cin >> S >> P;
    string DNA;
    cin >> DNA;

    int required[4]; // A, C, G, T가 최소 몇 개 필요한지
    for (int i = 0; i < 4; ++i) cin >> required[i];
    int count[4] = {0,}; // 현재 윈도우의 A, C, G, T 개수

    // 초기 윈도우 설정
    for (int i = 0; i < P; ++i) {
        count[idx(DNA[i])]++;
    }

    int ans = 0;
    if (is_valid(count, required)) ans++;

    // 슬라이딩 윈도우
    for (int i = P; i < S; ++i) {
        count[idx(DNA[i - P])]--; // 왼쪽 문자 제거
        count[idx(DNA[i])]++;     // 오른쪽 문자 추가
        if (is_valid(count, required)) ans++;
    }

    cout << ans << '\n';
    return 0;
}

• 내 풀이를 작성할 때 main문이 지저분하다고 생각하였는데, 이런 식으로 함수를 이용하면 조금 더 깔끔하게 풀이를 적을 수 있을 것 같다.

최초 풀이: 2023. 12. 15.

재풀이: 2025. 05. 22.

#data_structures #sorting #binary_search #set #hash_set

아이디어

$O(N)$의 시간복잡도를 가진 Linear Search(선형 탐색)를 이용한다면 최악의 경우 $M$ 개의 수에 대해 $A$의 0번째부터 $N-1$ 번 째 원소까지 탐색하게 되므로 $O(NM)$ 의 시간복잡도를 가지게 되어 시간초과가 발생한다.

우리는 단순히 특정 값이 $A$에 포함되었는지의 여부가 궁금하므로 $O(N)$의 시간복잡도를 가진 Binary Search(이진탐색) 을 이용하여 시간복잡도를 개선할 수 있다. Binary Search를 하기 위해서는 먼저 $A$를 정렬해야 하므로 이때 시간복잡도는 $O((N+M)logN)$ 이다.

최초풀이 (Binary Search 직접 구현)

#include <iostream>
#include <algorithm>

using namespace std;

int arr[100001];
int N;

int BinarySearch(int x);

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int M, tmp;
    cin >> N;

    for(int i = 0; i < N; i++){
        cin >> arr[i];
    }

    sort(arr, arr + N);

    cin >> M;

    for(int i = 0; i < M; i++){
        cin >> tmp;
        if(BinarySearch(tmp) == -1)
         cout << 0 << '\n';
        else
         cout << 1 << '\n';
    }
    return 0;
}

int BinarySearch(int x){
    int low = 0, high = N-1;
    int mid;

    while(low <= high){
        mid = (low + high) / 2;
        if(arr[mid] < x) low = mid + 1;
        else if(arr[mid] > x) high = mid - 1;
        else return mid;
    }
    return -1;
}

재풀이 (내장함수 이용)

/*
auto lower = lower_bound(vec.begin(), vec.end(), key);
-> 벡터에서 최초의 key 이상의 값을 iterator 형태로 저장
auto upper = upper_bound(vec.begin(), vec.end(), key);
-> 벡터에서 최초의 key 초과값을 iterator 형태로 저장장
*/
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    cin >> N;

    vector<int> A(N, 0);
    for(int i = 0; i < N; i++){
        cin >> A[i];
    }

    sort(A.begin(), A.end());

    int M;
    cin >> M;

    int num;
    for(int i = 0; i < M; i++){
        cin >> num;
        auto low = lower_bound(A.begin(), A.end(), num);
        if(low - A.begin() == N || *low != num) cout << 0;
        else cout << 1;
        cout << '\n';
    }
    return 0;
}

문제를 푼 날짜: 25. 05. 22.

#math #greedy

아이디어

팰린드롬을 만들 때 가장 큰 숫자 9를 최대한 활용하면 자릿수를 최소화할 수 있다.

• 앞뒤로 9를 한 번씩 추가하면(총 2자리 추가) 자리 합이 $18$만큼 올라감.
• 따라서 우선 $\frac{N}{18}$번 만큼 앞뒤에 9를 붙여준다.

세부 풀이 과정

1. $p = \displaystyle\left\lfloor \frac{N}{18} \right\rfloor$

   • 이때까지 추가된 자리 수는 $2p$

2. 나머지 $r = N \bmod 18$ 에 따라 추가 자리 수를 더함

   • $r=0$

     • 더할 필요 없음 → $+0$

   • $0 < r \le 9$

     • 가운데 한 자리만 추가 → $+1$

   • $10 \le r < 18$

     • $r$ 짝수 → 앞뒤에 한 번씩 추가 → $+2$
     • $r$ 홀수 → 앞뒤 + 가운데 한 자리 → $+3$

최종 답은

$$ \underbrace{2p}_{\substack{\text{9로 채운}\\text{기본 자리 수}}} ;+; \begin{cases} 0, & r=0,\ 1, & 0<r\le9,\ 2, & 10\le r<18,;r\text{ 짝수},\ 3, & 10\le r<18,;r\text{ 홀수}. \end{cases} $$

내 코드

#include <iostream>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    cin >> N;

    int ans = (N / 18) * 2;

    if(N % 18 == 0) cout << ans;
    else if(N % 18 <= 9) cout << ans + 1;
    else if((N % 18) % 2 == 0) cout << ans + 2;
    else cout << ans + 3;

    return 0;
}

(a) Neighborhood (근방)

• 어떤 점 $p$의 반지름 $r > 0$인 neighborhood는: $$ N_r(p) = { q \in X \mid d(p, q) < r } $$
• $\mathbb{R}^1$에서는 열린 구간, $\mathbb{R}^2$에서는 원 내부에 해당.

(b) Limit point (극한점)

• $p$의 모든 neighborhood가 $E$의 점 $q \ne p$ 를 포함하면 $p$는 $E$의 limit point.
• 예: $E = {1/n}$ → 0은 $E$의 극한점.

(c) Isolated point (고립점)

• $E$ 안에 있으면서 limit point가 아닌 점.
• 예: $E = {1, 2, 3}$ → 모든 점은 고립점.

(d) Closed set (닫힌 집합)

• 모든 limit point를 포함하는 집합.
• 예: $[0,1]$은 closed, $(0,1)$은 not closed.

(e) Interior point (내점)

• $p \in E$이고, 어떤 neighborhood $N_r(p) \subset E$이면 $p$는 interior point.

(f) Open set (열린 집합)

• 모든 point가 interior point일 때 $E$는 열린 집합.
• 예: $(0,1)$은 open, $[0,1]$은 open 아님.
• 주의! : closed와 open은 서로 반대되는 개념이 아님.

(g) Complement (여집합)

• $E^c = { p \in X \mid p \notin E }$

(h) Perfect set (완전 집합)

• $E$가 closed이고, 모든 점이 limit point이면 perfect.

(i) Bounded set (유계 집합)

• 어떤 실수 $M$과 점 $q$가 존재하여: $$ d(p, q) < M \quad \text{for all } p \in E $$
• 즉, $E$ 전체가 어떤 볼 안에 들어가는 경우.

(j) Dense set (조밀 집합)

• $X$의 모든 점이 $E$의 limit point이거나 $E$의 point이면, $E$는 $X$에서 조밀.

✅ 2.19 Theorem: Every neighborhood is an open set

어떤 점 $p$에 대한 반지름 $r$의 neighborhood $N_r(p)$는 항상 open set이다.

📝 Proof (증명)

• p의 neighborhood $E = N_r(p)$라고 하자.
• $q \in E$인 임의의 점을 잡자.
• $d(p, q) < r$이므로, 어떤 $h > 0$가 존재하여: $$ d(p, q) = r - h $$
• 이제 $q$ 중심의 neighborhood $N_h(q)$를 생각하자.
• 이 안의 임의의 점 $s$는 $d(q, s) < h$를 만족하므로,

삼각부등식에 의해: $$ d(p, s) \le d(p, q) + d(q, s) < r - h + h = r $$

즉, $s \in N_r(p)$이므로: $$ N_h(q) \subset N_r(p) $$

• 따라서 $q$는 $N_r(p)$의 interior point이다.
• 모든 $q \in N_r(p)$가 interior point이므로, $N_r(p)$는 open set이다.

✅ 2.20 Theorem: Limit point 주변에는 무한히 많은 점이 있다

어떤 점 $p$가 집합 $E$의 limit point라면,
$p$의 모든 neighborhood는 $E$의 무한히 많은 점들을 포함한다.

📝 Proof (by contradiction)

1. $p$가 $E$의 limit point라고 하자.

2. 그런데 어떤 neighborhood $N$이 $E$의 유한 개의 point들만 포함한다고 가정하자: $$ N \cap E = { q_1, \dots, q_n } \quad (q_i \ne p) $$

3. 이 점들 중 $p$와의 최소 거리를 $r$이라 하자: $$ r = \min{ d(p, q_1), \dots, d(p, q_n) } > 0 $$

4. 이제 반지름 $r$인 neighborhood $N_r(p)$를 고려하자.
   그런데 이 안에는 $q_1, \dots, q_n$ 중 아무 점도 포함되지 않음. ($q_1, \dots, q_n$ 는 $p$로부터 거리가 $r$ 이상이기 때문)

5. 따라서 $N_r(p) \cap E = \emptyset$

→ 이는 limit point의 정의에 모순. ($E$의 limit point $p$의 모든 neighborhood는 $p$가 아닌 $E$의 point $q$를 포함한다) → 즉, 모든 neighborhood에는 무한히 많은 $E$의 점이 있어야 한다.

📌 Corollary

유한한 집합은 limit point를 가질 수 없다.

• 왜냐하면 아무리 neighborhood를 키워도 그 안에 유한한 점밖에 없기 때문.

집합 $X$에 대해, 모든 두 점 $p, q \in X$에 대해 metric(거리함수) $d(p, q)$ 가 정의되어 있고 아래 조건들을 만족할 때, $(X, d)$를 metric space(거리공간) 라고 한다.

1. 양의 성질 (Positivity): $d(p, q) > 0$ if $p \ne q$, and $d(p, p) = 0$
2. 대칭성 (Symmetry): $d(p, q) = d(q, p)$
3. 삼각 부등식 (Triangle Inequality): $d(p, q) \le d(p, r) + d(r, q)$ for all $r \in X$

이러한 조건을 만족하는 함수 $d$를 metric 또는 distance function 이라고 한다.

✅ 2.16 Examples (Metric Space의 예시)

• 대표적 예시: 유클리드 공간 $\mathbb{R}^k$

  • 특히 $\mathbb{R}^1$ (실수 직선), $\mathbb{R}^2$ (복소수 평면)
  • 거리 함수: $d(x, y) = |x - y|$

• 중요한 성질:

  • Metric space의 부분집합도 자체로 metric space가 된다.
  • 즉, $Y \subset X$ 이면 $(Y, d)$도 metric space.
  • 이유: 정의 2.15의 조건들이 $Y$ 위에서도 그대로 유지되기 때문.

✅ 2.17 Definition (구간, 볼, 볼록 집합)

1. 구간의 정의

• 열린 구간 (open interval): $(a, b) = { x \in \mathbb{R} \mid a < x < b }$
• 닫힌 구간 (closed interval): $[a, b] = { x \in \mathbb{R} \mid a \le x \le b }$
• 반열린 구간 (half-open interval): $[a, b) = { x \in \mathbb{R} \mid a \le x < b }$ $(a, b] = { x \in \mathbb{R} \mid a < x \le b }$

2. k-cell

• $a_i < b_i$ for $i = 1, \dots, k$일 때,
  $\mathbb{R}^k$의 모든 점 $x = (x_1, \dots, x_k)$ 중
  $a_i \le x_i \le b_i$를 만족하는 점들의 집합: $$ [a_1, b_1] \times [a_2, b_2] \times \dots \times [a_k, b_k] $$
• 예:
  • 1-cell: $[a, b]$ (구간)
  • 2-cell: 직사각형
  • 3-cell: 직육면체

3. Open Ball / Closed Ball

• 중심 $x \in \mathbb{R}^k$, 반지름 $r > 0$일 때:

  • Open ball: $B(x, r) = { y \in \mathbb{R}^k \mid |y - x| < r }$

  • Closed ball: $\overline{B}(x, r) = { y \in \mathbb{R}^k \mid |y - x| \le r }$

• $\mathbb{R}^2$에서는 각각 원의 내부, 원 내부+테두리에 해당.

4. Convex Set (볼록 집합)

• 집합 $E \subset \mathbb{R}^k$가 다음 조건을 만족하면 convex라고 한다:

  임의의 $x, y \in E$ 및 $0 < \lambda < 1$에 대해
  $\lambda x + (1 - \lambda)y \in E$

• 직관: 두 점을 이은 선분 전체가 집합 안에 들어갈 때, 그 집합은 convex.

예시: Ball은 Convex

볼 $B(x, r)$ 안에 두 점 $y$, $z$가 있다고 하자. 즉,

$$ |y - x| < r, \quad |z - x| < r $$

이때, 선분 위의 점 $w = \lambda y + (1 - \lambda)z$ 가 여전히 ball 안에 들어감을 보이자.

📝 Proof

1. 선분 위의 점은 다음과 같이 정의된다:

   $$ w = \lambda y + (1 - \lambda)z $$

2. $w$가 ball 안에 있는지를 확인하기 위해 다음을 계산한다:

   $$ |w - x| = |\lambda y + (1 - \lambda)z - x| $$

3. 벡터 항을 정리하면:

   $$ |w - x| = |\lambda(y - x) + (1 - \lambda)(z - x)| $$

4. 삼각부등식을 적용하면:

   $$ |w - x| \le \lambda |y - x| + (1 - \lambda)|z - x| $$

5. $|y - x| < r$, $|z - x| < r$ 이므로:

   $$ \lambda |y - x| + (1 - \lambda)|z - x| < \lambda r + (1 - \lambda)r = r $$

6. 따라서,

   $$ |w - x| < r \Rightarrow w \in B(x, r) $$

→ 결론적으로, open ball은 convex이다.

• 같은 논리로 closed ball도 convex임을 증명할 수 있다 (등호 허용).
• $k$-cell (직사각형, 직육면체 등) 역시 convex이다.
• 반면, 오목한 모양이나 구멍 뚫린 집합은 convex가 아니다.

• 집합 $A$의 각 원소 $\alpha$에 대해 집합 $\Omega$의 부분집합 $E_\alpha$가 대응된다고 하자.
• 이때 $E_\alpha$ 를 원소로 갖는 집합 ${E_\alpha}$는 집합의 집합(set of sets) 이다.
• 이러한 경우 '집합의 모음(collection of sets)' 또는 '집합의 족(family of sets)' 이라고 부른다.
• 즉, set of sets 대신 collection이나 family라는 표현을 사용하여 보다 간결하게 표현할 수 있다.

✅ 2.12 Theorem (Countable Set의 Union도 Countable)

Countable sets(가산 집합들)의 수열 ${E_n}$ ($n=1,2,3,\dots$)이 주어졌을 때, $$ S = \bigcup_{n=1}^\infty E_n $$ 은 가산 집합이다.

📝 Proof (증명)

• 각 $E_n$의 원소들을 수열 ${x_{nk}}$ ($k=1,2,3,\dots$)로 나열한다.
• 이들을 2차원 배열로 정리하면: $$ \begin{matrix} x_{11} & x_{12} & x_{13} & \dots \ x_{21} & x_{22} & x_{23} & \dots \ x_{31} & x_{32} & x_{33} & \dots \ \vdots & \vdots & \vdots & \ddots \end{matrix} $$
• 위 배열을 대각선 순서(diagonal order) 로 나열하면: $$ x_{11}, x_{21}, x_{12}, x_{31}, x_{22}, x_{13}, \dots $$
• 이 나열은 $S$의 모든 원소를 포함한다.
• 중복 원소가 있다면 제거해도 여전히 $S$는 Countable Set(Theorem 2.8 -> Every infinite subset of a countable set is countable).

📌 Corollary

• $A$가 at least countable (가산 이하 집합) 이고,
  $A$의 각 원소 $\alpha$마다 집합 $B_\alpha$가 대응되며,
  이 $B_\alpha$들도 모두 가산 이하 집합이라고 하자.
• 이때 다음과 같은 합집합 $T$ 를 생각한다: $$ T = \bigcup_{\alpha \in A} B_\alpha $$
• 즉, $A$의 각 $\alpha$가 갖고 있는 $B_\alpha$들을 모두 모은 집합 $T$이다.
• 결론: $T$ 역시 가산 이하 집합이다.

✅ 📌 2.13 Theorem (Countable Set의 원소로 이뤄진 n-tuple의 set도 Countable)

Countable Set(가산 집합) $A$에 대해, $A$의 원소들로 이루어진 $n$-tuple들의 집합 $B_n$을 다음과 같이 정의한다: $$ B_n = { (a_1, \dots, a_n) \mid a_k \in A \text{ for } k = 1, \dots, n } $$ 여기서 $a_1, \dots, a_n$은 서로 달라도 되고 같아도 된다. 이때 $B_n$ 은 Countable이다.

📝 Proof (증명: 귀납법 사용)

1. $B_1$은 $A$ 자체이므로 countable이다.
2. $B_n$의 원소는 다음과 같은 형태로 쓸 수 있다: $$ (b, a) \text{ where } b \in B_{n-1}, a \in A $$
3. $B_{n-1}$가 countable이고, $A$도 countable이므로, 고정된 $b$에 대해 $(b, a)$의 집합은 $A$와 equivalent(동치)이며 countable이다.
4. 따라서 $B_n$은 union of a countable set of countable sets(가산 개수의 가산 집합들의 합집합) 이다.
5. Theorem 2.12에 의해 $B_n$은 가산 집합이다.
6. 귀납법으로 $B_n$이 모든 $n$에 대해 가산임이 성립.

📌 Corollary (유리수 집합의 가산성)

모든 유리수들의 집합 $\mathbb{Q}$는 Countable(가산)이다.

이유

• 모든 유리수 $p$는 $\frac{b}{a}$ 의 형태로 나타낼 수 있으며, $a, b$는 정수이다.
• 정수들의 쌍 $(a, b)$의 집합은 $B_2$로 볼 수 있고, 이는 Theorem 2.13에 의해 가산이다.
• 따라서 유리수들의 집합도 가산이다.

✅ 2.14 Theorem (0과 1로 이뤄진 무한 수열 집합은 uncountable)

0과 1로 이루어진 모든 무한 수열들의 집합 $A$는 uncountable(비가산)이다.

📝 Proof (칸토어의 대각선 논법)

1. $A$가 countable이라고 가정하자.
2. 그러면 $A$의 원소들을 다음과 같이 나열할 수 있다: $$ s_1, s_2, s_3, \dots $$
3. 새로운 수열 $s$를 다음과 같이 만든다: $$ \text{만약 } s_n \text{의 } n\text{번째 자릿수가 } 1 \text{이면 } s \text{의 } n\text{번째 자릿수는 } 0, \ \text{만약 } s_n \text{의 } n\text{번째 자릿수가 } 0 \text{이면 } s \text{의 } n\text{번째 자릿수는 } 1. $$
4. 이렇게 만든 $s$는 $s_1, s_2, s_3, \dots$ 중 어느 것과도 적어도 한 자릿수 이상 다르다.
5. 그러나 $s$는 분명 $A$의 원소이므로, $s$는 $A$에 있어야 한다.
6. 이는 $A$가 countable이라는 가정과 모순이다.
7. 따라서 $A$는 uncountable이다.

💡 참고: Cantor's Diagonal Process

• 이 증명 방식은 칸토어의 대각선 논법(Cantor's diagonal argument) 이라고 부른다.
• 0과 1로 이루어진 무한 수열을 실수의 이진 표현(binary representation) 으로 해석하면,
  실수 전체 집합이 uncountable이라는 사실이 바로 따라옴을 알 수 있다.

• 두 집합 $A$, $B$가 주어졌을 때, $A$의 각 원소 $x$에 대해 $B$의 원소 $f(x)$가 어떤 방식으로든 대응되면, $f$는 $A$에서 $B$로의 함수(function) 또는 사상(mapping) 이라고 한다.
• $f$의 정의역(domain): $A$
• $f$의 값(value): $f(x)$
• $f$의 치역(range): $f(A)$ (모든 $f(x)$의 집합) (집합 $A$에 대해서도 함수 $f$를 직접 적용하여 표현할 수 있다!)

✅ 2.2 Onto(전사) / One-to-One(단사)

Image (상, 이미지)

• $f: A \to B$가 주어졌을 때, $E \subset A$라면
  • $f(E) = {f(x) \mid x \in E}$ 를 $E$의 $f$에 의한 상(image) 이라고 한다.
  • 이때 $f(A)$는 $f$의 치역(range)이며 항상 $f(A) \subset B$이다.
  • 만약 $f(A) = B$이면, $f$는 $A$를 $B$로 'onto' (전사) 한다고 한다.

Inverse Image (역상)

• $E \subset B$라면
  • $f^{-1}(E) = {x \in A \mid f(x) \in E}$ 를 $E$의 $f$에 의한 원상(inverse image) 이라고 한다.
  • 주의: 이는 $f$가 역함수를 가지는지와 무관하게 정의된다.

One-to-One Mapping (단사)

• 모든 $y \in B$에 대해 $f^{-1}(y)$가 $A$의 원소를 최대 하나만 포함하면 $f$는 일대일(one-to-one, 1-1) mapping 이라고 한다.
• 즉, $f(x_1) \ne f(x_2)$ whenever $x_1 \ne x_2$ ($x_1, x_2 \in A$).

✅ 2.3 Equivalence of Sets (집합의 동치)

• $A$에서 $B$로의 일대일 대응(one-to-one mapping)이 존재한다면, $A$와 $B$는 1-1 'correspondence'가 있다고 하며, 같은 'cardinal number'(기수)를 가진다고 한다.
• 이를 간단히 $A \sim B$ 라고 쓴다.
• 이 관계는 다음 성질들을 만족한다:
  • Reflexive (반사성): $A \sim A$
  • Symmetric (대칭성): $A \sim B$ 이면 $B \sim A$
  • Transitive (추이성): $A \sim B$이고 $B \sim C$이면 $A \sim C$
• 이러한 성질을 갖는 관계를 equivalence relation (동치 관계) 이라고 한다.

✅ 2.4 Cardinality (기수)

• $n$이 양의 정수일 때, $J_n = {1, 2, \dots, n}$
• $J$는 모든 양의 정수(=자연수)의 집합 ${1, 2, 3, \dots}$
• 임의의 집합 $A$에 대해 다음과 같이 정의한다:
  • a) Finite (유한 집합): $A \sim J_n$인 $n$이 존재 (공집합도 유한으로 간주)
  • b) Infinite (무한 집합): $A$가 유한이 아닐 때
  • c) Countable (가산 집합): $A \sim J$
  • d) Uncountable (비가산 집합): 유한도 아니고 가산도 아닐 때
  • e) At most countable (가산 이하 집합): 유한 또는 가산일 때
• 💡 Countable set은 enumerable(열거 가능), denumerable(가산 가능)이라고도 불린다.

✅ 2.5 Example (정수 집합은 가산이다)

• $A$ = 모든 정수들의 집합 ${0, 1, -1, 2, -2, 3, -3, \dots}$
• $J$ = ${1, 2, 3, 4, 5, \dots}$
• $f: J \to A$인 함수를 다음과 같이 명시적으로 정의함으로써, $J$와 $A$가 동치임을 확인할 수 있다 :
  • $f(n) = \begin{cases} \frac{n}{2}, & \text{if } n \text{ is even} \ -\frac{n-1}{2}, & \text{if } n \text{ is odd} \end{cases}$
• 💡 따라서 $A$는 가산(countable)이다.

✅ 2.6 Remark (무한 집합의 특성)

• 유한 집합은 자신의 proper subset(진부분집합)과 동치가 될 수 없다.

• 그러나 무한 집합은 자신의 진부분집합과 동치가 가능하다.

  • ex) Example 2.5에서 $J$는 $A$의 진부분집합이지만 $A \sim J$

• 💡 따라서 Def 2.4(b) 에서 무한 집합의 정의는 다음과 같이 바꿀 수 있다:

  • $A$가 무한이라는 것은 $A$가 자신의 진부분집합과 동치인 경우이다.

  ---

  ✅ 2.6 Remark (무한 집합의 특성)

• 수열(sequence) 이란, 모든 양의 정수들의 집합 $J$ 위에서 정의된 함수 $f$를 의미한다.

• $f(n) = x_n$ ($n \in J$) 일 때, 수열 $f$는 보통 ${x_n}$ 또는 $x_1, x_2, x_3, \dots$ 로 표기한다.

• $f$의 값(value), 즉 $x_n$ 들을 수열의 항(term) 이라고 한다.

• 만약 $A$가 어떤 집합이고, 모든 $n \in J$에 대해 $x_n \in A$라면, ${x_n}$를 $A$ 안의 수열(sequence in $A$) 또는 $A$의 원소들로 이루어진 수열 이라고 한다.

📌 중요 포인트 (Countable set과 수열의 연결)

• 모든 countable set(가산집합)은 $J$ 위에 정의된 일대일 함수의 range(치역)으로 표현 가능하다.
  • 즉, Countable set의 원소들은 '서열화(arranged in a sequence)' 될 수 있다.
• 💡 쉽게 얘기해서, Countable set의 원소들을 수열로 나열할 수 있다 라고 말할 수 있다.

✅ 참고

• 때로는 편의를 위해 $J$ 대신 $0$ 이상의 정수들의 집합 ${0, 1, 2, \dots}$ 을 사용하는 경우도 있다.
  • 이 경우 수열을 $x_0, x_1, x_2, \dots$ 로 시작한다.

✅ 2.8 Theorem (가산 집합의 부분집합)

Countable Set(가산집합) $A$의 모든 Infinite Subset(무한 부분집합) $E$는 Countable(가산)이다.

📝 Proof (증명)

• $A$가 Countable Set이고 $E \subset A$, $E$가 Infinite Set이라고 하자.
• $A$의 원소들을 서로 다른 항으로 나열한 수열 ${x_n}$를 생각한다.
• 이제 $E$의 원소들을 다음과 같이 ${x_n}$에서 순서대로 찾아 수열 ${n_k}$를 구성한다:
  1. $n_1$은 $x_{n_1} \in E$인 가장 작은 $n$.
  2. $n_2$는 $n_1$보다 큰 수 중 $x_{n_2} \in E$인 가장 작은 $n$.
  3. 일반적으로, $n_k$는 $n_{k-1}$보다 큰 수 중 $x_{n_k} \in E$인 가장 작은 $n$.
• 이렇게 하면 ${f(k) = x_{n_k}}$ ($k=1,2,3,\dots$)는 $E$의 서로 다른 모든 원소를 포함하는 수열이 되며,
  • 이는 $E$와 $J$ 사이의 일대일 대응(one-to-one correspondence) 을 만들어준다.

💡 직관적 해석 (중요!!)

• Countable Set(가산집합)은 '가장 작은' Infinite Set(무한집합)이다.
• Uncountable Set(비가산 집합)은 절대 Countable Set(가산집합)의 subset(부분집합)이 될 수 없다.

• 체(Field): 두 연산(덧셈, 곱셈)이 정의된 집합 $F$로서, 각각에 대해 항등원, 역원, 교환법칙, 결합법칙, 분배법칙이 모두 성립한다.
• 순서체(Ordered field): 체 $F$에 "<"라는 순서 관계가 추가되어, 크기 비교가 가능함.

🔸 Theorem

There exists an ordered field $\mathbb{R}$ with the least-upper-bound property. Moreover, $\mathbb{Q} \subset \mathbb{R}$.

이 체 $\mathbb{R}$의 원소들을 실수(real numbers)라 부른다.

• 이 정리는 우리가 해석학을 전개할 수 있는 완비 공간 $\mathbb{R}$의 존재를 보장한다.
• $\mathbb{R}$의 구성은 Appendix에서 다룬다 (Dedekind cut).

✅ 1.20 Archimedean Property & Density of $\mathbb{Q}$

🔸 Thm (a) - Archimedean Property

If $x > 0$ and $y \in \mathbb{R}$, then there exists a positive integer $n$ such that $nx > y$.

✏️ Proof

1. Proof by contradiction: 모든 정수 $n \in \mathbb{N}$에 대해 $nx \leq y$ 가정.

2. 그러면 집합 $A = { nx \mid n \in \mathbb{N} }$는 upper bounded(위로 유계) 이다.

3. 따라서 $\alpha = \sup A$ 가 존재함 ($\mathbb{R}$의 least-upper-bound property에 의해)

4. 그런데 $x > 0$이므로 $\alpha - x < \alpha$

5. $\alpha$는 supremum(상한)이므로, $\alpha - x$는 upper bound(상계)가 아님. 즉, 어떤 $n \in \mathbb{N}$에 대해 $$ nx > \alpha - x $$

6. 따라서 $$ (n + 1)x > \alpha $$

   하지만 $(n + 1)x \in A$이고, $\alpha$는 $A$의 상한인데, 이를 초과하는 원소가 존재한다는 것은 모순

$\therefore$ 가정이 잘못되었으므로, $nx > y$를 만족하는 어떤 $n \in \mathbb{N}$ 가 항상 존재한다 . $\quad \blacksquare$

🔸 Thm (b) - $\mathbb{Q}$ is dense in $\mathbb{R}$

If $x < y$, then there exists a rational number $p$ such that $x < p < y$.

✏️ Proof

$y - x > 0$이므로, Archimedean 성질에 의해 $n \in \mathbb{N}$이 존재하여 $n(y - x) > 1$.
즉, $nx < ny - 1$, 이 사이에는 정수 $m$이 존재하므로 $nx < m < ny$.
양변을 $n$으로 나누면 $x < \frac{m}{n} < y$, 이때 $\frac{m}{n} \in \mathbb{Q}$.
→ 유리수는 실수 사이에 항상 존재한다. $\quad \blacksquare$

✅ 1.21 $n$제곱근의 존재와 유일성

🔸 Theorem

For every real number $x > 0$ and every integer $n > 0$, there exists a unique real number $y > 0$ such that $y^n = x$.

✏️ Proof (Existence)

1. $A = { t \mid 0 < t^n < x }$ 라는 집합을 생각하자.

2. $A$는 공집합이 아님
   → $x > 0$이므로 $t = \frac{x}{2}$ 같은 값은 $t^n < x$를 만족

3. $A$는 위로 유계
   → 예를 들어 $x + 1$ 같은 값은 $(x+1)^n > x$이므로 $A$의 상계

4. 따라서 $A \subset \mathbb{R}$는 위로 유계인 실수 부분집합
   → $\mathbb{R}$은 least-upper-bound property를 가지므로:

   $$ y = \sup A $$

   이 존재함

5. 이제 $y^n = x$임을 보이자.

   • 만약 $y^n < x$이면, $y + \epsilon \in A$가 되어 $y$보다 큰 상한이 생김 → 모순
   • 만약 $y^n > x$이면, $y - \epsilon$은 $A$의 상계가 되는데 $y$보다 작음 → 모순

$\Rightarrow$ 따라서 $y^n = x$

✏️ Proof (Uniqueness)

함수 $f(t) = t^n$은 $t > 0$에서 단조 증가하므로, $f(t_1) = f(t_2)$이면 $t_1 = t_2$이다.
→ 따라서 해는 유일하다. $\quad \blacksquare$

🔸 Corollary

If $a > 0$, $b > 0$ and $n \in \mathbb{N}$, then $$ (ab)^{1/n} = a^{1/n} \cdot b^{1/n} $$

✏️ Proof (Sketch)

양변을 $n$제곱하면: $$ ((ab)^{1/n})^n = ab = a \cdot b = (a^{1/n})^n \cdot (b^{1/n})^n = (a^{1/n} \cdot b^{1/n})^n $$

→ 양변의 $n$제곱이 같고 양수이므로 원래 수들도 같다. $\quad \blacksquare$

✅ 정리 요약

• $\mathbb{R}$은 순서체이며, least-upper-bound property를 만족하는 유일한 체이다.
• Archimedean 성질은 $\mathbb{R}$의 수들이 무한히 커질 수 있음을 보장한다.
• 유리수는 실수 사이에 항상 존재한다 → $\mathbb{Q}$는 $\mathbb{R}$에서 조밀(dense)하다.
• 실수는 모든 양의 수에 대해 $n$제곱근을 갖고, 이는 유일하다.

✅ 1.36 Euclidean Spaces

양의 정수 $k$에 대해, $\mathbb{R}^k$는 다음과 같은 모든 $k$-tuple의 집합이다:

$$ x = (x_1, x_2, \dots, x_k), \quad \text{where each } x_i \in \mathbb{R} $$

이때, 각 $x_i$는 좌표(coordinate) 라고 하며,
$\mathbb{R}^k$의 원소 $x$는 보통 점(point) 또는 벡터(vector) 라고 부른다.
($k = 1$일 때는 실수 직선, $k = 2$는 평면, $k = 3$은 3차원 공간을 의미함)

🔸 Inner Product (내적)

임의의 $x = (x_1, ..., x_k)$, $y = (y_1, ..., y_k) \in \mathbb{R}^k$에 대해
내적(inner product) 은 다음과 같이 정의한다:

$$ x \cdot y = \sum_{i=1}^{k} x_i y_i = x_1 y_1 + x_2 y_2 + \dots + x_k y_k $$

🔸 Norm (벡터의 크기)

벡터 $x \in \mathbb{R}^k$의 노름(norm), 또는 크기(magnitude) 는 다음과 같다:

$$ |x| = \sqrt{x \cdot x} = \sqrt{x_1^2 + x_2^2 + \dots + x_k^2} $$

✅ 1.37 Thm: 노름과 내적의 기본 성질

임의의 $x, y, z \in \mathbb{R}^k$, 스칼라 $\alpha \in \mathbb{R}$에 대해 다음이 성립한다:

• $\quad |x| \geq 0$
• $\quad |x| = 0 \iff x = 0$
• $\quad |\alpha x| = |\alpha||x|$
• $\quad |x \cdot y| \leq |x||y|$ (Cauchy-Schwarz 부등식)
• $\quad |x + y| \leq |x| + |y|$ (삼각부등식)
• $\quad |x - z| \leq |x - y| + |y - z|$ (거리의 삼각부등식)

✅ 1.38 Rmk: $\mathbb{R}^k$는 metric space(거리 공간)

위 정리 1.37의 결과 중 (a), (b), (f)는
$\mathbb{R}^k$가 metric space (거리공간) 으로 다뤄질 수 있음을 보장한다.

💡 metric space (거리공간)

"점들 사이의 거리(distance)" 를 정의할 수 있는 공간

• 두 점 $x, y \in \mathbb{R}^k$ 사이의 거리 $d(x, y)$를 다음과 같이 정의:

$$ d(x, y) := |x - y| $$

✅ Appendix

유리수 집합($\mathbb{Q}$)에서 실수 집합($\mathbb{R}$)을 구성하는 Dedekind 절단(Dedekind Cut) 방식을 정리한다.

📌 Step 1: Dedekind Cut의 정의

Dedekind 절단(Dedekind Cut) 이란, 유리수 집합 $\mathbb{Q}$의 부분집합 $\alpha$로 다음 세 조건을 만족하는 것을 말한다.

1. $\alpha \ne \emptyset$, $\alpha \ne \mathbb{Q}$
2. 만약 $p \in \alpha$이고 $q < p$이면, $q \in \alpha$
3. $\alpha$는 최대 원소를 갖지 않는다.

직관적으로 생각하면 cut은 유리수로 이뤄진 오른쪽이 열린 반직선으로 생각해볼 수 있다. 이후 $\mathbb{Q}$의 모든 cut의 집합을 $\mathbb{R}$ 로 표기한다.

📌 Step 2: $\mathbb{R}$의 순서 관계 정의

두 cut $\alpha, \beta \in \mathbb{R}$에 대해 다음과 같이 순서 관계를 정의한다.

$$ \alpha < \beta \quad\Longleftrightarrow\quad \alpha \text{ is a proper subset of } \beta $$

이 순서는 다음 성질을 만족하여, $\mathbb{R}$을 ordered set(순서집합) 으로 만든다.

• $\alpha < \beta$이고 $\beta < \gamma$이면 $\alpha < \gamma$
• $\alpha < \beta$, $\alpha = \beta$, $\beta < \alpha$ 중 오직 하나만 성립

📌 Step 3: Least Upper Bound Property

$\mathbb{R}$의 임의의 공집합이 아닌 부분집합 $S$가 bounded above(위로 유계)라고 하자. 그러면 다음을 보일 수 있다.

• 집합의 supremum(상한) $\sup S = \bigcup S$는 역시 cut이 된다.
• 즉, $\mathbb{R}$은 Least-upper-bound property를 가지는 집합이다.

이 성질을 통해 $\mathbb{R}$은 완비성을 갖게 된다.

📌 Step 4: 유리수의 포함 관계

임의의 유리수 $r \in \mathbb{Q}$에 대해 다음과 같은 Dedekind 절단을 정의하자.

$$ r^* = { q \in \mathbb{Q} \mid q < r } $$

이때, 유리수 $r$을 이렇게 구성된 절단으로 표현하면,
$\mathbb{Q}$는 자연스럽게 $\mathbb{R}$의 부분집합으로 포함된다.

💡 보충 설명

1. $\mathbb{Q} \cong \mathbb{Q}^*$
   (유리수 $\mathbb{Q}$와 절단으로 표현된 집합 $\mathbb{Q}^$는 순서체로서 동형이다)
   ⇒ 덧셈, 곱셈, 순서 관계까지 *보존하는 isomorphism**이 존재한다.

2. $\mathbb{Q}^* \subset \mathbb{R}$
   ⇒ 각 $r^* \in \mathbb{Q}^*$는 Dedekind cut이므로 실수 $\mathbb{R}$의 원소이다.

3. $\therefore\ \mathbb{Q} \cong \mathbb{Q}^* \subset \mathbb{R}$
   ⇒ $\mathbb{Q}$는 $\mathbb{R}$ 안에 자연스럽게 포함(embedding)되며,
   이 포함은 단순한 집합 이론적 포함이 아니라 구조(덧셈, 곱셈, 순서)를 보존하는 포함이다.

📌 Step 5: 덧셈의 정의

두 실수 $\alpha, \beta \in \mathbb{R}$에 대한 덧셈은 다음과 같이 정의한다.

$$ \alpha + \beta = { r + s \mid r \in \alpha,, s \in \beta } $$

이 덧셈은 다음 성질을 만족한다.

• 닫혀있음(closed)
• 결합법칙(associativity), 교환법칙(commutativity)을 만족

📌 Step 6: 곱셈의 정의

두 양의 실수 $\alpha, \beta > 0$에 대해서 곱셈을 다음과 같이 정의한다.

$$ \alpha \cdot \beta = { r \cdot s \mid r \in \alpha,, s \in \beta,, r, s > 0 } $$

부호가 다른 실수의 곱셈은 자연스러운 부호 규칙을 적용하여 확장할 수 있다. 이 곱셈도 체의 공리를 만족한다.

📌 Step 7: 덧셈 역원의 정의 (음수)

각 실수 $\alpha \in \mathbb{R}$에 대해 음수를 다음과 같이 정의한다.

$$ -\alpha = { r \in \mathbb{Q} \mid \exists s > 0,\ -r - s \notin \alpha } $$

이렇게 정의된 덧셈의 역원은 다음을 만족한다.

$$ \alpha + (-\alpha) = 0^* $$

📌 Step 8: 곱셈 역원의 정의

양의 실수 $\alpha \in \mathbb{R}$의 곱셈의 역원을 다음과 같이 정의한다.

$$ \alpha^{-1} = { r \in \mathbb{Q} \mid r > 0,\ \exists s > r,\ s^{-1} \notin \alpha } $$

이때 곱셈 역원은 다음과 같은 성질을 만족한다.

$$ \alpha \cdot \alpha^{-1} = 1^* $$

📌 Step 9: 체(Field)의 성질 확인

위의 과정을 통해 구성한 덧셈과 곱셈 연산이 다음의 체의 공리를 만족함을 확인할 수 있다.

• 덧셈과 곱셈의 교환법칙과 결합법칙 성립
• 분배법칙 성립
• 덧셈 항등원(0)과 곱셈 항등원(1) 존재
• 모든 원소는 덧셈 역원을 가짐
• 0을 제외한 모든 원소는 곱셈 역원을 가짐

따라서, $\mathbb{R}$은 순서체이면서 최소 상계 성질을 갖는 완비체(complete ordered field)가 된다.

💡 결론

이렇게 Dedekind 절단을 통해 유리수에서 실수를 엄밀히 구성할 수 있게 된다.

• 유리수 체계($\mathbb{Q}$)는 불완전(incomplete) 하다.
• 예를 들어, 수열 $a_n = 1, 1.4, 1.41, 1.414, \dots$ 은 $\sqrt{2}$ 로 수렴하는 것처럼 보인다.
• 하지만 이 극한값인 $\sqrt{2}$ 는 유리수 집합 $\mathbb{Q}$ 안에는 존재하지 않는다.
  • 그렇다면 $\sqrt{2}$ 는 대체 무엇일까?
  • 그리고 "수렴한다(converge)"는 개념을 어떻게 정확히 정의할 수 있을까?

이러한 질문이 바로 실수(real number) 개념을 필요로 하는 근본적인 이유이다.

✅ 1.1 Example

우선, 다음 명제를 생각하자: 명제: 방정식 $p^2 = 2$ 을 만족하는 유리수 $p$ 는 없다.

이 명제는 귀류법(proof by contradiction) 으로 증명할 수 있다. (증명은 생략)

추가적인 관찰 (Further Observations)

1. 두 개의 유리수 집합 $A, B$ 를 다음과 같이 정의한다:

$$ A = {p \in \mathbb{Q} : p^2 < 2 }, \quad B = {p \in \mathbb{Q} : p^2 > 2 } $$ 이때, A와 B의 교집합은 없으며 합집합은 유리수 전체다.

2. 임의의 $p \in A$ 를 선택한 후, 아래와 같은 새로운 수 $q$ 를 정의하자:

$$ q = p - \frac{p^2 - 2}{p + 2} = \frac{2p + 2}{p + 2} $$

그러면 이때, 다음 식이 성립한다:

$$ q^2 - 2 = \frac{2(p^2 - 2)}{(p + 2)^2} $$

3. 여기서 분모는 항상 양수이므로, 분자의 부호가 전체 부호를 결정한다.
우리가 고른 $p \in A$ 는 정의상 $p^2 < 2$ 이므로, $p^2 - 2 < 0$ 이다. 따라서:

• $q^2 - 2 < 0 \quad\Rightarrow\quad q^2 < 2 \quad\Rightarrow\quad q \in A$

또한:

• $\frac{p^2 - 2}{p + 2} < 0$ 이므로, 원래 정의된 식 $q = p - \frac{p^2 - 2}{p + 2}$ 에서 빼는 값이 음수이다.
• 따라서 $q > p$ 이다.

4. 즉, 임의의 $p \in A$에 대해서 항상 더 큰 유리수 $q \in A$ 를 찾을 수 있다.
이로써 집합 $A$ 는 절대로 최댓값(maximum)을 가지지 않음을 보였다.

5. 같은 방법으로, 집합 $B$ 도 최솟값(minimum)을 가지지 않음을 쉽게 확인할 수 있다.

✅ 증명의 결론과 의미:

• 우리는 유리수 전체를 두 집합 $A$ 와 $B$ 로 명확히 나누었다.
• 하지만 흥미롭게도 $A$ 의 최댓값과 $B$ 의 최솟값이 모두 존재하지 않는다.
• 분명히 두 집합 사이에는 어떤 수가 존재해야 할 것 같은데, 그 수는 유리수가 될 수 없다.
• 즉, 두 집합 사이의 "gap(빈틈)"이 존재하며, 이것이 바로 유리수 체계가 불완전하다는 증거이다.

🔑 요약:

유리수 집합($\mathbb{Q}$)은 밀도성(density)을 갖지만(모든 유리수쌍 사이에는 항상 또 다른 유리수 존재), 완비성(completeness)을 갖지 않는다.
그래서 우리는 이 빈틈을 채워주는 더 확장된 체계인 "실수 체계(real number system)"가 필요하다.

✅ 1.3 Definitions

• 집합 $A$가 집합 $B$의 부분집합(subset) 이라는 것은,
  집합 $A$의 모든 원소가 집합 $B$에도 포함됨을 의미하며, 다음과 같이 나타낸다:

$$ A \subset B \quad \Longleftrightarrow \quad \text{($A$ is a subset of $B$)} $$

• 만약 $A \subset B$이면서 $A \ne B$인 경우, 즉,
  $A$의 모든 원소가 $B$에 포함되지만 $B$에 속한 원소 중 적어도 하나는 $A$에 속하지 않는 경우를
  $A$는 $B$의 진부분집합(proper subset) 이라 부른다.

• 중요:

만약 $A \subset B$이고 동시에 $B \subset A$라면

$$ A = B $$

라고 쓴다.
그렇지 않은 경우는 $A \ne B$라고 표기한다.

✅ 1.5 Order (순서)

집합 $S$ 위의 순서(order) 는 다음의 두 가지 성질을 만족하는 관계(relation) 이며, 일반적으로 "$<$"로 나타낸다.

(i) 집합 $S$의 임의의 원소 $x, y$에 대해서 다음의 세 가지 명제 중 정확히 하나만 성립한다.

$$ x < y,\quad x = y,\quad y < x $$

즉, 임의의 두 원소를 비교하면 항상 명확히 크거나, 작거나, 같거나 중 하나만 성립해야 한다.

(ii) 집합 $S$의 임의의 원소 $x, y, z$에 대해, 만약 $x < y$이고 $y < z$라면, 다음이 성립한다.

$$ x < z $$

즉, 순서 관계는 추이적(transitive) 이다.

💡 cf. 관계 (relation)

수학에서 말하는 관계(relation) 란 두 집합 $A$, $B$에 대해
순서쌍 $(a, b)$들의 모임, 즉 $R \subset A \times B$인 어떤 부분집합을 의미한다.
이것은 "$a$와 $b$가 어떤 방식으로 연결되어 있다"는 것을 수학적으로 나타내는 방법이다.

✅ 1.6 Ordered Set (순서집합)

위에서 정의한 순서(order)가 부여된 집합을 순서집합(ordered set)이라 부른다.

즉, 집합 $S$가 순서집합이라는 것은, 집합 $S$ 위에 앞선 두 조건(i, ii)을 만족하는
명확한 순서 관계("$<$")가 정의되어 있다는 것을 의미한다.

✅ 1.7 Upper Bound & Lower Bound (상계/하계) (★)

집합 $S$가 순서집합(ordered set) 이고, $E \subset S$라고 하자.

만약 어떤 원소 $\beta \in S$가 존재하여,
모든 $x \in E$에 대해 $x \leq \beta$를 만족한다면,
우리는 집합 $E$가 위로 유계(bounded above) 라고 하고,
그러한 $\beta$를 $E$의 상계(upper bound) 라고 부른다.

하계(lower bound) 는 이와 비슷하게, 어떤 $\alpha \in S$가 모든 $x \in E$에 대해 $\alpha \leq x$를 만족하면 $\alpha$를 $E$의 하계라고 부른다.

✅ 1.8 Supremum & Infimum (상한/하한) (★)

집합 $S$가 순서집합(ordered set)이고 $E \subset S$이며 $E$가 위로 유계(bounded above) 라고 하자.
이때 다음 조건을 만족하는 어떤 $\alpha \in S$가 존재한다면, 우리는 $\alpha$를 집합 $E$의 최소 상계(least upper bound) 또는 상한(supremum) 이라 하고, 다음과 같이 쓴다:

$$ \alpha = \sup E $$

조건:

1. $\alpha$는 $E$의 upper bound(상계) 이다.
   (즉, 모든 $x \in E$에 대해 $x \leq \alpha$)

2. 임의의 $\gamma < \alpha$는 $E$의 upper bound(상계)가 아니다 .
   (즉, $\gamma < \alpha$이면 어떤 $x \in E$가 존재하여 $x > \gamma$이다.)

→ 이러한 $\alpha$는 최소 상계 이므로 유일하게 존재함이 '조건 2' 로부터 자명하다.

• 하한(infimum) 또는 최대 하계(greatest lower bound)는 동일한 방식으로 정의된다.

✅ 예시 (from 1.1)

• 앞서 등장했던 집합 $A = { p \in \mathbb{Q} \mid p^2 < 2 }$의 경우,
  $A$의 모든 상계는 $B = { p \in \mathbb{Q} \mid p^2 > 2 }$의 원소들과 정확히 같다.
  즉, $B$가 $A$의 upper bounds를 구성한다.

• 하지만 $B$는 $\mathbb{Q}$에서 최솟값을 가지지 않으므로, $A$는 $\mathbb{Q}$ 내에서는 least upper bound (즉, $\sup A$)를 가지지 않는다.

💡 보충 설명

• 일반적으로 $\alpha = \sup E$가 존재할 때, $\alpha$는 $E$의 원소일 수도 있고 아닐 수도 있다.
  • $\alpha \in E$인 경우 → $\sup E$는 최댓값(maximum)이다.
  • $\alpha \notin E$인 경우 → $E$는 상한을 가지지만, 최댓값은 없다.

    ✅ 1.10 Least-upper-bound property (최소 상계 성질) (★)

순서집합 $S$가 최소 상계 성질(least-upper-bound property) 을 만족한다는 것은 다음을 의미한다:

• 임의의 공집합이 아닌 부분집합 $E \subset S$가 위로 유계(bounded above)일 때,
  반드시 $E$의 상한(supremum), 즉 $\sup E$가 집합 $S$ 안에 존재한다.

예시
앞서 살펴본 바와 같이, 유리수 집합 $\mathbb{Q}$는 최소 상계 성질을 만족하지 않는다.
(예: 집합 $A = { p \in \mathbb{Q} \mid p^2 < 2 }$는 $\mathbb{Q}$ 내에서 위로 유계(bounded above)이지만 $\sup A$를 갖지 않음.)

✅ 1.11 Least-upper-bound property와 Greatest-lower-bound theory의 관계 (★★)

Least-upper-bound theroy 을 만족하는 모든 순서집합(ordered set)은 Greatest-lower-bound property(최대 하계 성질) 도 만족한다.

조금 더 엄밀히 서술하면:

• 순서집합(Ordered Set) $S$가 Least-upper-bound property를 가진다고 하자.
• 공집합이 아닌 부분집합 $B \subset S$가 아래로 유계(bounded below)라고 하자.
• 집합 $B$의 모든 하계(lower bound)를 모은 집합을 $L$이라 하면,
  $$ \alpha = \sup L $$ 가 반드시 집합 $S$ 안에 존재하며, 이때 다음이 성립한다: $$ \alpha = \inf B $$

즉, 집합 $B$의 하한(infimum) 이 존재함을 의미한다.

📌 Proof (증명)

• $B$가 아래로 유계(bounded below)이므로, 하계들의 집합인 $L$은 비어있지 않다(적어도 하나의 원소를 가짐).
• $L$은 정확히 집합 $B$의 모든 원소 $x \in B$에 대해 $y \leq x$ 를 만족하는 원소 $y \in S$로 이루어져 있다.
  즉, $B$의 모든 원소 $x$는 $L$의 상계(upper bound)가 된다. 그러므로 $L$은 위로 유계(bounded above)이다.
• 최소 상계 성질(Least-upper-bound property) 가정에 따라 $L$은 $S$ 안에서 supremum을 가진다. 이를 $\alpha$라고 하자.

이제 다음 두 가지를 보이면 된다.

1. $\alpha$가 실제로 집합 $B$의 하계임을 보이자.

   만약 $\gamma < \alpha$ 라면, 정의에 따라 $\gamma$는 $L$의 upper bound가 될 수 없다. 즉, $\gamma \notin B$임을 의미하며( $B$ 의 모든 원소는 L의 upper bound이기 때문), 따라서 $B$의 모든 원소 $x$는 $\gamma$보다 크거나 같아야 하므로, 자연스럽게 모든 $x \in B$에 대해 $\alpha \leq x$가 성립한다. 즉, $\alpha$는 $B$의 하계이며, $\alpha \in L$이다.

2. $\alpha$가 $B$의 최대 하계임을 보이자.

   만약 어떤 $\beta > \alpha$가 있다면, $\alpha$가 $L$의 상계(supremum)이기 때문에 $\beta$는 더 이상 $L$에 포함될 수 없다. 따라서 $\beta$는 $B$의 하계가 아니다.

   즉, $\alpha$는 $B$의 하계 중 가장 큰 최대 하계가 된다. 이로써 $\alpha = \inf B$임이 증명된다.

이로써 Least-upper-bound property를 만족하는 집합이 Greatest-lower-bound property도 만족함을 보였다 $\square$

문제를 푼 날짜: 2025. 04. 16

#implementation #math

내 풀이

#include <iostream>
#include <queue>
using namespace std;


const int  MAX = 100000;

int troop[MAX + 1]; // 0으로 초기화
priority_queue<int> pq;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    int tmp;

    cin >> N;

    for(int i = 0; i < N; i++){
        cin >> tmp;
        troop[tmp]++;
    }

    for(int i = 1; i <= MAX; i++){
        if(troop[i] != 0) pq.push(troop[i]);
    }  


    if(pq.top() > (N+1) / 2) cout << "NO";
    else cout << "YES";

    return 0;
}

✅ 아이디어

처음에는 입력을 받았을 때 문제의 입출력예시 설명처럼 위치를 바꾸는 식으로 해볼까 생각을 했었고, 그 다음에는 우선순위 큐를 이용해서 일정 조건을 만족하는지 여부를 큐가 empty할 때까지 반복하는 방법을 생각했었다. 그러다 보니 코드에 불필요하게 우선순위 큐가 사용되어있다. 그냥 반복문 돌리면서 max만 찾아도 상관없다.

문제를 푼 날짜: 2025. 04. 14

#binary_search #data_structures #geometry #hash_set #math #set

내 풀이

/*
Naive Idea: 매 후보지마다 각 과일이 꼬치에 포함되는지 체크
-> O(NM) : 9 * 10^10
-> TLE! :(

Improved Idea: 
후보지의 핵심: 기울기 & x부호 (단, y축 위의 점은 기울기 존재x이므로 따로 체크)
-> 과일의 정보를 사전에 저장하면 되지 않을까?
-> Worst Case: Y=X 직선 위에(X>0) 모든 후보지와 과일이 다 존재하는 경우 -> TLE :(

Any Better Idea??

과일의 정보 -> (기울기, x좌표) 로 저장 : ex) key: 기울기[1] -> value: -1, 3, 4 ... 
후보지의 정보 -> (기울기, x좌표) 로 저장
             -> 만약에 기울기가 같고 x좌표의 부호 역시 같다면 더 큰 것만 남기면 됨!

** Implementation?!
Initial Idea: map 활용, 기울기를 key로 사용

Question: 기울기가 같지만 x좌표의 부호가 다른 경우?
-> 엄... 기울기를 key로 쓰고, value를 vector로 잡은 다음에 x좌표 양수 음수 각각 하나씩 저장하는 꼴?

+) 기울기는 float로 저장해야 할 듯?!
++) 기울기 존재하지 않는 경우 예외 처리하는 게 비효율적 -> 기울기 상한이 10억이니 초과하는 기울기로 임의설정
-> WA 뜬 후 발견! : x=0인 case는 부호 판정하는 부분에서 문제가 생겼닷!! x<->y 스왑으로 해결하자..

+++) 기울기를 key로 사용하는 근본적 문제점(부동소수점문제)? 
-> gcd로 나눈 (x, y) 사용
ex. (2, 4) -> (1, 2) / (-3, -6) -> (1, 2)

++++) 기울기 방향 고려하여 부호화
*/

#include <iostream>
#include <map>
#include <vector>
#include <cstdlib>
#include <numeric>
#include <utility>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, M; // N: 과일의 수, M: 후보지의 수
    cin >> N >> M;

    int x, y; // 입력 위한 임시변수
    map<pair<int, int>, vector<int>> Fruits;
    map<pair<int, int>, int> Candidates;

    // 과일 위치 입력받기
    for(int i = 0; i < N; i++){
        cin >> x >> y;

        // y축 위에 있으면 기울기 존재 x, y > 0 이면 (0, 1), y <0 이면 (0, -1) 생성
        if(x == 0){
            if(y > 0) Fruits[{0, 1}].push_back(y);
            else Fruits[{0, -1}].push_back(y);
        } 
        else{
            int GCD = gcd(abs(x), abs(y));
            Fruits[{x/ GCD, y / GCD}].push_back(x);
        }
    }

    // 후보지 입력받기
    for(int i = 0; i < M; i++){
        cin >> x >> y;

        pair<int, int> slope;
        // y축 위에 있으면 기울기 존재 x, y > 0 이면 (0, 1), y < 0이면 (0, -1)
        if(x == 0){
            if(y > 0){
                slope = {0, 1};
                x = y;
            } else{
                slope = {0, -1};
                x = y;
            }
        }
        else{
            int GCD = gcd(abs(x), abs(y));
            slope = {x / GCD, y / GCD};
        }

        if(Candidates.find(slope) == Candidates.end()) Candidates[slope] = x;

        else if(abs(x) > abs(Candidates[slope])) Candidates[slope] = x;
    }

    // 후보지 key(=기울기) 순회하면서 최댓값 찾기
    int max = 0;

    for(auto& [key, value] : Candidates){
        int cnt = 0;
        for(auto& fruit : Fruits[key]){
            if(abs(value) >= abs(fruit)) cnt++;
        }
        if(cnt > max) max = cnt;
    }

    cout << max;
    return 0;
}

✅ 아이디어

• 각 후보지마다 전체 과일을 iterate하면서 이 과일이 꼬치에 들어가는 지 체크? -> TLE
• 후보지 & 과일의 정보를 기울기로 저장하자!

• 각 후보지마다 기울기가 같은 과일들만 조사하면 됨. (단, y축 위 점의 경우 기울기 존재하지 않으므로 예외 처리 해야 함)

🧠 풀면서 틀렸던 부분 & 얻어가야 하는 내용

• 기울기를 key로 사용할 때, 실수표현은 부동소수점 오차로 인해 의도한 바와 다르게 작동할 수 있음을 간과함!

• pair<int, int>로 기울기 표현함. (기울기벡터 개념, 최대공약수로 (x, y)좌표 나눔)

• 기울기가 같더라도 방향이 다른 경우 (ex. (2, 4), (-3, -6))의 경우 다르게 취급해야 함!

• 기울기 벡터 표현 시 부호 고려

• 후보지의 경우 기울기 같고 방향마저 동일하다면 제일 멀리있는 후보지 하나만 고려하면 됨.

• 부호가 같은지 판별하는 조건식 사용할 때 곱하기를 사용했었는데 (v * fruit > 0) 이 경우 int범위를 초과하는 문제가 발생하게 됨! (자료형의 크기 초과하는 경우 없는지 항상 체크)

• • pair<int, int> => <utility>
  • abs( int )=> <cstdlib>
  • gcd(int x, int y) => <numeric>

• 기울기를 사용하는 아이디어는 문제에 처음 접근할 때 (Survival Week1 당일) 바로 떠올렸음에도, 이후 구현 및 WA를 고치기 위해 꽤 많은 시간을 투자했음. 문제가 생겼을 때 빠르게 고칠 수 있는 클린 코드가 아닌, 그 순간순간 내 머릿속에 있는 아이디어를 배설하는 식의 주먹구구 코딩을 한 것이 큰 문제인 것 같다... 클린 코드를 쓰는 연습이 많이 필요해 보인다. 아래는 지피티가 개선해준 나의 코드이다.

개선된 코드

#include <iostream>
#include <map>
#include <vector>
#include <numeric>  // std::gcd (C++17 이상)
#include <cstdlib>  // abs 함수
#include <algorithm>

using namespace std;
using Slope = pair<int, int>;

// 함수: 주어진 점 (x, y)에 대해 정규화된 기울기와 기준 좌표를 구한다.
// - 수직선(x==0)인 경우: y>0이면 key = {0, 1}과 기준 = y, y<0이면 key = {0, -1}과 기준 = y
// - 수직선이 아닌 경우: x, y를 gcd로 나누어 key = {x/g, y/g}와 기준 = x를 사용한다.
void normalizePoint(int x, int y, Slope &slope, int &pos) {
    if (x == 0) { 
        // 수직선인 경우 y>0와 y<0를 분리해서 처리
        if (y > 0) {
            slope = {0, 1};
            pos = y;
        } else {
            slope = {0, -1};
            pos = y;
        }
    } else {
        int g = gcd(abs(x), abs(y));
        slope = {x / g, y / g};
        pos = x;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int nFruits, nCandidates;  
    cin >> nFruits >> nCandidates;

    // 과일들은 (정규화된 기울기, 기준 좌표) 형태로 저장
    // - 수직선인 경우, 기준은 y좌표, 그 외에는 x좌표
    map<Slope, vector<int>> fruits;
    // 후보지는 같은 기울기 그룹 내에서 양수와 음수 방향 각각 최고 값(원점에서 가장 멀리 떨어진 후보)만 저장
    // 따로 후보지 벡터를 관리하는 대신, 한 방향에 대해 단 하나의 후보지만 고려하면 됨
    map<Slope, int> candidate; 

    // 과일 입력
    for (int i = 0; i < nFruits; i++) {
        int x, y;
        cin >> x >> y;
        Slope slp;
        int pos;
        normalizePoint(x, y, slp, pos);
        fruits[slp].push_back(pos);
    }

    // 후보지 입력: 같은 기울기 그룹 내에서는 기준 값의 절대값이 더 큰 후보지만 남긴다.
    for (int i = 0; i < nCandidates; i++) {
        int x, y;
        cin >> x >> y;
        Slope slp;
        int pos;
        normalizePoint(x, y, slp, pos);

        // 처음 보는 그룹이면 바로 저장, 이미 있으면 절대값이 더 크면 갱신
        if (candidate.find(slp) == candidate.end() || abs(pos) > abs(candidate[slp])) {
            candidate[slp] = pos;
        }
    }

    // 각 기울기 그룹 별로 후보지가 포함할 수 있는 과일의 개수를 셈.
    // 조건: 후보지(원점에서의 기준 좌표의 절대값)가 과일(해당 그룹에서 저장된 기준 좌표의 절대값)보다 크거나 같아야 한다.
    int ans = 0;
    for (const auto & [slp, candPos] : candidate) {
        // 해당 기울기를 가진 과일이 없다면 넘어감
        if (fruits.find(slp) == fruits.end())
            continue;

        int count = 0;
        for (int fruitPos : fruits[slp]) {
            if (abs(candPos) >= abs(fruitPos))
                count++;
        }
        ans = max(ans, count);
    }

    cout << ans << "\n";
    return 0;
}

개괄

코테 대비를 위해 대회 형식의 연습도 필요할 듯하여 3시간 제한으로 진행하였다. 제4회 SMUPC의 문제를 사용하였고, 싸지방에 모여서 진행했으나 중간에 뇌우조치로 작업가야해서(…) 흐름이 끊기긴 했다.

A번. SMUPC NAME (BOJ 31859) (브론즈 1)

#implementation #string

내 풀이

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int alphabet[26]; // 'a'->0에 대응, 사용됐을 경우 1
int isAvailable[21]; // 제거할 시 1

int main() {

    string name; // 최대 20자
    string nickname = "";
    int N;
    int cnt = 0; // 제거 문자 수

    cin >> N;
    cin >> name;

    for(int i = 0; i < name.length(); i++){
        if(alphabet[name[i] - 'a'] == 0) alphabet[name[i] - 'a'] = 1;
        else{
            cnt++;
            isAvailable[i] = 1;
        }
    }

    for(int i = 0; i < name.length(); i++){
        if(isAvailable[i] == 0) nickname += name[i];
    }

    cnt += 4;
    nickname += to_string(cnt);

    N += 1906;
    nickname = to_string(N) + nickname;

    reverse(nickname.begin(), nickname.end());

    nickname = "smupc_" + nickname;

    cout << nickname;
    return 0;
}

개선된 풀이

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    cin >> N;

    string name;
    cin >> name;

    // 알파벳 사용 여부를 저장하는 벡터 (false: 아직 안 씀, true: 이미 사용됨)
    vector<bool> used(26, false);

    // 중복되지 않는 문자를 담을 문자열
    string filteredName;
    // 중복된 문자(두 번째 이상 등장한 문자) 개수
    int duplicateCount = 0;

    for (char c : name) {
        int idx = c - 'a'; 
        // 아직 사용되지 않은 알파벳이라면
        if (!used[idx]) {
            used[idx] = true;  
            filteredName.push_back(c);
        } else {
            // 이미 사용된 알파벳이면 중복 문자 수 증가
            duplicateCount++;
        }
    }

    // 문제 요구사항에 따라 중복 문자 수에 4를 더함
    duplicateCount += 4;

    // N에 1906을 더함
    N += 1906;

    // 닉네임: (N값) + (중복 제거된 문자열) + (중복 문자 수)
    string nickname = to_string(N) + filteredName + to_string(duplicateCount);

    // 문자열 뒤집기
    reverse(nickname.begin(), nickname.end());

    // "smupc_"를 접두어로 추가
    nickname = "smupc_" + nickname;

    // 결과 출력
    cout << nickname << "\n";
    return 0;
}

✅ 풀면서 느낀 점

• 빠르게 풀고 넘겼어야 할 A번 문제이지만, string 오랜만에 다루면서 구현에 어려움을 겪고 16분 걸림

• String 문제 풀 것!

B번. 열심히 일하는 중 (BOJ 31860) (실버 2)

#implementation #data_structures #simulation #priority_queue

내 풀이

/*
일의 수: N
일 처리 후 M만큼 중요도 감소
중요도 K 이하로 떨어지면 그 일은 완료.

만족도 = (전날 만족도 / 2) + 오늘 한 일 중요도
(첫날의 경우 전날 만족도 0으로 가정)

Goal1: 일 끝내는데 얼마나 걸림?
Goal2: 매일매일 만족도

Idea: priority_queue를 활용해보자!
*/

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

priority_queue<int> work; // 중요도 크기 내림차순으로 정렬
vector<int> daily_satisfaction;

int main() {
    int N, M, K;
    int tmp;
    int day = 0; // 업무 끝나는 데 걸리는 일 수
    int satisfaction = 0; // 전날 만족도

    cin >> N >> M >> K;

    for(int i = 0; i < N; i++){
        cin >> tmp;
        work.push(tmp);
    }

    while(!work.empty()){
        int importance = work.top();
        day++;
        work.pop();

        satisfaction = satisfaction / 2 + importance;
        daily_satisfaction.push_back(satisfaction);

        importance -= M;
        if(importance > K) work.push(importance);
    }

    cout << day << '\n';
    for(auto &k : daily_satisfaction){
        cout << k << '\n';
    }
    return 0;
}

✅ 풀면서 느낀 점

• 16분 소요 -> 무난하게 넘김!
• 문제 접근: ‘매 순간 중요도가 제일 높은 작업 택해야함‘

• ‘중요도 순으로 항상 정렬‘

• priority queue!

• 코테 때 나올 문제도 텍스트양이 많아 독해를 빠르게 잘 하는 것이 관건일 것 -> 문제의 조건 써보면서 문제 이해하기!

C번. 비밀번호 만들기 (BOJ 31861) (실버 1)

#dp

내 풀이

/*
IDEA: DP 문제?!

DP[n][k]
n번째 문자(1<=n<=26) 뒤에 문자열 길이 k (0<=k<1000) 경우의수

기저사례
DP[n][0] = 1

DP[n][1] = {현재 문자: x, 가능한 범위: 1<=a<=26 , |a-x| >= N}일 때 a의 개수


Given N, M
=> we need to find DP[1][M-1] + DP[2][M-1] + ... + DP[26][M-1]!
*/

#include <iostream>
using namespace std;

int DP[27][1000];
int N, M;
int findDP(int a, int b);

int main() {

    int sum = 0; // 구하고자 하는 경우의 수
    cin >> N >> M;

    // DP배열 초기화
    for(int i = 1; i <= 26; i++){
        for(int j = 0; j <= M - 1; j++){
            DP[i][j] = -1;
        }
    }

    for(int i = 1; i <= 26; i++){
        sum = (sum + findDP(i, M-1)) % 1000000007;
    }

    cout << sum;
    return 0;
}

int findDP(int a, int b){
    if(DP[a][b] != -1) return DP[a][b];
    else if(b == 0){
        DP[a][b] = 1;
        return 1;
    }
    else if(b == 1){
        int cnt = 0;
        for(int i = 1; i <= 26; i++){
            if(abs(i - a) >= N) cnt++;
        }
        DP[a][b] = cnt;
        return cnt;
    }
    else{
        int sum = 0;
        for(int i = 1; i <= 26; i++){
            if(abs(i - a) >= N){
                sum = (sum + findDP(i, b - 1)) % 1000000007;
            }
        }
        DP[a][b] = sum;
        return sum;
    }
}

✅ 풀면서 느낀 점

• 28분 소요 -> 잘 풀었음!
• 문제 접근: ‘가능한 경우의 수 카운팅‘ + ‘int형 범위 초과하는 정답‘

• DP를 사용하지 않을까?

• 무엇을 기록(재사용)해야 할까?

• DP 문제를 풀 때 구해야 할 2가지
  • 점화식
  • 기저사례(base case) 더 구하기 쉬운 기저사례를 먼저 떠올리고 점화식에 접근하니 잘 풀 수 있었음!

D번. 내진 설계 (BOJ 31863) (골드 5)

#graphs #graph_traversal #implementation #simulation

내 풀이 (대회 시간 후 완성)

/*
IDEA: 시키는 그대로 하자!

지진의 종류가 2개. → 본진(2칸) & 여진(1칸)
핵심 → 본진은 어차피 처음 1번만! 이후에는 여진만 발생 가능.
→ 본진을 따로 처리해주고, 여진을 queue로 처리해주자!

*/
#include <iostream>
#include <queue>
using namespace std;

char Map[1001][1001];

struct Position{
    int x, y;
};

int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};

queue<Position> q;
int collapse = 0; // 무너진 건물 수

// 건물 만났을 때 처리 방식 똑같으므로 함수로 처리해주자!
void WeakBuilding(int x, int y);
void StrongBuilding(int x, int y);

int main() {
    int N, M;
    int num = 0; // 기존 건물 수

    Position source;

    cin >> N >> M;

    // 맵 입력받기 & 진원지 찾아주기
    for(int i = 0; i < N; i++){
        for(int j = 0; j < M; j++){
            cin >> Map[i][j];
            if(Map[i][j] == '@'){
                source.x = i;
                source.y = j;
            }

            else if(Map[i][j] == '*' || Map[i][j] == '#') num++;
        }
    }

    // 본진 처리해주기
    for(int i = 0; i < 4; i++){
        int pointx = source.x + dx[i];
        int pointy = source.y + dy[i];

        if(pointx >= 0 && pointx < N && pointy >= 0 && pointy < M){
            // 방파제일 경우 -> 여기서 끝!
            if(Map[pointx][pointy] == '|') continue;

            // 내진X 건물 -> 건물 무너짐 & 여진 발생!
            else if(Map[pointx][pointy] == '*') WeakBuilding(pointx, pointy);

            // 내진O 건물 -> 내진X 건물로 바뀜!
            else if(Map[pointx][pointy] == '#') StrongBuilding(pointx, pointy);

            // 방파제 아닌 case이므로 => 두 칸 갈 수 있는지 체크!
            pointx += dx[i];
            pointy += dy[i];
            if(pointx >= 0 && pointx < N && pointy >= 0 && pointy < M){
                if(Map[pointx][pointy] == '*') WeakBuilding(pointx, pointy);
                else if(Map[pointx][pointy] == '#') StrongBuilding(pointx, pointy);
            }
        }
    }

    // 여진 처리해주기
    while(!q.empty()){
        int pointx = q.front().x;
        int pointy = q.front().y;

        q.pop();

        for(int i = 0; i < 4; i++){
            int newpointx = pointx + dx[i];
            int newpointy = pointy + dy[i];

            if(newpointx >= 0 && newpointx < N && newpointy >= 0 && newpointy < M){
                if(Map[newpointx][newpointy] == '|') continue;
                else if(Map[newpointx][newpointy] == '*') WeakBuilding(newpointx, newpointy);
                else if(Map[newpointx][newpointy] == '#') StrongBuilding(newpointx, newpointy);
            }

        }
    }

    cout << collapse << ' ' << num - collapse;
    return 0;
}

void WeakBuilding(int x, int y){
    collapse++;
    Map[x][y] = '.';

    Position tmp;
    tmp.x = x;
    tmp.y = y;
    q.push(tmp);
}

void StrongBuilding(int x, int y){
    Map[x][y] = '*';
}

✅ 풀면서 느낀 점

• 이 문제에서 시간을 꽤 소요했고, 결정적으로 풀었음에도 WA(Wrong Answer)가 나와 멘붕이 오면서 나머지 문제를 못 풀고 이 문제마저 해결하지 못하게 되었다.
• 로직이 어려운 문제가 전혀 아니었고, 내가 생각한 바와 같이 ‘시키는 대로‘ 하면 되는 문제였다.
• 어이없게도 내 로직 역시 맞았고, int num = 0; 을 int num;으로 쓴 것 하나만이 문제였다.
  • 온라인 컴파일러를 사용하였는데, 주어진 예제도 맞고, 내가 만든 사이드케이스 역시 문제없이 실행됐던 이유는 아마 컴파일러 버전이 높아 초기화하지 않은 변수를 0으로 알아서 초기화했기 때문(?)으로 생각한다.

    🧠 피드백

    이 문제에서 발생한 패착은 크게 2가지
• • 1. 로직이 어렵지 않았음에도 최초풀이를 완성하는 데 시간이 걸린 점**
• • 2. 테케가 맞았음에도 WA가 나오는 상황에 대처하지 못한 점** 이다.

1번의 문제는 결국 집중력 문제로, 제한된 시간 안에 빠르게 문제를 정확히 푸는 훈련을 많이 하는 것이 주요할 것으로 보인다. (수능에 비유하자면, 80분 동안 국어 시험지 한 세트를 푸는 연습)

2번의 문제는 Online Judge와 내가 사용한 컴파일러의 환경이 다를 수 있다는 점을 몰랐던 것, 그리고 내 코드를 꼼꼼히 디버깅하지 못한 점에서 기인한다.

** ‘ 어떤 전략을 세울 것인가? ‘와도 결부된다. 분명히 내 로직이 맞다는 확신이 있음에도 미상의 원인으로 WA가 뜰 때, 뒷 문제들 또한 로직을 바로 떠올릴 수 있다면 일단 뒷 문제부터 푸는 것이 좋은 전략이 되겠지만, 뒤의 문제들이 쉽게 풀기 힘든 난이도라면 이 문제는 ** 절대 틀려서는 안 될 문제일 것이고, 코드를 처음부터 파헤쳐 봤어야 했다. 앞으로 같은 경우가 발생한다면 변수 선언에서 문제가 없는 지도 꼭 체크해야겠다.

나머지 문제들은 시간 내에 읽지 못했거나, 조금 접근하다 말았음으로 개별 문제를 따로 푼 후 피드백할 예정이다.

문제를 푼 날짜: 2025. 04. 11

#graphs #graph_traversal #trees #bfs #dfs

[Figure 1] 문제를 이해하는 과정에서 싸지방 윈도우의 그림판을 이용해서 그려봤다. 상당한 퀄리티이다.

문제를 푼 날짜: 2025. 04. 11

내 풀이

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

const int MAX = 100000;
vector<int> adj_list[MAX + 1];
int Parent[MAX + 1]; // 아직 부모노드 못 찾은 상태(초기값) == 0
queue<int> q;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    cin >> N;

    // 인접 리스트 업데이트
    for(int i = 0; i < N; i++){
        int tmp1,tmp2;
        cin >> tmp1 >> tmp2;
        adj_list[tmp1].push_back(tmp2);
        adj_list[tmp2].push_back(tmp1);
    }

    int x = 1;
    for(auto &k : adj_list[1]){
        Parent[k] = 1;
        q.push(k);
    }

    while(!q.empty()){
        x = q.front();
        q.pop();

        for(auto &k: adj_list[x]){
            if(Parent[k] == 0){
                Parent[k] = x;
                q.push(k);
            }
        }
    }

    for(int i = 2; i <= N; i++){
        cout << Parent[i] << '\n';
    }
    return 0;
}

** 이번 문제는 피드백할 점이 딱히 없었다 ㅎㅎ **