난쟁이 개발자

[Silver I] 데스 나이트 - 16948문제 링크성능 요약메모리: 114540 KB, 시간: 132 ms분류너비 우선 탐색, 그래프 이론, 그래프 탐색제출 일자2025년 3월 6일 21:29:13문제 설명게임을 좋아하는 큐브러버는 체스에서 사용할 새로운 말 "데스 나이트"를 만들었다. 데스 나이트가 있는 곳이 (r, c)라면, (r-2, c-1), (r-2, c+1), (r, c-2), (r, c+2), (r+2, c-1), (r+2, c+1)로 이동할 수 있다.크기가 N×N인 체스판과 두 칸 (r1, c1), (r2, c2)가 주어진다. 데스 나이트가 (r1, c1)에서 (r2, c2)로 이동하는 최소 이동 횟수를 구해보자. 체스판의 행과 열은 0번부터 시작한다.데스 나이트는 체스판 밖으로 벗어날..

[Gold III] 텀 프로젝트 - 9466문제 링크성능 요약메모리: 238560 KB, 시간: 1016 ms분류깊이 우선 탐색, 그래프 이론, 그래프 탐색제출 일자2025년 2월 10일 16:55:40문제 설명이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 수도 있다. 프로젝트 팀을 구성하기 위해, 모든 학생들은 프로젝트를 함께하고 싶은 학생을 선택해야 한다. (단, 단 한 명만 선택할 수 있다.) 혼자 하고 싶어하는 학생은 자기 자신을 선택하는 것도 가능하다.학생들이(s1, s2, ..., sr)이라 할 때, r=1이고 s1이 s1을 선택하는 경우나, s1이 s2..

[Gold IV] 떡 돌리기 - 20007문제 링크성능 요약메모리: 119248 KB, 시간: 236 ms분류데이크스트라, 그래프 이론, 최단 경로, 정렬제출 일자2025년 2월 9일 01:42:25문제 설명군인인 성현이는 전역 후에 새 집으로 이사를 갔다. 주변 이웃과 친하게 지내고 싶은 마음에 이웃집에 떡을 돌리기로 했다. 떡은 한번에 하나씩만 들고 갈 수 있다. 집들 사이에는 총 M개의 양방향 도로가 있다. 귀찮은 성현이는 하루에 X보다 먼 거리를 걷지 않고 거리가 가까운 집부터 방문한다. 또 잠은 꼭 본인 집에서 자야 하므로 왕복할 수 없는 거리는 다음날 가기로 다짐한다. N-1개의 이웃집 모두에게 떡을 돌리기 위해서는 최소 며칠이 소요될 것인가.집의 번호는 0번부터 N-1번까지 차례대로 붙어있다..

[Gold IV] DSLR - 9019문제 링크성능 요약메모리: 216180 KB, 시간: 5032 ms분류너비 우선 탐색, 그래프 이론, 그래프 탐색제출 일자2025년 2월 4일 21:18:26문제 설명네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 저장된 n을 다음과 같이 변환한다. n의 네 자릿수를 d1, d2, d3, d4라고 하자(즉 n = ((d1 × 10 + d2) × 10 + d3) × 10 + d4라고 하자)D: D 는 n을 두 배로 바꾼다. 결과 값이 9999 보다 큰 경우에는 10000 으로 나눈 나머지를 취한다. 그 결과 값..

[Silver I] 그래프 탐색 2 - 14218문제 링크성능 요약메모리: 115600 KB, 시간: 232 ms분류너비 우선 탐색, 깊이 우선 탐색, 그래프 이론, 그래프 탐색제출 일자2025년 2월 3일 18:31:45문제 설명남규나라의 왕 zych는 도로 정비 계획을 발표하였다. 두 도시를 있는 도로들을 새로 만드는 계획이다. 도로 정비 계획은 두 도시에 대한 정보가 주어지는데, 도로를 정비하는 일은 매우 큰 일이기에 계획을 순서대로 하나씩 시행해 나갈 것이다.Zych는 차후 도로 정비 계획에 참고하기 위하여, 각 도시들이 수도에 방문하는데 최소 몇 개의 도시들을 방문해야 하는지 조사하기로 하였다.남규나라의 초기 도시상태가 주어지고 도로 정비계획이 주어질 때, 한 도로가 정비될 때마다 각 도시별로 ..

