Post

2026-06-17 TIL (78일차)

Posted Updated
By BAEK MUSONG(백무송)
26 min read
2026-06-17 TIL (78일차)

[C++] find 가이드

find 사용처

① <algorithm> 라이브러리의 std::find (순차 탐색)

  • 적용 대상: vector, array, list, deque 등 (배열 형태의 자료구조)
  • 시간 복잡도: $O(N)$ (처음부터 끝까지 하나씩 뒤져봄)
  • 특징: 자료구조 내부에 find 함수가 없어서 알고리즘 라이브러리를 빌려 씁니다.

② 컨테이너 전용 멤버 함수 container.find() (이진 탐색 / 해시 탐색)

  • 적용 대상: set, map, unordered_set, unordered_map
  • 시간 복잡도: $O(\log N)$ (이진 탐색 트리 기반) 또는 $O(1)$ (해시 테이블 기반)
  • 특징: 자체적으로 엄청나게 빠른 탐색 기능을 가지고 있습니다.
  • 코테 주의점: set이나 map에서 std::find(s.begin(), s.end(), target)를 쓰면 바보같이 $O(N)$으로 탐색합니다. 반드시 s.find(target) 멤버 함수를 써야 합니다!

2. find로 “위치(인덱스)”를 찾을 수 있나요?

네, 가능합니다! 단, find는 ‘인덱스 번호(숫자)’가 아니라 ‘반복자(Iterator, 포인터와 비슷한 개념)’를 반환하기 때문에 약간의 연산이 필요합니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

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

using namespace std;

int main() {
    vector<int> v = {10, 20, 30, 40, 50};
    int target = 30;

    // 1. find 사용
    auto it = find(v.begin(), v.end(), target);

    // 2. 찾았는지 확인 및 인덱스 구하기
    if (it != v.end()) {
        // [꿀팁] 현재 이터레이터에서 시작점(v.begin())을 빼면 인덱스가 나옵니다!
        int index = it - v.begin(); 
        cout << "찾았습니다! 인덱스: " << index << "\n"; // 출력: 인덱스: 2
    } else {
        cout << "배열에 존재하지 않습니다.\n";
    }
    
    return 0;
}

3. find로 “원소의 갯수”도 찾을 수 있나요?

아니요, 불가능합니다. find는 배열을 돌다가 ‘가장 처음 발견한 원소’의 위치만 반환하고 바로 종료됩니다. 뒤에 같은 숫자가 더 있어도 무시합니다. 원소의 갯수를 찾으려면 find 대신 std::count를 사용해야 합니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

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

using namespace std;

int main() {
    vector<int> v = {10, 20, 30, 20, 20, 50};
    
    // 20이 몇 개 있는지 찾기
    int count_20 = count(v.begin(), v.end(), 20);
    
    cout << "20의 갯수: " << count_20 << "개\n"; // 출력: 20의 갯수: 3개
    
    return 0;
}

4. string(문자열)에서의 find는 다릅니다!

코딩 테스트에서 문자열 파싱 문제에 무조건 쓰이는 string::find는 벡터와 작동 방식이 조금 다릅니다. 이터레이터가 아닌 ‘인덱스(size_t)’를 바로 반환합니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

#include <iostream>
#include <string>

using namespace std;

int main() {
    string str = "hello world";
    
    // "world"라는 문자열이 시작되는 인덱스 찾기
    size_t pos = str.find("world");
    
    // 벡터의 v.end() 대신, 문자열은 string::npos 로 없는지 확인합니다.
    if (pos != string::npos) {
        cout << "찾은 위치 인덱스: " << pos << "\n"; // 출력: 6
    }
    
    return 0;
}

코딩 테스트 실전 요약

  1. vector에서 값 찾기/인덱스 구하기 ➡️ find(v.begin(), v.end(), target) 후 it - v.begin()
  2. vector에서 갯수 구하기 ➡️ count(v.begin(), v.end(), target)
  3. set, map에서 존재 여부 확인 ➡️ 무조건 s.find(target) 멤버 함수 사용 (시간 초과 방지)
  4. string에서 단어 위치 찾기 ➡️ str.find("단어") 후 string::npos와 비교


