오구리의 DevLog

▶24445 - 알고리즘 수업 - 너비 우선 탐색 2 ▶문제오늘도 서준이는 너비 우선 탐색(BFS) 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해 보자.N개의 정점과 M개의 간선으로 구성된 무방향 그래프(undirected graph)가 주어진다. 정점 번호는 1번부터 N번이고 모든 간선의 가중치는 1이다. 정점 R에서 시작하여 너비 우선 탐색으로 노드를 방문할 경우 노드의 방문 순서를 출력하자.너비 우선 탐색 의사 코드는 다음과 같다. 인접 정점은 내림차순으로 방문한다.bfs(V, E, R) { # V : 정점 집합, E : 간선 집합, R : 시작 정점  for each v ∈ V - {R}  visited[v]  ▶입력첫째 줄에 정점의 수..

▶25193 - 곰곰이의 식단 관리▶문제곰곰이는 치킨을 좋아한다. 그러다 보니 매 끼니에 치킨을 먹고 있다. 당신은 곰곰이의 트레이너로서 곰곰이의 식단을 관리해 주기로 했다.곰곰이가 N일간 먹어야 할 음식들의 리스트가 주어졌을 때, 리스트의 순서를 원하는 대로 조정하여 곰곰이가 연속으로 치킨을 먹는 날의 최댓값을 가장 작게 만들려고 한다.곰곰이의 건강을 위해 위와 같은 프로그램을 작성해 보자. ▶입력첫 번째 줄에 식단을 정할 일수 N(1≤N≤100000)이 주어진다.두 번째 줄에 음식의 리스트인 길이 N의 문자열 S가 주어진다. 문자열은 영어 대문자로만 이루어져 있다. Si가 C인 경우, i번째 음식이 치킨이며, 그 외의 경우에는 다른 음식이다. ▶출력첫째 줄에 모든 집을 칠하는 비용의 최솟값을 출력한다..

▶17404 - RGB거리 2 ▶문제RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다.집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자.1번 집의 색은 2번, N번 집의 색과 같지 않아야 한다.N번 집의 색은 N-1번, 1번 집의 색과 같지 않아야 한다.i(2 ≤ i ≤ N-1) 번 집의 색은 i-1, i+1번 집의 색과 같지 않아야 한다. ▶입력첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다..

▶31910 - 이진수 격차 ▶문제각 칸에 0 또는 1이 적혀 있는 N×N 격자가 있다. 인선이는 1행 1열에서 출발해 N행 N열까지 이동하는데, 오른쪽(열 번호가 증가하는 방향) 또는 아래(행 번호가 증가하는 방향)로만 한 칸씩 이동할 수 있다. 인선이는 어떤 칸에 방문할 때마다 그 칸에 적힌 문자를 자신이 갖고 있는 문자열의 뒷부분에 덧붙인다. 예를 들어, 주어진 그림에서 인선이가 1행 1열에서 출발하여 순서대로 오른쪽, 아래, 오른쪽으로 한 칸씩 이동한다면 인선이가 가진 문자열은 1101이다. N행 N열에 도착하면 인선이는 자신이 갖고 있는 문자열을 이진수로 해석한 값 M을 계산한다. 예를 들어, 인선이가 가진 문자열이 1101일 경우 M = 13이다. 인선이가 계산하게 될 M의 최댓값을 구하시오...

▶31450 - Everyone is winner ▶문제Your friend is a kindergarten teacher. Since the Olympic Games in Paris are approaching, he wants to teach the kids about different aspects of sports competitions. As part of this idea, he plans to have one day when kids receive medals for their behaviour in kindergarten. For example, he would give out a medal for the kid who shares their toys the most, or for the ..

▶11505 - 구간 곱 구하 ▶문제 어떤 N개의 수가 주어져 있다. 그런데 중간에 수의 변경이 빈번히 일어나고 그 중간에 어떤 부분의 곱을 구하려 한다. 만약에 1, 2, 3, 4, 5라는 수가 있고, 3번째 수를 6으로 바꾸고 2번째부터 5번째까지 곱을 구하라고 한다면 240을 출력하면 되는 것이다. 그리고 그 상태에서 다섯 번째 수를 2로 바꾸고 3번째부터 5번째까지 곱을 구하라고 한다면 48이 될 것이다. ▶입력 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000)가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 곱을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄까지 N개의 수가 주어진다. 그리고 N+2번..

