분류 전체보기
-
[Python 3] BOJ - 1701 "Cubeditor"BOJ 2020. 7. 8. 14:30
# 문제 링크 : https://www.acmicpc.net/problem/1701 1701번: Cubeditor 문제 Cubelover는 프로그래밍 언어 Whitespace의 코딩을 도와주는 언어인 Cubelang을 만들었다. Cubelang을 이용해 코딩을 하다보니, 점점 이 언어에 맞는 새로운 에디터가 필요하게 되었다. 오랜 시간 고�� www.acmicpc.net # 풀이 : 이 문제의 핵심은 failure 배열의 이해이다. 우선 failure 배열이 무엇인지 알기전에 문제의 설명에 대해 예시를 통해 이해해보자. 문제의 설명의 골자는 현재 어떤 문자열 s에서 2번 이상 나타나는 부분문자열 중 길이가 가장 긴 것의 길이를 출력하라는 것이다. 현재 그림 1은 길이가 1이고 최소 2번 이상 출현하는 부..
-
[Python 3] BOJ - 1697 "숨바꼭질"BOJ 2020. 6. 25. 10:42
# 문제 링크 : https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 문제 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 www.acmicpc.net # 풀이 : 개인적으로 이 문제의 핵심은 BFS라고 생각한다. 비록 문제에 직접적으로 그래프는 없지만 BFS형식으로 풀 수 있다. BFS/DFS의 핵심은 정점을 한번만 방문하는 것이다. 그런데 이 문제에서 만일 2초 후 위치가 7이 된다고 가정하자. 그런데 또 5초 후 위치가 7이라면 이는 방문하지 않아도 된다. 왜냐하면 만일 동생의 위치가 7이라면 2..
-
[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)..