2024-03-14 AI 코딩 TIL

튜터님 강의

 

다 기억해두자고

트리란 무엇인가??

1. 1대 n의 관계를 가지고 있어야 한다.
2. 순서가 없음.
3. 부모와 자식 관계가 있다.
4. 서브 트리  = 트리중에서 다시 루트를 잡아서 보는 방법
5. 리프 노드 = 자식이 없는 노드
6. 자손 노드 = 자신 밑에 있는 모든 자식 노드 

 

완전 이진트리 = 1,2,3,4,5 노드가 순서대로 있을 때

그냥 이진트리는 1,2,5,6,7이라도 상관없다.

트리 순회 방법

전위 순회
위에서 부터 아래로

중위 순회
제일 좌 또는 우측 부터 진행

후위 순회
최하위 부터 최상위 까지

 

이진 탐색 트리

왼쪽은 부모보다 작은 값 오른 쪽은 부모보다 큰 값

여기서 중위 순회를 하면 내림차순 오름차순이 된다.

힙(heap)

키값이 큰 노드나 작은 노드를 찾는 법

키값에 중복이 있으면 안됨!

heap이 아님 그냥 이진트리임

분할 정복?

SW Expert Academy

SW Expert Academy

서브트리 문제 풀기

처음에 풀었던 방법과 너무 달랐다...

import sys
# from collections import deque

# 표준입력을 파일로 설정
sys.stdin = open("input.txt", "r")


def subtree(node):
    global result
    if node:
        result += 1
        subtree(graph[node][0])
        subtree(graph[node][1])


T = int(input())
# 여러개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
for test_case in range(1, T + 1):

    e, n = map(int, input().split())

    graph = [[0, 0] for _ in range(e + 2)]
    # x의 값을 리스트로 변경시켜준다.
    x = list(map(int, input().split()))
    # 홀수 번은 노드의 번호 짝수 번은 연결된 노드를 표시하니 2씩 증가하면서 그래프에 값을 넣어주면 됩니다.
    for i in range(0, len(x), 2):
        if graph[x[i]][0] == 0:
            graph[x[i]][0] = x[i+1]
        elif graph[x[i]][1] == 0:
            graph[x[i]][1] = x[i+1]

    result = 0

    subtree(n)
    print(f"#{test_case} {result}")


    # ------큐 설정 이건 이진 트리가 아니다 ㅋㅋ------
    # queue = deque()
    # # e = 노드 연결 횟수 (총 노드는 e+1개)
    # # n = 루트 노드로 선택 할 것 그 밑에 있는 값을 전부 세어보자
    # e, n = map(int, input().split())
    # # 총노드 갯수가 e+1개에다가 1번 부터 쓰고 싶으니깐 앞에 빈칸 합쳐서 e+2개를 만들어준다.
    # graph = [[] for _ in range(e+2)]
    # # x의 값을 리스트로 변경시켜준다.
    # x = list(map(int, input().split()))
    # # 홀수 번은 노드의 번호 짝수 번은 연결된 노드를 표시하니 2씩 증가하면서 그래프에 값을 넣어주면 됩니다.
    # for i in range(0, len(x), 2):
    #     graph[x[i]].append(x[i+1])
    # # 시작할 번호를 큐에 넣어준다.
    # queue.append(n)
    # # 본인을 포함 자식노드가 몇개가 있는지 횟수 탐색
    # counter = 0
    #
    # # 반복문 진행
    # while queue:
    #     # 큐안에 있는 값 꺼내기
    #     x = queue.popleft()
    #     # 꺼내면서 카운트 1증가
    #     counter += 1
    #     # 해당노드에 있는 번호 전부 큐에 넣기 이 문제의 특성상 되돌아가는 방향은 없기 때문에 방문 표시는 안해도 됩니다.
    #     for i in graph[x]:
    #         queue.append(i)
    # # 결과 출력
    # print(f"#{test_case} {counter}")

이진 트리중에서 한 노드를 집어서 그 노드를 포함한 자손노드의 갯수를 구하는 문제 입니다.

---

오늘의 문제 풀이

오늘은 정말 간발의 차이로 문제를 해결하지 못했다...
너무 아깝다...

비밀번호

처음에 문자를 돌린다는 것이 그냥 될 줄 알았는데 함수를 따로 써서 만들어야 한다는 것을 알게 되었고 다음은 16진수를 10진수로 변환하는 방법을 찾아 보았는데 간단하게 int(”16진수”,16)을 입력하면 10진수로 변환이 가능하다는 것을 알았습니다.

