시간 제한 메모리 제한 1초 128MB 문제 대한민국은 동아시아에 위치한 한반도에 위치하고 있다. 3면이 바다인 한국의 서쪽으로 서해, 동쪽으로 동해, 남쪽으로 남해에 의해 둘러싸여 있다. 대한민국의 동해안에는 도시가 N개 있고, 서해안에는 도시가 M개 있다. (M ≤ 1000, N ≤ 1000) 각 도시는 북쪽부터 남쪽까지 번호가 1번부터 매겨져 있다. 새로 취임한 대통령은 서해안과 동해안을 연결하는 K개의 고속도로를 만들려고 한다. 각 고속도로는 동해안에 있는 도시와 서해안에 있는 도시를 연결하는 일직선 도로이다. (원래 일직선인 도로는 운전사를 지루하게 하고 피로감을 느끼게 하여 사고의 원인이 되므로, 일부러 고저를 만들거나 커브를 만들어서 그러한 일이 일어나지 않도록 설계되어 있다) 고속도로가 서..

1. 다익스트라 알고리즘(Dijksrta)시작 정점으로부터 간선으로 연결된 정점들을 순차적으로 방문한다. 간선의 가중치를 포함해 방문한 정점의 거리가 갱신된다면 방문한 정점에서 이 과정을 다시 반복한다. 원리만 따지면 너비우선탐색과 크게 다르지 않다. 모든 간선의 가중치가 1인 그래프가 주어진다면 너비우선탐색을 실시하는 것이 다익스트라와 같은 효과가 있다.이런 무향 그래프가 있다고 할 때 1에서부터 6까지의 최단거리를 구해보자. 먼저 모든 정점의 거리를 충분히 큰 값인 inf로 설정한다. 실제로 무한일 필요는 없고 탐색하고자 하는 모든 상황에 대해 예상되는 최대 탐색 거리보다 크기만 하면 된다. 최대 정점의 수가 V개이고 간선의 최대 가중치가 W라면 inf는 V*W보다 큰 값이면 된다. 탐색의 출발 정점..

시간 제한 메모리 제한 2초 512MB 문제 (그림생략) 사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선이 같은 위치를 갖는다. 아래 그림은 N = 5, H = 6 인 경우의 그림이고, 가로선은 없다. 초록선은 세로선을 나타내고, 초록선과 점선이 교차하는 점은 가로선을 놓을 수 있는 점이다. 가로선은 인접한 두 세로선을 연결해야 한다. 단, 두 가로선이 연속하거나 서로 접하면 안 된다. 또, 가로선은 점선 위에 있어야 한다. 위의 그림에는 가로선이 총 5개 있다. 가로선은 위의 그림과 같이 인접한 두 세로선을 연결해야 하고, 가로선을 놓을 수 있는 위치를 연결해야..

시간 제한 메모리 제한 2초 512MB 문제 자연수를 저장하는 데이터베이스 S에 대해 다음의 쿼리를 처리합시다. 유형 1 : S에 자연수 X를 추가한다. 유형 2 : S에 포함된 숫자 중 X번째로 작은 수를 응답하고 그 수를 삭제한다. 입력 첫째 줄에 사전에 있는 쿼리의 수 N 이 주어집니다. (1 ≤ N ≤ 2,000,000) 둘째 줄부터 N개의 줄에 걸쳐 각 쿼리를 나타내는 2개의 정수 T X가 주어집니다. T가 1이라면 S에 추가할 X가 주어지는 것입니다. (1 ≤ X ≤ 2,000,000) T가 2라면 X는 S에서 삭제해야 할 몇 번째로 작은 수인지를 나타냅니다. S에 최소 X개의 원소가 있음이 보장됩니다. 출력 유형 2의 쿼리 개수만큼의 줄에 각 쿼리에 대한 답을 출력합니다. 풀이 S를 어떤 자..

A 가지 한 두름 주세요 간단한 배열 탐색 문제. 10*10 크기의 작은 배열이기 때문에 그냥 브루트포스 돌려서 모든 행과 열을 탐색해 똑같은 문자로만 이루어진 행, 열이 존재하면 1, 아니면 0을 출력한다. D :rightplant: 정말 심각하게 시간 오래 끌어서 패널티 폭탄 맞은 문제. 양쪽으로 배열 관리를 하며 다음 수를 왼쪽에 넘겨줄지, 오른쪽에 넘겨줄지 결정한다. 결정 기준은 새로 추가될 숫자를 포함 왼쪽과 오른쪽의 차이가 가장 적게 나는 쪽으로 넘겨주면 된다. [left - 1 - right]와 같은 식으로 배열을 관리하면 되는데, 만약 left 총합 + 1보다 right 총합이 크거나 같다면 left의 모든 숫자들을 1씩 증가시키고 1을 left에 append. 아닌 경우는 반대로 righ..

시간 제한메모리 제한1초1024MB문제「Move or Block!」 게임은 N칸의 일자형 게임보드에서 할 수 있는 2인용 보드게임이다. 게임보드의 각 칸은 비어 있거나 벽이 세워져 있으며, 비어 있는 칸 중 하나에 두 플레이어가 움직일 수 있는 하나의 말을 올려두고 게임을 시작한다. 게임은 두 명의 플레이어가 턴을 번갈아 가면서 진행한다. 각 플레이어는 자신의 턴이 되었을 때 말의 인접한 칸에 모두 벽이 세워져 있으면 패배한다. 아니라면 아래 두 가지 행동 중 하나를 선택하여 한 번 플레이하고 턴을 넘긴다. 말을 비어 있는 인접한 칸 중 하나로 움직인다.비어 있는 칸을 하나 골라 벽을 세운다.민규와 윤수가 「Move or Block!」 게임을 하려 한다. 주어진 게임보드에서 두 플레이어 모두 최적의 방법..

시간 제한 메모리 제한 2초 512MB 문제 성관이는 다음과 같은 성질을 만족하는 배열을 좋아한다. 배열의 길이는 N이다. 배열에 채워져있는 수는 1보다 크거나 같고, K보다 작거나 같은 자연수이다. 배열에서 연속한 수가 A와 B일 때, A

시간 제한 메모리 제한 1초 512MB 문제 취준생 주헌이는 드디어 취업에 성공했다. 주헌이가 취직한 회사는 비대면 전자계약 서비스 모두싸인(MODUSIGN) 이라는 회사이다. 그리고 오늘은 첫 출근날이다. 주헌이의 출근길에는 다리가 있는데, 전날에 비가 많이 오는 바람에 다리가 끊어져 판자 여러 개로 쪼개져 버렸다. 주헌이는 무사히 회사에 도착할 수 있을까? 다리는 수직선으로 나타낼 수 있으며, 각 판자는 구간 [ L, R ]의 범위에 놓여 있다. 주헌이는 0에서 출발하여 오른쪽(양의 방향)으로만 이동한다. 판자로 덮인 좌표는 자유롭게 건너갈 수 있다. 하지만 판자로 덮이지 않은 좌표는 오직 주헌이가 점프를 해야만 건너갈 수 있으며, 점프를 할 경우 착지한 위치에 판자가 놓여 있어야 한다. 판자의 양 ..