난쟁이 개발자

[Gold IV] 이중 우선순위 큐 - 7662문제 링크성능 요약메모리: 352484 KB, 시간: 3144 ms분류자료 구조, 우선순위 큐, 트리를 사용한 집합과 맵제출 일자2025년 1월 21일 14:58:54문제 설명이중 우선순위 큐(dual priority queue)는 전형적인 우선순위 큐처럼 데이터를 삽입, 삭제할 수 있는 자료 구조이다. 전형적인 큐와의 차이점은 데이터를 삭제할 때 연산(operation) 명령에 따라 우선순위가 가장 높은 데이터 또는 가장 낮은 데이터 중 하나를 삭제하는 점이다. 이중 우선순위 큐를 위해선 두 가지 연산이 사용되는데, 하나는 데이터를 삽입하는 연산이고 다른 하나는 데이터를 삭제하는 연산이다. 데이터를 삭제하는 연산은 또 두 가지로 구분되는데 하나는 우선순위가..

[Gold V] 와드 - 23747문제 링크성능 요약메모리: 174512 KB, 시간: 420 ms분류너비 우선 탐색, 그래프 이론, 그래프 탐색, 구현, 시뮬레이션제출 일자2025년 1월 21일 13:59:51문제 설명한별이는 출근하던 도중 이세계 대환장 버스에 치였다.그림 B.1: 이세계 대환장 버스그림 B.2: 출근하는 한별이올해 휴가를 전부 써 버려 당장 판교로 돌아가야 하는 한별이는 돌아가기 위한 방법을 어떻게든 찾아보기 위해 이세계를 돌아다녀 보려고 한다.이세계는 R×C$R\times C$의 격자로 되어 있다. 지금은 밤이어서 한별이는 자신이 위치한 칸 및 그 칸에서 위, 아래, 왼쪽 또는 오른쪽으로 인접한 칸만을 볼 수 있지만, 와드를 설치하면 조금 더 넓은 영역의 시야를 확보할 수 있다. ..