그리디(Greedy) 알고리즘의 성립 조건과 한계

그리디 알고리즘은 이름 그대로 “매 순간 지금 당장 눈앞에 보이는 최선의 선택(탐욕적인 선택)을 하는 알고리즘”입니다. 하지만 이 방식이 항상 완벽한 정답을 보장하지는 않습니다.

그리디가 완벽하게 작동하려면 특정 조건들이 맞아야 하는데, 이를 이해하기 위해 먼저 ‘지역 최적’과 ‘전역 최적’의 개념을 알아야 합니다.

1. 지역 최적(Local Optimum) vs 전역 최적(Global Optimum)

  • 지역 최적 (Local Optimum): “지금 내 위치에서 주변을 둘러봤을 때 가장 좋아 보이는 것”입니다.
  • 전역 최적 (Global Optimum): “게임이 끝났을 때를 기준으로, 전체에서 가장 좋은 진짜 정답”입니다.

그리디 알고리즘은 철저하게 ‘지역 최적’만을 쫓는 알고리즘입니다. 예를 들어, 등산을 할 때 안대가 씌워진 채로 무조건 ‘지금 발을 디딜 수 있는 곳 중 가장 높은 곳’으로만 올라간다고 생각해 보세요. 운이 좋으면 진짜 정상(전역 최적)에 도달하겠지만, 중간에 있는 작은 언덕(지역 최적) 꼭대기에 도착하고는 “여기가 정상인가 보다!” 하고 멈춰버릴 수도 있습니다.

즉, 지역 최적들의 합이 전역 최적이 되지 않는 경우, 그리디 알고리즘은 실패합니다.

2. 그리디가 성공하기 위한 “두 가지 속성”

그리디가 작은 언덕에 빠지지 않고 진짜 정상(전역 최적)을 찾으려면, 다음 두 가지 속성을 반드시 모두 만족해야 합니다.

① 탐욕적 선택 속성 (Greedy Choice Property)

“지금 한 최선의 선택이, 나중에 뒤돌아봐도 절대 후회 없는 선택이어야 한다.”

  • 의미: 각 단계에서 탐욕적으로 내린 선택이 최종 결과(전체 최적해)에 무조건 포함되어야 합니다. 앞선 선택이 이후의 선택에 악영향을 주지 않아야 합니다.

② 최적 부분 구조 (Optimal Substructure)

“큰 문제를 작은 문제로 쪼개도, 그 원리가 똑같이 적용되어야 한다.”

  • 의미: 전체 문제의 최적해가 부분 문제의 최적해들로 구성될 수 있어야 합니다.
  • 예시: 730원을 거슬러 주어야 할 때, 가장 큰 500원짜리를 하나 씁니다. 그러면 이제 문제는 “남은 230원을 어떻게 최적으로 거슬러 줄 것인가?”라는 작은 문제로 완벽하게 축소됩니다.

3. 핵심: “왜 동전이 배수 관계일 때만 그리디가 통할까?”

동전 거스름돈 문제에서 “큰 동전이 항상 작은 동전들의 배수”라는 조건은 앞서 말한 ‘① 탐욕적 선택 속성’을 지켜주는 절대적인 방어막입니다.

이 방어막이 깨지면 어떻게 되는지 비교해 보겠습니다.

Case 1: 배수 관계가 맞을 때 (우리나라 화폐: 10원, 50원, 100원, 500원)

  • 목표: 80원 거슬러 주기
  • 작은 동전 여러 개를 모으면 무조건 큰 동전으로 대체할 수 있습니다. (10원짜리 5개 = 50원 1개).
  • 따라서 “무조건 가장 큰 동전(50원)을 먼저 쓰는 것(탐욕적 선택)”이 언제나 정답입니다. 50원 1개, 10원 3개로 총 4개가 최적해입니다.