▶10868 - 최솟값 ▶문제 N(1 ≤ N ≤ 100,000) 개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100,000) 개 주어졌을 때는 어려운 문제가 된다. 이 문제를 해결해 보자. 여기서 a번째라는 것은 입력되는 순서로 a번째라는 이야기이다. 예를 들어 a=1, b=3이라면 입력된 순서대로 1번, 2번, 3번 정수 중에서 최솟값을 찾아야 한다. 각각의 정수들은 1 이상 1,000,000,000 이하의 값을 갖는다. ▶입력 첫째 줄에 N, M이 주어진다. 다음 N개의 줄에는 N개의 정수가 주어진다. 다음 M개의 줄에는 a, b의 쌍이 주어진다. ▶출력 M개의 줄에 입력받은 순서..

▶2357 - 최솟값과 최댓값 ▶문제 N(1 ≤ N ≤ 100,000) 개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수, 또는 제일 큰 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100,000) 개 주어졌을 때는 어려운 문제가 된다. 이 문제를 해결해 보자. 여기서 a번째라는 것은 입력되는 순서로 a번째라는 이야기이다. 예를 들어 a=1, b=3이라면 입력된 순서대로 1번, 2번, 3번 정수 중에서 최소, 최댓값을 찾아야 한다. 각각의 정수들은 1 이상 1,000,000,000 이하의 값을 갖는다. ▶입력 첫째 줄에 N, M이 주어진다. 다음 N개의 줄에는 N개의 정수가 주어진다. 다음 M개의 줄에는 a, b의 쌍이 주어진다..

▶2042 - 구간 합 구하기 ▶문제 어떤 N개의 수가 주어져 있다. 그런데 중간에 수의 변경이 빈번히 일어나고 그 중간에 어떤 부분의 합을 구하려 한다. 만약에 1,2,3,4,5라는 수가 있고, 3번째 수를 6으로 바꾸고 2번째부터 5번째까지 합을 구하라고 한다면 17을 출력하면 되는 것이다. 그리고 그 상태에서 다섯 번째 수를 2로 바꾸고 3번째부터 5번째까지 합을 구하라고 한다면 12가 될 것이다. ▶입력 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄까지 N개의 수가 주어진다. 그리고 N+2번째 줄부..

▶14427 - 수열과 쿼리 15 ▶문제 길이가 N인 수열 A1, A2,..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 i v : Ai를 v로 바꾼다. (1 ≤ i ≤ N, 1 ≤ v ≤ 109) 2 : 수열에서 크기가 가장 작은 값의 인덱스를 출력한다. 그러한 값이 여러 개인 경우에는 인덱스가 작은 것을 출력한다. 수열의 인덱스는 1부터 시작한다. ▶입력 첫째 줄에 수열의 크기 N이 주어진다. (1 ≤ N ≤ 100,000) 둘째 줄에는 A1, A2,..., AN이 주어진다. (1 ≤ Ai ≤ 109) 셋째 줄에는 쿼리의 개수 M이 주어진다. (1 ≤ M ≤ 100,000) 넷째 줄부터 M개의 줄에는 쿼리가 주어진다. ▶출력 2번 쿼리에 대해서 정답을 한 줄에 하나씩 ..

▶9063 - 대지 ▶문제 임 씨는 1950 년 한국전쟁으로 많은 손해를 본 사람들 중 하나다. 전쟁 통에 손해보지 않은 사람이 어디 있을까 만은 그는 6.25 가 일어나기 전만 해도 충청도 지방에 넓은 대지를 소유한 큰 부자였다. 전쟁이 나자 임 씨는 땅문서와 값나가는 것들만 챙겨서 일본으로 피난을 가지만 피난 중에 그만 땅문서를 잃어버리고 만다. 전쟁이 끝난 후에 임 씨의 땅은 이미 다른 사람들의 논밭이 되어 있었고, 임 씨는 땅을 되찾으려 했지만 문서가 없으니 생떼 쓰는 것과 다를 바 없었다. 이러다가 임 씨는 길바닥에 나앉게 생겼다. 이때, 임 씨에게 좋은 생각이 떠올랐으니 바로 자신이 습관처럼 땅 깊숙이 뭔가 표식을 해놓았던 사실이다. 임 씨는 한적할 때마다 자신의 논밭을 거닐다가 땅속 깊은 곳..

