본문 바로가기

전체 글

 (70)
BOJ 1238 파티 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 특정 노드로 이동했다가 돌아와야 한다는 점을 추가해야 하는 최장/최단 거리 탐색 문제이다. 다익스트라 알고리즘의 동작에 대하여 잘 모른다면 [링크] 를 우선 참조하자 노드 A에서 출발했다 가정했을 때, 이미 방문한 노드 그룹에 대한 처리와, 이후에 필요할 다른 임의의 노드에서 A 노드로 왔다가 임의의 노드로 돌아가는 (= A에서 출발해서 임의의 노드로 이동하는) 값을 이용하기 위하여 아래와 같이 memo 변수를 추가로 이용했다. 그..
BOJ 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 정답으로 출력할 값이 int의 영역을 벗어나는 것을 예측 못해서 시간을 조금 소비했던 문제였다. 문제 자체는 그리디 알고리즘의 정석에 가깝다고 생각된다. 문제에서 주어진 예시는 설명에 적합하지 않은 관계로 아래와 같이 임의로 만든 예시를 가지고 설명을 진행한다. 이 문제는 가방 1개당 가져갈 수 있는 보석이 1개로 1 대 1 매칭이 된다. 용량이 20 짜리 가방에 무게가 1짜리 보석을 넣어도 해당 가방..
BOJ 2014 소수의 곱 2014번: 소수의 곱 첫째 줄에 K(1 ≤ K ≤ 100), N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 K개의 소수가 오름차순으로 주어진다. 같은 소수가 여러 번 주어지는 경우는 없으며, 주어지는 소수는 모두 541보다 작거나 www.acmicpc.net 문제를 어렵게 생각하지 않는 것 이 중요한 문제다. 각 소수마다 계산해야 하는 대상이 달라질 수 있는데, 그 대상을 새롭게 탐색하지 않는 부분에 포인트를 맞추어 구현했다. 최초에 정답 확인용 리스트에 1을 넣은 채로 시작하도록 하자. 파란 사각형은 입력으로 주어진 소수들을 의미하고, 파란 사각형 밑에 붙을 흰색 작은 사각형은 각 소수의 연산 대상이라고 생각하면 된다. 자세한 내용은 아래에 기술한다. 각 소수 별로 다른 우선순위 큐 를 ..
BOJ 1916 최소비용 구하기 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 바로 이전 글인 1753번 문제 최단경로와 동일하게 다익스트라 알고리즘으로 해결 가능한 문제이다. BOJ 1753번 최단경로 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 dev-game-standalone.tistory.com 동일한 풀이를 갖는..
BOJ 1697번 숨바꼭질 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 피보나치수열을 구하는 것만큼이나 간단한 동적 계획법 문제이다. 동적 계획법은 상향식 계산과, 하향식 계산으로 구분되는데, 오늘은 1697번 문제를 상향식 구현을 해본다. 수빈이와 동생이 놀고 있는 점들을 아래와 같이 나타냈다. 상향식 동적 계획법 (= tabulation) 이므로 모든 경우의 수를 다 구하며 정답을 향해 갈 것이다. 규칙은 아래와 같다. (규칙 A) 현재 시간에 탐색된 점들을 저장한다. (큐 등을 이용) (규칙 B) 저..
BOJ 1002번 터렛 1002번: 터렛 각 테스트 케이스마다 류재명이 있을 수 있는 위치의 수를 출력한다. 만약 류재명이 있을 수 있는 위치의 개수가 무한대일 경우에는 -1을 출력한다. www.acmicpc.net 두 원의 중심과 반지름이 주어졌을때, 두개의 원의 위치관계를 묻는 문제이다. 두 원의 관계에서 접점의 갯수는 무한개, 0개, 1개, 2개, 로 4가지가 있을 수 있다. 무한개는 두 원의 중심이 같고, 반지름도 같은 경우가 있으며 0개인 경우는 반지름이 다른 동심원(A), 작은원이 큰원의 내부에 위치했을때(B), 두 원이 닿지 않는 거리에 있을때(C) 1개인 경우는 두 원이 내접했을때(D), 외접했을때(E) 2개인 경우는 그 외의 상황(F) 으로 정리가 가능하다. 먼저 두 원이 일치하는 경우는 중심좌표가 같고, 반지..
BOJ 1753번 최단경로 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 그래프의 간선에 가중치가 존재할 때, 최소 / 최대 비용을 구하는 알고리즘 중 하나인 다익스트라(Dijkstra) 알고리즘을 아는지 묻는 문제이다. 다만 다익스트라 알고리즘은 간선의 가중치가 양수 영역에 있어야 한다. 음수 가중치를 가지는 그래프의 최단거리 탐색 문제는 벨만 포드 알고리즘을 이용하도록 하자. 벨만 포드 알고리즘 문제도 조만간 하나 풀어야겠다. 문제의 예시를 그래프로 나타내면 오른쪽과 같다. 커다란 블록은 노드..
BOJ 1644 소수의 연속합 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 간단한 내용을 어렵게 설명한 문제라는 생각이 들었다. 요약하면 주어지는 자연수 N 이하의 소수를 모두 구한 뒤, 그 소수들의 구간합을 구해서 N이 되는 구간이 몇 개인지를 세는 문제이다. N이하의 소수를 구하는 것은 에라토스테네스의 체 를 이용하여 구할 수 있으니 결국 구간합을 여러 번 구하는 문제인 셈이다. N이하의 소수를 구하는 내용은 인터넷이나 바로 전 글을 참고하여 해결했다 가정하자. BOJ 4948 베르트랑 공준 4948번: 베르트랑 공준 베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. 이 ..

티스토리툴바