baekjoon20 [백준 5214번] 환승 난이도: 골드 I 문제 링크: https://www.acmicpc.net/problem/5214 5214번: 환승 첫째 줄에 역의 수 N과 한 하이퍼튜브가 서로 연결하는 역의 개수 K, 하이퍼튜브의 개수 M이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ K, M ≤ 1000) 다음 M개 줄에는 하이퍼튜브의 정보가 한 줄에 하나씩 주어 www.acmicpc.net 각 노드와 연결 정보가 주어지고, 시작점으로부터 도착점까지 최단 거리를 구하면 되는 문제입니다. 단순하게 접근했다가 틀렸는데, 문제의 조건을 분석해 봅시다. 한 튜브에 최대 1000개의 역이 연결되어 있고, 튜브는 최대 1000개 존재합니다. 이것을 튜브에 연결된 모든 역이 서로 연결되어 있는 방식으로 구현하면, O(n^3)의 공간복잡도를 .. 2021. 10. 26. [백준 2304번] 창고 다각형 난이도: 실버 II 문제 링크: https://www.acmicpc.net/problem/2304 2304번: 창고 다각형 첫 줄에는 기둥의 개수를 나타내는 정수 N이 주어진다. N은 1 이상 1,000 이하이다. 그 다음 N 개의 줄에는 각 줄에 각 기둥의 왼쪽 면의 위치를 나타내는 정수 L과 높이를 나타내는 정수 H가 한 개의 www.acmicpc.net 단순 구현 문제입니다. 문제에서 주어진 넓이를 구하려면 다음과 같은 과정을 거치면 됩니다. 가장 높은 기둥의 높이를 미리 구해둔다. 이후 모든 기둥을 좌표 순으로 정렬한다. 좌, 우 양 끝에서 다음과 같은 과정을 거친다. 시작점의 위치와 높이를 기록한다. 가장 높은 기둥 방향으로 전진하며, 이전에 기록한 높이보다 더 높은 기둥을 찾은 경우 아래와 같.. 2021. 10. 22. [백준 23090번] 난민 난이도: 골드 I 문제 링크: https://www.acmicpc.net/problem/23090 23090번: 난민 문제의 답을 공백으로 구분하여 \(N\)줄에 걸쳐 출력한다. \(i\)번째 줄에, \(1\)번째 부터 \(i\)번째까지 이주해온 난민들이 정수시설까지 이동하는 거리의 합이 최소가 되도록 하는 정수시설의 \(y\ www.acmicpc.net 백준에서 새로 추가된 문제들을 보다가 모교 프로그래밍 대회에 나왔던 문제길래 한번 풀어 봤습니다. x = 0을 따라서 강이 흐르고 있고, 정화 시설은 강 위에 설치하게 됩니다. 매번 설치된 모든 난민촌에서 정화 시설까지의 거리의 합이 최소가 되는 곳에 정화 시설을 설치하고, 거리가 최소가 되는 곳이 2개 이상 존재하는 경우, y값이 가장 낮은 곳에 설치.. 2021. 10. 12. [백준 1856번] 웜홀 난이도: 골드 III 문제 링크: https://www.acmicpc.net/problem/1865 1865번: 웜홀 첫 번째 줄에는 테스트케이스의 개수 TC(1 ≤ TC ≤ 5)가 주어진다. 그리고 두 번째 줄부터 TC개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는 지점의 수 N(1 ≤ N ≤ 500), www.acmicpc.net 이 문제는 최단거리 문제인데, 노드와 노드 사이의 거리가 음수인 경우가 존재하는 특이한 경우입니다. 이를 위해 벨만-포드 (Bellman-ford) 알고리즘을 사용해야 합니다. 벨만-포드 알고리즘은 예전에 최단거리 알고리즘을 다루면서 언급한 적이 있는데, 언급만 하고 자세히 다루지는 않았습니다. 알고리즘에 대한 설명은 여기를 참고하였습니다. 총 노드의.. 2021. 10. 2. [백준 1943번] 동전 분배 난이도: 골드 III 문제 링크: https://www.acmicpc.net/problem/1943 1943번: 동전 분배 세 개의 입력이 주어진다. 각 입력의 첫째 줄에 동전의 종류 N(1≤N≤100)이 주어진다. 각 입력의 둘째 줄부터 N+1째 줄까지 각각의 동전의 금액과 개수가 빈 칸을 사이에 두고 주어진다. 단, 원장선 www.acmicpc.net DP를 통해 접근할 수 있는 문제입니다. 그리디로 왜 안 되는지는... 잘 모르겠네요 ㅠ 모든 동전의 값의 합을 먼저 구하고, 이것이 홀수라면 반으로 나눌 수 없으므로 0을 출력하고 넘어갑니다. 짝수라면, 총 값의 반을 최대 기준으로, 만들 수 있다면 해당 테이블에 1을 기록하며 진행합니다. 이전 인덱스의 값을 참조하여 진행하기 때문에 탑-다운 방식으로.. 2021. 9. 30. [백준 1823번] 수확 난이도: 골드 III 문제 링크: https://www.acmicpc.net/problem/1823 1823번: 수확 첫째 줄에 벼의 개수 N(1 ≤ N ≤ 2,000)이 주어지고 두 번째 줄부터 N+1번쨰 줄까지 벼의 가치 v(i) (1 ≤ v(i) ≤ 1,000) 가 주어진다. www.acmicpc.net 벼가 한 줄로 쭉 세워져 있고, 벼의 가치는 각각 입력으로 들어옵니다. 벼를 나중에 수확할수록 이익을 더 얻기 때문에, 끝까지 가 봐야 알 수 있으므로 그리디 방식으로는 해결할 수 없습니다. 이 문제의 경우, DP를 이용하여 접근할 수 있습니다. 보통 DP 문제의 경우 맨 마지막 값이 정답이 되는데, 이 문제의 경우 배열의 앞과 뒤를 좁혀 가며 탐색을 하므로, 중간의 어느 지점이 맨 마지막에 탐색하.. 2021. 9. 29. 이전 1 2 3 4 다음
