경우없는 개발 블로그

• 중복 부분 문제 (Overlapping Subproblems):
  • 동적 프로그래밍 문제는 동일한 하위 문제를 여러 번 반복해서 푸는 특성이 있습니다. 예를 들어 피보나치 수열에서 F(n) = F(n-1) + F(n-2)와 같은 점화식을 사용할 때, F(n-1)과 F(n-2)를 반복적으로 계산하는 경우가 많습니다.
  • DP에서는 이러한 중복 계산을 **메모이제이션 (Memoization)**이나 탑다운/바텀업 접근법으로 저장해 두고, 동일한 하위 문제가 다시 등장하면 저장된 값을 사용하여 계산을 줄입니다. 이를 통해 시간 복잡도를 줄여 효율성을 높입니다.
• 최적 부분 구조 (Optimal Substructure):
  • 최적 부분 구조란 문제를 작은 하위 문제들로 나누어 해결할 수 있고, 각 하위 문제의 최적해를 결합하여 전체 문제의 최적해를 구성할 수 있는 특성입니다. 다시 말해, 전체 문제를 해결하는 최적의 해답이 하위 문제들의 최적해로 이루어져 있다는 것입니다.
  • 예를 들어, 최단 경로 문제에서는 특정 노드까지의 최단 경로가 그 이전 경로들의 최단 경로들로 이루어져 있습니다.

#동적 계획법(DP)이란?

DP의 두 가지 핵심 특성

1. 중복되는 부분 문제(Overlapping Subproblems):
   • 동적 계획법은 문제를 풀 때 동일한 부분 문제가 여러 번 반복됩니다. 예를 들어, 피보나치 수열에서 F(n)=F(n−1)+F(n−2)F(n) = F(n-1) + F(n-2)F(n)=F(n−1)+F(n−2)를 구할 때, F(n−1)F(n-1)F(n−1)과 F(n−2)F(n-2)F(n−2)을 재귀적으로 구하게 됩니다. 하지만 F(n−2)F(n-2)F(n−2)는 F(n−1)F(n-1)F(n−1)을 계산할 때도 다시 구하게 됩니다. 이처럼 중복된 계산이 자주 발생하므로, 이를 메모이제이션 또는 테이블 저장을 통해 중복 계산을 방지합니다.
2. 최적 부분 구조(Optimal Substructure):
   • 최적 부분 구조란, 큰 문제의 해답이 그 문제를 구성하는 작은 문제들의 최적 해답으로부터 도출될 수 있다는 특성입니다. 즉, 작은 문제의 최적 해가 변하지 않고 그대로 전체 문제의 최적 해를 이루는 데 기여한다는 것입니다.
   • 예를 들어, 피보나치 수열에서 F(n)=F(n−1)+F(n−2)F(n) = F(n-1) + F(n-2)F(n)=F(n−1)+F(n−2)로 계산할 수 있듯이, 작은 문제들의 최적해를 통해 큰 문제의 답을 구할 수 있습니다.

동적 계획법의 활용 예

• 피보나치 수열: 피보나치 수열을 재귀적으로 구할 때, 각 숫자의 결과를 저장하여 중복된 계산을 방지합니다.
• 배낭 문제: 배낭 문제에서 최대 가치를 구할 때, 각 부분 문제(작은 용량의 배낭에서 최대 가치를 구하는 문제)가 전체 문제의 해답을 구성합니다.

즉 DP 는 동일한 부분문제가 반복되면서 그 부분문제로 전체의 큰 문제를 풀 수 있으며

작은 문제의 최적 해가 바뀌지 않을 때 라고 할 수 있다.

#분할 정복(Divide and Conquer)이란?

**분할 정복(Divide and Conquer)**은 문제를 더 작은 부분 문제로 나눈 후, 각 부분 문제를 독립적으로 해결하고, 이들의 해답을 합쳐서 전체 문제를 해결하는 방식입니다. 분할 정복에서는 중복된 부분 문제가 발생하지 않으며, 각 부분 문제의 결과가 전체 문제의 최적 해답을 직접적으로 보장하지는 않습니다.

분할 정복의 특징

1. 최적 부분 구조가 없다:
   • 분할 정복에서는 각 부분 문제의 해답이 전체 문제의 최적 해답을 바로 보장하지 않습니다. 작은 문제들을 해결한 후, 이를 병합하는 과정에서 전체 문제의 해답이 달라질 수 있습니다.
   • 예를 들어, 병합 정렬(Merge Sort)에서 부분 배열이 정렬되었다고 해서 바로 전체 배열이 정렬되는 것은 아닙니다. 부분 배열들을 병합해야 최종적으로 전체 배열이 정렬됩니다.
