2025-01월 Algoirthm

Baekjoon - 이진 트리(13325번)

 

이진트리의 성질을 고찰해 볼 수 있는 문제이다. 우선 문제에서 주어진 트리가 포화 이진 트리이기 때문에 특수한 조건들이 많이 성립한다.

 

1. 전체 노드의 개수

우선 트리의 높이가 주어질 때, 전체 트리의 노드 개수를 구할 수 있다. 이는 등비수열의 합과 관련 있는데 아래와 같은 예를 한번 보자.

root: 1개

1층: 2개

2층: 4개

3층: 8개

4층: 16개

5층: 32개

총 노드의 개수는 1+2+4+8+16+32이다. 이는 초항이 1이고 등비가 2인 수열의 6번째 까지 항의 합으로 1*2^6-1/(2-1) = 63이다. 일반화 하면 포화 이진 트리의 노드 개수는 트리의 높이를 k라고 할 때, 2^(k+1)-1이다.

 

2. 부모 노드와 자식 노드의 관계

포화 이진 트리이기 때문에 모든 부모 노드는 자식의 개수가 2개이다. 또한 부모 노드의 인덱스를 알면 자식 노드의 인덱스를 알 수 있고 자식 노드의 인덱스를 알면 부모 노드의 인덱스를 알 수 있다.

 

전체 코드

import sys

tree_height = int(sys.stdin.readline())
edge_weight = [0,0]+list(map(int, sys.stdin.readline().split()))
node_n = 2**(tree_height+1)-1

s = [1]

def dfs(s):
    t = s.pop()
    if t*2 > node_n:
        return edge_weight[t]

    n1 = t*2
    n2 = t*2+1
    l_s = dfs(s+[n1])
    r_s = dfs(s+[n2])

    acc_s = l_s
    if l_s > r_s:
        acc_s = l_s
        edge_weight[n2] += l_s-r_s
    elif l_s < r_s:
        acc_s = r_s
        edge_weight[n1] += r_s-l_s

    return acc_s + edge_weight[t]
dfs(s)
print(sum(edge_weight))

 

 

---

 

 

Baekjoon -나무탈출(15900번)

트리에서 리프 노드인지 판별하는게 중요한 문제

 

---

Baekjoon -보드게임?()

 

---

Baekjoon - 후위 표기법(1918번)

문제에서 초기에 설명한 방법으로 풀려다가 실패하고... 풀이를 참조하였다. 

연산의 우선순위는 아래와 같다. 

1. () 괄호 안에 둘러쌓인 연산 부터 수행한다.

2. *, / 연산을 +, - 보다 먼저 수행한다.

3. 왼쪽에 있는 연산을 오른쪽 연산 보다 먼저 수행한다.

 

처음 고안한 풀이 방법은 아래와 같다. 

1. *, / 연산에 대하여 () 괄호를 추가한다.

2. () 괄호로 둘러쌓인 연산에 대하여 먼저 수행한다.

3. 2번 연산의 결과와 남아 있는 문자 그리고 +, - 연산자에 대하여 연산을 수행한다.

 

---

Baekjoon - 빵집(3109번)

2차원 배열에서 행을 x로 할지 열을 x로 할지에 대한 것 - 결국 통일성이 중요함.

새로운 스택을 구성하고 재귀함수를 실행하기 전, visited를 업데이트 하는것의 의미 - 상관이 없는 이유

dictionary -> list로 변경함으로써 메모리를 절약하는 방법

 

---

Baekjoon - 저울(2437번) *** 

발상의 전환이 필요했던 문제.

그리디보다 DP의 개념과 더 유사했던 것 같은 문제

현재 W까지 만들 수 있었다면 1부터 W까지 만들 수 있는 것이고 다음 추의 무게 W`에 대하여 1부터 W까지 W`에 더한 값을 만들 수 있다는 개념이 중요했던 문제이다.

 

전체 코드

import sys

n = int(sys.stdin.readline())

w_l = sorted(list(map(int, sys.stdin.readline().split())))

### 1. 첫번째 접근 방법

# upper_limit = sum(w_l)

# dp = [0 for _ in range(upper_limit+1)]
# report = [0 for _ in range(upper_limit+1)]
# for i in range(n):
#     dp[0] = 1

# for w in w_l:
#     for j in range(upper_limit, w-1, -1):
#         dp[j] += dp[j-w]

# for i in range(upper_limit+1):
#     if dp[i] == 0:
#         print(i)
#         break



### 2. 풀이를 참고한 접근 방법

num_sum = 0
for w in w_l:
    if num_sum + 1 < w:
        print(num_sum +1)
        break
    num_sum += w
else:
    print(num_sum + 1)

---

Baekjoon - 트리의 높이와 너비(2250번) 

트리를 조회하는 순서가 중요했던 문제, 전위순회 후위순회 중위순회 등과 연계 될 수도...

변수를 사용하던 것을 그대로 사용하는것과 새로 만드는 것의 차이가 중요했던 문제

전체 코드

import sys

n_num = int(sys.stdin.readline())

root = n_num*(n_num+1)/2
tree = {}
for _ in range(n_num):
    temp = list(map(int, sys.stdin.readline().split()))
    p_n = temp[0]
    c_l = temp[1:]
    tree[p_n] = c_l
    if c_l[0] != -1:
        root -= c_l[0]
    if c_l[1] != -1:
        root -= c_l[1]

s = [root]
col = {}
depth_num = {}
def dfs(s, extra, depth):
    t = s.pop()
    l_n, r_n = tree[t]

    cur_num_l = 0
    if l_n != -1:
        cur_num_l = dfs(s+[l_n], extra, depth+1)
    col[t] = cur_num_l +1 + extra
    if depth not in depth_num:
        depth_num[depth] = [col[t]]
    else:
        depth_num[depth].append(col[t])

    cur_num_r = 0
    if r_n != -1:
        cur_num_r = dfs(s+[r_n], extra + cur_num_l+1, depth+1)
    return cur_num_l +1  + cur_num_r

dfs(s, 0, 1)

final = []
for d in depth_num:
    if len(depth_num[d]) >1:
        final.append([max(depth_num[d])-min(depth_num[d])+1,d])
if len(final) != 0:
    answer = sorted(final, key = lambda x : [-x[0], x[1]])[0]
    print(answer[1], answer[0])
else:
    print(1, 1)