관찰과 질문, 그리고 데이터

https://www.acmicpc.net/problem/10775 10775번: 공항 문제 오늘은 신승원의 생일이다. 박승원은 생일을 맞아 신승원에게 인천국제공항을 선물로 줬다. 공항에는 G개의 게이트가 있으며 각각은 1에서 G까지의 번호를 가지고 있다. 공항에는 P개의 비행기가 순서대로 도착할 예정이며, 당신은 i번째 비행기를 1번부터 gi (1 ≤ gi ≤ G) 번째 게이트중 하나에 영구적으로 도킹하려 한다. 비행기가 도킹된 게이트에는 다른 비행기가 도착할 수 없다. 이렇게 공항을 운영할 경우 간혹 비행기가 어떤 곳에도 도킹하지 못하는 www.acmicpc.net Union Find 문제. 문제를 Union find 형태로 풀어내는 방법은 https://mygumi.tistory.com/245 백준..

https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net Brute Force + DFS 문제처럼 보이지만, Python은 조합 경우의 수를 itertools의 내장함수 combinations을 사용할 수 있어 쉽게 풀 수 있다.

https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 벽 또는 빈 칸이다. 청소기는 바라보는 방향이 있으며, 이 방향은 동, 서, 남, 북중 하나이다. 지도의 각 칸은 (r, c)로 나타낼 수 있고, r은 북쪽으로부터 떨어진 칸의 개수, c는 서쪽으로 부터 떨어진 칸의 개수이다. 로봇 청소기는 다음 www.acmicpc.net 삼성SW역량평가 A형 기출문제로, 엄청 어려운 문제라기보다는 신중하게 생각해서 코드를 짜야 하다보니 시간이 부족했을 법한 문제. ..

https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크기가 N×M인 직사각형으로 나타낼 수 있으며, 직사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다. 일부 칸은 바이러스가 존재하며, 이 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다. www.acmicpc.net 연구소 3과 접근방법은 동일하다. combinations을 사용할 대상이 '벽 3개'로 바뀐 것일 뿐. BFS에서의 특이점이라면, BFS에..

https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸, 왼쪽에서부터 c번째 칸을 의미한다. r과 c는 1부터 시작한다. 이 도시에 사는 사람들은 치킨을 매우 좋아한다. 따라서, 사람들은 "치킨 거리"라는 말을 주로 사용한다. 치킨 거리는 집과 가장 가까운 치킨집 사이의 거리이다. 즉, 치킨 거리는 www.acmicpc.net 삼성SW역량테스트 기출문제. Brute Force + BFS 형태. 치킨집 중에 M개를 고르는 형태는 '연구소 3' 문제와 마찬가지로..

https://www.acmicpc.net/problem/17142 17142번: 연구소 3 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고, 활성 상태인 바이러스는 상하좌우로 인접한 모든 빈 칸으로 동시에 복제되며, 1초가 걸린다. 승원이는 연구소의 바이러스 M개를 활성 상태로 변경하려고 한다. 연구소는 크기가 N×N인 정사각형으로 나타낼 수 있으며, 정사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 www.acmicpc.net 삼성 SW역량테스트 기출문제였다고 한다. BFS와 DFS를 모두 사용하는 문제라고 하는데, Python에서는 '경우의 수'를 뽑아내..

위상 정렬 문제. Python의 heapq 라이브러리를 활용해서 위상정렬을 구현할 수 있다. import heapq n, m = map(int, input().split()) arr = [[] for _ in range(n+1)] precede = [0 for _ in range(n+1)] heap, result = [], [] for _ in range(m): x, y = map(int, input().split()) arr[x].append(y) # 연결된 간선. x번 문제는 y번보다 먼저 풀어야 한다. precede[y] += 1 # 이어진 노드의 진입차수. # (y번 문제는 몇 개의 선행문제와 연결되어 있는지. 진입차수라 보면 된다) for i in range(1, n+1): if precede[..