효팍이의 프로그래밍

백준 1520번 내리막 길 백준 1520번 내리막 길 그냥 탐색으로 풀면 시간초과가 난다.. 그래서 dp 기법을 추가로 사용해야한다. 탐색해서 결과가 나오면 그걸 dp에 저장하고 다른 탐색 때 사용한다..흠.. 코드 import sys, heapq from typing import List input = sys.stdin.readline sys.setrecursionlimit(10**6) class Solution: def down_hill(self, M: int, N: int, graph: List[List[int]]): """dfs로 탐색을 하고 dp기법을 사용하여 배열에 각 칸마다의 결과 값을 저장해나가면서 이전에 갔었던 칸을 지나갈시에 dp에서 답을 가져와서 사용함으로써 깊이 탐색의 시간을 줄인다..

백준 1167번 트리의 지름 백준 1167번 트리의 지름 아무점을 잡고 dfs로 가장 거리가 먼 정점을 찾는다. 이 정점을 기준으로 다시 dfs로 가장 먼 거리를 찾는다. 코드 from typing import List, Tuple import sys import collections input = sys.stdin.readline sys.setrecursionlimit(10**6) class Solution: def diameter(self, V: int, graph: List[List[Tuple]]): def dfs(u, count): visited[u] = True for v, w in graph[u]: if not visited[v]: vertex, weight = dfs(v, count+w) i..

문제 상근이는 겨울방학을 맞아 N개국을 여행하면서 자아를 찾기로 마음먹었다. 하지만 상근이는 새로운 비행기를 무서워하기 때문에, 최대한 적은 종류의 비행기를 타고 국가들을 이동하려고 한다. 이번 방학 동안의 비행 스케줄이 주어졌을 때, 상근이가 가장 적은 종류의 비행기를 타고 모든 국가들을 여행할 수 있도록 도와주자. 상근이가 한 국가에서 다른 국가로 이동할 때 다른 국가를 거쳐 가도(심지어 이미 방문한 국가라도) 된다. 입력 첫 번째 줄에는 테스트 케이스의 수 T(T ≤ 100)가 주어지고, 각 테스트 케이스마다 다음과 같은 정보가 주어진다. 첫 번째 줄에는 국가의 수 N(2 ≤ N ≤ 1 000)과 비행기의 종류 M(1 ≤ M ≤ 10 000) 가 주어진다. 이후 M개의 줄에 a와 b 쌍들이 입력된다..

문제 눈금의 간격이 1인 M×N(M,N≤100)크기의 모눈종이가 있다. 이 모눈종이 위에 눈금에 맞추어 K개의 직사각형을 그릴 때, 이들 K개의 직사각형의 내부를 제외한 나머지 부분이 몇 개의 분리된 영역으로 나누어진다. 예를 들어 M=5, N=7 인 모눈종이 위에 과 같이 직사각형 3개를 그렸다면, 그 나머지 영역은 와 같이 3개의 분리된 영역으로 나누어지게 된다. 와 같이 분리된 세 영역의 넓이는 각각 1, 7, 13이 된다. M, N과 K 그리고 K개의 직사각형의 좌표가 주어질 때, K개의 직사각형 내부를 제외한 나머지 부분이 몇 개의 분리된 영역으로 나누어지는지, 그리고 분리된 각 영역의 넓이가 얼마인지를 구하여 이를 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 M과 N, 그리고 K가 빈칸을 ..