yoo.dev

문제 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 � www.acmicpc.net 풀이 해봐야 몇개 안되겠다 싶어서 브루트포스로 모든 상황을 다 돌리기로 하고, 그래도 반복의 횟수를 조금 줄이기 위해 하나도 물에 잠기지 않는 경우와, 모두 물에 잠기는 경우를 가지치기 했다. 그래서 인풋을 받으면서 값들의 최소와 최대를 minimum, maximum에 저장했다. 그 후, minimum부터 maximum까지 포문을 돌면서 인풋 값이 들어있는 field 배열을 복사해서 bfs를 했고, 안전영역의 갯수를 카운팅해줬다. import sys from ..

문제 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 풀이 dp를 사용해서 풀었다. import sys # N: 물품 수 / K: 무게제한 N, K = map(int, sys.stdin.readline().split(" ")) # (N+1) * (K+1) 배열 생성 dp = [[0 for _ in range(K+1)] for _ in range(N+1)] # 물품별로 [무게(w), 가치(v)] 받기 items = [] for _ in range(..

문제 6603번: 로또 문제 독일 로또는 {1, 2, ..., 49}에서 수 6개를 고른다. 로또 번호를 선택하는데 사용되는 가장 유명한 전략은 49가지 수 중 k(k>6)개의 수를 골라 집합 S를 만든 다음 그 수만 가지고 번호를 선택하는 www.acmicpc.net 코드 import sys from itertools import combinations flag = 1 while flag: line = sys.stdin.readline() li = list(map(int, line.split(" "))) k = li[0] if k == 0: flag = 0 break del li[0] for each in list(combinations(li, 6)): for num in each: print(num,..

문제 15652번: N과 M (4) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 풀이 중복조합 nHr을 구하기 위해서는 itertools의 combinations_with_replacement를 사용하면 된다. import sys from itertools import combinations_with_replacement N, M = map(int, sys.stdin.readline().split(" ")) li = [] for i in range(1,N+1): li.append(i) for each in list(combination..

문제 15651번: N과 M (3) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 풀이 중복을 허용하는 순열을 구하기 위해서는 itertools의 product를 사용해야한다. product(리스트, repeat=n) import sys from itertools import product N, M = map(int, sys.stdin.readline().split(" ")) li = [] for i in range(1,N+1): li.append(i) for each in list(product(li, repeat=M)): for nu..

문제 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 풀이 오름차순으로 정렬해야한다는 점에서 N과 M(1) 문제와 차이가 있다. 즉, 오름차순이 아닌 순열 (예. 1 2 4 3)은 다 프린트하지 말아야한다. 따라서 조합으로 풀었다. import sys from itertools import combinations N, M = map(int, sys.stdin.readline().split(" ")) li = [] for i in range(1,N+1): li.append(i) for each in list(c..

문제 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 풀이 중복되는 수열을 여러번 출력하면 안된다해서 조합인줄 알았는데 그 의미가 아니었다. 따라서 itertools의 permutations로 풀었음 import sys from itertools import permutations N, M = map(int, sys.stdin.readline().split(" ")) li = [] for i in range(1,N+1): li.append(i) for each in list(permutations(li, M)..

문제 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주�� www.acmicpc.net 풀이 인풋을 인접 리스트에 저장하고, dfs로 탐색하는 방법으로 풀었다. import sys # V: vertex, E: edge V, E = map(int, sys.stdin.readline().split()) adj = [[] for _ in range(V)] visited = [0 for _ in range(V)] stack = [] def dfs(): while stack: x = st..