Case 2: 배수 관계가 깨졌을 때 (가상의 화폐: 10원, 40원, 50원)

  • 목표: 80원 거슬러 주기
  • 그리디 알고리즘의 판단 (실패): “당장 눈앞에 50원짜리가 제일 크네? 50원 써!” 👉 50원 1개를 쓰고 30원이 남습니다. 30원은 10원짜리 3개로 채워야 합니다. 총 4개(50, 10, 10, 10)를 사용했습니다.
  • 실제 전역 최적해 (정답): 40원짜리 동전 2개(40, 40)만 쓰면 끝납니다!

왜 실패했을까?

50원은 40원의 배수가 아닙니다. 즉, “작은 동전(40원)을 모아서 큰 동전(50원)을 대체할 수 없는 상황”이 발생한 것입니다. 당장 눈앞에 보이는 50원을 선택하는 것(지역 최적)이, 결국 10원짜리를 여러 개 쓰게 만들어서 전체적으로는 더 손해(전역 최적 실패)를 보게 만든 것입니다. 즉, ‘탐욕적 선택 속성’이 깨져버렸습니다.

4. 결론 및 요약

  • 그리디는 빠르고 강력하지만, “지역 최적 = 전역 최적”이 보장되는 특수한 상황에서만 정답을 냅니다.
  • 탐욕적 선택 속성과 최적 부분 구조 두 가지를 모두 만족하면 그리디를 사용해(그리디 GO!) 문제를 순식간에 풀 수 있습니다.
  • 하지만 동전의 배수 관계가 깨지는 것처럼 조건이 하나라도 부족하다면, 그리디는 오답을 냅니다. 이때는 모든 경우의 수를 확인하거나 최적해를 저장해 나가는 동적 계획법(DP)이나 백트래킹을 사용해야만 정답을 찾을 수 있습니다.


동적 계획법(DP): 점화식(Recurrence Relation)

1. 점화식이란 무엇인가요?

점화식(Recurrence Relation)은 수학에서 “어떤 수열의 일반항을 그 이전의 항들을 이용하여 정의한 공식”을 말합니다. 쉽게 말해, “현재의 정답을 구하기 위해 과거의 정답들을 어떻게 조립할 것인가?”를 나타내는 규칙입니다.

  • 가장 친숙한 예시 (피보나치 수열): 앞의 두 수를 더해서 현재 수를 만드는 수열입니다. (1, 1, 2, 3, 5, 8…) 이것을 점화식으로 표현하면 다음과 같습니다. $F_n = F_{n-1} + F_{n-2}$

DP가 점화식을 사용하는 이유는, DP 자체가 “큰 문제를 작은 문제들로 쪼개서 풀고, 그 결과를 합쳐서 큰 문제의 답을 내는 기법”이기 때문입니다. 이때 작은 문제들을 합치는 ‘설계도’가 바로 점화식입니다.

2. 점화식 도출을 위한 4단계 접근법 (실전 가이드)

DP 문제를 마주쳤을 때, 막무가내로 코드를 짜기보다 아래 4단계를 거치는 훈련을 해야 합니다.

1단계: 상태(State) 정의하기

dp 배열(또는 테이블)이 정확히 무엇을 의미하는지 한 문장으로 정의해야 합니다. 이 단계를 대충 넘기면 절대 점화식을 세울 수 없습니다.

  • 예: dp[i] = i번째 계단까지 도달하는 경우의 수
  • 예: dp[i] = i번째 날까지 얻을 수 있는 최대 이익

2단계: 기저 상태(Base Case) 설정하기

과거의 답을 조합하려면 가장 최초의 답(시작점)이 필요합니다. 더 이상 쪼개지지 않는 가장 작은 문제의 답을 수동으로 넣어줍니다.

  • 예: dp[1] = 1 (1번 계단에 가는 법은 1가지)
  • 예: dp[2] = 2 (2번 계단에 가는 법은 1칸+1칸, 2칸으로 2가지)

