[백준] 16953번 A → B

문제

정수 A를 B로 바꾸려고 한다. 가능한 연산은 다음과 같은 두 가지이다.

• 2를 곱한다.
• 1을 수의 가장 오른쪽에 추가한다.

A를 B로 바꾸는데 필요한 연산의 최솟값을 구해보자.

입력

첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다.

출력

A를 B로 바꾸는데 필요한 연산의 최솟값에 1을 더한 값을 출력한다. 만들 수 없는 경우에는 -1을 출력한다.

예제 입력 1

2 162

예제 출력 1

5

2 → 4 → 8 → 81 → 162

예제 입력 2

4 42

예제 출력 2

-1

예제 입력 3

100 40021

예제 출력 3

5

100 → 200 → 2001 → 4002 → 40021

내 코드

시간초과

from collections import deque

A, B = map(int, input().split())

q = deque([A])
visited = deque([A])
counts = 1
is_while_break = False

while q:
    counts += 1

    for _ in range(len(q)):
        a = q.popleft()

        a_set = (a * 10 + 1, a * 2)
        if B in a_set:
            is_while_break = True
            break

        for number in a_set:
            if (number <= 10**9) and (number*2 <= B) and (number not in visited):
                visited.append(number)  # 방문 리스트 추가
                q.append(number)

    if is_while_break:
        break

    if not q:
        counts = -1
        break

print(counts)

수정한 내 코드

visited를 list → set 로 바꾸니 시간 통과된다.

from collections import deque

A, B = map(int, input().split())

q = deque([A])
visited = set([A])
counts = 1
found = False

while q:
    counts += 1

    for _ in range(len(q)):
        a = q.popleft()

        a_set = (a * 10 + 1, a * 2)
        if B in a_set:
            found = True
            break

        for number in a_set:
            if (number*2 <= B) and (number not in visited):
                visited.add(number)  # 방문 처리
                q.append(number)

    if found:
        break

    if not q:
        counts = -1
        break

print(counts)

chatGPT

문제점 분석 및 개선 방향

• 시간 초과의 원인:
  1. visited를 deque로 사용:visited에서 중복 여부를 확인하는 데 시간이 많이 소요됩니다.이는 deque가 O(n)의 탐색 비용을 가지기 때문입니다.
  2. 불필요한 조건 검사:(number * 2 <= B) 조건은 BFS에서 이미 최소 연산으로 도달 가능한 노드들만 탐색하기 때문에 필요하지 않습니다.
  3. 방문 처리 시점의 비효율:방문 리스트 추가가 큐에 삽입한 후에 이루어져, 같은 값을 중복 처리할 가능성이 생깁니다.

---

개선된 코드

from collections import deque

def find_min_operations(A, B):
    queue = deque([(A, 1)])  # 초기 값과 연산 횟수
    visited = set()  # 방문 처리: 탐색 속도 향상을 위해 set 사용

    while queue:
        current, count = queue.popleft()

        # 목표 값에 도달
        if current == B:
            return count

        # 가능한 연산 수행
        for next_num in (current * 2, current * 10 + 1):
            if next_num <= B and next_num not in visited:  # B를 초과하지 않고 방문하지 않은 경우
                visited.add(next_num)  # 방문 처리
                queue.append((next_num, count + 1))

    return -1  # 목표 값에 도달할 수 없는 경우

# 입력
A, B = map(int, input().split())
print(find_min_operations(A, B))

---

주요 개선사항

1. visited를 set으로 변경:
   • 중복 방문 여부를 O(1) 시간 복잡도로 확인할 수 있어 탐색 속도가 크게 향상됩니다.
2. 연산 결과 next_num의 범위 확인:
   • next_num <= B 조건을 통해 불필요한 연산을 제거합니다.이는 B를 초과하는 값은 절대 목표 값에 도달할 수 없음을 이용한 것입니다.
3. 큐에 (값, 연산 횟수) 저장:
   • 각 값에 대해 연산 횟수를 함께 저장해, 별도의 카운터 변수 없이 최단 경로를 계산합니다.

---

시간 복잡도 분석

• BFS 탐색:
  • 각 노드는 한 번만 방문되므로 O(V), 여기서 V는 최대 B−A입니다.B−A
  • V
  • 연산 2x와 10x+1으로 각 노드에서 최대 두 개의 자식 노드를 생성하므로, 간선은 O(E), 최대 2V입니다.10x+1
  • 2V
  • 2x
• visited 확인:
  • set을 이용한 중복 확인은 O(1)입니다.

최종적으로 시간 복잡도는 O(V), 즉 탐색 가능한 값의 범위에 비례합니다.

부가 질문

set 를 이용한 중복확인이 list를 이용한 확인보다 더 빠른 이유는?

set이 list보다 중복 확인이 더 빠른 이유는 탐색 알고리즘의 차이 때문입니다.

---

1. list의 탐색 방식: 선형 탐색

• list는 내부적으로 순차 탐색(선형 탐색)을 수행합니다.
• 예를 들어, value in list를 확인할 때, 파이썬은 리스트의 각 요소를 처음부터 끝까지 하나씩 비교합니다.
• 시간 복잡도: O(n)n은 리스트의 길이입니다.
• nn

---

2. set의 탐색 방식: 해시 테이블

• set은 내부적으로 해시 테이블을 기반으로 작동합니다.
• 각 값에 대해 고유의 해시 값을 생성하고, 이 해시 값을 키로 사용해 데이터를 저장합니다.
• 요소를 찾을 때도 해시 값을 기반으로 바로 접근하므로 데이터의 길이에 관계없이 일정한 시간 안에 탐색이 가능합니다.
• 시간 복잡도: O(1) (평균적인 경우)

---

3. 결론: 시간 차이

• list: 데이터가 많아질수록 탐색 시간이 선형적으로 증가(O(n)).예: 리스트에 1,000,000개의 요소가 있으면, 최악의 경우 1,000,000번의 비교가 필요.
• set: 데이터 크기와 관계없이 평균 O(1)로 탐색.예: 해시 충돌이 적다면, 1,000,000개의 데이터가 있어도 탐색은 한 번에 가능.

---

4. 추가적인 장점: set의 중복 제거

• set은 중복 요소를 자동으로 제거합니다.이로 인해 중복 데이터 확인과 저장이 동시에 이루어질 수 있어 코드 작성과 실행 효율이 향상됩니다.

내 생각

1. 중복 방문 여부를 배열로 관리할때는 list말고 set를 이용하자. 훨씬 빠르다.
2. 조건으로 범위를 제한할 때 중복된 범위가 없는지 다시 한 번 생각하자.