윤필도 / 7월4주차 / 2문제

[happypildo]

하노이 탑

문제 설명

• 잘 알려진 하노이 탑 문제, 판을 옮긴 횟수와 경로를 출력하는 문제이다.

알고리즘 분류

• 재귀 함수

어려웠던 점

• 수업에 배운 재귀 함수를 공부해보고자 풀어봤는데, 기저 조건은 찾기 쉬웠지만 유도 부분을 고민하는데 시간을 꽤 쓴 것 같음

시간 복잡도

• O(2^n) (여기서, n은 판 개수)

접근 방식

• 봉이 3개 있고 각각을 1, 2, 3번이라 한다.
• 간단하게, 두 개의 판을 1번에서 3번으로 옮긴다고 하면 문제를 다음과 같이 쪼갤 수 있음
  • "한 개(맨 위)의 판을 1번에서 2번으로 옮기고" + "나머지 판(맨 아래)을 1번에서 3번으로 옮기고" + "한 개(맨 위)의 판을 2번에서 3번으로 옮기기"
• 이 방식을 일반화해서 풀었음

새로 알게 된 점

• 재귀는 그림 그리면서 풀면 직관을 얻을 수 있는 것 같다.

1일차 과제 1번

문제 설명

• 위치가 고정된 숫자 N개가 주어지고, 연산자 N-1개가 주어질 때 가능한 연산 중 가장 작은 값과 큰 값의 차를 구하시오.

알고리즘 분류

• 완전 탐색

어려웠던 점

• 완전 탐색에서 주의해야 할 시간 복잡도를 해결하는 것이 어려웠음

시간 복잡도

• memoization을 활용했기에 어떻게 계산해야할지 모르겠읍니다.

접근 방식

• 연산자의 가능한 조합 수를 permutation 형태로 찾고,
• 각 계산 결과를 모아서 최대와 최소를 구함
  • 연산자가 만약 [+, +, +, +, -]가 주어지게 되면 permuation을 단순하게 구하면 시간 초과가 발생 (combination은 순서가 없어서 안 됨)
  • 따라서 memoization 기법을 통해 중복된 연산은 구하지 않게 함

새로 알게 된 점

• Memoization을 dictionary로 구현하면 편하다.

[RomanticBear]

메모이제이션 방법을 사용해본적이 없는데 하노이탑 문제로 복습 겸 사용해겠습니다 ╰(°▽°)╯

[ramge132]

1. 하노이의 탑

원판이 20개 초과라면 다이렉트로 출력 갯수 꽂는게 인상적임

2. 사칙연산

몇 가지 개선할 수 있는 부분이 보여서 공유함.

시간복잡도

현재 코드에서, 연산자 수 m에 대한 모든 순열을 생성하고, 각각에 대해 n-1번의 연산을 수행하기 때문에 팩토리얼 시간 복잡도를 가짐

즉, 시간 복잡도가 O(m! * n)로, 연산자 수(m)가 늘어날수록 성능 저하가 우려됨.

제안

이진 트리를 순회하면서 계산을 수행하는 방식이 시간 복잡도가 O(N)으로 효율적.

이진 트리 사칙연산 코드:

def evaluate_expression_tree(node):
    # leaf 노드인 경우 (정수 값)
    if isinstance(tree[node], int):
        return tree[node]

    # internal 노드인 경우 (연산자)
    left = evaluate_expression_tree(tree[node][1])
    right = evaluate_expression_tree(tree[node][2])

    if tree[node][0] == '+':
        return left + right
    elif tree[node][0] == '-':
        return left - right
    elif tree[node][0] == '*':
        return left * right
    elif tree[node][0] == '/':
        return left / right

# 총 10개의 테스트 케이스를 처리
for t in range(1, 11):
    N = int(input().strip())  # 정점의 개수 N 입력
    tree = {}  # 트리를 저장할 딕셔너리 생성

    # N개의 줄에 걸쳐 각 정점의 정보를 입력받음
    for _ in range(N):
        node_info = input().strip().split()
        node_id = int(node_info[0])  # 정점 번호

        if len(node_info) == 2:
            # leaf 노드인 경우
            tree[node_id] = int(node_info[1])
        else:
            # internal 노드인 경우
            operator = node_info[1]
            left_child = int(node_info[2])
            right_child = int(node_info[3])
            tree[node_id] = (operator, left_child, right_child)

    # 루트 노드 (1)부터 시작하여 식을 평가한 결과를 얻음
    result = int(evaluate_expression_tree(1))
    # 결과 출력
    print(f"#{t} {result}")

[happypildo]

피드백 감사합니다~~!!

시간 복잡도 측면에서 손해를 많이 보는 것 같네요...

추가적으로는 제 방식으로 하면 공간 복잡도 많이 잡아 먹게 되더라고요!

피드백 주신대로 다음 번에는 "조합 만들고 다 계산" 보다는 "조합 만들면서 계산"의 개념으로 가봐야겠네요.

감사합니다~