https://www.acmicpc.net/problem/20926 20926번: 얼음 미로 탐험가 테라는 얼음 미로에 갇혔다. 얼음 미로의 바닥은 빙판으로 되어 있어 발을 내디디면 바위에 부딪힐 때까지 미끄러진다. 예를 들어, 위 그림에서 테라가 왼쪽 방향으로 이동한다면 중간에 www.acmicpc.net 🐢 해설 시작하는 위치를 플레이어라고 하면 플레이어는 이동할 때 1)나가거나 2) 구멍에 빠지거나 3) 벽에 부딪히거나 4) 탈출하거나 하는 총 4가지 경우로만 이동할 수 있다. 이때 얼음을 타면서 최소한의 시간으로 탈출하는 경우를 찾아야 하는데 이를 위해 큐에 담겨있는 이동하는 플레이어 객체를 소요시간이 낮은 순으로 우선 탐색하기 위해 우선순위 큐를 이용했다. 초기 플레이어 위치를 큐에 넣어서 BF..
https://www.acmicpc.net/problem/20924 20924번: 트리의 기둥과 가지 첫 번째 줄에는 노드의 개수 $N$($1 \le N \le 200\,000$)과 루트 노드의 번호 $R$($1 \le R \le N$)이 주어진다. 이후 $N-1$개의 줄에 세 개의 정수 $a$, $b$, $d$($1 \le a, b \le N$, $ a \ne b$)가 주어진다. 이는 $a$번 www.acmicpc.net 🐢풀이 일단 트리 구조임을 알 수 있으므로 인접리스트로 트리 구조를 구현했다. 이후 기둥을 구하는 부분과 기가(G)에서 가지를 구하는 부분으로 나눠서 접근했다. 무엇보다 주어지는 간선의 정보가 방향이 아닌 무방향이므로 양방향으로 연결시켜줘야 했고, 따라서 각 노드에 대한 방문 체크를 ..
https://www.acmicpc.net/problem/20923 20923번: 숫자 할리갈리 게임 첫째 줄에는 도도와 수연이가 가지는 카드의 개수 $N$($ 1 \leq N \leq 30\,000$)과 게임 진행 횟수 $M$($ 1 \leq M \leq 2\,500\,000$)이 주어진다. 둘째 줄부터 $N$개의 줄에는 띄어쓰기로 구분하여 도도와 수연 www.acmicpc.net 🐢 접근방법 문제에서 나오는 덱(Deque) 자료구조를 사용하는 문제였다. su와 do에게 주어진 카드들을 자신의 차례 때마다 하나씩 꺼내고 조건을 확인하고 (자신의 소유 개수가 0개인지, 나의 승리 조건 인지, 상대의 승리 조건인지) turn수를 증가시키고 종료시간일 경우 종료하도록 했다. 자신의 차례때 꺼낸 카드는 순서대..
https://www.acmicpc.net/problem/2623 2623번: 음악프로그램 첫째 줄에는 가수의 수 N과 보조 PD의 수 M이 주어진다. 가수는 번호 1, 2,…,N 으로 표시한다. 둘째 줄부터 각 보조 PD가 정한 순서들이 한 줄에 하나씩 나온다. 각 줄의 맨 앞에는 보조 PD가 담당한 www.acmicpc.net 🐢문제설명 대표적인 위상정렬 문제이다. 각 pd별로 원하는 순서가 있고 모든 pd의 요구사항에 맞는 순서대로 가수를 줄세워야 한다. 이를 위해서는 의존관계를 명시해주기 위해서 인접리스트와 진입차수를 위한 배열을 사용하면 된다. 인접리스트이 용도는 A가수가 부르고 난 후 다음에 부를 수 있는 B가수를 이어주기 위한 용도이고, 진입 차수는 자신 앞에 선행되어야 할 가수의 수를 적..
https://www.acmicpc.net/problem/20005 20005번: 보스몬스터 전리품 입력의 첫째 줄에는 멤멤월드의 지도의 크기를 나타내는 두 정수 M(6 ≤ M ≤ 1000), N(6 ≤ N ≤ 1000)과 플레이어의 수 P(1 ≤ P ≤ 26)가 주어진다. M은 지도의 세로 길이, N은 지도의 가로 길이이다. 입 www.acmicpc.net 🐢해결방법1 (나의 풀이법 - 추천하지 않음) 구현 + BFS로 접근했다. 각 유저들은 1초마다 이동을하고, 보스를 만나면 죽을 때 까지 그자리에서 계속 보스를 때리고, 아직 보스를 만나지 않은 플레이어는 더 이동을 하게 했다. 플레이어는 알파벳 소문자로 들어온다고 했으나 순차적이다라는 말은 따로 없었으므로 크기가 26인 배열을 만들었고, 각 플레이..
🐢 다익스트라의 사용 Q. 다익스트라는 언제 사용하는 알고리즘일까? A. 시작점이 주어졌을때, 최소 비용으로 (혹은 최대 이익)으로 정점들을 거쳐서 다른 모든 정점까지 가는 비용을 알 수 있다. 🐢 기본 구조 // pair는 다음 노드로 가기위한 비용과 다음 노드의 정보가 들어있다 ArrayList[] adj = new ArrayList[N]; // dp는 현재 노드에서 특정 노드까지의 비용을 업데이트하기 위한 배열 int dp[N]; // 시작점을 제외한 모든 노드들에 대해 비용을 최대로 잡아준다, 시작점은 0 for (int i = 0; i < N; i++) dp[i] = INF; dp[S] = 0; adj 리스트 배열에 모든 간선들에 대해서 시작점을 기준으로 넣어준다 dp[i] == S부터 i까지의..
https://www.acmicpc.net/problem/21940 21940번: 가운데에서 만나기 위 조건을 만족하는 도시 $X$의 번호를 출력한다. 만약 가능한 도시 $X$가 여러 개인 경우는 도시의 번호를 오름차순으로 출력한다. www.acmicpc.net 🐢문제 친구들과 만나기 위한 중간 지점을 구해야하는 문제이다. 양방향 그래프가 아닌 단방향 그래프이고, 주어진 친구 위치에서 다른 모든 정점으로 도로가 있는 것이 아니므로 주의해야한다. 각 친구 위치에서 모든 정점을 중간위치 x로 놓고 비교해서 특정 x일 때 왕복거리가 가장 높은 값이 가장 낮도록 하는 x를 구하면 된다. 🐢해설 x를 구하기 위해서 다익스트라 방법과 플로이드와샬 방법을 사용할 수 있는데, 단방향이므로 친구들의 위치에서만 다익스트라..
https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 🐢문제설명 베낭에 최대한의 이익을 내면서 담는 것이 목표인 문제인데, 이러한 유형을 냅색 문제라고 한다. 냅색 문제는 대부분 dp로 풀면 되는경우가 많다. 이번 문제 또한 대표적인 냅색 문제이므로 dp로 풀어보자. 🐢풀이법 먼저 베낭에 담을 수 있는 최대 무게만큼 배열을 선언해 준다. 그러면 배열의 각 인덱스는 베낭에 담긴 무게가 ..
https://www.acmicpc.net/problem/2146 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net 모든섬들에 대해서 자신을 제외한 모든 섬들에 대한 다리를 만들고 최소값을 비교하면 최대 섬의 개수 100개일 경우 100 * 99 .. 로 100!의 경우가 나온다. 따라서 이러한 방법이 아니라 100개의 섬에 대해서 각각 다른 섬을 찾으면서 다리를 놓다가 아무 섬이든 닿으면 최단거리 다리길이 값을 갱신하고 이 이상값이 나올경우 제외하는 방법으로 하면 더 빠르게 풀수 있다. 참고로 최단 거리다리를 찾아..
https://www.acmicpc.net/problem/2539 2539번: 모자이크 수찬이는 선생님을 도와서 교실 벽면을 장식할 모자이크 그림을 그리기로 하였다. 이를 위하여 직사각형 모양의 큰 도화지를 준비하여 교실 벽에 붙이고 1cm 간격으로 가로선과 세로선을 그려서 www.acmicpc.net 이분탐색 문제를 풀어보고 있는데 항상 이분탐색에서 부등호 처리가 헷갈려서 정리해본다 이분탐색에서 범위설정하는 경우를 나눠본다면 1) 원하는 값에 부합하는 경우가 유일한 경우 2) 원하는 값에 도달하더라도 가능한 값이 더 존재할 수 있어서 하한값을 높여가며 값에 해당하는 마지막 부분을 찾는 경우 - 최대 이익 3) 원하는 값에 도달하더라도 가능한 값이 더 존재할 수 있어서 상한값을 낮춰가면서 값에 해당하는 ..
- Total
- Today
- Yesterday