BOJ
-
[Python 3] BOJ - 1600 "말이 되고픈 원숭이"BOJ 2020. 5. 16. 21:14
# 문제 링크 : https://www.acmicpc.net/problem/1600 1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있�� www.acmicpc.net # 풀이 : 개인적으로 이 문제는 벽 부수고 이동하기와 매우 유사하게 풀 수 있다고 생각한다. 따라서, 이 문제의 핵심은 정점 나누기라고 생각한다. 전체 맵으로 보면 같은 위치지만 상태변화에 따라 해당 정점이 다른 의미를 지니기에 상태의 정보를 담을 공간을 추가적으로 만들어 줘야 한다. 또 주의해야 할 점은 말처럼 이동하는 것을 '특수 이동'이라고 할 때, 반..
-
[Python 3] BOJ - 1561 "놀이 공원"BOJ 2020. 5. 15. 16:51
# 문제 링크 : https://www.acmicpc.net/problem/1561 1561번: 놀이 공원 문제 N명의 아이들이 한 줄로 줄을 서서 놀이공원에서 1인승 놀이기구를 기다리고 있다. 이 놀이공원에는 총 M종류의 1인승 놀이기구가 있으며, 1번부터 M번까지 번호가 매겨져 있다. 모든 놀이기 www.acmicpc.net # 풀이 : 개인적으로 이 문제는 이분탐색이 핵심이라 생각한다. 실제로 최대 입력인 20억일 때 선형으로 탐색하게 되면 시간 초과를 피할 수 없기 때문이다. 따라서 k분일 때 1분부터 k분까지 총 놀이기구를 이용한 어린이 수를 계산할 수 있으면 이분 탐색을 이용해 정확히 끝나는 시간을 알 수 있다. 5개의 놀이기구가 각각 1분, 2분, 3분, 4분, 5분의 운행시간을 가지는 경우..
-
[Python 3] BOJ - 1520 "내리막 길"BOJ 2020. 5. 12. 18:19
#문제 링크 : https://www.acmicpc.net/problem/1520 1520번: 내리막 길 첫째 줄에는 지도의 세로의 크기 M과 가로의 크기 N이 빈칸을 사이에 두고 주어진다. 이어 다음 M개 줄에 걸쳐 한 줄에 N개씩 위에서부터 차례로 각 지점의 높이가 빈 칸을 사이에 두고 주어진다. www.acmicpc.net # 풀이 : 개인적으로 이 문제는 DP문제라고 생각한다. 이 문제를 풀 때 단순히 BFS, DFS를 하게 되면 같은 정점을 계속 방문하게 되므로 시간초과 및 메모리초과를 피할 수 없기 때문이다. BFS와 Bottom-Up DP로 풀수도 있고 DFS와 Top-Bottom DP로도 풀 수 있으니 취향에 따라 접근하면 되지만 이번 포스팅에서는 DFS와 Top-Bottom DP로 포스팅..
-
[Python 3] BOJ - 1517 "버블 소트"BOJ 2020. 5. 7. 19:59
# 문제 링크 : https://www.acmicpc.net/problem/1517 1517번: 버블 소트 첫째 줄에 N(1≤N≤500,000)이 주어진다. 다음 줄에는 N개의 정수로 A[1], A[2], …, A[N]이 주어진다. 각각의 A[i]는 0≤|A[i]|≤1,000,000,000의 범위에 들어있다. www.acmicpc.net # 풀이: 이 문제는 머지 소트로 푸는 방법과 펜윅 트리(세그먼트 트리)로 푸는 두가지 방법이 있는데 이번 포스팅에서는 펜윅 트리로 풀이할 예정이다. 따라서 개인적으로 이문제의 핵심은 펜윅 트리의 Inversion을 구하는 것이라 생각한다. 이전 버블소트 관련 포스팅은 몇번째 사이클만에 정렬이 완료되는지를 묻는다면 이번 버블 소트 문제는 원소를 바꾼 횟수를 구하는 문제이..
-
[Python 3] BOJ - 1463 "1로 만들기"BOJ 2020. 5. 4. 19:29
# 문제 링크 : https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net # 풀이 : 이 문제는 다이나믹 프로그래밍으로 풀 수 있다. 왜냐하면 현재 수가 i라고 한다면 3i에서 3으로 나눠서 오는 방법이 있고, 2i에서 2로 나눠서 오는 방법, 마지막으로 i + 1에서 1을 빼서 i로 오는 방법 총 세가지가 있기 때문이다. 따라서 경우가 작은 경우로 나눌 수 있고 그것이 연관되어있기 때문에 이 문제는 다이나믹 프로그래밍이라 할 수 있다. 따라서 점화식은 아래의 그림과 같다 점화식의 첫번째 경우는 i가 2로만 나누어 떨어지는 경우는 i/2와 i-1에서 i로 올 수 있..
-
[Python 3] BOJ - 1413 "박스 안의 열쇠"BOJ 2020. 5. 3. 17:58
# 문제 링크 : https://www.acmicpc.net/problem/1413 1413번: 박스 안의 열쇠 첫째 줄에 박스와 열쇠의 개수 N과 폭탄의 개수 M이 공백을 사이에 두고 주어진다. N은 20보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다. www.acmicpc.net # 풀이 : 개인적으로 이 문제의 핵심은 제1종 스털링 수를 이해하는 것이다. 제1종 스털링 수에 대한 설명은 여기를 참고하면 된다. 그런데 사실 이 문제는 제1종 스털링 수를 모른다 해도 충분히 풀 수 있다. 그림 1은 상자가 3개일 때 가능한 6가지 경우의 수를 나타낸 것이다. 빨간색 글자들로 나타낸 조합은 폭탄이 3개가 있어야 모든 상자를 열 수 있는 조합이다. 파란색 글자들로 나타낸 조합은 폭탄이 2..
-
[Python 3] BOJ - 1406 "에디터"BOJ 2020. 5. 2. 23:18
# 문제 링크 : https://www.acmicpc.net/problem/1406 1406번: 에디터 문제 한 줄로 된 간단한 에디터를 구현하려고 한다. 이 편집기는 영어 소문자만을 기록할 수 있는 편집기로, 최대 600,000글자까지 입력할 수 있다. 이 편집기에는 '커서'라는 것이 있는데, 커서는 문장의 맨 앞(첫 번째 문자의 왼쪽), 문장의 맨 뒤(마지막 문자의 오른쪽), 또는 문장 중간 임의의 곳(모든 연속된 두 문자 사이)에 위치할 수 있다. 즉 길이가 L인 문자열이 현재 편집기에 입력되어 있으면, 커서가 위치할 수 있는 곳은 L+1가지 경우가 www.acmicpc.net # 풀이 : 개인적으로 이 문제는 커서의 위치를 굳이 구하지 않아도 된다는 점과 스택을 이용해야 한다. 문제의 시간제한이 ..
-
[Python 3] BOJ - 1377 "버블 소트"BOJ 2020. 4. 29. 16:51
# 문제 링크 : https://www.acmicpc.net/problem/1377 1377번: 버블 소트 첫째 줄에 N이 주어진다. N은 500,000보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 A[1]부터 A[N]까지 하나씩 주어진다. A에 들어있는 수는 1,000,000보다 작거나 같은 자연수 또는 0이다. www.acmicpc.net # 풀이 : 개인적으로 이 문제의 핵심은 규칙성 이해라고 생각한다. 위 그림 1은 버블 소팅의 바깥 반복문, 즉 i가 1인 경우이다. 첫번째 사이클이 끝나면 배열의 최대값 10은 교환을 통해 맨 마지막 인덱스에 들어간다. 마지막 인덱스에 들어갈 수 밖에 없으므로 10은 인덱스가 계속 증가한다. 반대로, 10과 교환되는 수들(2, 5, 3)은 인덱스가 감소한..