3단계: 점화식(관계식) 찾기

i번째 상황을 구하기 위해, 바로 직전 상황(i-1, i-2 등)에서 어떻게 넘어올 수 있는지 모든 경우의 수를 따져봅니다.

  • “내가 5번째 계단에 서 있으려면, 방금 어디서 올라왔어야 하지?” 👉 4번째 계단에서 1칸 올라오거나, 3번째 계단에서 2칸 올라왔어야 함.
  • 점화식 도출: dp[i] = dp[i-1] + dp[i-2]

4단계: 구현 방식 선택 (Top-down vs Bottom-up)

  • Top-down (메모이제이션): 재귀 함수를 사용하여 큰 문제에서 작은 문제로 내려갑니다.
  • Bottom-up (타뷸레이션): 반복문(for문)을 사용하여 dp[1]부터 dp[N]까지 차근차근 채워 올라갑니다. (코딩 테스트에서 주로 권장됨)

3. 대표적인 DP 예제: “1로 만들기” 접근해보기

[문제 요약] 어떤 수 $N$에 대해 1) 3으로 나누거나, 2) 2로 나누거나, 3) 1을 뺄 수 있습니다. $N$을 1로 만드는 ‘최소 연산 횟수’를 구하세요.

[접근 과정]

  1. 상태 정의: dp[i] = 숫자 i를 1로 만드는 데 필요한 최소 연산 횟수
  2. 기저 상태: dp[1] = 0 (1은 이미 1이므로 연산이 0번 필요함)
  3. 점화식 찾기: 숫자 i가 10이라고 가정해 봅시다. 10은 어디서 왔을까요?
    • 10 - 1 = 9 (9에서 1을 더해서 옴) 👉 dp[i-1]
    • 10 / 2 = 5 (5에서 2를 곱해서 옴) 👉 dp[i/2]
    • 10 / 3은 안 나누어 떨어지므로 패스.
    • 그렇다면 9를 1로 만드는 최적의 횟수(dp[9])와 5를 1로 만드는 최적의 횟수(dp[5]) 중 더 작은 값에 +1(이번 연산 횟수)을 하면 됩니다.
    • 최종 점화식: dp[i] = min(dp[i-1], dp[i/2], dp[i/3]) + 1 (나누어 떨어질 때만 고려)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

// 1로 만들기 (Bottom-up C++ 예시)
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int n = 10;
    vector<int> dp(n + 1, 0);

    // dp[1]은 0이므로 i=2부터 시작
    for (int i = 2; i <= n; i++) {
        // 1. 기본적으로 1을 빼는 경우
        dp[i] = dp[i - 1] + 1;

        // 2. 2로 나누어 떨어지는 경우, 이전 값과 비교하여 최소값 갱신
        if (i % 2 == 0) {
            dp[i] = min(dp[i], dp[i / 2] + 1);
        }

        // 3. 3으로 나누어 떨어지는 경우, 최소값 갱신
        if (i % 3 == 0) {
            dp[i] = min(dp[i], dp[i / 3] + 1);
        }
    }

    cout << n << "을 1로 만드는 최소 횟수: " << dp[n] << "\n";
    return 0;
}


동적 계획법(DP)의 핵심: “같은 계산을 두 번 하지 마라”

1. DP가 통하기 위한 두 가지 필수 조건

DP를 적용하려면 문제에 다음 두 가지 속성이 있어야 합니다.

  1. 중복 부분 문제 (Overlapping Subproblems): 동일한 작은 문제들이 반복해서 나타나야 합니다. (예: 피보나치 수열에서 F(3)이 여러 번 중복되어 호출됨)
  2. 최적 부분 구조 (Optimal Substructure): 큰 문제의 최적해가 작은 문제들의 최적해로 이루어져야 합니다. (이는 앞서 배운 그리디 알고리즘과 공유하는 속성입니다.)

