본문 바로가기

전체 글

 (85)
연구소 3 [백준 17142번] 문제 https://www.acmicpc.net/problem/17142 17142번: 연구소 3 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고 www.acmicpc.net 내 풀이 삼성 시험에서는 itertools를 쓸 수 없다고 해서 dfs로 순열을 구현하였다. dfs로 활성 바이러스가 될 수 있는 애들 M개를 골랐다. M개를 골랐으면, 그 애들을 활성 바이러스로 하여 bfs로 빈칸에 활성 바이러스가 얼마나 퍼지는지 구하였다. 바이러스가 퍼질 때 중요한 것은 비활성 바이러스의 존재이다. 비활성 바이러스는 활성 바이러스와 만나면 활성 바이러스가 되어 빈칸에 바이러스를 ..
마법사 상어와 파이어볼 [백준 20056번] 문제 https://www.acmicpc.net/problem/20056 20056번: 마법사 상어와 파이어볼 첫째 줄에 N, M, K가 주어진다. 둘째 줄부터 M개의 줄에 파이어볼의 정보가 한 줄에 하나씩 주어진다. 파이어볼의 정보는 다섯 정수 ri, ci, mi, si, di로 이루어져 있다. 서로 다른 두 파이어볼의 위치 www.acmicpc.net 내 풀이 grid를 []로 구성된 2차원 배열로 선언하였다. (따지고 보면 모양이 독특한 3차원 배열이다. 길이가 가변적인 3차원 배열..?) 먼저 파이어볼을 이동시키는 것을 구현하였다. 하나의 좌표에 여러 개의 파이어볼이 있을 수 있으므로, 여러 개의 파이어볼이 있는지 파악하고 전부 이동시켜주는 것이 중요하다. 이동시킨 후, 2개 이상의 파이어볼이 있..
이차원 배열과 연산 [백준 17140번] 문제 https://www.acmicpc.net/problem/17140 17140번: 이차원 배열과 연산 첫째 줄에 r, c, k가 주어진다. (1 ≤ r, c, k ≤ 100) 둘째 줄부터 3개의 줄에 배열 A에 들어있는 수가 주어진다. 배열 A에 들어있는 수는 100보다 작거나 같은 자연수이다. www.acmicpc.net 내 풀이 원래 C 연산을 따로 구현하였으나, list(zip(*arr))을 사용하면 전치가 된다는 것을 배우고, R 연산만으로 해결하였다. R을 열심히 구현하였다. 배열의 한 행씩 받아서 각 숫자가 몇 개 있는지 구한 후 튜플을 사용하여 저장하였다. 그리고 sort로 정렬하였다. 만약 한 행의 길이가 100보다 길면 잘라내었고, max_len도 100으로 갱신하였다. 그렇게 새로..
미세먼지 안녕! [백준 17144번] 문제 https://www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net 내 풀이 문제에서 말하는 순서대로 구현하였다. 미세먼지를 먼저 확산시키고 -> 공기청정기를 작동시켰다. 풀 때 가장 중요한 것은, 중간중간 코드가 맞는지 결과를 프린트해보는 것이다. 공기청정기를 구현할 때에는 좀 더 머리를 써볼까 생각도 했지만, 짧은 시간 안에 빨리 푸는 연습을 하느라 그냥 생각나는 대로 풀었다. 공기청정기가 닿는 미세먼지들의 좌표를 배열에 다 담고, 그 배열에서 한 칸씩..
드래곤 커브 [백준 15685번] 문제 https://www.acmicpc.net/problem/15685 15685번: 드래곤 커브 첫째 줄에 드래곤 커브의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 드래곤 커브의 정보가 주어진다. 드래곤 커브의 정보는 네 정수 x, y, d, g로 이루어져 있다. x와 y는 드래곤 커 www.acmicpc.net 내 풀이 전형적인 규칙 찾기 문제이다. 드래곤 커브가 만들어질 때 방향을 구해보면 규칙을 찾을 수 있다. 문제에 나온 예시로 규칙을 찾아보자. 0세대 : 0 1세대 : 0 1 2세대 : 0 1 2 1 3세대 : 0 1 2 1 2 3 2 1 4세대 : 0 1 2 1 2 3 2 1 2 3 0 3 2 3 2 1 k세대에 새로 만들어지는 방향은 k-1세대의 방향들을 뒤집은..
감시 [백준 15683번] 문제 https://www.acmicpc.net/problem/15683 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net 내 풀이 문제를 딱 봤을 때 모든 경우의 수를 구해야 하기 때문에 dfs를 사용해야 할 것 같았다. 그래서 먼저 CCTV의 번호와 위치를 cctv 리스트에 저장하였다. CCTV는 번호에 따라서 감시하는 방향과 방향의 수가 다르다. 그래서 각 CCTV가 감시할 수 있는 모든 방향을 딕셔너리에 저장하였다. 그래고 dfs를 사용하여 모든 경우의 수를 구해주었다. 여기서 중요한 것은 tm..
인구 이동 [백준 16234번] 문제 https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 내 풀이 BFS를 사용해서 국경선을 공유하는 그룹을 찾고, 국경선을 공유하는 그룹에는 몇 개의 나라가 있는지 리턴하는 함수를 만들었다. 인구 이동이 며칠 동안 이루어지는지 구해야 하므로 while 반복문을 사용했고, 여기서 while문을 중단시키기 위한 조건이 중요하다. 국경선을 공유하는 그룹이 1개 이상인 경우 flag를 True로 만들었다. flag가 계속 False라면 인..
치킨 배달 [백준 15686번] 문제 https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 내 풀이 나도 combinations 써서 구현할까 하다가 재귀 함수 연습할 겸 재귀로 풀어보았다. 재귀 함수 백트래킹을 사용하여 치킨집 중에서 M개를 선택하였다. 선택된 치킨집과 집과의 거리를 구하였다. import sys, math input = sys.stdin.readline N, M = map(int, input().strip().split()) city, ho..

티스토리툴바