one Book a Day

골드2여서 시간 메모리 빡빡할까봐 쫄았는데 그냥 무지성 코드로 통과.. 슬라이스 정렬,중앙값찾기.,count로 출력숫자 제어. import sys input = sys.stdin.readline for test in range(int(input())): M = int(input()) seqs = [] for i in range(M//10+1): seqs.extend(list(map(int,input().split()))) print(M//2+1) print(seqs[0], end=" ") if M !=1: cnt=1 for i in range(2,M,2): print(sorted(seqs[:i+1])[(i+1)//2], end=" ") cnt+=1 if cnt==10: print() cnt=0 else:..

최소거리 배열 다 구해서 전부 더해준 다음 합 미니멈인 방번호 출력 다익스트라로 간단하게 풀었다. import sys input = sys.stdin.readline from heapq import heappop, heappush from collections import defaultdict # 각 친구들 위치에서 모든 방에 대해 최소거리 배열 출력. def dijkstra(start): global dp_dists dp_dists = [float('inf')] * (N + 1) heap = [] dp_dists[start] = 0 heappush(heap, [dp_dists[start], start]) while heap: cur_dist, cur_node = heappop(heap) if dp_di..

출발지, 도착지에 따라. BFS로 거리구하면 끝. import sys input = sys.stdin.readline from collections import defaultdict,deque def Distance(a,b): queue = deque() queue.append(a) visited = [False]*(N+1) visited[a] = True target_dist = [0]*(N+1) while queue: v = queue.popleft() if v==b: print(target_dist[v]) return for next,dist in graph[v]: if not visited[next]: queue.append(next) visited[next] = True target_dist[n..

문자열 뒤집은 key찾아서 key길이와 중앙값 출력. import sys input = sys.stdin.readline N = int(input()) files = [input().rstrip() for _ in range(N)] for i in range(N-1): for j in range(i,N): if files[i][::-1] == files[j]: print(len(files[i]), files[i][len(files[i])//2]) exit()

다익스트라 알고리즘 최단경로를 찾는 알고리즘 중 양의 가중치만이 있는 그래프만을 취급 특정 위치에서 도착위치의 최단경로를 찾는 알고리즘(모든경로의 최단경로를 구하지는 않는다. 그리디하게 정점을 선택해 방문. 선택한 정점의 인접정점 중 방문되지 않은 것들에 대해 최단경로를 구해가며 도착지점에 도달. 배열에 각각 노드에 접근 시 가중치 합을 저장하며 지나간다. 0번 노드에서 출발해서 방문하지 않은 인접한 노드 중에 가중치가 가장 적은 노드에 대해 방문한다. 현재 그리디하게 선택한 경로의 가중치 합이 나중에 최단 경로가 아닐 수도 있으니 배열에 가중치의 합들을 저장하며 지나간다 1번 노드에서 인접한 노드 중 가중치가 제일 작은것은 4번이다. 이 때, 비교해봐야하는 것은 0번 노드에서 4번노드로 가는 경로 중 ..

실질적으로 별찍기(프렉탈 분할정복) 을 접한건 두번째다 첫번째는 감이 잘 안왔는데 이제는 슬슬 감이온다. 1. 입력값 2. 최소단위로 분할 3. 최소문제 해결 4. 더 큰문제 정복 5. 조합 정복시 그림이 잘 안그려질때는 실질적으로 뭐가 몇개 늘어났는지. 최소단위가 몇개 늘어나는지 잘 살펴보면 된다. 그리고 최소단위를 반복, 순회하면서 반복 덧셈, 곱셈을통해 확장시켜나가면 된다. 이 문제같은 경우 가장 작은 삼각형이 다음 차수에 밑에 2개 더 붙고 그다음은 그 큰 3개의 삼각형이 밑에 2개씩 더붙는다. 즉 이전 그림의 두배씩 아래쪽 배열에 추가된다고 생각하면 된다. 또 처음 들어갔던 배열도 " " 빈칸을 추가해줘야하는데 얼마나 추가해주냐면 실질적으로 늘어나는 3칸을 세어 3칸 -> 6칸 -> 12칸 즉 ..

10분 테코톡 쿨라임님 손너잘님 발표자료 참고했습니다. HTTP1.1&HTTP2&QUIC HTTP는 Application Layer의 프로토콜. HTTP는 신뢰성있는 연결만 해줄 수 있다면 전송프로토콜은 TCP/UDP 뭘써도 상관없다고함. TCP(Transmission Control Protocol) connection을 수립하기 전에 신뢰성 있는 Connection을 위해 3 Way Handshake를 함. 3 악수를 통해 연결이 수립되면 데이터를 전송함. 전송하면 잘 받았다고 응답을 보냄(유실되면 다시 데이터 요청) 제어, 핸드셰이커, 등등신뢰성 구축에 신경을 많이씀. UDP(User Datagram Protocol) 신뢰성 x 받는걸 신경을 안쓰고 그냥 보냄. TCP vs UDP HTTP 0.9 요..

visited 뒤에 [nx][ny]안붙힌거 찾느라 1시간 걸렸다. import sys input = sys.stdin.readline from collections import deque def BFS(x,y,h): global result queue = deque() queue.append([x,y]) dx = [0,0,1,-1] dy = [1,-1,0,0] out_rain = False cnt = 1 visited[x][y] = True while queue: x,y = queue.popleft() for i in range(4): nx = x+dx[i] ny = y+dy[i] if 0

JavaScript Object Notation. Javascript 객체 문법을 따르는 문자 기반의 데이터 포맷 객체 리터럴과 매우 흡사하지만 순수한 텍스트로 구성된 데이터 형식이다. 데이터를 교환하거나 저장하기 위한 문법(XML과 같은용도) 일반 자바스크립트의 객체처럼 원하는 만큼 중첩시켜서 사용할 수도 있다. JSON 형식에서는 null, number, string, array, object, boolean을 사용할 수 있다. JSON 객체를 .json 확장자를 가진 단순 텍스트 파일에 저장할 수 있으며 MIME 타입은 application/json 이다. JSON은 순수히 데이터 포맷으로 오직 프로퍼티만 담을 수 있다. 메서드는 담을 수 없다 JSON은 문자열과 프로퍼티의 이름 작성시 큰 따옴표만..

최소 신장 트리(MST, 크루스칼, 프림 알고리즘) 최소 신장 트리(Minnimum Spanning Tree) spanning Tree 중에서 사용된 간선들의 가중치 합이 최소인 트리. 신장 트리(Spanning Tree)란 그래프 내의 모든 정점을 포함하는 트리 최소 연결 : 간선의 수가 가장 적다. n개의 정점을 가지는 그래프의 최소 간선의 수는 (n-1)개 이고, (n-1)개의 간선으로 연결 되어이으면 필연적으로 트리형태가 되고 이게 신장 트리이다. 즉 그래프에서 일부 간선을 선택해서 만든 트리. DFS, BFS을 이용하여 그래프에서 신장 트리를 찾을 수 있다. 탐색 도중에 사용된 간선만 모으면 만들 수 있다. 하나의 그래프에는 많은 신장 트리가 존재할 수 있다. Spanning Tree는 트리의 ..