2. 중복되는 부분 문제가 없다:
   • 분할 정복에서 각 부분 문제는 독립적입니다. 동일한 부분 문제가 여러 번 반복되지 않으며, 한 번 계산한 부분 문제는 다른 문제에서 다시 계산되지 않습니다.
   • 이는 동적 계획법과의 큰 차이점 중 하나입니다. 예를 들어, 병합 정렬에서 배열을 두 부분으로 나누어 정렬할 때, 같은 부분 문제를 반복해서 계산하지 않으며, 각 부분 문제는 독립적으로 처리됩니다.

분할 정복의 활용 예

• 병합 정렬(Merge Sort): 배열을 반으로 나누어 각각을 정렬한 후, 두 정렬된 배열을 병합하여 전체 배열을 정렬하는 알고리즘입니다. 작은 문제들이 해결된 후에도 병합 과정에서 전체 해답이 결정됩니다.
• 퀵 정렬(Quick Sort): 피벗을 기준으로 배열을 나누어 각각을 정렬하고, 그 결과를 합쳐서 전체 배열을 정렬하는 알고리즘입니다.

동적 계획법 (DP)                                                                               분할 정복 (Divide and Conquer)

# 쉽게 생각해서..

예를들어서 병합정렬을 생각해보도록하자

병합정렬은 부분으로 나눠서 정렬하는데

결국에는 합쳐서 모두 정렬을 해야 되기 때문에

부분적으로 정렬한것이 그대로 최적해가 보장되지 않는다고 할 수 있다.

(부분 정렬한거 그대로 사용 안하니까)

때문에  부분 문제의 답이 최적해가 아니라고 볼 수 있고

그리고 또한

**병합 정렬(Merge Sort)**에서는 부분 배열을 계속해서 더 작은 부분으로 나눠도, 이미 처리된 부분 문제를 다시 처리하지 않는다. 이게 바로 중복되는 부분 문제가 없다는 의미이다

더 설명해보자면

병합정렬을 위해서 부분을 쪼개서 합치게 된다면

그 합쳐진 부분문제는 "다른문제" 라고 할 수 있다.

왜냐면 그 다른 문제를 풀때는 이전의 부분문제를 요구하지 않기 때문이다.

 때문에 이전문제를 메모리제이션 할 필요가 없으니 중복되는 부분문제라 볼수 없다

1) substr 함수

substr 함수는 문자열의 특정 부분을 잘라내는 데 사용됩니다.

기본 사용법

#include <iostream>
#include <string>

using namespace std;

int main() {
    string s = "0123456789";

    string subs1 = s.substr(2, 5); // subs1 = "23456"
    cout << "subs1: " << subs1 << endl;

    string subs2 = s.substr(5); // subs2 = "56789"
    cout << "subs2: " << subs2 << endl;

    string subs3 = s.substr(); // subs3 = "0123456789"
    cout << "subs3: " << subs3 << endl;

    return 0;
}

• 시작 위치와 길이를 지정하여 문자열을 자릅니다.
• 시작 위치만 지정하면 해당 위치부터 끝까지 문자열을 자릅니다.
• 아무 것도 지정하지 않으면 문자열 전체를 복사합니다.

find 함수와 함께 사용하기

#include <iostream>
#include <string>

using namespace std;

int main() {
    string s = "0123456789";

    string subs1 = s.substr(s.find('6')); // subs1 = "6789"
    cout << "subs1: " << subs1 << endl;

    string subs2 = s.substr(s.find('6'), 2); // subs2 = "67"
    cout << "subs2: " << subs2 << endl;

    return 0;
}​

• find 함수를 이용해 특정 문자나 문자열을 찾고, 그 위치부터 잘라낼 수 있습니다.

추가 팁:

• substr 함수는 범위가 문자열의 길이를 초과할 경우 자동으로 문자열 끝까지 자릅니다.
• 인덱스가 음수거나 범위를 벗어나면 out_of_range 예외가 발생할 수 있으므로 주의가 필요합니다.

2) sstream을 이용한 쪼개기

sstream을 이용하면 문자열을 특정 구분자로 쉽게 쪼갤 수 있습니다.

기본 사용법

#include <sstream>
#include <vector>
#include <string>
#include <iostream>

using namespace std;

int main() {
    string s = "012 34567 89";
    istringstream ss(s);
    string subs1; // 임시 변수
    vector<string> v;

    while (getline(ss, subs1, ' ')) {
        v.push_back(subs1); // v = {"012", "34567", "89"}
    }

    // 결과 출력
    for (const auto& str : v) {
        cout << str << " ";
    }

    return 0;
}​

• getline 함수를 이용하여 구분자로 문자열을 쪼개고, 이를 벡터에 저장합니다.

추가 팁:

• getline 함수는 구분자를 지정하지 않으면 기본적으로 줄바꿈 문자(\n)를 구분자로 사용합니다.
• 문자열을 여러 번 쪼개야 할 경우 istringstream을 반복 사용하여 처리할 수 있습니다.

