문제 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`를 활용할..
문제 코딩테스트 연습 - 단속카메라 [[-20,15], [-14,-5], [-18,-13], [-5,-3]] 2 programmers.co.kr 문제 풀이 고속도로를 이동하는 모든 차량이 고속도로를 이용하면서 단속용 카메라를 한 번은 만나도록 카메라를 설치하여야 한다. 이때 최소 몇 대의 카메라를 설치해야 하는지 반환하는 문제이다. 처음에 문제를 접하였을 때는 카메라를 만났는지 모든 구간을 확인하며 문제를 풀고자 하였다. 정답은 맞았지만 다른 사람들이 푼 코드를 보니 더 짧고, 빠르게 풀 수 있는 방법이 있었다.😂 설치된 카메라를 진입 지점으로 갱신해 가며, 진입 지점이 설치된 카메라의 위치보다 작다면 카메라를 추가하고 위치를 갱신하면 `O(N)`의 시간으로 문제를 해결할 수 있다. 코드 from mat..
문제 코딩테스트 연습 - 디스크 컨트롤러 하드디스크는 한 번에 하나의 작업만 수행할 수 있습니다. 디스크 컨트롤러를 구현하는 방법은 여러 가지가 있습니다. 가장 일반적인 방법은 요청이 들어온 순서대로 처리하는 것입니다. 예를�� programmers.co.kr 문제 풀이 하드 디스크의 요청된 작업을 작업이 종료되는 시간이 빠른 순으로 처리하도록 하여 평균 처리 시간을 반환하는 문제이다. 요청된 작업 순으로 정렬 후에 처리할 작업을 하나씩 `pop`하여 `heap`을 통해 처리 시간이 가장 큰 작업부터 루트가 되도록 유지한다. 이와 같은 과정을 통해, 문제에 요구하는 것과 같이 작업을 처리할 수 있다. 코드 import heapq from collections import deque RQEUST = 0 d..
문제 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 문제 풀이 M명의 사람이 입국심사를 받으려고 할 때, 입국 심사의 소요 시간이 최소가 되는 시간을 출력하는 문제이다. 문제를 풀기 위해서는 `이분 탐색`을 통해, 심사가 가능한 최소 시간을 구할 수 있다. 이 문제에서 이분 탐색의 `mid` 값은 입국 심사하는데 소요되는 전체 시간을 의미한다. 예를 들어 `mid`가 30초라면 30 // 심사하는데 걸리는 시간을 구하게 되면 입국할 수 있는 사람 수가 결정되게 된다. 코드 T = int(input()) for test_case in range(1, T + 1): answer = 0 n, m = map(int,..
문제 17089번: 세 친구 첫째 줄에 사람의 수 N(3 ≤ N ≤ 4,000), 친구 관계의 수 M(0 ≤ M ≤ 4,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계를 의미하는 두 정수 A, B가 주어진다. 친구 관계는 A와 B, 그리고 B와 A가 친� www.acmicpc.net 문제 풀이 문제에서는 N명의 사람이 있고, 세 사람을 선택할 때 세 사람이 모두 친구이고 세 사람의 친구 수의 합이 최소가 되는 경우를 찾아 반환하여야 한다. 문제의 조건에는 세 사람을 선택할 경우 세 사람은 친구에서 제외해야 한다는 조건이 있다. 처음에는 문제를 `DFS`를 통해 접근해야 하지 않나 라고 생각하였는데 세 사람을 선택하는 것을 `3중 반복문`을 통해 경우를 탐색하면 시간 초과가 발생하지 않고 문제를..
문제 16943번: 숫자 재배치 두 정수 A와 B가 있을 때, A에 포함된 숫자의 순서를 섞어서 새로운 수 C를 만들려고 한다. 즉, C는 A의 순열 중 하나가 되어야 한다. 가능한 C 중에서 B보다 작거나 같으면서, 가장 큰 값을 구해보� www.acmicpc.net 문제 풀이 A, B의 숫자가 주어질 때 A의 자릿수로 구할 수 있는 순열을 구하여 B보다 작으면서 가장 큰 값을 반환하는 문제이다. `DFS`를 통해 순열을 구하면서, B보다 작은지 확인하고 최대 값을 갱신해 주면 된다. 중간에 가지치기를 해주고 싶어서, 순열의 처음 값이 B의 첫 번째 값보다 크다면 가지를 뻗지 않게 하려고 했는데... 74~75% 정도에서 `틀렸습니다.` 를 출력한다. 가지치지를 하지 않으니 정답을 맞출 수 있었다. 코..