반대로 “0:x”.format(10진수 값)을 넣으면 16진수로도 변환이 가능합니다.

# Code
import sys

# 표준입력을 파일로 설정
sys.stdin = open("input.txt", "r")


# 문자 회전 시키는 함수
def text_rotate(text):
    one_text = text[0]
    remove_text = text[1:]
    sum_text = remove_text + one_text
    return sum_text


# 각 문자에 맞추어 16진수 비밀번호 만들기
def make_hex(text, num):
    # 16진수 받을 통
    text_list = []
    # 반복 제한 한 변이 돌면 끝
    n = 0
    # 반복 시작
    while n < num:
        # num글자 마다 때야 하니깐 num씩 증가 마지막은 num - 1만큼은 필요 없음
        for i in range(0, len(text) - num + 1, num):
            # 만든 번호가 저장되어 있지않다면 넣기
            if text[i:i + num] not in text_list:
                text_list.append(text[i:i + num])
        #  문자 돌리기
        text = text_rotate(text)
        # 한 칸씩 앞으로
        n += 1
    return text_list


T = int(input())
# 여러개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
for test_case in range(1, T + 1):
    # n // 4 해주면 글자수가 만들어짐
    n, k = map(int, input().split())
    # 문자 그대로 받아주기
    x = input()
    # 16진수를 10진수로 변환해서 옴겨 담기
    pass_word = []
    for i in make_hex(x, n // 4):
        pass_word.append(int(i, 16))
    # 10진수 정렬
    pass_word.sort(reverse=True)
    # 출력
    print(f"#{test_case} {pass_word[k-1]}")

못된 사탕 나누기

자꾸 런타임 오류가 나서 정말 막막했는데… 튜터님의 조언을 보고나서 문제를 찾아서 해결 할 수 있었습니다!!!
정말 한발 자국만 더 갔으면 됐었는디!!! 런타임 에러가 나는건 데이터 초과가 나서 그런것 이였습니다. 제곱하는 부분에 c를 나누어 주기만 해도 답을 찾을 수 있었습니다. 이 문제에서 해결 포인트는 a든 b든 둘 중 하나의 값을 먼저 찾는 것입니다. 왜냐하면 a와 b가 아무리 값을 서로 주고 받아도 결국 총 합은 a+b = c로 동일 하기 때문에 저는 a의 값을 먼저 찾는 방향으로 했습니다. 계속 반복 적인 수를 찾아 볼려고 공책에 써 본 결과  a의 값은 회차가 거듭 될 수록 a * ( 2 ^ k ) % 의 일반항을 보인다는 것을 찾았습니다. 간단하게 예제 문으로 보자면 a가 4 b가 9일 떄 합 인 c의 값은 13입니다. 여기서 a가 작으니 4+4 = 8 이 되고 다음은 8대 5니깐 5를 줘서 3이 됩니다. 그런데 여기서 a의 입장 만 보고 8에서 큰지 작은지 보지말고 다시 두배가 된다고 하면  16이 되는데 여기서 13을 나두고 나머지의 값은 3이 됩니다 그러면 앞에 계산했던 방법과 같은 3의 값을 찾을 수 있습니다. 결국 빼는 걸 생각하지 않고 두 배가 되는 방법만으로 a의 값을 찾을 수 있게 됩니다. 이제 구하는 법을 알았으니 2을 몇 번 곱했는지만 알면 되는데 여기서 이제 막혔었는데. 2^k 번 곱하게 될 때 그냥 제곱 그대로 놔두면 값이 초과되어 런타임 오류가 나는 것이 였습니다. 그래서 매번 곱할 때 c 이상의 값은 필요 없기 때문에 % c 를 해주면 필요한 값만 챙길 수 있는 것 입니다.

# Code

import sys

# 표준입력을 파일로 설정
sys.stdin = open("input.txt", "r")


def power(a, b, c):
    if b == 0:
        return 1

    x = power(a, b // 2, c)

    if b % 2 == 0:
        return (x * x) % c

    else:
        return (x * x * a) % c


T = int(input())
# 여러개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
for test_case in range(1, T + 1):

    a, b, k = map(int, input().split())

    c = a + b

    a = (a * power(2, k, c)) % c

    b = c - a

    print(f"#{test_case} {min(a, b)}")

# --------- 튜터님 기회!-------
# def division(n, _sum):
#     if n == 0:
#         return 1
#     result = division(n // 2, _sum)
#     result = (result * result) % _sum
#     if n % 2 == 1:
#         result = (result * 2) % _sum
#     return result
#
#
# def find(a, b, k):
#     _sum = a + b
#     result = (division(k, _sum) * a) % _sum
#     return min(result, _sum - result)
#
#
# if __name__ == "__main__":
#     t = int(input())
#     for i in range(t):
#         a, b, k = map(int, input().split())
#         print("#{} {}".format(i + 1, find(a, b, k)))


# T = int(input())
# # 여러개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
# for test_case in range(1, T + 1):
#
#     a, b, k = map(int, input().split())
#
#     c = a + b
#
#     a = (a * (2 ** k)) % c
#
#     b = c - a
#
#     print(f"#{test_case} {min(a, b)}")




    # -----시간 초과!-------
    # a, b, k = map(int, input().split())
    #
    # for _ in range(k):
    #     if a <= b:
    #         c = a
    #         a *= 2
    #         b -= c
    #     else:
    #         c = b
    #         b *= 2
    #         a -= c
    #
    # print(f"#{test_case} {min(a, b)}")

 

힙

뭘해도 시간 초과가 뜹니다…….
모르겠다.. 인터넷에 해답도 없고

- 와,,,, 이건 파이썬 만에 문제였는데 팀원분이 알려주셔서 알게 되었습니다!

   
위 사진과 같이 출력문을 한번에 모아서 해야지 시간 초과가 안 뜬다고 합니다.

반복문 안에 print도 시간은 많이 잡아 먹나 봅니다.

import heapq
import sys

# 표준입력을 파일로 설정
sys.stdin = open("input.txt", "r")

T = int(input())
# 여러개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
for test_case in range(1, T + 1):
    # 힙통
    heap = []
    # 출력 받아올 pop 밥통
    text = []
    # 실행 횟수
    n = int(input())
    # 반복문 실행
    for _ in range(n):
        # 넣는거면 1,2 두개로 들어오고 뺴는 거면 2 만 만들어옴
        a = list(map(int, input().split()))
        # 그러므로 글자수가 2개면 넣는 방향으로
        if len(a) > 1:
            heapq.heappush(heap, -a[1])
        #  글자수가 1개이면 빼는 방향으로
        else:
            # 그중에서도 힙통이 비면 뺄게 없으니 -1이라도 출력
            if len(heap) == 0:
                text.append(-1)
            else:
                # 출력할게 있으면 가장 큰 숫자 빼내기 (-로 넣고 빼고 -하면 큰값이 됩니다.)
                text.append(-heapq.heappop(heap))
    # 모아놓은 출력 상자 뽑아서 문자로 만들기
    t = " ".join(map(str, text))
    print(f"#{test_case} {t}")


# ---- 다른 방법 ---
# MAXN = 100000
#
# heap = [0] * MAXN
# heapCnt = 0
#
# def add(val):
#     global heapCnt
#     pivot = heapCnt
#     heap[heapCnt] = val
#     heapCnt += 1
#     while pivot > 0:
#         ppivot = pivot
#         pivot -= 1
#         pivot //= 2
#         if heap[pivot] < val:
#             heap[ppivot] = heap[pivot]
#             heap[pivot] = val
#         else:
#             return
#
# def pop():
#     global heapCnt
#     if heapCnt == 0:
#         return -1
#     val = heap[0]
#     heapCnt -= 1
#     heap[0] = heap[heapCnt]
#     pivot = 0
#     while True:
#         ppivot = pivot
#         pivot *= 2
#         pivot += 1
#         if pivot >= heapCnt:
#             break
#         elif pivot + 1 == heapCnt:
#             if heap[ppivot] > heap[pivot]:
#                 break
#             tmp = heap[ppivot]
#             heap[ppivot] = heap[pivot]
#             heap[pivot] = tmp
#             break
#         else:
#             if heap[pivot] < heap[pivot + 1]:
#                 pivot += 1
#             if heap[ppivot] > heap[pivot]:
#                 break
#             tmp = heap[pivot]
#             heap[pivot] = heap[ppivot]
#             heap[ppivot] = tmp
#     return val
#
# T = int(input())
# for tc in range(1, T + 1):
#     print('#' + str(tc), end=' ')
#     heapCnt = 0
#     N = int(input())
#     for _ in range(N):
#         act = list(map(int, input().split()))
#         if act[0] == 1:
#             num = act[1]
#             add(num)
#         else:
#             print(pop(), end=' ')
#     print()