본문 바로가기

문제 해결/BOJ117

[백준] 택배 https://www.acmicpc.net/problem/1719 1719번: 택배 첫째 줄에 두 수 n과 m이 빈 칸을 사이에 두고 순서대로 주어진다. n은 집하장의 개수로 200이하의 자연수, m은 집하장간 경로의 개수로 10000이하의 자연수이다. 이어서 한 줄에 하나씩 집하장간 경 www.acmicpc.net 1. 문제 이해 모든 집하장간의 최단 경로로 이동하는 경로에 가장 먼저 방문해야하는 지점을 찾는 문제입니다. 2. 문제 접근 첫번째 접근: 플로이드 와샬 모든 집하장간의 최단 경로를 찾아야 하기에 플로이드 와샬을 먼저 떠올렸습니다. 제가 문제를 처음 읽었을 때 놓쳤던 부분이 가장 먼저 방문해야하는 지점인데 가장 마지막 지점을 출력하고 있어서 틀렸었습니다. 가장 먼저 방문해야하는 지점을 찾는 .. 2023. 4. 20.
[백준] 로봇 https://www.acmicpc.net/problem/1726 1726번: 로봇 많은 공장에서 로봇이 이용되고 있다. 우리 월드 공장의 로봇은 바라보는 방향으로 궤도를 따라 움직이며, 움직이는 방향은 동, 서, 남, 북 가운데 하나이다. 로봇의 이동을 제어하는 명령어는 www.acmicpc.net 1. 문제 이해 로봇을 움직일 때 명령어가 한번 수행됩니다. 1 ~ 3만큼 이동시킬 수 있는 Go K 명령어와 왼쪽, 오른쪽으로 90도 만큼 움직일 수 있는 Turn dir 명령어가 있습니다. 출발지점과 현재 바라보는 방향에서 출발하여 도착지점에서 주어진 방향으로 바라볼 수 있기 위해 필요한 최소 명령어를 출력하면 됩니다. 2. 문제 접근 첫번째 접근: BFS 3차원 dist 배열과 heap을 사용한 BFS.. 2023. 4. 19.
[백준] ACM Craft https://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 1. 문제 이해 스타크래프트처럼 건물 순서 규칙이 주어집니다. 그리고 건물을 지어지는데 소요시간이 걸리게 됩니다. 이 문제의 목표느는 건물 순서 규칙에 따라서 건물을 지었을 때 특정 건물을 짓는 데 걸리는 최소 시간을 구하는 문제입니다. 2. 문제 접근 첫번째 접근: 위상정렬 그래프가 단방향 간선으로 이루어져 있고 순서에 따라서 건물들이 지어져야하는 것을 보고 위상정렬을 떠올릴 수 있었습니다.. 2023. 4. 18.
[백준] 우주신과의 교감 https://www.acmicpc.net/problem/1774 1774번: 우주신과의 교감 (1,1) (3,1) (2,3) (4,3) 이렇게 우주신들과 황선자씨의 좌표가 주어졌고 1번하고 4번이 연결되어 있다. 그렇다면 1번하고 2번을 잇는 통로를 만들고 3번하고 4번을 잇는 통로를 만들면 신들과 선자씨끼 www.acmicpc.net 1. 문제 이해 황선자씨와 연결되어 있는 우주신 네트워크에 새로운 우주신들이 추가되었습니다. 우주신들끼리 통신이 가능하므로 우주신 - 우주신, 황선자 - 우주신들간에 통로를 연결하고자 하는데 새로 만들어야 할 정신적인 통로들의 길이의 합이 최소가 되도록 해야합니다. 2. 문제 접근 첫번째 접근: 최소 스패닝 트리 문제를 읽자마자 최소 스패닝 트리를 구축하는 문제임을 알 .. 2023. 4. 18.
[백준] 수확 https://www.acmicpc.net/problem/1823 1823번: 수확 첫째 줄에 벼의 개수 N(1 ≤ N ≤ 2,000)이 주어지고 두 번째 줄부터 N+1번쨰 줄까지 벼의 가치 v(i) (1 ≤ v(i) ≤ 1,000) 가 주어진다. www.acmicpc.net 1. 문제 이해 1XN의 긴 밭의에 벼가 있고 양쪽 끝에서만 벼를 수확할 수 있습니다. 벼를 수확할 때 얻을 수 있는 이익은 K일에 수확할 경우 (벼의 가치 * K)를 얻을 수 있게 됩니다. 따라서, 양끝에서 벼를 어떤 순서로 수확하느냐에 따라 얻을 수 있는 이익이 달라지게 되는데 이중 얻을 수 있는 최대 이익을 계산해야합니다. 2. 문제 접근 첫번째 접근: 그리디 양쪽 끝에서만 벼를 수확할 수 있으므로 deque를 생각했습니다. .. 2023. 4. 17.
[백준] 웜홀 https://www.acmicpc.net/problem/1865 1865번: 웜홀 첫 번째 줄에는 테스트케이스의 개수 TC(1 ≤ TC ≤ 5)가 주어진다. 그리고 두 번째 줄부터 TC개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는 지점의 수 N(1 ≤ N ≤ 500), www.acmicpc.net 음의 가중치가 있는 그래프에서 음의 사이클이 있는지 여부를 체크하는 문제입니다. 벨만포드의 개선버전인 SPFA 알고리즘을 활용하여 풀이하였습니다. 분리되어 있는 그래프가 있을 수 있어서 Visited 배열을 통하여 방문되지 않은 그래프가 있으면 해당 그래프에서 음의 사이클이 있는지를 체크해주도록 하였습니다. 최단경로와 관련된 알고리즘들이 많습니다. 다익스트라, 벨만포드, 플로이드와샬,.. 2023. 4. 16.
[백준] 욕심쟁이 판다 https://www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에 www.acmicpc.net DP를 활용하여 풀이하였습니다. 대나무의 수가 증가하는 방향으로 움직어야합니다. 반대로, 대나무의 수가 감소하는 방향으로 움직여도 됩니다. 저는 대나무의 수를 큰 수로 내림차순으로 정렬을 하고 현재 대나무의 위치에서 사방탐색을 진행해주면 DP 배열을 채워주면 됩니다. 만약, 현재 대나무의 수보다 작은 대나무 숲이 인접해있다면 현재 대나무 숲에서 이동이 가능합니다. 따라서, 현재까지 이동.. 2023. 4. 15.
[백준] 로고 https://www.acmicpc.net/problem/3108 3108번: 로고 로고는 주로 교육용에 쓰이는 프로그래밍 언어이다. 로고의 가장 큰 특징은 거북이 로봇인데, 사용자는 이 거북이 로봇을 움직이는 명령을 입력해 화면에 도형을 그릴 수 있다. 거북이는 위치와 www.acmicpc.net 개인적으로 재미있었던 문제입니다. 유니온-파인드를 활용하여 푸는 문제입니다. 이 문제의 포인트는 3가지입니다. 첫번째는 연필을 올리기는 작업이 필요한 경우는 서로 포함관계가 없는 직사각형이 존재할 때 연필 올리기 작업이 필요하다는 것입니다. 따라서, 겹치는 사각형들은 하나의 그룹으로 만들어주면 됩니다. 두번째는 포함관계를 어떻게 찾을 것인가에 대한 것입니다. 저는 한 직사각형의 가로변과 다른 사각형의 세로변이.. 2023. 4. 14.
[백준] 중량제한 https://www.acmicpc.net/problem/1939 1939번: 중량제한 첫째 줄에 N, M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1 ≤ A, B ≤ N), C(1 ≤ C ≤ 1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 www.acmicpc.net 다익스트라를 활용하여 풀이하였습니다. 시작점에서 도착점으로 도달할 수 있는 경로 중에서 현재 노드까지 도달할 수 이:있는 최대 중량치와 다음 노드로 가는 간선의 중량치 중 더 작은 중량치를 선택하고 기존에 다음 노드까지 갈 수 있는 중량치보다 더 크면 갱신이 가능하게 됩니다. 이렇게 수행하면 각 노드까지 옮길 수 있는 최대 중량치가 저장이.. 2023. 4. 14.

티스토리툴바