히치키치

문제 https://www.acmicpc.net/problem/1516 1516번: 게임 개발 첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. 건물의 번호는 1부 www.acmicpc.net 풀이 위상 정렬 : 변형 (동시에 건축 가능) arr : 가로 = 짓기 위해 필요한 재료(건물) , 세로 = 짓는 건물 진입차수 = 0 : 필요한 재료를 다 만든 상태 진입 차수가 0인 것을 enque -> pop하면서 해당 건물이 재료로 이용되는 것의 진입차수 -1 하기 걸리는 시간은 여러 개의 건물 중 가장 오래 걸리는 것 코드 #문제 : https://www.acmicpc.n..

문제 https://www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에 www.acmicpc.net 풀이 재귀 & 동적 계획 시작점 지정X -> 각 지점에서 시작할 때 가장 긴 생존 일 구하기 vist : 해당 지점 방문시 최대 생존 일 저장 코드 #문제 : https://www.acmicpc.net/problem/1937 from sys import setrecursionlimit setrecursionlimit(10**9) def dfs(i, j): if visit[i][j]..

문제 https://www.acmicpc.net/problem/2263 2263번: 트리의 순회 첫째 줄에 n(1≤n≤100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다. www.acmicpc.net 풀이 중위 순회 : root 왼쪽 자식 - root - root 오른쪽 자식 후위 순회 : root 왼쪽 자식 - root 오른쪽 자식 - root 전위 순회 : root - root 왼쪽 자식 - root 오른쪽 자식 후위 순회 마지막 노드 = 중위 순회의 루트 노드 후위 순회에서 루트를 뽑기 -> 전위 순회에 차례로 붙이기 루트 노드 찾아서 왼쪽 오른쪽 나눠서 재귀 진행 (왼쪽 실행 -> 오른쪽 실행) 예시 후위 순회 :..

문제 https://www.acmicpc.net/problem/1520 1520번: 내리막 길 첫째 줄에는 지도의 세로의 크기 M과 가로의 크기 N이 빈칸을 사이에 두고 주어진다. 이어 다음 M개 줄에 걸쳐 한 줄에 N개씩 위에서부터 차례로 각 지점의 높이가 빈 칸을 사이에 두고 주어진다. www.acmicpc.net 풀이 dp + dfs dp[x][y] : 지도 arr[x][y]까지 가는 경우의 수 / 방문 상태 기록 dp[x][y]=0 : 지도 arr[x][y]까지 가는 경로 없음 dp[x][y]=>1 : 이전의 방문 경로가 있음. 해당 값에 더해줌 dp[x][y]=-1 : 아직 방문하지 않은 경로 #문제 : https://www.acmicpc.net/problem/1520 import sys inp..