▶13560 - 축구 게임 ▶문제 축구는 지구에서 가장 인기 있는 스포츠 중의 하나입니다. n 팀으로 이루어진 축구 리그가 있습니다. 하나의 팀은 다른 모든 팀과 정확히 한 번씩만 경기를 합니다. 그러므로, 각 팀은 n - 1번의 경기를 하게 됩니다. 무승부는 승부차기를 하기 때문에 없습니다. 한 경기 후에 이긴 한 팀은 1 점을 얻게 되고, 진 팀은 0 점을 얻게 됩니다. 베스트 팀 선정을 위해 경기 일정이 끝난 후에 각 팀은 리그 사무소에 획득한 점수를 보고하게 됩니다. 리그 사무소는 각 팀이 보고한 점수가 실수가 없는지 확실히 해두고 싶습니다. 즉, 보고한 점수가 유효한지 아닌지 알고 싶은 것이고, 이 말은 리그 룰에 따르는 경우 이 점수들을 각 팀에 할당하는 것이 가능해야 합니다. 주어진 n 개의..

▶13458 - 시험 감독 ▶문제 총 N개의 시험장이 있고, 각각의 시험장마다 응시자들이 있다. i번 시험장에 있는 응시자의 수는 Ai명이다. 감독관은 총감독관과 부감독관으로 두 종류가 있다. 총감독관은 한 시험장에서 감시할 수 있는 응시자의 수가 B명이고, 부감독관은 한 시험장에서 감시할 수 있는 응시자의 수가 C명이다. 각각의 시험장에 총감독관은 오직 1명만 있어야 하고, 부감독관은 여러 명 있어도 된다. 각 시험장마다 응시생들을 모두 감시해야 한다. 이때, 필요한 감독관 수의 최솟값을 구하는 프로그램을 작성하시오. ▶입력 첫째 줄에 시험장의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 각 시험장에 있는 응시자의 수 Ai (1 ≤ Ai ≤ 1,000,000)가 주어진다. 셋째 ..

▶11779 - 최소비용 구하기2 ▶문제 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+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 그리고 그다음에는 도착지의 도시 번호가 주어지고 또 그 버스 비..

▶14719 - 빗물 ▶문제 2차원 세계에 블록이 쌓여있다. 비가 오면 블록 사이에 빗물이 고인다. 비는 충분히 많이 온다. 고이는 빗물의 총량은 얼마일까? ▶입력 첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로길이 W가 주어진다. (1 ≤ H, W ≤ 500) 두 번째 줄에는 블록이 쌓인 높이를 의미하는 0 이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치부터 차례대로 W개 주어진다. 따라서 블록 내부의 빈 공간이 생길 수 없다. 또 2차원 세계의 바닥은 항상 막혀있다고 가정하여도 좋다. ▶출력 2차원 세계에서는 한 칸의 용량은 1이다. 고이는 빗물의 총량을 출력하여라. 빗물이 전혀 고이지 않을 경우 0을 출력하여라. ▶풀이 처음에는 그냥 모두 확인하는 방식으로 풀었다. 당연히 시간 ..

▶18185 - 라면 사기 (Small) ▶문제 라면마니아 교준이네 집 주변에는 N개의 라면 공장이 있다. 각 공장은 1번부터 N번까지 차례대로 번호가 부여되어 있다. 교준이는 i번 공장에서 정확하게 Ai개의 라면을 구매하고자 한다(1 ≤ i ≤ N). 교준이는 아래의 세 가지 방법으로 라면을 구매할 수 있다. i번 공장에서 라면을 하나 구매한다(1 ≤ i ≤ N). 이 경우 비용은 3원이 든다. i번 공장과 (i+1)번 공장에서 각각 라면을 하나씩 구매한다(1 ≤ i ≤ N-1). 이 경우 비용은 5원이 든다. i번 공장과 (i+1)번 공장, (i+2)번 공장에서 각각 라면을 하나씩 구매한다(1 ≤ i ≤ N-2). 이 경우 비용은 7원이 든다. 최소의 비용으로 라면을 구매하고자 할 때, 교준이가 필요..

