분류 전체보기
-
[Python 3] BOJ - 13398 "연속합 2"BOJ 2021. 9. 3. 00:52
# 문제 링크 https://www.acmicpc.net/problem/13398 13398번: 연속합 2 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net # 풀이 개인적으로 이 문제의 핵심은 다이나믹 프로그래밍이라고 생각한다. 우선 수를 하나도 빼지 않고 연속한 수들을 더해 최대값을 구하는 것부터 구해보자. 위 그림 1은 현재 3을 선택하는 경우를 나타낸다. 문제에서 연속해야한다고 했기 때문에 이전의 -10을 유지한채 3을 더해야 한다. 그런데 이전의 연속합을 무시하고 지금부터 다시 연속합을 만드는 경우도 있다. 따라서, select의 ..
-
[Python 3] BOJ - 17619 "개구리 점프"BOJ 2021. 9. 1. 14:25
# 문제 링크 https://www.acmicpc.net/problem/17619 17619번: 개구리 점프 첫 번째 줄에 통나무 개수 N과 질문의 개수 Q가 주어진다. 다음 N개의 줄에 각 통나무에 x1, x2, y의 세 정수 좌표가 주어진다. 주어진 통나무는 두 점 (x1, y)와 (x2, y)를 잇는 형태이다. (x1 < x2) 모든 www.acmicpc.net # 풀이 개인적으로 이 문제의 핵심은 정렬과 유니온 파인드라고 생각한다. 위 그림 1에서는 임의의 5개의 선분이 나타나 있다. 현재 a 선분과 d 선분은 겹쳐져 있지 않지만 점프를 통해서 갈 수 있다. 왜냐하면 a에서 b로, b에서 d로 가면 도착할 수 있기 때문이다. c와 d 역시 마찬가지이다. 그러나, e는 자기자신을 제외한 어느 선분도..
-
[Python 3] BOJ - 5721 "사탕 줍기 대회"BOJ 2021. 8. 31. 22:48
# 문제 링크 https://www.acmicpc.net/problem/5721 5721번: 사탕 줍기 대회 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 M과 N이 주어졌다. (1 ≤ M × N ≤ 105) 다음 M개 줄에는 박스에 들어있는 사탕의 개수 N개가 주어진다. 박스에 들 www.acmicpc.net # 풀이 개인적으로 이 문제의 핵심은 다이나믹 프로그래밍이라고 생각한다. 그림 1은 한 행을 기준으로 한 상태 공간 배열을 채우는 것을 나타낸다. 즉, 이 때의 상태 공간은 col[row][idx][status]이며 의미는 현재 row행을 기준으로 idx번째 열에서 status의 상태에 따라 얻을 수 있는 사탕의 최대 갯수이다. 문제의 조건에 따라 현재 열을 선..
-
[Python 3] BOJ - 1162 "도로포장"BOJ 2021. 8. 30. 12:07
# 문제 링크 https://www.acmicpc.net/problem/1162 1162번: 도로포장 첫 줄에는 도시의 수 N(1 ≤ N ≤ 10,000)과 도로의 수 M(1 ≤ M ≤ 50,000)과 포장할 도로의 수 K(1 ≤ K ≤ 20)가 공백으로 구분되어 주어진다. M개의 줄에 대해 도로가 연결하는 두 도시와 도로를 통과하 www.acmicpc.net # 풀이 개인적으로 이 문제의 핵심은 2차원 다익스트라 알고리즘이라고 생각한다. 일반적으로 다익스트라 알고리즘은 1차원 배열이지만, 이 문제에는 정점과 또 다른 정보인 포장 횟수가 있으며 포장 여부에 따라 간선의 가중치가 달라지기 때문에 1차원으로 설정한다면 포장에 대한 정보를 알 수 없다. 따라서, 포장을 시키지 않는 경우를 기본적으로 검사한 후..
-
[Python 3] BOJ - 2151 "거울 설치"BOJ 2021. 8. 26. 22:36
# 문제 링크 https://www.acmicpc.net/problem/2151 2151번: 거울 설치 첫째 줄에 집의 크기 N (2 ≤ N ≤ 50)이 주어진다. 다음 N개의 줄에는 N개의 문자로 집에 대한 정보가 주어진다. ‘#’는 문이 설치된 곳으로 항상 두 곳이며, ‘.’은 아무 것도 없는 것으로 빛은 www.acmicpc.net # 풀이 개인적으로 이 문제의 핵심은 BFS라고 생각한다. 문제를 많이 풀었다면 0-1 BFS 혹은 우선순위 큐를 이용한 BFS가 떠오를 것이다. 어느쪽으로 풀어도 정답을 도출할 수 있으나 이번 포스팅은 0-1 BFS로 풀어보겠다. 0-1 BFS에 대해 간략히 설명하자면, 일반적인 BFS에서는 간선의 모든 가중치가 1인데 반해 가중치가 0 혹은 1로만 이루어진 그래프의 ..
-
[Python 3] BOJ - 1933 "스카이라인"BOJ 2021. 8. 25. 21:26
# 문제 링크 https://www.acmicpc.net/problem/1933 1933번: 스카이라인 첫째 줄에 건물의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 N개의 건물에 대한 정보가 주어진다. 건물에 대한 정보는 세 정수 L, H, R로 나타나는데, 각각 건물의 왼쪽 x좌표, 높이, 오 www.acmicpc.net # 풀이 개인적으로 이 문제의 핵심은 우선순위 큐와 정렬과 set의 적절한 사용이라고 생각한다. 고려해야 할 것이 많은 어려운 문제이다. 위 사진은 문제 링크에 있는 사진을 발췌한 것에 약간의 수정을 한 것이다. 빨간 점은 갑자기 높이가 상승했기 때문에 스카이라인의 경계가 되는 부분이며, 파란 점은 갑자기 높이가 하강했기 때문에 스카이라인의 경계가 되는 부..
-
[Python 3] BOJ - 1700 "멀티탭 스케줄링"BOJ 2021. 8. 24. 20:56
# 문제 링크 https://www.acmicpc.net/problem/1700 1700번: 멀티탭 스케줄링 기숙사에서 살고 있는 준규는 한 개의 멀티탭을 이용하고 있다. 준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등 여러 개의 전기용품을 사용하면서 어쩔 수 없이 각종 전 www.acmicpc.net # 풀이 개인적으로 이 문제의 핵심은 그리디 알고리즘이라고 생각한다. 왜냐하면 현재 모든 구멍이 사용중이라면 어떤 하나를 뽑을 때 가장 나중에 사용할 전자기기를 뽑는 것이 최적이기 때문이다. 아주 간략한 증명은 다음과 같다. 현재 구멍이 모두 사용중이고 다음에 써야 할 전자기기를 A라고 하자. 만일 이 때 A가 구멍에 꽂혀있다면 A를 굳이 뽑아야 할 필요는 없다. 만약 A를 뽑는다면..
-
[Python 3] BOJ - 16681 "등산"BOJ 2021. 8. 20. 18:55
# 문제 링크 https://www.acmicpc.net/problem/16681 16681번: 등산 첫 번째 줄에 지도에 표시된 지점의 개수, 지점을 잇는 경로의 개수, 주환이의 거리 비례 체력 소모량, 높이 비례 성취감 획득량을 나타내는 정수 N, M, D, E가 공백을 사이에 두고 주어진다. (2 ≤ www.acmicpc.net # 풀이 개인적으로 이 문제의 핵심은 대칭성을 이용하는 것이다. 문제에서 집에서 목표까지는 높이가 증가하는 방향, 목표에서 학교까지는 높이가 감소하는 방향으로 가는 조건이 있다. 따라서 학교에서 높이까지는 높이가 증가하는 방향이라고 할 수 있다. 그런데 집-목표-학교의 최소 거리는 집-목표 + 목표-학교의 각각의 최소 거리의 합보다 더 작을 수 없다. 따라서, 높이가 증가하..