[Silver I] 양팔저울 - 17610문제 링크성능 요약메모리: 206480 KB, 시간: 220 ms분류브루트포스 알고리즘제출 일자2025년 1월 21일 12:11:30문제 설명무게가 서로 다른 k개의 추와 빈 그릇이 있다. 모든 추의 무게는 정수이고, 그릇의 무게는 0으로 간주한다. 양팔저울을 한 번만 이용하여 원하는 무게의 물을 그릇에 담고자 한다. 주어진 모든 추 무게의 합을 S라 하자. 예를 들어, 추가 3개이고 그 무게가 각각 {1, 2, 6}이면, S = 9이고, 양팔 저울을 한번만 이용하여 1부터 S사이 모든 정수에 대응하는 물을 다음과 같이 그릇에 담을 수 있다. 여기서, X는 그릇에 담는 물의 무게를 나타내고, □는 그릇을 나타낸다.X123456789 □:1□:2□:(1+2)(□+2..

[Gold III] ACM Craft - 1005문제 링크성능 요약메모리: 142612 KB, 시간: 636 ms분류방향 비순환 그래프, 다이나믹 프로그래밍, 그래프 이론, 위상 정렬제출 일자2025년 1월 20일 03:58:34문제 설명서기 2012년! 드디어 2년간 수많은 국민들을 기다리게 한 게임 ACM Craft (Association of Construction Manager Craft)가 발매되었다.이 게임은 지금까지 나온 게임들과는 다르게 ACM크래프트는 다이나믹한 게임 진행을 위해 건물을 짓는 순서가 정해져 있지 않다. 즉, 첫 번째 게임과 두 번째 게임이 건물을 짓는 순서가 다를 수도 있다. 매 게임시작 시 건물을 짓는 순서가 주어진다. 또한 모든 건물은 각각 건설을 시작하여 완성이 될 ..

[Gold IV] 사이클 게임 - 20040문제 링크성능 요약메모리: 115452 KB, 시간: 352 ms분류자료 구조, 분리 집합제출 일자2025년 1월 20일 02:34:33문제 설명사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한 번호가 부여된 평면 상의 점 n 개가 주어지며, 이 중 어느 세 점도 일직선 위에 놓이지 않는다. 매 차례 마다 플레이어는 두 점을 선택해서 이를 연결하는 선분을 긋는데, 이전에 그린 선분을 다시 그을 수는 없지만 이미 그린 다른 선분과 교차하는 것은 가능하다. 게임을 진행하다가 처음으로 사이클을 완성하는 순간 게임이 종료된다...

1. Numpy 불러오기import numpy as np2. Array 생성# 1차원 배열arr1 = np.array([1, 2, 3])# 2차원 배열arr2 = np.array([[1,2,3], [4,5,6]])# 3차원 배열arr3 = np.array([[[1,2,3], [4,5,6]], [[7,8,9], [10,11,12]], [[-1,-2,-3], [-4,-5,-6]]])# 배열 초기화zeros = np.zeros((2, 3)) # [[0. 0. 0.], [0. 0. 0.]]ones = np...

[Gold III] 최소비용 구하기 2 - 11779문제 링크성능 요약메모리: 122568 KB, 시간: 256 ms분류데이크스트라, 그래프 이론, 최단 경로제출 일자2025년 1월 14일 04:30:49문제 설명n(1≤n≤1,000)개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 m(1≤m≤100,000)개의 버스가 있다. 우리는 A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화 시키려고 한다. 그러면 A번째 도시에서 B번째 도시 까지 가는데 드는 최소비용과 경로를 출력하여라. 항상 시작점에서 도착점으로의 경로가 존재한다.입력첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m..

[Gold IV] 팰린드롬? - 10942문제 링크성능 요약메모리: 153904 KB, 시간: 552 ms분류다이나믹 프로그래밍제출 일자2025년 1월 12일 02:51:57문제 설명명우는 홍준이와 함께 팰린드롬 놀이를 해보려고 한다.먼저, 홍준이는 자연수 N개를 칠판에 적는다. 그 다음, 명우에게 질문을 총 M번 한다.각 질문은 두 정수 S와 E(1 ≤ S ≤ E ≤ N)로 나타낼 수 있으며, S번째 수부터 E번째 까지 수가 팰린드롬을 이루는지를 물어보며, 명우는 각 질문에 대해 팰린드롬이다 또는 아니다를 말해야 한다.예를 들어, 홍준이가 칠판에 적은 수가 1, 2, 1, 3, 1, 2, 1라고 하자.S = 1, E = 3인 경우 1, 2, 1은 팰린드롬이다.S = 2, E = 5인 경우 2, 1, 3..

[Gold IV] 스도쿠 - 2239문제 링크성능 요약메모리: 142488 KB, 시간: 5592 ms분류백트래킹, 구현제출 일자2024년 12월 19일 22:55:24문제 설명스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다음을 보자.위 그림은 참 잘도 스도쿠 퍼즐을 푼 경우이다. 각 행에 1부터 9까지의 숫자가 중복 없이 나오고, 각 열에 1부터 9까지의 숫자가 중복 없이 나오고, 각 3×3짜리 사각형(9개이며, 위에서 색깔로 표시되었다)에 1부터 9까지의 숫자가 중복 없이 나오기 때문이다.하다 만 스도쿠 퍼즐이 주어졌을 때, 마저 끝내는 프로그램을..

[level 1] 달리기 경주 - 178871문제 링크성능 요약메모리: 89.6 MB, 시간: 1260.57 ms구분코딩테스트 연습 > 연습문제채점결과정확성: 100.0합계: 100.0 / 100.0제출 일자2025년 01월 04일 22:26:27문제 설명얀에서는 매년 달리기 경주가 열립니다. 해설진들은 선수들이 자기 바로 앞의 선수를 추월할 때 추월한 선수의 이름을 부릅니다. 예를 들어 1등부터 3등까지 "mumu", "soe", "poe" 선수들이 순서대로 달리고 있을 때, 해설진이 "soe"선수를 불렀다면 2등인 "soe" 선수가 1등인 "mumu" 선수를 추월했다는 것입니다. 즉 "soe" 선수가 1등, "mumu" 선수가 2등으로 바뀝니다.선수들의 이름이 1등부터 현재 등수 순서대로 담긴 문자열..