▶4963 - 섬의 개 ▶문제 정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬의 개수를 세는 프로그램을 작성하시오. 한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사각형이다. 두 정사각형이 같은 섬에 있으려면, 한 정사각형에서 다른 정사각형으로 걸어서 갈 수 있는 경로가 있어야 한다. 지도는 바다로 둘러싸여 있으며, 지도 밖으로 나갈 수 없다. ▶입력 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도가 주어진다. 1은 땅, 0은 바다이다. 입력의 마지막 줄에는 0이 두 개 주어진다. ▶출력 각 테스트 케이스에 ..

▶16930 - 달리기 오랜만에 플래티넘 문제를 풀고 싶어서 쉬워 보이는 걸로 골랐다. 플래티넘3 문제지만 그렇게 어렵진 않았고, 플5 정도로 느껴졌다. ▶문제 진영이는 다이어트를 위해 N×M 크기의 체육관을 달리려고 한다. 체육관은 1 × 1 크기의 칸으로 나누어져 있고, 칸은 빈칸 또는 벽이다. x행 y열에 있는 칸은 (x, y)로 나타낸다. 매 초마다 진영이는 위, 아래, 오른쪽, 왼쪽 중에서 이동할 방향을 하나 고르고, 그 방향으로 최소 1개, 최대 K개의 빈칸을 이동한다. 시작점 (x1, y1)과 도착점 (x2, y2)가 주어졌을 때, 시작점에서 도착점으로 이동하는 최소 시간을 구해보자. ▶입력 첫째 줄에 체육관의 크기 N과 M, 1초에 이동할 수 있는 칸의 최대 개수 K가 주어진다. 둘째 줄부..

▶16947 - 서울 지하철 2호선 ▶문제 서울 지하철 2호선은 다음과 같이 생겼다. 지하철 2호선에는 51개의 역이 있고, 역과 역 사이를 연결하는 구간이 51개 있다. 즉, 정점이 51개이고, 양방향 간선이 51개인 그래프로 나타낼 수 있다. 2호선은 순환선 1개와 2개의 지선으로 이루어져 있다. 한 역에서 출발해서 계속 가면 다시 출발한 역으로 돌아올 수 있는 노선을 순환선이라고 한다. 지선은 순환선에 속하는 한 역에서 시작하는 트리 형태의 노선이다. 두 역(정점) 사이의 거리는 지나야 하는 구간(간선)의 개수이다. 역 A와 순환선 사이의 거리는 A와 순환선에 속하는 역 사이의 거리 중 최솟값이다. 지하철 2호선과 같은 형태의 노선도가 주어졌을 때, 각 역과 순환선 사이의 거리를 구해보자. ▶입력 ..

▶1083 - 소트 ▶문제 크기가 N인 배열 A가 있다. 배열에 있는 모든 수는 서로 다르다. 이 배열을 정렬할 때, 연속된 두 개의 원소만 교환할 수 있다. 그리고, 교환은 많아봐야 S번 할 수 있다. 이때, 정렬한 결과가 사전순으로 가장 뒷서는 것을 출력한다. ▶입력 첫째 줄에 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 각 원소가 차례대로 주어진다. 이 값은 1000000보다 작거나 같은 자연수이다. 마지막 줄에는 S가 주어진다. S는 1000000보다 작거나 같은 음이 아닌 정수이다. ▶출력 첫째 줄에 문제의 정답을 출력한다. ▶풀이 최댓값을 찾아서 가장 왼쪽으로 넣어주는 방식을 사용하기로 했다. 최댓값이 들어간 가장 좌측 index는 고정시키는 방식이다. 일단 i번째부터 ..