본문 바로가기

Problem Solving

 (85)
6064 카잉 달력 www.acmicpc.net/problem/6064 6064번: 카잉 달력 입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터는 한 줄로 구성된다. www.acmicpc.net 육십갑자의 확장판 문제. M = 10, N = 12 인 경우는 육십갑자의 방식과 같다. (10개의 천간, 12개의 지지) 총 경우의 수는 M과 N의 최소공배수 만큼이다. 따라서 육십갑자의 모든 경우의 수는 10과 12의 최소공배수인 60이다. 처음에는 최소공배수를 구해서 그만큼 돌리다가 안나오면 -1, 나오면 출력을 하려고 했으나... 그냥 배열로 중복을 체크하면서, x는 고정시킨 채 y가 나오는 해를 구할 때까지..
1202 보석 도둑 www.acmicpc.net/problem/1202 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 처음에 이 문제를 보고 바로 동전DP를 떠올렸지만, 각 가방에 한 개의 보석만 넣을 수 있고, 각각의 가방에 넣을 수 있는 보석의 무게가 다르기 때문에 조금 다른 문제라 생각했다. 풀이 방법 용량이 작은 가방부터 넣을 수 있는 최대 가치의 보석을 넣으면 된다. 예를들어, 아래와 같은 상황이라고 하자. 먼저 가방 용량을 오름차순으로 정렬하고, 보석을 무..
16928 뱀과 사다리 게임 www.acmicpc.net/problem/16928 16928번: 뱀과 사다리 게임 첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으 www.acmicpc.net 전형적인 BFS 문제. 1번칸부터 100칸까지 있으며 10 X 10 맵으로 되어있다. 하지만 이 문제에서는 그냥 100칸짜리 1차원 배열에 넣어도 상관 없다. 1번칸에서 100번칸까지 가면 되는 문제. 주사위를 굴려 1칸부터 6칸까지 갈 수 있으며, 해당 칸에 사다리가 있으면 더 앞으로(+), 뱀이 있으면 뒤로(-) 움직이게 된다. 100칸 int 배열에 사다리, ..
9019 DSLR www.acmicpc.net/problem/9019 9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net BFS 문제인가? 한번 생각하게 하는 문제. 언제 우리가 원하는 수를 만들 지 모르니 D, S, L, R 모든 연산을 해보고, 이미 한번 만났던 애들인지 한번 체크해보고 다음을 계산하게하여 푸는 문제. Queue에 연산결과(수)와 지금까지의 연산과정을 모두 넣어야하므로 std::queue 으로 진행하였다. 이 문제에서 키 포인트 1. 이미 연산했던 수 인지 아닌지 체크하기. -> 이미 연산했던 수라..
벨만-포드 최단경로 알고리즘 한 시작점에서 다른 모든 정점까지의 최단 거리(간선 가중치의 합이 최소)를 구하는 알고리즘 중 가장 유용한 알고리즘으로 다익스트라 알고리즘이 있다. 하지만 다익스트라 알고리즘은 음수 간선이 있는 그래프의 경우, 그 정당성이 보장되지 않아 벨만-포드 알고리즘을 사용해야한다. 벨만-포드 알고리즘은 음수 간선이 있는 최단 경로를 찾을 뿐만 아니라, 그래프에 음수 사이클이 있어서 최단 거리가 제대로 정의되지 않을 경우 알려주기도 한다. 벨만-포드 알고리즘 시작점에서 각 정점까지 가는 최단 거리의 상한을 적당히(?) 예측한 뒤, 예측 값과 실제 최단 거리 사이의 오차를 반복적으로 줄여가는 방식으로 동작한다. 수행 과정에서 각 정점까지 최단 거리의 상한을 담은 배열 upper[]을 유지한다. 이 값은 알고리즘이 진..
오일러 서킷을 찾아내는 알고리즘 모든 정점이 짝수점(정점의 차수가 짝수인 점)이고, 모든 간선이 하나의 컴포넌트에 포함되어 있다고 가정하자. 함수 findRandomCircuit(u) : 현재 정점에 인접한 간선 중 아직 따라간 적 없는 임의의 간선을 재귀적으로 따라가기를 반복하다가, 더이상 따라갈 간선이 없을 때 종료. 함수를 실행하면 여러 부분 서킷이 생성될텐데, 전체를 포함하는 하나의 서킷을 원하므로 모든 부분 서킷들을 합쳐야한다. 부분 서킷이 생긴다는 말은 무슨 말일까? 어떤 정점에서부터 출발하는 간선이 하나가 아닌 여러개일 수 있는데, 이때 서킷의 정의에 따라 출발하는 간선만큼 해당 정점으로 오는 간선이 존재해야한다. -> 그만큼 부분서킷이 생긴다. 해당 정점에서 나가는 간선이 2개 존재한다면, 2개의 부분 서킷이 생긴다. 이..
[ALGOSPOT] 단어 제한 끝말잇기 (WORDCHAIN) 출처 : algospot.com/judge/problem/read/WORDCHAIN algospot.com :: WORDCHAIN 단어 제한 끝말잇기 문제 정보 문제 끝말잇기는 참가자들이 원을 그리고 앉은 뒤, 시계 방향으로 돌아가면서 단어를 말하는 게임입니다. 이 때 각 사람이 말하는 단어의 첫 글자는 이전 사람이 algospot.com 끝말잇기는 참가자들이 원을 그리고 앉은 뒤, 시계 방향으로 돌아가면서 단어를 말하는 게임입니다. 이 때 각 사람이 말하는 단어의 첫 글자는 이전 사람이 말한 단어의 마지막 글자와 같아야 합니다. 단어 제한 끝말잇기는 일반적인 끝말잇기와 달리 사용할 수 있는 단어의 종류가 게임 시작 전에 미리 정해져 있으며, 한 단어를 두 번 사용할 수 없습니다. 단어 제한 끝말잇기에서..
오일러 서킷 (Eulerian circuit) 오일러 서킷(Eulerian circuit) : 그래프의 모든 간선을 정확히 한번씩 지나서 시작점으로 돌아오는 경로. 오일러 경로(Eulerian path) : 그래프의 모든 간선을 정확히 한번씩 지나는 경로. 시작점과 도착점이 다르다. 무향 그래프에서 오일러 서킷을 찾으려면? 먼저 오일러 서킷의 존재 여부를 확인한다. 1. 그래프의 간선들이 두 개 이상의 컴포넌트에 나뉘어 있는 경우는 오일러 서킷이 존재할 수 없다. 그래프의 정점이 둘 이상의 컴포넌트로 쪼개져 있어도, 간선들이 한 컴포넌트에 있다면 오일러 서킷은 존재한다. 그래프의 모든 '간선'을 지나 시작점으로 되돌아오기만 하면 되기 때문. 2. 도착점에 인접한 모든 간선은 이미 지나온 상황이어야한다. 3. 도착점에 인접한 간선의 수는 항상 짝수이다..

티스토리툴바