2. 점화식: “큰 문제를 작은 문제의 식으로 쓰기”

점화식은 큰 문제를 작은 문제들로 쪼개어 표현하는 수식입니다. 피보나치 수열이 가장 대표적인 예입니다.

  • 점화식: $F(n) = F(n-1) + F(n-2)$

이 점화식을 순수 재귀(Pure Recursion)로만 풀면, 계산했던 값을 또 하고 또 하면서 시간 복잡도가 $O(2^n)$으로 치솟아 순식간에 약 3억 번 이상의 연산이 발생하게 됩니다. 이를 해결하는 것이 바로 DP의 두 가지 구현 방식입니다.

3. 코드로 보는 DP의 두 가지 구현 방식

DP는 연산 결과를 저장(메모)하는 방식과 방향에 따라 크게 두 가지로 나뉩니다. 두 방식 모두 시간 복잡도를 $O(n)$으로 획기적으로 줄여줍니다. (3억 번의 연산이 약 79번으로 단축됩니다!)

① 탑다운 (Top-down) 방식: 메모이제이션 (Memoization)

  • 방향: 큰 문제에서 시작해 작은 문제로 내려가며 풉니다. (재귀 함수 사용)
  • 핵심 원리: 계산 결과를 배열(memo)에 “메모”해 둡니다. 다음에 똑같은 계산을 요구받으면, 멍청하게 다시 계산하는 대신 메모장에서 값을 꺼내서 바로 반환합니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

#include <iostream>
#include <vector>

using namespace std;

// 계산 결과를 저장할 "메모장" (배열 초기화: 0으로 채움)
vector<int> memo(100, 0);

int fibo_top_down(int n) {
    // 기저 상태 (종료 조건)
    if (n == 1 || n == 2) return 1;

    // 🚨 [핵심] 이미 계산해서 메모해 둔 값이라면? 계산하지 않고 메모를 꺼내 씀!
    if (memo[n] != 0) {
        return memo[n];
    }

    // 처음 계산하는 값이라면, 점화식을 통해 계산 후 메모장에 적어둠
    memo[n] = fibo_top_down(n - 1) + fibo_top_down(n - 2);
    return memo[n];
}

② 바텀업 (Bottom-up) 방식: 타뷸레이션 (Tabulation)

  • 방향: 가장 작은 문제부터 차근차근 답을 구해가며 큰 문제로 올라옵니다. (반복문 사용)
  • 핵심 원리: 결과들을 표(Table)의 밑바닥부터 채워 나간다고 하여 타뷸레이션이라고 부릅니다. 함수 호출 스택이 쌓이지 않아 코딩 테스트에서 메모리 초과 위험이 적고, 실행 속도가 더 빠른 안전한 방식입니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

#include <iostream>
#include <vector>

using namespace std;

int fibo_bottom_up(int n) {
    // 표(Table) 역할을 할 배열 생성
    vector<int> dp(100, 0);

    // 기저 상태 수동 설정 (가장 작은 문제의 답)
    dp[1] = 1;
    dp[2] = 1;

    //  [핵심] 3부터 n까지 차근차근 올라가며 표를 채움
    for (int i = 3; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2]; // 점화식 적용
    }

    return dp[n]; // 최종적으로 완성된 가장 큰 문제의 답 반환
}

요약

  • 순수 재귀: 바보같이 계산했던 걸 계속 또 계산합니다. ($O(2^n)$)
  • DP (메모이제이션/타뷸레이션): 한 번 푼 문제의 답을 배열에 저장해두고 재활용하여 “같은 계산을 절대 두 번 하지 않습니다”. ($O(n)$)
TIL(Today I Learned), 2026-06-17
TIL 2026 내일배움캠프 C++ Unreal 코딩테스트
This post is licensed under CC BY 4.0 by the author.