BOJ
-
[Python 3] BOJ - 1689 "겹치는 선분"BOJ 2020. 6. 24. 10:58
# 문제 링크 : https://www.acmicpc.net/problem/1689 1689번: 겹치는 선분 첫째 줄에는 선분의 개수(1 ≤ N ≤ 1,000,000)가 입력으로 들어온다. 그 다음 N개의 줄에 선분의 시작 좌표와 끝나는 좌표가 입력으로 들어온다. 선분의 좌표는 절댓값이 10억보다 작거나 같은 정수� www.acmicpc.net # 풀이 : 이 문제의 핵심은 정렬과 정보 추가라고 생각한다. 단순히 점을 나열한다면 선분에 대한 정보를 알 수 없다. 만일 (0,2), (1,3)이라는 점 2개가 주어졌다고 하자. 그렇다면 점들의 리스트인 [0,2,1,3]으로는 어떤 선분이 어디에서 겹치는지 알 수 없다. 물론 이중 for문을 사용하면 구할 수는 있지만 N이 백만이기 때문에 시간초과를 피할 수 ..
-
[Python 3] BOJ - 1688 "지민이의 테러"BOJ 2020. 6. 23. 19:05
# 문제 링크 : https://www.acmicpc.net/problem/1688 1688번: 지민이의 테러 첫째 줄에 방어막의 꼭짓점의 개수 N(3 ≤ N ≤ 10,000)이 주어진다. 이어서 N개의 줄에는 꼭짓점들의 좌표가 순서대로 주어진다. 시계방향으로 주어질 수도 있고, 반시계방향으로 주어질 수도 있�� www.acmicpc.net # 풀이 : 개인적으로 이 문제의 핵심은 CCW라고 생각한다. CCW란 세 점의 좌표가 주어졌을 때 세 점이 놓인 방향이 반시계 방향인지, 시계 방향인지, 일직선 상인지 판별하는 알고리즘이다. 현재 빨간점을 시작점으로 하고 파란점을 경유하면서 초록점을 끝점으로 하는 경로의 진행방향은 시계방향이다. 그런데 반대로 초록점을 시작점으로 하고 파란점을 경유하면서 빨간점을 끝..
-
[Python 3] BOJ - 1658 "돼지 잡기"BOJ 2020. 6. 1. 23:48
# 문제 링크 : https://www.acmicpc.net/problem/1658 1658번: 돼지 잡기 문제 종혁이는 자물쇠로 잠긴 M개의 돼지우리가 있는 농장에서 일하고 있다. 종혁이는 열쇠가 없기 때문에 우리들을 열지 못한다. 이 농장에 손님들은 하루에 한 명씩 방문한다. 이들은 몇몇 우� www.acmicpc.net # 풀이 : 개인적으로 이 문제의 핵심은 최대 유량이라고 생각한다. 그보다도 어떻게 최대 유량을 모델링하는지가 더 핵심이라고 생각한다. 현재 그림 1과 같은 그래프가 존재한다고 가정하자. 이 때 각 간선은 단방향 간선이고 간선에 쓰여있는 표기 n/m에서 m은 정점 a에서 정점 b로 보낼 수 있는 유량이라고 하고 n은 실제로 정점 a에서 정점 b로 보낸 유량이라고 하자. 정점 a에서 ..
-
[Python 3] BOJ - 1657 "두부장수 장홍준"BOJ 2020. 5. 30. 09:28
# 문제 링크 : https://www.acmicpc.net/problem/1657 1657번: 두부장수 장홍준 첫째 줄에는 두부판의 세로크기 N, 가로크기 M이 주어진다. N, M은 1이상 14이하의 정수이다. 그 다음 N줄에 걸쳐 M개의 문자가 주어진다. 각 문자는 그 칸의 두부의 등급을 나타내며 A, B, C, D, F 중 �� www.acmicpc.net # 풀이 : 이 문제는 앞서 포스팅한 격자판 채우기와 매우 유사한 문제이다. 다만 차이가 있다면 격자판 채우기는 그냥 방법의 수를 모두 더하는 것이라면 이번 문제는 두부를 자르는 모든 경우의 가격 중 최대값을 구하는 문제이다. 추가적으로 격자판 채우기는 빈칸이 없게 모든 칸을 채워야 했지만 이 문제는 빈칸이 있어도 된다는 점이 차이점이다. 따라서..
-
[Python 3] BOJ - 1655 "가운데를 말해요"BOJ 2020. 5. 27. 16:40
# 문제 링크 : https://www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 수빈이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 수빈이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net # 풀이 : 이 문제의 핵심은 중앙값의 특성을 파악하는 것이다. 결론적으로는 최대 힙과 최소 힙의 이용인데 중앙값의 특성을 이용하면 왜 최대힙과 최소힙을 써야하는지 알 수 있다. 그림 1에서는 홀수일 때의 경우와 짝수일 때의 경우를 나타내었다. 홀수인 경우 중앙값은 3이다. 짝수인 경우 중앙값은 문제의 조건에 따라 2와 3중 더 작은 수라고 했기 때문에 2이다. ..
-
[Python 3] BOJ - 1648 "격자판 채우기"BOJ 2020. 5. 25. 15:50
# 문제 링크 : https://www.acmicpc.net/problem/1648 1648번: 격자판 채우기 준규는 침대에 누워서 천장을 바라보고 있었다. 천장은 격자판 모양이었고, 계속해서 천장을 바라보다 보니 이런 생각이 들었다. 세로 크기가 N이고, 가로 크기가 M인 격자판을 2x1 크기의 도미노 www.acmicpc.net # 풀이 : 이 문제를 풀면 타일링 문제들을 쉽게 풀 수 있다. 왜냐하면 BOJ 타일링 문제들은 N혹은 M을 고정시키지만 이 문제는 N과 M이 변하기 때문이다. 개인적으로 이 문제는 비트마스킹을 이용한 다이나믹 프로그래밍이 핵심이라고 생각한다. 우선 다이나믹 프로그래밍인 이유는 어떤 칸을 (i, j)라고 한다면 (i, j - 1)에서 옆으로 채울 수도 있고 (i - 1, j)..
-
[Python 3] BOJ - 1629 "곱셈"BOJ 2020. 5. 23. 18:06
# 문제 링크 : https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net # 풀이 : 개인적으로 이 문제는 이진수를 이용하는 것이라 생각한다. 물론 파이썬 내장 함수중 pow(x,y,z)를 통해서 한 줄만에 해결할 수 있지만, 이진수를 이용하여 a의 b승을 c로 나눈 나머지를 구하는 방식은 차후에 행렬의 제곱에서도 유효하기 때문에 이진수를 이용한 방법을 통해 푸는것이 낫다. a의 19승을 구하는 경우를 생각해보자. 선형으로 계속 a를 곱해나가면 19번의 곱셈이 필요하므로 만일 문제의 입력이 극단적으로 커지는 경우는 ..
-
[Python 3] BOJ - 1562 "계단 수"BOJ 2020. 5. 19. 19:05
#문제 링크 : https://www.acmicpc.net/problem/1562 1562번: 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net # 풀이 : 문제 풀이에 앞서 비트 연산에 대한 개괄적인 이해를 하고 본 포스팅을 본다면 이해에 도움이 될 것이다. 개인적으로 이 문제의 핵심은 비트마스킹을 이용한 다이나믹 프로그래밍이라고 생각한다. 문제에서 계단 수란 각 자릿수의 차이가 1인 수를 의미하고 특히 0부터 9까지의 수를 모두 사용해야 한다. 추가적으로 0으로 시작하는 수는 없다. 그림 1에서는 앞 세자리는 계단수로 이루어져 있다. 그런데 여기서 4자리 수가 되려면 ?자리에 당연히 6이 들어와야 한다. 그런데 문제에서 입력이 자릿수이고 계단..