one Book a Day

후위, 중위순회로 전위순회 찾기. 후위순회의 마지막 순회가 루트노드인 것을 이용 그 루트노드를 기준으로 좌우로 찢을 수 있었다. 인덱싱을 위해 최초 인덱스로 부터 중위순회로 얻은 left,right값으로 트리를 좌우로 분할하면서도 인덱싱이 가능하게 설계. 두세번 코드해석해봤는데 아직도 혼자 설계하라면 할수있을까 싶다. import sys sys.setrecursionlimit(10**6) n = int(input()) in_order = list(map(int, input().split())) post_order = list(map(int, input().split())) pos = [0]*(n+1) for i in range(n): pos[in_order[i]] = i # 중위 순회로 부모노드의 위치에..

부분집합은 조합툴쓰면 너무 편하다.. 자모음 cnt해서 조건 만족하면 정답 리스트에 넣었다. import sys input = sys.stdin.readline from itertools import combinations L,C = map(int,input().split()) secret = list(input().split()) # 암호는 사전순 sorted되어있다. secret.sort() # 최소한개모음 두개자음 mom_char = ['a','e','i','o','u'] combs = list(combinations(secret,L)) ans = [] for chars in combs: mom_cnt=0 child_cnt=0 for char in chars: if char in mom_char: ..

DFS하니까 재귀에러나고 시간초과 메모리초과 가관이어서 BFS로 다시 풀었다. 구조는 똑같이 queue에 1을 넣고 1부터 위에서 아래로 탐색하며 parent값을 자식들에게 할당하는 방식. import sys input = sys.stdin.readline from collections import defaultdict,deque N = int(input()) graph = defaultdict(list) for _ in range(N-1): a,b = map(int,input().split()) graph[a].append(b) graph[b].append(a) queue = deque([1]) ans = {} check = [False for _ in range(N+1)] while queue: pa..

TCP/UDP Transport Layer End Point 간 신뢰성있는 데이터 전송을 담당하는 계층 신뢰성 : 데이터를 순차적, 안정적인 전달 전송 : 포트 번호에 해당하는 프로세스에 데이터를 전송 전송계층이 없다면? 데이터의 순차 전송 원활x 송진자가 전달하고자했던 데이터가 안가게됨(1,2,3 -> 2,1,3)으로 바뀜. Flow (흐름 문제) 원인 : 송수신자 간의 데이터 처리 속도 차이 // 수신자가 처리할수있는 데이터량을 초과 Congestion (혼잡 문제) 원인 : 네트워크의 데이터 처리 속도 (ex. 라우터) // Network 가 혼잡해서 데이터가 안오고 통신이안됨. 결과 : 데이터의 손실 발생. TCP(Transmission Control Protocol) 신뢰성있는 데이터 통신을 가..

항상 문자열에서 검사하고 중복 갯수세고 하는거 나오면 set()으로 목록 만들고 ord써서 반복문 돌릴수 있게 설계한다거나 char_count 배열에 갯수 저장해 넣고 뺄때 쓸 수 있게 설계. string ='' 두고 더하고 빼고 슬라이싱 인덱싱 하는 스킬 더 기를 것. 문자열로 DFS돌리는 문제 은근 나옴. 슬라이싱으로 두문자씩, 두숫자씩 묶거나 숫자문자면 중간중간 int써서 수식계산 및 비교 까지 가능. 진법변환까지는 아직 문제못봄. from sys import stdin input = stdin.readline def dfs(depth, string): global N, cnt if depth == N: # print(string) cnt += 1 return # 종류별로 알파뱃 검사(깊이마다) f..

강의실의 갯수N = queue의 방의 갯수. 최소 heap을 사용해 가장 빨리 돌아오는 수업 종료시간보다 시작해야하는 수업이 빠르면 방 하나 증가 적으면 끝난수업빼고 새수업 넣는다. 즉 최대 필요한 room의갯수가 계속유지된다. 최솟값, 최댓값을 계속 뽑아내야 할때는 heapq.. 잘 생각해보자 import heapq import sys N = int(input()) timeTable = [list(map(int,sys.stdin.readline().split())) for _ in range(N)] timeTable.sort(key=lambda x: x[0]) queue = [] heapq.heappush(queue,timeTable[0][1]) for i in range(1,N): # last_tim..

싸이클을 만들 수 있느냐는 문제 조건은 1. 이전칸으로 가지 않을 것 2. 이전칸을 제외하고 방문했던 지점을 만나면 싸이클이 존재. N,M=map(int,input().split()) matrix=[list(map(str,input()))for _ in range(N)] visited = [[False]*M for _ in range(N)] dy=[0,0,1,-1] dx=[1,-1,0,0] # 싸이클의 조건 # 1. 바로 이전 칸으로 가지 말 것( 이전 좌표 가억해두고 같으면 이동하지말것.) # 2. 그럼에도 불구하고 갔던 곳(visited true)를 만나면 싸이클이 존재하므로 True를 반환할것. def dfs(x,y,px,py,ball): if visited[x][y]==True: return Tr..

분할정복 대표적인 문제이다. 연산 갯수를 줄이기 위해 반으로 쪼개고 쪼개 A*1로 쪼갠다음 그 결과값을 양쪽에서 곱해주면서 조합해준다. 분할 : 곱해야 하는 갯수 B를 2로 나누어 주며 분할한다. 정복 : A*1의 정복을 통해 계산한다. 조합 : A*A / (A*A) * (A*A) / 이런식으로 결과값을 제곱하면서 올라와 모든 재귀가 끝나면 연산이 끝난다. import sys input = sys.stdin.readline A, B, C = map(int, input().split(' ')) # 정복 def conq(length): # 정복 : length가 1이 되면 A를 반환하겠다.(최소단위 연산의 정복) if length == 1: return A %C # 짝수면 좌우로 찢고 if length % ..

벽을 뚫는다 = 이동시 비용이 든다. = 가중치 있는 그래프 가중치가 0 과 1로 이루어진 그래프 탐색으로 맨앞 요소에 가중치 누적요소 cnt를 넣어 가중치가 낮은 길로 target을 찾아가는 bfs를 그리면 된다. heap을 이용해 낮은가중치탐색을 하는방법과 deque을 이용해 가중치가0인 노드이동에 대해 appendleft를 해주는 방법도 있다. 여튼 먼저 탐색해준다는게 핵심. import sys input = sys.stdin.readline from heapq import heappush, heappop m, n = map(int, input().split()) dx = [1, -1, 0, 0] dy = [0, 0, -1, 1] maze = [] visited = [[0] * m for i in ..

다익스트라의 정석.(단방향) import sys input = sys.stdin.readline from collections import defaultdict from heapq import heappush,heappop def dijkstra(start): global min_dists heap = [] min_dists = [float('INF')]*(V+1) min_dists[start] = 0 heappush(heap,[min_dists[start],start]) while heap: cur_dists,cur_node = heappop(heap) if cur_dists > min_dists[cur_node]: continue for next_dists,next_node in graph[cur_n..