코딩테스트/Python 문제풀이

[백준] 사다리 조작

https://www.acmicpc.net/problem/15684 15684번: 사다리 조작 사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선 www.acmicpc.net dfs를 이용하는 문제입니다. 우선 문제부터 간단하게 요약하면, 사다리가 주어지는데, 이 사다리에 사다리를 3개까지 추가해서 각각의 사다리가 도착지점도 번호가 같도록 만드려 하는데, 필요한 사다리의 최소갯수를 구해야 하는 문제입니다. DFS를 이용해야 합니다. 로직은 아래와 같습니다. 1. 각 사다리를 놓을 수 있는 지점에 사다리를 하나씩 놓아본다.(중복된 경우의 수 안하도록 주의) 2. 만약 ..

[백준] 토마토

https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net bfs를 활용하는 문제입니다. 우선 문제부터 간단하게 요약하면, 상자안에 익은 토마토, 안익은 토마토, 빈칸이 존재합니다. 이 때, 매일 익은 토마토 옆에 있는 안익은 토마토가 익을 때, 모든 토마토가 익기 위한 일 수를 구해야 합니다. bfs를 이용하면 되는 간단한 문제입니다. bfs의 초기 queue에 1인 지점들의 좌표를 넣어줍니다. (익은 토마토의 좌표를 넣습니다.)..

[백준] 치킨 배달

https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 조합을 이용한 구현 문제입니다. 우선 문제부터 간단하게 요약하면, 도시에 치킨 집들과, 일반 가정집들이 있습니다. 이 때, 가정집에서 가장 가까운 치킨 집 까지의 택시거리를 치킨 거리라고 정의합니다. ps. 거리의 종류에 대한 포스팅도 흥미로운 주제가 될 것 같습니다... 언젠가 기회가 되면 포스팅해보는 것으로... 도시에서 치킨집들을 M개 만큼만 골라서 가정집들의 치킨거리의..

[백준] 서강그라운드

https://www.acmicpc.net/problem/14938 14938번: 서강그라운드 예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 www.acmicpc.net 플로이드 워셜(Floyd-Warshall) 알고리즘을 사용하는 문제입니다. 우선 문제부터 간단하게 요약하면, 예은이가 특정한 지역에 내려서 거리 m이하로 도착할 수 있는 곳에서 아이템을 먹을 때, 먹을 수 있는 아이템의 최대 갯수를 return해야 합니다. 실제로 문제를 한번 읽어보는 것이 좋습니다. 우선 도시가 만약 1~5까지 있다고 생각해 봅시다. 이 때, 예은이가 먹을 수 있는 아이템을 각 도시별..

[백준] 미세먼지 안녕!

https://www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net 구현 문제입니다. 우선 문제부터 간단하게 요약하면, 방에 미세먼지와 공기 청정기가 있고, 매 1초마다 두가지 과정이 진행됩니다. 1. 미세먼지의 확산 2. 공기청정기로 인한 공기 정화와 순환 이러한 과정이 T 초간 일어난 후 방안의 전체 미세먼지의 수를 출력해야 하는 문제입니다. 특별한 알고리즘이 사용되지 않고, 말 그대로 1,2의 과정을 정확하게 구현하면 됩니다. for loop 내부에 ste..

[백준] 숨바꼭질 2

https://www.acmicpc.net/problem/12851 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net bfs를 이용하는 문제입니다. 우선 문제부터 간단하게 요약하면, 0 5, 3, 8 2-> 3, 1, 4 6-> 7, 5, 12 각각 시간에 따라 bfs의 진행과정에서 등장하는 정보들을 적어 두었습니다. 시간이 0인 경우 3, 시간이 1인 경우에는 시간이 0일 때의 3으로 부터 유도되는 4,2,6이 등장하고, 이후의 과정들 또한 마찬가지 입니다. 이 때 3은 시..

[백준] 최소비용 구하기 2

https://www.acmicpc.net/problem/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 다익스트라 알고리즘을 사용하는 문제입니다. 우선 문제부터 간단하게 요약하면, 도시의 개수, 버스의 개수가 주어지고 버스들의 cost가 주어집니다. 이 때, 출발 도시에서 도착 도시까지의 최단 cost를 구하고, 이때의 path 정보 또한 구해야 하는 문제입니다. 기존의 다익스트라 알고리즘에 추가적으로 최단 거리로 가는 경로 또한 구해야 하는 문제입니다. 최단 cos..

[백준] 감시

https://www.acmicpc.net/problem/15683 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net DFS를 통한 구현 문제입니다. 우선 문제부터 간단하게 요약하면, 다음 그림과 같이 4방향을 감시할 수 있는 cctv들이 놓여있는 방이 있습니다. 이 방에는 벽이 있고, 만약 벽이 있다면, cctv는 벽 뒷편은 보지 못합니다. 이 때, cctv의 사각지대를 최소화 시키는 것이 문제입니다. 실제로 문제가 조금 기니 한번 읽어보는 것을 권장합니다. DFS를 통해 각각의 cctv에 대해 가능..