[Gold III] 줄 세우기 - 2252문제 링크성능 요약메모리: 121640 KB, 시간: 252 ms분류방향 비순환 그래프, 그래프 이론, 위상 정렬제출 일자2025년 1월 28일 07:57:21문제 설명N명의 학생들을 키 순서대로 줄을 세우려고 한다. 각 학생의 키를 직접 재서 정렬하면 간단하겠지만, 마땅한 방법이 없어서 두 학생의 키를 비교하는 방법을 사용하기로 하였다. 그나마도 모든 학생들을 다 비교해 본 것이 아니고, 일부 학생들의 키만을 비교해 보았다.일부 학생들의 키를 비교한 결과가 주어졌을 때, 줄을 세우는 프로그램을 작성하시오.입력첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 횟수이다. 다음 M개의 줄에는 키를 비교한 두 ..

[Gold IV] 플로이드 - 11404문제 링크성능 요약메모리: 121432 KB, 시간: 196 ms분류플로이드–워셜, 그래프 이론, 최단 경로제출 일자2024년 12월 2일 23:26:23문제 설명n(2 ≤ n ≤ 100)개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 m(1 ≤ m ≤ 100,000)개의 버스가 있다. 각 버스는 한 번 사용할 때 필요한 비용이 있다.모든 도시의 쌍 (A, B)에 대해서 도시 A에서 B로 가는데 필요한 비용의 최솟값을 구하는 프로그램을 작성하시오.입력첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어..

[Gold V] 선수과목 (Prerequisite) - 14567문제 링크성능 요약메모리: 142820 KB, 시간: 376 ms분류방향 비순환 그래프, 다이나믹 프로그래밍, 그래프 이론, 위상 정렬제출 일자2024년 11월 28일 21:10:35문제 설명올해 Z대학 컴퓨터공학부에 새로 입학한 민욱이는 학부에 개설된 모든 전공과목을 듣고 졸업하려는 원대한 목표를 세웠다. 어떤 과목들은 선수과목이 있어 해당되는 모든 과목을 먼저 이수해야만 해당 과목을 이수할 수 있게 되어 있다. 공학인증을 포기할 수 없는 불쌍한 민욱이는 선수과목 조건을 반드시 지켜야만 한다. 민욱이는 선수과목 조건을 지킬 경우 각각의 전공과목을 언제 이수할 수 있는지 궁금해졌다. 계산을 편리하게 하기 위해 아래와 같이 조건을 간소화하여 ..

그래프는 노드(vertex)와 간선(edge)을 이용한 비선형 데이터 구조 . 보통 그래프는 데이터 간의 관계를 표현하는 데 사용됨. 데이터를 노드로, 노드 간의 관계나 흐름을 간선으로 표현함. 간선은 방향이 있을 수도, 없을 수도 있음. 만약 관계나 흐름에서 정도를 표현할 필요가 있다면 가중치라는 개념을 추가하여 표현하기도 함. 그래프 용어 정리 예를 들어 도시 간의 인구 이동을 그래프로 표현하면 다음과 같다. 그림에서 사각형으로 표현한 것은 노드(또는 정점), 화살표로 표현한 것은 간선, 간선 위에 숫자로 표현한 것은 가중치다. 노드에는 어떤 데이터가 들어있다. 인구 이동의 경우 어디서 얼마나 이동했는지 표시할 필요가 있으므로 간선에 가중치를 표현함. 흐름을 표현하는 방향성 간선은 방향을 가질 수도 ..