BOJ
-
[Python 3] BOJ - 2579 "계단 오르기"BOJ 2020. 3. 29. 14:24
# 문제 링크 : https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다. 예를 들어 와 같이 시작점에서부터 첫 번째, 두 번째, 네 번째, 여섯 번째 계단을 밟아 도착점에 도달하면 총 점수는 10 + 20 + 25 + 20 = 75점이 된다. 계단 오르는 데는 다음과 같은 규칙이 있다. 계단은 한 번에 한 계단씩 www.acmicpc.net # 풀이 : 개인적으로 문제의 핵심은 다이나믹 프로그래밍을 이용하는 것, 이 문제에서는 현재 계단에 올라가기 위해 이전계단에 대한 경우를..
-
[Python 3] BOJ - 1931 "회의실 배정"BOJ 2020. 3. 28. 20:21
# 문제 링크 : https://www.acmicpc.net/problem/1931 1931번: 회의실배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net # 풀이: 개인적으로 이 문제의 핵심은 그리디 알고리즘 문제라는 것과 정렬 기준을 세우는 것이다. 현재 i번째 회의를 선택한다고 하자. 이미 회의의 갯수는 정해져 있으므로 더 많은 회의를 진행하기 위해서는 i의 끝나는 시간과 i + 1의 시작되는 시간의 간격이 크면 클수록 더 많은 회의를 진행할 수 있다. 따라서 빨리 끝나는 회의일 수록 간격이 더 크다. 만일 끝나는 시간이 같다면, 일찍 시작하는 회의일 수록 간격이 더 커져 많은 회의를 진행 할 수 있다. 따라서, 회의를 정렬할 때 우선적으로 끝..
-
[Python 3] BOJ - 1929 "소수 구하기"BOJ 2020. 3. 28. 19:04
# 문제 링크 : https://www.acmicpc.net/problem/1929 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) www.acmicpc.net # 풀이 : 개인적으로 문제의 핵심은 에라토스테네스의 체를 통해 전처리하는 것이라 생각한다. N,M제한이 백만이므로 미리 백만까지의 소수 리스트를 구한다음, N,M에 따라 출력을 해주면 정답을 찾을 수 있다. 에라토스테네스의 체 알고리즘 과정은 다음과 같다. 예시를 위해 1부터 100까지의 경우만 구한다고 가정하자. 각각의 수가 소수인지를 판별하여 리스트에 넣는다면 비효율적이다. 그렇다면 어떻게 해야할까? 소수의 정의를 생각해보자. '1과 자기자신만을 약수로 갖는 수..
-
[Python 3] BOJ - 11049 "행렬 곱셈 순서"BOJ 2020. 3. 28. 00:08
# 문제 링크 : https://www.acmicpc.net/problem/11049 11049번: 행렬 곱셈 순서 첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같다. www.acmicpc.net # 풀이 : 개인적으로 이 문제의 핵심은 다이나믹 프로그래밍 문제라는 것과 x와 y번째 사이의 k라는 변수를 유도하는 것이라고 생각한다. 만일 문제로 주어진 행렬이 4개라고 가정하고, 각각의 행렬 정보가 A = 5 X 3, B = 3 X 2, C = 2 X 6, D = 6 X 7이라 하자. 곱한다는 것은 무조건 2개 이상의 행렬이 피연산자일 때만 가능하므로 아래 ..
-
[Python 3] BOJ - 14938 "서강그라운드"BOJ 2020. 3. 26. 20:02
# 문제 링크 : https://www.acmicpc.net/problem/14938 14938번: 서강그라운드 예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 하는 게임이다. 서강그라운드에서 1등을 하면 보상으로 치킨을 주는데, 예은이는 단 한번도 치킨을 먹을 수가 없었다. 자신이 치킨을 못 먹는 이유는 실력 때문이 아니라 아이템 운이 없어서라고 생각한 예은이는 낙하산에서 떨어질 때 각 지역에 아이템 들이 몇 개 있는지 알려주는 www.acmicpc.net # 풀이 : 개인적으로 문제의 핵심은 다익스트라 알고리즘을 유추할 수 있는지라고 생각한다. 다익스트라 알고리즘은 ..
-
[Python 3] BOJ - 2568 "전깃줄 2"BOJ 2020. 3. 26. 19:33
# 문제 링크 : https://www.acmicpc.net/problem/2568 2568번: 전깃줄 - 2 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100,000 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 위치의 번호가 차례로 주어진다. 위치의 번호는 500,000 이하의 자연수이고, 같은 위치에 두 개 이상의 전깃줄이 연결될 수 없다. www.acmicpc.net # 풀이 : 개인적으로 문제의 핵심은 가장 긴 증가하는 부분 수열, 즉 LIS를 유추할 수 있는지라고 생각한다. 왜냐하면 현재 왼쪽의 전봇대를 인덱스, 오른쪽의 전봇대를 값이라고 생각한다면, 문제의 조건에 따라 인덱스가 증가함에 따라 점점 ..
-
[Python 3] BOJ - 15686 "치킨 배달"BOJ 2020. 3. 24. 21:07
# 문제 링크 : https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸, 왼쪽에서부터 c번째 칸을 의미한다. r과 c는 1부터 시작한다. 이 도시에 사는 사람들은 치킨을 매우 좋아한다. 따라서, 사람들은 "치킨 거리"라는 말을 주로 사용한다. 치킨 거리는 집과 가장 가까운 치킨집 사이의 거리이다. 즉, 치킨 거리는 www.acmicpc.net # 풀이 : N,M 제한이 작으므로 브루트 포스를 이용하여 접근하였다. 총 N개의 치킨집 중 M개만 남기고 모두 제..
-
[Python 3] BOJ - 2206 "벽 부수고 이동하기"BOJ 2020. 3. 22. 22:00
# 문제 링크 : https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다. 만약에 이동하는 도중에 한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 한 개 까지 부수고 이동 www.acmicpc.net # 풀이 : 개인적으로 이 문제의 핵심은 기존의 BFS문제가 2차원 구조를 다루었다면 이 문제는 3차원 구조..