Learn to share,Share to learn
그리디 알고리즘(2) 본문
TL;DR
1. abs(A-B)로 절대값
2. A.count('1') = A에서 1 개수 세어줌
3. zip 함수
https://www.acmicpc.net/problem/12782
12782번: 비트 우정지수
진홍이는 숫자를 좋아한다. 오늘도 숫자를 가지고 놀던 진홍이는 두 숫자의 비트 우정지수를 구해보았다. 비트 우정지수란, 10진법으로 나타낸 두 정수를 이진수로 나타내었을 때, 두 숫자를 같
www.acmicpc.net
절대값 비교의 필요성을 느꼈다.
A_one = A.count('1')
B_one = B.count('1')
difference = abs(A_one - B_one) # A와 B에서 1의 개수 차이의 절대값
문제
진홍이는 숫자를 좋아한다. 오늘도 숫자를 가지고 놀던 진홍이는 두 숫자의 비트 우정지수를 구해보았다. 비트 우정지수란, 10진법으로 나타낸 두 정수를 이진수로 나타내었을 때, 두 숫자를 같게 만드는데 필요한 최소 연산 횟수를 말한다. 연산의 종류는 다음과 같다.
- 하나의 이진수에서 임의의 자리의 숫자를 0 또는 1로 바꾼다.
- 하나의 이진수에서 서로 다른 자리에 있는 두 숫자의 위치를 바꾼다.
예를 들어, 10진수 11과 12의 비트 우정지수를 구해보자. 11을 이진수로 나타내면 1011이고, 12를 이진수로 나타내면 1100이다. 1011에서 2의 자리를 0으로 바꾸고(1011 -> 1001), 1의 자리와 4의 자리의 숫자를 서로 바꾸면(1001 -> 1100) 1100이 된다. 즉, 1011을 1100으로 바꾸는 최소 연산 횟수는 두 번으로, 11과 12의 비트 우정지수는 2가 된다.
진홍이는 어떤 두 수가 주어졌을 때 두 수의 비트 우정지수를 구하는 프로그램을 만들고 싶다. 하지만, 아쉽게도 진홍이는 프로그래밍에 약해 10진수를 이진수로 바꾸는 것 밖에 하지 못한다. 여러분이 진홍이를 도와 두 수의 비트 우정지수를 구하는 프로그램을 만들어 주자!
입력
입력의 첫 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 50)가 주어진다.
각 테스트케이스의 첫 번째 줄에는 두 이진수 N, M이 주어진다. N, M의 자릿수는 1,000,000을 넘지 않으며, 자릿수는 서로 같다.
출력
각 테스트 케이스마다 두 수의 비트 우정지수를 출력한다.
예제 입력 1 복사
3
1011 1100
100101 110100
00110100 10010111
예제 출력 1 복사
2
1
3
from collections import Counter
N = int(input())
for _ in range(N):
count=0
A,B = input().split()
C = list(A)
D = list(B)
A_one = A.count('1')
B_one = B.count('1')
for i in range(0,len(C)):
if C[i]!=D[i] and A_one!=B_one:
count+=1
C[i]='1'
D[i]='1'
문자열은 불변이니까 리스트에 넣어서 비교해야한다. 카운터에 대해 공부한덕에 1의 개수도 쉽게 셀수 있었다. 그리디인데 브루트포스마냥 풀려다 막혔다. 일단 첫 생각은 1이 차이나는 만큼 1이 부족한쪽에 더해주고, 인덱스 0부터 비교하면서 다를때마다 카운트를 올려주든 하려했는데 영 잘못생각한거같고.. 로직을 생각해내지 못했다.
문제의 핵심은 최소한의 연산으로 두 이진수를 같게 만드는 것이다. 이를 위해 다음과 같은 단계를 거쳐야 한다:
- 불일치하는 비트의 개수 찾기: 두 이진수에서 서로 다른 위치에 있는 0과 1의 개수를 찾는다. 이는 위치를 바꿔서 일치시킬 수 있는 비트의 쌍의 최대 개수를 나타낸다.
- 필요한 변경의 최소 횟수 계산: 두 이진수에서 1의 개수가 다른 경우, 이 차이만큼은 반드시 0을 1로 바꾸거나 그 반대의 연산을 수행해야 한다. 이것이 필요한 최소 변경 횟수의 기저가 된다.
- 위치 변경을 통한 최적화: 불일치하는 비트 중에서 위치를 바꿔 일치시킬 수 있는 비트의 쌍을 찾아 해당 연산을 수행한다. 이 경우, 한 번의 연산으로 두 비트를 동시에 일치시킬 수 있으므로 연산 횟수를 최소화할 수 있다.
이제 코드를 수정하자. 먼저, 불일치하는 비트의 개수를 찾고, 1의 개수가 다른 경우 그 차이를 계산한다. 그 다음, 위치 변경을 최대한 활용하여 최소 연산 횟수를 계산한다.
from collections import Counter
T = int(input())
for _ in range(T):
A, B = input().split()
count = 0
# 불일치하는 0과 1의 개수 찾기
mismatch_0 = mismatch_1 = 0
for a, b in zip(A, B): # A와 B의 각 비트를 짝지어 비교
if a != b: # 불일치하는 경우
if a == '1':
mismatch_1 += 1 # A에서 1, B에서 0인 경우
else:
mismatch_0 += 1 # A에서 0, B에서 1인 경우
# 위치 변경을 최대한 활용
# 불일치하는 0과 1 중 더 많은 것이 최소 연산 횟수가 됨
count = max(mismatch_0, mismatch_1)
print(count)
- zip 함수: zip 함수는 두 개 또는 그 이상의 이터러블(iterable, 예: 리스트, 문자열 등)을 인자로 받아, 동일한 인덱스의 요소를 튜플로 묶어주는 역할을 한다. 이 경우, zip(A, B)는 문자열 A와 B의 각 문자를 순서대로 짝지어준다.
- 절대값 비교: 파이썬에서 절대값은 abs 함수로 계산한다. 예를 들어, 두 숫자의 차이의 절대값을 구하고 싶다면 abs(A - B) 형태로 사용하면 된다.
알겠다. 이 문제에서 그리디 알고리즘을 적용하는 방식을 좀 더 자세히 설명하겠다. 먼저, zip 함수에 대한 설명과 예시를 제공하고, 그 다음에 비트 우정지수 문제에 대해 다시 설명하겠다.
zip 함수 설명 및 예시
zip 함수는 여러 이터러블(iterable)들을 인자로 받아, 각 이터러블에서 동일한 인덱스의 요소를 튜플로 묶어주는 역할을 한다. 이터러블에는 리스트, 튜플, 문자열 등이 포함될 수 있다. 여기 몇 가지 예시가 있다:
- 리스트 두 개를 짝짓기:
list1 = [1, 2, 3] list2 = ['a', 'b', 'c'] for number, letter in zip(list1, list2): print(number, letter) # 출력: # 1 a # 2 b # 3 c
- 문자열과 리스트 짝짓기:
string = "ABC" numbers = [1, 2, 3] for letter, number in zip(string, numbers): print(letter, number) # 출력: # A 1 # B 2 # C 3
- 세 개의 리스트 짝짓기:
list1 = [1, 2, 3] list2 = ['a', 'b', 'c'] list3 = [0.1, 0.2, 0.3] for num, let, flt in zip(list1, list2, list3): print(num, let, flt) # 출력: # 1 a 0.1 # 2 b 0.2 # 3 c 0.3
비트 우정지수 문제 설명
이제 비트 우정지수 문제로 돌아가자. 이 문제의 핵심은 두 이진수의 불일치하는 비트를 최소한의 연산으로 일치시키는 것이다. 각 이진수에서 불일치하는 0과 1의 개수를 센다. 그리고 이 중에서 위치를 바꿔 일치시킬 수 있는 최대 개수를 찾는다. 위치를 바꾸는 것은 한 번의 연산으로 두 비트를 일치시킬 수 있으므로 가장 효율적이다.
두 이진수에서 불일치하는 0과 1의 개수를 세고, 이 중 작은 값을 가진 개수만큼 위치를 바꿔 일치시킬 수 있다. 이후 남은 불일치하는 비트는 각각 한 번씩 변경해야 한다. 그래서 최소 연산 횟수는 두 이진수에서 불일치하는 0과 1 중 더 많은 것의 개수가 되는 것이다.
예를 들어:
- A = 10101, B = 11011 일 경우,
- 불일치하는 비트: 2번째, 4번째 (A에서 0, B에서 1)
- 불일치하는 0의 개수: 2 (A의 2번째, 4번째)
- 불일치하는 1의 개수: 0 (B의 해당 없음)
- 최소 연산 횟수: max(2, 0) = 2
이 방식으로 각 비트의 불일치를 최소한의 연산으로 해결할 수 있고, 이것이 그리디 알고리즘의 핵심이다.
'알고리즘' 카테고리의 다른 글
그리디 알고리즘(4)enumerate,zip 함수와 함께 (1) | 2024.01.28 |
---|---|
그리디 알고리즘(3) (0) | 2024.01.28 |
그리디 알고리즘 간단 고찰과 다시 볼 문제 (0) | 2024.01.27 |
튜플로 리스트 저장하기(2개 이상의 값들 리스트로 저장하기) (0) | 2024.01.26 |
알고리즘 팁2 (0) | 2024.01.26 |