Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 이진 문자열이 나타내는 수를 만드는 최소 연산 횟수 구하기

문제 설명

이진 문자열 str이 주어졌을 때, 이 문자열이 나타내는 수를 만들기 위해 수행해야 하는 최소 연산 횟수를 구하는 문제입니다. 사용할 수 있는 연산은 다음 두 가지뿐입니다.

  • 2x 더하기
  • 2x 빼기

예를 들어 이진 문자열이 "1000"이라면 23을 한 번 더하는 연산만으로 충분하므로 최소 연산 횟수는 1입니다.

반면 이진 문자열이 "101"이라면 22와 20을 각각 더해야 하므로 최소 연산 횟수는 2입니다.

접근 방법: 동적 프로그래밍(DP)

단순히 1인 비트의 개수를 세는 것만으로는 최적해를 보장할 수 없습니다. 예를 들어 "111"(= 7)의 경우 1인 비트가 3개이지만, 23을 더한 뒤 20을 빼는 방식을 쓰면 단 2번의 연산으로 목표 값을 만들 수 있습니다. 즉, 빼기 연산을 적절히 활용하면 연속된 1이 많은 경우 연산 횟수를 줄일 수 있습니다.

이 문제는 문자열을 뒤집어 최하위 비트부터 차례대로 처리하면서, 각 비트 위치마다 두 가지 상태를 함께 고려하는 동적 프로그래밍으로 해결할 수 있습니다.

  • result[i][0] : i번째 비트까지 처리했을 때, 추가적인 자리올림 없이 정확히 일치시키는 데 필요한 최소 연산 횟수
  • result[i][1] : i번째 비트까지 처리했을 때, 상위 자리에 1을 더해 자리올림이 발생한 상태에서 필요한 최소 연산 횟수

현재 비트가 '0'이면 그대로 두거나, 자리올림 상태를 해소하기 위해 한 번의 연산(2i 빼기)을 추가할 수 있습니다. 현재 비트가 '1'이면 그 반대 방향으로 상태가 전이됩니다. 최종적으로는 자리올림이 없는 상태인 result[n-1][0]이 정답이 됩니다.

C++ 구현

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

int getMinOperations(string s){
    reverse(s.begin(), s.end());
    int n = s.length();
    int result[n + 1][2];
    if (s[0] == '0') {
        result[0][0] = 0;
    } else {
        result[0][0] = 1;
    }
    result[0][1] = 1;
    for (int i = 1; i < n; ++i) {
        if (s[i] == '0') {
            result[i][0] = result[i - 1][0];
            result[i][1] = 1 + min(result[i - 1][1],
            result[i - 1][0]);
        } else {
            result[i][1] = result[i - 1][1];
            result[i][0] = 1 + min(result[i - 1][0],
            result[i - 1][1]);
        }
    }
    return result[n - 1][0];
}

int main(){
    string str = "101";
    cout << "최소 필요 연산 횟수 = " << getMinOperations(str) << endl;
    return 0;
}

실행 결과

위 프로그램을 컴파일하고 실행하면 다음과 같은 결과가 출력됩니다.

최소 필요 연산 횟수 = 2

복잡도 분석

  • 시간 복잡도 : O(n) — 문자열의 길이 n에 대해 각 비트를 한 번씩 순회합니다.
  • 공간 복잡도 : O(n) — 각 비트 위치별로 두 가지 상태를 저장하는 2차원 배열을 사용합니다.