튜터님 강의
다 기억해두자고
트리란 무엇인가??
- 1대 n의 관계를 가지고 있어야 한다.
- 순서가 없음.
- 부모와 자식 관계가 있다.
- 서브 트리 = 트리중에서 다시 루트를 잡아서 보는 방법
- 리프 노드 = 자식이 없는 노드
- 자손 노드 = 자신 밑에 있는 모든 자식 노드
완전 이진트리 = 1,2,3,4,5 노드가 순서대로 있을 때
그냥 이진트리는 1,2,5,6,7이라도 상관없다.
트리 순회 방법
전위 순회
위에서 부터 아래로
중위 순회
제일 좌 또는 우측 부터 진행
후위 순회
최하위 부터 최상위 까지
이진 탐색 트리
왼쪽은 부모보다 작은 값 오른 쪽은 부모보다 큰 값
여기서 중위 순회를 하면 내림차순 오름차순이 된다.
힙(heap)
키값이 큰 노드나 작은 노드를 찾는 법
키값에 중복이 있으면 안됨!
heap이 아님 그냥 이진트리임
분할 정복?
서브트리 문제 풀기
처음에 풀었던 방법과 너무 달랐다...
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()
'AI 코딩 교육 TIL' 카테고리의 다른 글
2024-03-18 AI 코딩 TIL (3) | 2024.03.18 |
---|---|
2024 -03-15 AI 코딩 TIL (4) | 2024.03.15 |
2024-03-13 AI 코딩 TIL (0) | 2024.03.13 |
2024-03-12 AI 코딩 TIL (0) | 2024.03.12 |
2024-03-11 AI 코딩 TIL (0) | 2024.03.11 |