주어진 조건에 따라 배열에서 길이 K의 이진 문자열을 구성합니다.

이 튜토리얼에서는 배열 요소를 사용하여 I와 동일한 하위 집합의 합을 얻을 수 있는 경우 i번째 인덱스에 "1"이 포함되도록 길이가 K인 이진 문자열을 구성해야 합니다. 문제를 해결하는 두 가지 방법을 배우겠습니다. 첫 번째 접근 방식에서는 동적 프로그래밍 방법을 사용하여 하위 집합의 합이 인덱스 "I"와 같은 것이 가능한지 확인합니다. 두 번째 방법에서는 bitset을 사용하여 배열 요소를 통해 가능한 모든 합계를 찾습니다.

문제 설명 - N개의 정수를 포함하는 배열이 제공됩니다. 또한 이진 문자열의 길이를 나타내는 정수 M이 제공됩니다. 다음 조건을 따르도록 길이가 M인 이진 문자열을 만들어야 합니다.

• 합이 인덱스 "I"와 동일한 배열의 하위 집합을 찾을 수 있으면 인덱스 "I"의 문자는 1이고, 그렇지 않으면 0입니다.

• 내 인덱스는 1부터 시작합니다.

예제 예

으아악 으아악

지침

• 합이 1인 부분 집합은 {1}입니다.

• 합이 2인 부분 집합은 {2}입니다.

• 합이 3인 부분 집합은 {1, 2}입니다.

• 합이 4인 부분 집합을 찾을 수 없으므로 4번째 인덱스에 0을 넣습니다.

으아악 으아악

지침

합이 1에서 5 사이가 되도록 가능한 모든 조합을 만들 수 있습니다. 따라서 처음 5자는 1이고 마지막 4자는 0입니다.

으아악 으아악

지침

배열 요소를 사용하면 1과 4의 합을 얻을 수 없으므로 첫 번째와 네 번째 인덱스 위치에 0을 배치합니다.

방법 1

이 방법에서는 동적 프로그래밍을 사용하여 배열 요소를 사용하여 인덱스 'I'와 동일한 합계를 구성할 수 있는지 확인합니다. 각 인덱스에 대해 이를 확인하고 이진 문자열에 1 또는 0을 추가합니다.

알고리즘

• 1단계 - 크기 N의 벡터를 만들고 정수 값으로 초기화합니다. 또한 문자열 유형의 "bin" 변수를 정의하고 빈 문자열로 초기화합니다.

• 2단계 - for 루프를 사용하여 총 반복 횟수를 문자열 길이와 동일하게 만듭니다.

• 3단계 - for 루프에서 배열 N과 인덱스 값을 매개변수로 전달하여 isSubsetSum() 함수를 호출합니다.

• 4단계 - isSubsetSum() 함수가 true를 반환하면 "bin"에 "1"을 추가합니다. 그렇지 않으면 "bin"에 "0"을 추가합니다.

• 5단계 - isSubsetSum() 함수를 정의하여 배열 요소를 합산할 수 있는지 확인합니다.

• 5.1단계 - dpTable이라는 2차원 벡터를 정의합니다.

• 5.2단계 - 제로섬이 항상 가능하므로 'dpTable[i][0]'을 true로 초기화합니다. 여기서 'I'는 인덱스 값이다.

• 5.3단계 - 빈 배열의 합계가 불가능하므로 'dpTable[0][j]'를 false로 초기화합니다.

• 5.4단계 - 이제 두 개의 중첩 루프를 사용합니다. 첫 번째 루프는 1에서 N까지 반복되고 다른 루프는 1에서 합계까지 반복됩니다.

• 5.5단계 - for 루프에서 현재 요소의 값이 합계보다 크면 무시합니다.

• 5.6단계 − 그렇지 않으면 요소를 포함하거나 제외하여 합계를 구합니다.

• 5.7단계 − 결과가 포함된 'dpTable[N][sum]'을 반환합니다.

예

으아악

출력

으아악

시간 복잡도 - O(N^3), isSubsetSum()의 시간 복잡도가 O(N^2)이고 드라이버 코드에서 이를 N번 호출하기 때문입니다.

공간 복잡도 - O(N^2), isSubsetSum() 함수에서 2차원 벡터를 사용하기 때문입니다.

비트셋 사용방법

이 방법에서는 비트 세트를 사용하여 배열의 다양한 요소를 결합하여 가능한 모든 합계 값을 찾습니다. 여기서 bitset은 이진 문자열을 생성한다는 의미입니다. 결과 비트 세트에서 각 비트는 합계가 특정 인덱스와 같은지 여부를 나타내며 여기에서 찾아야 합니다.

알고리즘

• 1단계 - 배열과 M을 정의합니다. 추가적으로 createBinaryString() 함수를 정의하세요.

• 2단계 - 다음으로 원하는 길이의 비트 세트를 정의하여 이진 문자열을 생성합니다.

• 3단계 - 0의 합은 항상 가능하므로 비트[0]을 1로 초기화합니다.

• 4단계 - for 루프를 사용하여 배열 요소를 반복합니다

.

• 5단계 - 먼저 배열 요소에 대해 "비트" 왼쪽 시프트 연산을 수행합니다. 그런 다음 결과 값은 비트 값과 OR로 연결됩니다.

• 6단계 − 인덱스 1에서 M까지 설정된 비트의 값을 인쇄합니다.

예

으아악

출력

으아악

시간 복잡도 - 단일 for 루프를 사용하기 때문에 O(N)입니다.

공간 복잡도 - 비트 세트의 값을 저장하기 때문에 O(N)입니다.

결론

여기서 공간 및 시간 복잡도 측면에서 첫 번째 방법보다 나은 두 번째 방법을 최적화했습니다. 그러나 두 번째 방법은 비트 세트에 대한 이해가 없으면 초보자가 이해하기 어려울 수 있습니다.

위 내용은 주어진 조건에 따라 배열에서 길이 K의 이진 문자열을 구성합니다.의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!