시나위

https://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 그냥 대충 보면 완전탐색인것처럼 보이지만 N=100000이므로 DP 문제이다. 2행의 배열이 주어졌을때 구할수 있는 최대값을 찾는 문제이다. T = int(input()) for tc in range(T): N = int(input()) sticker = [list(map(int, input().split())) for _ in range(2)] memo = [[0 for _ in ra..

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..

이 게시글을 쓴 이유는 하나다. 강의가 한번 끊기면 공부할 마음도 같이 끊기기 때문에 공부에 집중하기 위해서. 특정 사이트에서 강의를 보고 있었는데 아는 내용도 어느정도 있어 빠르게 넘기려고 했다. 하지만 네트워크의 문제인지 2배속으로 재생하거나 10초 뒤로 몇번 넘기면 자주 끊겼다. 차라리 전체파일을 다운 받아서 보는게 낫다고 생각했고, 공유할 목적이 아닌 혼자만 볼 생각이니 파일을 합쳐도 되지 않을까 해서 바로 실행에 옮겼다. 사용환경 python 3.7.9 첫번째로 파일을 다운로드 할수 있는지 부터 알아보았다. 내가 사용하는 사이트에선 강의를 파일을 일정 시간으로 나눠서 보낸다. (대부분 스트리밍이 그럴것이라고 생각한다) 이 모든 파일을 합치면 전체 비디오를 만들수 있으므로 다운로드 할수 있는지도 ..

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 ..