3) C의 strtok 함수 사용

strtok 함수는 C 스타일 문자열을 특정 구분자로 쪼갤 때 사용됩니다.

기본 사용법

#include <iostream>
#include <cstring>

using namespace std;

int main() {
    char str[] = "a b c d e f";
    char* p_str = strtok(str, " ");
    
    while (p_str != NULL) {
        cout << p_str << ' ';
        p_str = strtok(NULL, " ");
    }

    return 0;
}

• 첫 번째 인자에 자를 문자열을, 두 번째 인자에 구분자를 넣어 사용합니다.

여러 구분자 사용하기

#include <iostream>
#include <cstring>

using namespace std;

int main() {
    char str2[] = "a-b,c:d e-f";
    char* p_str2 = strtok(str2, ",- :");

    while (p_str2 != NULL) {
        cout << p_str2 << ' ';
        p_str2 = strtok(NULL, ",- :");
    }

    return 0;
}

• 여러 구분자를 설정하여 문자열을 쪼갤 수 있습니다.

추가 팁:

• strtok 함수는 원본 문자열을 변경합니다. 따라서 원본 문자열을 보존해야 할 경우 복사본을 사용해야 합니다.
• strtok 함수는 스레드 안전하지 않으므로 멀티스레딩 환경에서는 사용을 피하거나 대체 함수(strtok_r)를 사용하는 것이 좋습니다.

마무리

위에서 다룬 substr, sstream, strtok 함수는 각각의 장점과 단점을 가지고 있습니다. 상황에 맞게 적절한 방법을 사용하여 문자열을 효율적으로 다뤄보세요. 이 글이 여러분의 C++ 프로그래밍에 도움이 되길 바랍니다.

코드 예제

substr 함수

#include <iostream>
#include <string>

using namespace std;

int main() {
    string s = "0123456789";

    string subs1 = s.substr(2, 5); // subs1 = "23456"
    cout << "subs1: " << subs1 << endl;

    string subs2 = s.substr(5); // subs2 = "56789"
    cout << "subs2: " << subs2 << endl;

    string subs3 = s.substr(); // subs3 = "0123456789"
    cout << "subs3: " << subs3 << endl;

    return 0;
}

sstream을 이용한 쪼개기

#include <sstream>
#include <vector>
#include <string>
#include <iostream>

using namespace std;

int main() {
    string s = "012 34567 89";
    istringstream ss(s);
    string subs1; // 임시 변수
    vector<string> v;

    while (getline(ss, subs1, ' ')) {
        v.push_back(subs1); // v = {"012", "34567", "89"}
    }

    // 결과 출력
    for (const auto& str : v) {
        cout << str << " ";
    }

    return 0;
}

strtok 함수 사용

#include <iostream>
#include <cstring>

using namespace std;

int main() {
    char str[] = "a b c d e f";
    char* p_str = strtok(str, " ");
    
    while (p_str != NULL) {
        cout << p_str << ' ';
        p_str = strtok(NULL, " ");
    }

    return 0;
}

여러 구분자 사용하기

#include <iostream>
#include <cstring>

using namespace std;

int main() {
    char str2[] = "a-b,c:d e-f";
    char* p_str2 = strtok(str2, ",- :");

    while (p_str2 != NULL) {
        cout << p_str2 << ' ';
        p_str2 = strtok(NULL, ",- :");
    }

    return 0;
}

https://www.acmicpc.net/problem/10951

cin.eof() 를 사용

주요 사항

1. 입력 시도 후에 확인 가능: cin.eof()는 입력 시도가 실패한 후에만 의미가 있습니다. 즉, cin >> variable과 같은 입력 시도가 먼저 이루어져야 합니다. 만약 입력 시도가 실패하고 그 이유가 파일의 끝에 도달했기 때문이라면, 그때 cin.eof()는 참이 됩니다.
2. eof 플래그: cin.eof()가 참이라는 것은 스트림이 파일의 끝에 도달했음을 의미합니다. 하지만 파일 끝에 도달했다고 해서 바로 cin.eof()가 참이 되지는 않습니다. 먼저 입력 시도가 이루어져야 하고, 그 시도가 파일 끝에 도달했음을 감지해야 합니다.

#include <iostream>
#include <vector>

using namespace std;

bool visited[10];


int main() {

    while (1) {
        int a, b;
        cin >> a >> b;

        if (cin.eof()) {
            break;
        }
    }

    
    return 0;
}

문장 입력받기

#include <iostream>
#include <map>
#include <string>
#include <iomanip>

using namespace std;

int main() {


    // 입력 받기 (EOF까지)
    while (getline(cin, tree)) {

    }



    return 0;
}