본문 바로가기

알고리즘

 (67)
온풍기 안녕! [백준 23289번] 문제 https://www.acmicpc.net/problem/23289 23289번: 온풍기 안녕! 유난히 추운 날씨가 예상되는 이번 겨울을 대비하기 위해 구사과는 온풍기를 설치하려고 한다. 온풍기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기 www.acmicpc.net 내 풀이 문제가 길어서 문제 이해를 잘해야 한다. 여기서 가장 중요하다고 생각했던, 내가 가장 애를 먹었던 부분은 바로 '벽'이다. 내 식대로 문제를 해석해서 벽을 세우는 부분(can_go)에서 자꾸 에러가 떴다. 조건을 맞게 단 줄 알았는데, 아니었다. 그래서 다시 문제로 돌아가 벽에 해당하는 문장을 여러 번 읽고 이해하려고 했다. 벽을 놓는 방법이다. 해결 방법이 어렵다기 보다는 이해하는..
마법사 상어와 복제 [백준 23290번] 문제 https://www.acmicpc.net/problem/23290 23290번: 마법사 상어와 복제 첫째 줄에 물고기의 수 M, 상어가 마법을 연습한 횟수 S가 주어진다. 둘째 줄부터 M개의 줄에는 물고기의 정보 fx, fy, d가 주어진다. (fx, fy)는 물고기의 위치를 의미하고, d는 방향을 의미한다. 방향 www.acmicpc.net 내 풀이 문제에서 구현하라고 하는 대로 구현하면 된다. 다 풀고나서 테스트를 해보았을 때, 몇 개의 테스트 케이스에서 답이 안 나왔다. 이유를 알아보니, 상어가 이동할 수 있는 3개의 칸을 구할 때, (1, 1) -> (1, 2) -> (2, 2) -> (1, 2)와 같이 이전에 방문했던 칸을 다시 방문할 수 있다는 조건을 따로 달아주지 않았던 것이었다. 이..
상어 중학교 [백준 21609번] 문제 https://www.acmicpc.net/problem/21609 21609번: 상어 중학교 상어 중학교의 코딩 동아리에서 게임을 만들었다. 이 게임은 크기가 N×N인 격자에서 진행되고, 초기에 격자의 모든 칸에는 블록이 하나씩 들어있고, 블록은 검은색 블록, 무지개 블록, 일반 블록 www.acmicpc.net 내 풀이 문제에서 말한 모든 조건을 다 구현하였다. bfs를 사용하여 블록 그룹을 확인하였다. 그리고 크기가 가장 큰 블록 그룹을 찾을 때에는 블록 그룹의 좌표들을 리스트에 저장하여서 확인하였다. 지워야 하는 블록 그룹은 -2로 만들었다. 중력을 구할 때에는 카운트를 사용하였다. -2(빈 곳) 일 때는 카운트를 세어서 -2가 연속으로 몇 칸 있는지 구하였다. -1(검은 블록)일 때는 카운..
게리맨더링 2 [백준 17779번] 문제 https://www.acmicpc.net/problem/17779 17779번: 게리맨더링 2 재현시의 시장 구재현은 지난 몇 년간 게리맨더링을 통해서 자신의 당에게 유리하게 선거구를 획정했다. 견제할 권력이 없어진 구재현은 권력을 매우 부당하게 행사했고, 심지어는 시의 이름 www.acmicpc.net 내 풀이 문제 풀기 전에 인구수가 적힌 그리드의 인덱스가 1부터 시작한다는 점을 생각하고 가야 한다. 가장 고민을 많이 한 것은 '경계 안에 어떻게 5로 채울지'였다. i번 행을 확인하면서 5가 2개 들어있는 행만 5의 위치를 알아내었다. 5가 i번 행의 a열과 i번 행의 b열에 있다면, i번 행의 a+1열에서 b열까지를 모두 5로 만들어주었다. N = int(input()) # 1부터 시작하는 ..
톱니바퀴 [백준 14891번] 문제 https://www.acmicpc.net/problem/14891 14891번: 톱니바퀴 총 8개의 톱니를 가지고 있는 톱니바퀴 4개가 아래 그림과 같이 일렬로 놓여져 있다. 또, 톱니는 N극 또는 S극 중 하나를 나타내고 있다. 톱니바퀴에는 번호가 매겨져 있는데, 가장 왼쪽 톱니바퀴 www.acmicpc.net 내 풀이 dir에 돌려야 할 방향을 저장하고, 나중에 한꺼번에 톱니를 돌리는 것이 핵심이다. 1은 시계방향, -1은 반시계 방향, 0은 부동이다. 회전시킨 톱니바퀴를 기준으로 왼쪽을 검사하고, 오른쪽을 검사하면 된다. wheels = [input() for _ in range(4)] K = int(input()) def clock(wheel): return wheel[-1] + wheel..
아기 상어 [백준 16236번] 문제 https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 내 풀이 bfs를 사용하여 아기 상어와 모든 물고기 간의 거리를 구하였다. 이동할 때 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없다는 조건을 고려하였다. 그러나 아기 상어가 먹을 수 있는 물고기 리스트인 fishes에 넣을 때에는 물고기의 크기가 아기 사어의 크기보다 작은지 확인하였다. 같으면 fishes에 들어갈 수 없기 때문이다. fishes를 조건에 따라 정렬하였다. 거..
나무 재테크 [백준 16235번] 문제 https://www.acmicpc.net/problem/16235 16235번: 나무 재테크 부동산 투자로 억대의 돈을 번 상도는 최근 N×N 크기의 땅을 구매했다. 상도는 손쉬운 땅 관리를 위해 땅을 1×1 크기의 칸으로 나누어 놓았다. 각각의 칸은 (r, c)로 나타내며, r은 가장 위에서부터 www.acmicpc.net 내 풀이 문제에서 하라는 대로 구현하면 된다. 그러나 여기서 중요하게 여겨야 할 것은 봄과 여름을 묶어서 구현하고, 가을과 겨울을 묶어서 구현하는 것이다. 봄과 여름을 묶은 이유는, 봄을 구현하고 여름을 구현해도 여름은 죽은 나무가 원래 자신이 있던 칸에 양분으로 추가되기 때문에 다른 칸에 영향을 전혀 미치지 않기 때문이다. 그러나 가을은 나무가 번식하여 다른 칸에 영향을 주..
경사로 [백준 14890번] 문제 https://www.acmicpc.net/problem/14890 14890번: 경사로 첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다. www.acmicpc.net 내 풀이 [3, 2, 1, 1, 1,]처럼 생긴 도로가 있다고 해보자. 이 도로를 [[3], [2], [1, 1, 1]]와 같이 생긴 temp로 만들었다. temp를 돌면서 temp[i-1]과 temp[i] 안의 숫자가 몇 차이 나는지 확인하였다. 1 차이가 나면 check를 사용하여 방문 체크를 해주었다. 방문 체크를 하는 이유는 경사로가 이미 있는 곳에 또 경사로를 놓지 않게 하기 위함이다. check[i] <..

티스토리툴바