시나위

https://www.acmicpc.net/problem/1068 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net import sys; input = sys.stdin.readline N = int(input()) node_parent = [-1 for _ in range(N)] node_son = [[] for _ in range(N)] root = 0 for son, parent in enumerate(map(int, input().split())): if parent == -1: root = son..

https://www.acmicpc.net/problem/6593 6593번: 상범 빌딩 당신은 상범 빌딩에 갇히고 말았다. 여기서 탈출하는 가장 빠른 길은 무엇일까? 상범 빌딩은 각 변의 길이가 1인 정육면체(단위 정육면체)로 이루어져있다. 각 정육면체는 금으로 이루어져 있어 www.acmicpc.net import sys;input = sys.stdin.readline from collections import deque # 탐색 def bfs(start, end, size, building): q = deque() q.append(start) visit = [[[0 for k in range(size[2] + 2)] for j in range(size[1] + 2)] for i in range(si..

https://programmers.co.kr/learn/courses/30/lessons/42628 코딩테스트 연습 - 이중우선순위큐 programmers.co.kr from heapq import heappush, heappop def solution(operations): answer = [0, 0] min_h, max_h = [], [] number_in_heap = dict() for op in operations: if op[0] == 'I': # 숫자 삽입 _, num = op.split() num = int(num) heappush(min_h, num) heappush(max_h, -num) if not number_in_heap.get(num): number_in_heap[num] = 0..

https://programmers.co.kr/learn/courses/30/lessons/42627 코딩테스트 연습 - 디스크 컨트롤러 하드디스크는 한 번에 하나의 작업만 수행할 수 있습니다. 디스크 컨트롤러를 구현하는 방법은 여러 가지가 있습니다. 가장 일반적인 방법은 요청이 들어온 순서대로 처리하는 것입니다. 예를 programmers.co.kr from heapq import heappush, heappop def solution(jobs): # jobs가 정렬이 안되어있음 jobs.sort(key=lambda x: (x[0], x[1])) # 0 변수 선언 min_h = [] jobs_idx = 0 cur = 0 s, rt = None, None running = False answer_list..

https://programmers.co.kr/learn/courses/30/lessons/42579?language=python3 코딩테스트 연습 - 베스트앨범 스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다. 속한 노래가 programmers.co.kr def solution(genres, plays): # 0 해시 생성 genre_set = set() genre_dict = dict() genre_play_dict = dict() # 1 입력 for i in range(len(genres)): if genres[i] not in genre_set: genre_set.add(ge..

https://www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 지난번 풀었던 문제인데 재채점된 이후에 값이 틀리게 나와서 다시 풀게되었다. import sys; input = sys.stdin.readline from heapq import heappop, heappush def dijkstra(start, end, num_of_nodes): INF = 200_000 * 1_000 * 2 q = [] q.appen..

https://www.acmicpc.net/problem/11444 11444번: 피보나치 수 6 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net #include #include using namespace std; typedef long long ll; typedef vector matrix; #define DIVMOD 1000000007; matrix operator *(matrix a, matrix b) { ll i, j, k; matrix ret(2, vector(2)); for (i = 0; i < a.size(); ++i) { for (j = 0; j < a.size(); ++j) { for (k = 0; ..

https://www.acmicpc.net/problem/10830 10830번: 행렬 제곱 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. www.acmicpc.net 오랜만에 분할정복 문제이다. dp를 사용하지 않아서 알고리즘 자체는 어렵지 않는데 c++사용할때 조금 문제가 있었다. #include #include using namespace std; void copy(int* dest, const int* origin, int N) { // N: size of dest(same as size of origin) for (int i = 0; i < N; ++i) { for ..

https://www.acmicpc.net/problem/1966 1966번: 프린터 큐 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 www.acmicpc.net #define _CRT_SECURE_NO_WARNINGS #include #include int main() { int tc, N, M, i, j, cnt, pos; scanf("%d", &tc); for (i = 0; i < tc; i++) { // initialize cnt = 0; int num[10] = { 0, }; // num of objects scanf("%d %d", &N, &M); ..

https://www.acmicpc.net/problem/18258 18258번: 큐 2 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 2,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net #define _CRT_SECURE_NO_WARNINGS #include #include # define FAIL 99999999 typedef struct _Node { int data; struct _Node* next; } Node; typedef struct _Queue { Node* front; Node* rear; int size; } Queue; void in..