CEO

문제 16916번: 부분 문자열 첫째 줄에 문자열 S, 둘째 줄에 문자열 P가 주어진다. 두 문자열은 빈 문자열이 아니며, 길이는 100만을 넘지 않는다. 또, 알파벳 소문자로만 이루어져 있다. www.acmicpc.net 문제 풀이 문자열 S, P가 주어질 때 P가 S의 부분 문자열인지 판단하여 결과를 반환하는 문제이다. 두 문자열의 길이는 100만 미만이므로 단순히 `print(int(p in s))`와 같이 풀게 되면 시간 초과가 발생한다. 따라서 `KMP 알고리즘`을 활용하여 필요 없는 곳의 탐색을 건너뛰도록 하여야 시간 내에 통과할 수 있다. 문제를 풀기 위해서는 `KMP 알고리즘`을 이해하고 구현하면 쉽게 해결할 수 있다. 코드 def make_table(): length = len(p) ta..

문제 6087번: 레이저 통신 크기가 1×1인 정사각형으로 나누어진 W×H 크기의 지도가 있다. 지도의 각 칸은 빈 칸이거나 벽이며, 두 칸은 'C'로 표시되어 있는 칸이다. 'C'로 표시되어 있는 두 칸을 레이저로 통신하기 위해서 www.acmicpc.net 문제 풀이 레이저와 레이저 사이의 통신을 하기 위해 최소한의 거울을 설치하여 통신이 가능하도록 하는 거울의 개수를 반환하는 문제이다. 문제를 풀기 위해서는 레이저가 방향을 바꾸지 않고 최대한 나아갈 수 있는 경우와, 방향을 바꾸는 경우를 생각하여 문제를 접근하면 다음과 같은 로직을 생각할 수 있다. BFS로 탐색을 시작한다. 방향을 바꾸지 않고 갈 수 있는 경로들을 최대한 탐색한다. 범위를 벗어나지 않거나, 벽이 아닌 경우를 말한다. 방향이 바뀌게..

문제 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모�� www.acmicpc.net 문제 풀이 이전에 다룬 안전 영역, 단지번호붙이기 문제와 같이 `Floodfil`을 활용하여, 접근 가능한 영역을 판단하고 그에 따라 처리하는 문제이다. 이 문제에서는 방문 가능한 영역에 대한 조건과 방문 후에 기존 인구에 대한 처리 부분이 추가된 문제이다. 현재 국가로부터 방문 가능한 인접 국가는 `L

문제 17143번: 낚시왕 낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다. www.acmicpc.net 문제 풀이 문제 요구 사항에 따라 순차적으로 구현하면 맞을 수 있는 문제이다. 낚시왕이 물고기를 잡고, 상어가 움직이는 것을 순차적으로 실행하면 문제에서 요구하는 답을 찾을 수 있다. 낚시왕이 `c + 1`, 즉 열을 한 칸 이동하여 해당 열 중 가장 땅과 가까운 행의 인덱스가 낮은 상어부터 잡게 된다. 잡은 상어는 사라지게 된다. 1초 동안 상어가 이동한다. 상어는 각각 1초에 이동할 수 있는 거리를 가지게 된다. 따라서 속도가 5라면 ..

문제 16235번: 나무 재테크 부동산 투자로 억대의 돈을 번 상도는 최근 N×N 크기의 땅을 구매했다. 상도는 손쉬운 땅 관리를 위해 땅을 1×1 크기의 칸으로 나누어 놓았다. 각각의 칸은 (r, c)로 나타내며, r은 가장 위에서부터 www.acmicpc.net 문제 풀이 시뮬레이션 문제로 문제 요구사항에 따라 그대로 구현하면 된다. 나무들은 계절에 따라 다음과 같이 나이가 변화하게 된다. 따라서 각 계절에 따른 로직을 구현하고 `K` 만큼 반복하면 답을 찾을 수 있다. 봄 나무 나이 만큼의 양분을 먹고 나이가 1 증가한다. 자신이 위치한 곳의 양분만 먹을 수 있다. 하나의 칸에 여러 개의 나무가 있다면, 나이가 어린 나무부터 양분을 섭취한다. 나무의 나이만큼 양분을 먹지 못하면 죽게 된다. 여름 봄..

문제 19236번: 청소년 상어 첫째 줄부터 4개의 줄에 각 칸의 들어있는 물고기의 정보가 1번 행부터 순서대로 주어진다. 물고기의 정보는 두 정수 ai, bi로 이루어져 있고, ai는 물고기의 번호, bi는 방향을 의미한다. 방향 bi는 www.acmicpc.net 문제 풀이 4x4 크기에 물고기들이 있고, 상어는 `(0, 0)` 부터 시작하여 물고기를 잡아먹는다. 상어는 물고기를 잡아먹으면 그 물고기의 방향에 따라서 움직일 수 있으며 해당 방향의 모든 칸에 접근이 가능하다. 상어가 물고기를 잡아먹은 후엔 물고기들은 다음과 같이 이동한다. 물고기는 한 칸씩 이동할 수 있다. 이동할 수 없는 칸은 4x4 크기를 벗어나는 영역이거나, 상어의 위치가 있는 영역이다. 이동할 수 있을 때 까지, 방향을 45도로..

문제 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가�� www.acmicpc.net 문제 풀이 아기 상어가 NxN 크기의 공간에 물고기를 먹으면서 이동 할때, 최단 시간을 반환하여야 한다. 문제에서는 아기 상어가 움직이기 위한 조건들이 존재한다. 아기 상어는 자신보다 크거나 같은 크기의 물고기는 먹을 수 없다. 가장 가까이 있는 물고기 부터 우선적으로 먹어야 한다. 여러 마리를 먹을 수 있다면, 가장 왼쪽에 있는 물고기를 우선 순위로 먹어야 한다. 문제를 처음에는 `BFS`와 `sort`를 통해 풀 었지만, `heapq`를 활용할..

문제 17089번: 세 친구 첫째 줄에 사람의 수 N(3 ≤ N ≤ 4,000), 친구 관계의 수 M(0 ≤ M ≤ 4,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계를 의미하는 두 정수 A, B가 주어진다. 친구 관계는 A와 B, 그리고 B와 A가 친� www.acmicpc.net 문제 풀이 문제에서는 N명의 사람이 있고, 세 사람을 선택할 때 세 사람이 모두 친구이고 세 사람의 친구 수의 합이 최소가 되는 경우를 찾아 반환하여야 한다. 문제의 조건에는 세 사람을 선택할 경우 세 사람은 친구에서 제외해야 한다는 조건이 있다. 처음에는 문제를 `DFS`를 통해 접근해야 하지 않나 라고 생각하였는데 세 사람을 선택하는 것을 `3중 반복문`을 통해 경우를 탐색하면 시간 초과가 발생하지 않고 문제를..