4Legs_Archives

문제 링크 : www.acmicpc.net/problem/16118 16118번: 달빛 여우 첫 줄에 나무 그루터기의 개수와 오솔길의 개수를 의미하는 정수 N, M(2 ≤ N ≤ 4,000, 1 ≤ M ≤ 100,000)이 주어진다. 두 번째 줄부터 M개의 줄에 걸쳐 각 줄에 세 개의 정수 a, b, d(1 ≤ a, b ≤ N, a ≠ b www.acmicpc.net 가중치를 번갈아 x2, /2 하여 이동하도록 하는 다익스트라 알고리즘을 구현하는 문제이다. 우선 가중치의 /2에 값이 유실되지 않도록 그래프의 가중치는 입력값의 2배로 설정한다. 기존 다익스트라 알고리즘의 우선순위 큐에 인자를 추가하여, (이 풀이에선 sprint 이다.) 해당 인자의 값에 따라 다익스트라 내의 새 dist에 x2 또는 /2..

문제 링크 : www.acmicpc.net/problem/9370 9370번: 미확인 도착지 (취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 www.acmicpc.net 결국 문제는 특정한 하나의 간선을 출발지로부터의 최단경로에 포함하는 노드들을 구하는 것이다. 후술할 다른 풀이방법도 있지만, 문제의 의도에 따라 다익스트라 알고리즘을 적용해 정석으로 풀이해보자. 위의 예제 그래프에서 2번 노드에서 어떤 목적지 후보 노드에 대한 최단경로가 1-3 간선을 포함하고 있다면, 1번 노드에서 그 목적지 후보 노드에 대한 최단거리는 출발 노드로부터 목적지 후보 노드까지..

[서론] 그래프 최단경로 알고리즘으로, 꽤 자주 보이는 유형이다. 다익스트라 알고리즘은 음수가 아닌 가중치가 있는 그래프에서 한 점으로부터 다른 모든 점까지의 최단 경로를 구하는 알고리즘이다. [동작 원리] 다음과 같은 그래프에서, 1번 노드와 나머지 각 노드 간의 최단거리를 다익스트라 알고리즘을 통해 구해보자. 다익스트라 알고리즘은 위와 같은 상태에서 시작한다. 테이블의 값은 출발 노드로부터 해당 노드까지의 최소 가중치 합을 의미하며, 테이블의 값이 INF(무한대)라면 해당 노드와 연결되어 있지 않다는 의미이다. 아직은 1번 노드만 확인했으므로, 다른 모든 노드에 대해 INF가 기록된 모습이다. 출발 노드로부터 인접한 각 노드에 대해 테이블에 거리를 기록한다. 예시 그래프에서는 출발 노드 1이 2, 3..

문제 링크 : www.acmicpc.net/problem/1422 1422번: 숫자의 신 첫째 줄에 K와 N이 공백을 사이에 두고 주어진다. K와 N은 각각 1,000보다 작거나 같은 자연수이고, N은 K보다 크거나 같다. 둘째 줄에는 K개의 수가 한 줄에 하나씩 주어진다. 각 수는 1,000,000,000보�� www.acmicpc.net 예전에 풀었던 DP 문제인 '방번호' 문제와 비슷한 맥락의 문제이다. 가장 큰 수를 만들기 위해선, 각 숫자들을 최소 한 번씩 사용해야 하므로 숫자의 앞자리가 큰 순으로 붙여나간다. 각 숫자들을 최소 한 번씩 사용하고 난 뒤, 추가로 사용할 숫자는 가장 큰 수가 될 것이다. 즉, 입력으로 들어오는 숫자들을 어떻게 정렬할 것인지가 문제의 핵심이 된다. 추가로 사용할 숫..

문제 링크 : www.acmicpc.net/problem/1256 1256번: 사전 첫째 줄에 N, M, K가 순서대로 주어진다. N과 M은 100보다 작거나 같은 자연수이고, K는 1,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 중복조합과 관련된 dp문제이다. a와 z를 통해 문자열을 만드는 것은 다음과 같이 생각할 수 있다. i개의 a에 대해 바깥 공간을 포함한 사이 공간들에 j개의 j를 넣는 것으로 생각하면, j개의 z를 i+1개의 공간에 넣는 가짓수가 된다. 따라서, iHj가 곧 구하는 만들 수 있는 총 문자열의 갯수가 된다. 중복조합을 계산하기 위해서는 팩토리얼이 섞인 식을 계산해야 하는데, 이 부분에서 dp를 활용할 수 있다. 굳이 증명하자면 중복조합은 다음과..

문제 링크 : www.acmicpc.net/problem/2243 2243번: 사탕상자 첫째 줄에 수정이가 사탕상자에 손을 댄 횟수 n(1≤n≤100,000)이 주어진다. 다음 n개의 줄에는 두 정수 A, B, 혹은 세 정수 A, B, C가 주어진다. A가 1인 경우는 사탕상자에서 사탕을 꺼내는 경우이다. � www.acmicpc.net 문제의 상황에서 맛있는 정도가 1인 사탕이 3개, 2인 사탕이 4개, 5인 사탕이 10개 있다고 가정하자. 이 때, 6번째 사탕과 12번째 사탕의 맛있는 정도는 얼마일까? k번째 사탕의 맛있는 정도를 알기 위해서는 각 사탕들 갯수에 대한 누적합이 필요하다. 사탕이 맛있는 정도를 d라 하자. d = 1 인 사탕은 3개, d = 2인 사탕은 4개이다. d = 2인 사탕까지의..

[서론] 크기가 1000인 배열이 있다. 이 배열의 각 원소는 1부터 10까지의 수이다. 이때 i번째 원소부터 j번째 원소까지의 합을 구하고 싶다. 어떤 방법이 좋을까? 가장 먼저 떠오르는 것은 누적합을 이용한 방법일 것이다. Sk를 Arr[0] ~ Arr[k] 까지의 모든 원소의 합이라 정의할 때, 누적합을 이용해, 구간 (i, j)의 구간합을 Sj - S(i - 1) 로 O(1)에 구할 수 있다. 이 때, Arr의 원소 중 일부가 변경된다면 어떻게 될까? 올바른 구간합을 구하기 위해서는, 누적합을 저장해 놓은 배열을 다시 갱신해야 할 것이다. 배열의 크기가 N이고, 배열값의 변경이 M회 일어날 때 Worst Case에 시간복잡도는 O(NM)이 된다. 이는 N, M의 크기가 어느 정도 커지면 시간 효율..

문제 링크 : www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가�� www.acmicpc.net 삼성 SW 역량 테스트 기출문제이다. 이 문제도 전형적인 2차원 배열에서의 BFS 문제이지만, 단순 BFS로는 해결되지 않는 부분이 있다. 문제의 조건에서, 먹을 수 있는 물고기가 1마리보다 많다면, 거리가 가장 가까운 물고기를 먹으러 간다. 거리는 아기 상어가 있는 칸에서 물고기가 있는 칸으로 이동할 때, 지나야하는 칸의 개수의 최솟값이다. 거리가 가까운 물고기가 많다면, 가장 위에 ..

문제 링크 : www.acmicpc.net/problem/1194 1194번: 달이 차오른다, 가자. 첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고, www.acmicpc.net 문제를 봤을 때 BFS로 풀어야 하는 문제이구나! 하는 느낌은 바로 받을 수 있지만, 막상 문제를 해결하려고 하면 생각이 복잡해지는 문제이다. 출구를 향해 일단 가다가 잠긴 문을 만나면 목적지를 열쇠로 바꿔가면서 가는 방법을 제일 처음 생각해 볼 수 있다. 이 방법은 각 출구마다의 최단경로 path를 기억해 놓고, 통과해야 하는 문이 어떤 문들인지를 파악한 후에 가장..

문제 링크 : www.acmicpc.net/problem/1726 1726번: 로봇 많은 공장에서 로봇이 이용되고 있다. 우리 월드 공장의 로봇은 바라보는 방향으로 궤도를 따라 움직이며, 움직이는 방향은 동, 서, 남, 북 가운데 하나이다. 로봇의 이동을 제어하는 명령어는 �� www.acmicpc.net 다소 전형적인 2차원 배열에서의 BFS 응용 문제이다. 2차원 배열의 판(Board)에 로봇(말)이 있고, 목표 지점까지의 최소 거리 등을 구하는 유형의 문제이다. [BFS에 대해] BFS (Breadth-First Search, 너비 우선 탐색) [서론] BFS는 DFS와 더불어 그래프 탐색의 기본적인 알고리즘이다. DFS로 풀 수 있는 문제의 대부분은 BFS로 풀 수 있다. 갈 수 있는 모든 노드를..