https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 아이디어 그냥 구현하면 되는 문제였다!! 전체 코드 from queue import deque N, M, V = map(int, input().split()) tmp = [[int(x) for x in input().split()] for _ in range(M)] def dfs(x): visited[x] = 1 print(x, end=" ") if visit..
Coding Test
https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 아이디어 DP 문제이다. 아래와 같이 각 한 인덱스를 기준으로 최솟값을 구해나가면 쉽게 구할 수 있다. 즉, 아래와 같은 점화식을 추론할 수 있다. dp[i][0] = min(dp[i-1][1], dp[i-1][2]) + datas[i][0] dp[i][1] = min(dp[i-1][0], dp[i-1][2]) + datas[i][1] dp[i][2] = min(dp[i-1]..
https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 아이디어 DP문제이다. 우선 n이 1~5일 때를 구해서 규칙을 찾았다. n 경우의 수 1 1 2 2 3 3 4 5 5 8 . . . n의 경우의 수는 n-1의 경우의 수 + n-2의 경우의 수 였다. 이렇게 규칙을 찾고 찾은 식을 바탕으로 코드를 작성해보았다. 전체 코드 import sys input = sys.stdin.readline n = int(input()) if n == 1: print(1) else: dp..
https://www.acmicpc.net/problem/20055 20055번: 컨베이어 벨트 위의 로봇 길이가 N인 컨베이어 벨트가 있고, 길이가 2N인 벨트가 이 컨베이어 벨트를 위아래로 감싸며 돌고 있다. 벨트는 길이 1 간격으로 2N개의 칸으로 나뉘어져 있으며, 각 칸에는 아래 그림과 같이 1부 www.acmicpc.net 아이디어 벨트가 각 칸 위에 있는 로봇과 함께 한 칸 회전한다. 가장 먼저 벨트에 올라간 로봇부터, 벨트가 회전하는 방향으로 한 칸 이동할 수 있다면 이동한다. 만약 이동할 수 없다면 가만히 있는다. 로봇이 이동하기 위해서는 이동하려는 칸에 로봇이 없으며, 그 칸의 내구도가 1 이상 남아 있어야 한다. 올리는 위치에 있는 칸의 내구도가 0이 아니면 올리는 위치에 로봇을 올린다..
