[TIL] 2024년 7월 16일 오늘의 TIL

08:30 ~ 12:00	이진 탐색 트리
14:00 ~ 15:00	CSAPP 퀴즈
16:00 ~ 24:00	알고리즘 풀이

 
 
 
 
1. 이진 검색 트리 https://www.acmicpc.net/problem/5639

import sys
input = sys.stdin.readline
#recursion error 방지
sys.setrecursionlimit(10**9) # python3 으로 꼭 바꾸기


# li 안에 있는 값을 비교해본다
# 현재 나보다 작은 애는 왼쪽 / 크면 오른쪾
# 재귀함수를 만들어보자 (종료조건, 콜스택)

def postorder(arr,result):
    if len(arr) == 0:
        return

    left_arr, right_arr = [], []
    root = arr[0]
    for i in range(1, len(arr)):
        if arr[i] > root:
            left_arr = arr[1:i]
            right_arr = arr[i:]
            break
    else:
        left_arr = arr[1:]

    postorder(left_arr, result)
    postorder(right_arr, result)
    result.append(root)

#  이진 검색 트리 입력받기
arr = []
# 입력 끝내기
while True:
    try:
        x = int(input().strip())
        arr.append(x)
    except:
        break

result = []
postorder(arr, result)
print(*result, sep='\n')

몇 시간 만에 풀었는지는 비밀... 호호..  일단 입력값이 노드의 개수도 안 알려주고 그냥 막 넣어야 해서 그거 처리하는 while문 만드는 것부터 사실 처음 해봤다. 그리고 sep=" "를 쓰면 배열 안의 인덱스 값 하나하나에 대해 " " 안의 값으로 처리해 준다
이 문제를 끙끙댔던 가장 큰 이유는 바로 postorder() 안의 For else 구문이다. 
이건....... 다음 포스팅에 계쏙 )).. 
아무튼 이렇게 해결해 냈다. 
 
 
 
2. 최소 스패닝 트리 https://www.acmicpc.net/problem/1197

# 최소 스패닝(신장) 트리
# https://www.acmicpc.net/problem/1197

# 크루스칼 알고리즘????

import sys

input = sys.stdin.readline

v, e = map(int, input().split())
parent = [0] * (v+1) # 부모 테이블 초기화
for i in range(1, v+1): # 각 정점의 부모를 자신으로 설정
    parent[i] = i

def find_parent(parent, x):
    if parent[x] != x: # x가 자기 자신이 아니라면
        parent[x] = find_parent(parent, parent[x]) # 해당 x로 다시 함수 호출(재귀)
    return parent[x]

def union_parent(parent, a, b): # 두 원소가 속한 집합을 합침
    a = find_parent(parent, a)
    b = find_parent(parent, b)
    if a < b:
        parent[b] = a # b의 부모를 a가 한다.
    else:
        parent[a] = b # a의 부모를 b가 한다.


edges = []
total_cost = 0

for _ in range(e):
    a, b, cost = map(int, input().split())
    edges.append((cost, a, b))

    edges.sort()

for edge in edges:
    cost, a, b = edge
    if find_parent(parent, a) != find_parent(parent, b):
        union_parent(parent, a, b)
        total_cost += cost

print(total_cost)

 
 
3. 화요일 퀴즈에 대하여
오늘도 어김없이 화요일 퀴즈를 봤다. 
다른 것들은 다 무난하게 썼던 것 같은데 마지막 문제인 b-tree를 사용하지 않았으면 어떻게 차이가 있는지? 생각해 본 적이 없어서 막 지어내서 썼다 ㅋㅌㅋㅌㅋ 공부는 꼼꼼하게 하자.라는 교훈을 얻게 된 하루였다. 이상. 끝.

점메 : 비빔밥