•알고리즘(Algorithm )

[백준7662&파이썬] 이중 우선순위 큐를 만들고 관리하기(중복값 처리에 대해 항상 생각하자)

# 문제 백준 7662 파이썬 이중 우선순위 큐 풀이 7662번: 이중 우선순위 큐 입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 Q에 적 www.acmicpc.net # 코드 ''' - 정렬을 이용한 풀이방법은 시간초과 - 정렬 O( k * log N) - 힙을 이용해서 풀고 싶다 - 힙을 두개이용하는 방법 말고 없을까? - nlargeset 풀이방법을 이용 - 중복값이 두번 들어올 수 있다. - 이럴경우 dict을 True / False 로 관리하면 관리 할 수 없게 된다. - 고유 ID값을 주고 그걸 사용하자. ''' import sys from heapq impo..

[백준15651&파이썬] 중복순열을 구하는 두가지 방법

# 문제 백준 15651 N과M 3 파이썬 풀이 15651번: N과 M (3) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net # 코드 import sys from itertools import product N,M = map(int,sys.stdin.readline().split()) targets = [i for i in range(1,N+1)] # 중복순열의 문제 def dfs(mstr,cnt) : global M if cnt == M+1 : print(mstr) return for target in targets : next = m..

[백준15650&파이썬] 파이썬에서 조합문제 해결하기

# 문제 백준15650 N과M (2) 파이썬 풀이 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net # 코드 import sys from itertools import combinations N,M = map(int,sys.stdin.readline().split()) # 조합의 문제이다. for combi in combinations(range(1,N+1), M) : print(*combi) # 백트래킹으로 풀기 def dfs(arr,index) : if len(arr) == M : print(*arr) re..

[백준15649&파이썬] 파이썬에서 순열을 구해야 할때

# 문제 백준 15649 N과M (1) 파이썬 풀이 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net # 코드 import sys from itertools import permutations N,M = map(int,sys.stdin.readline().split()) targets = [i for i in range(1,N+1)] # # print(targets) # # 중복없이 M개를 고른 수열 # 조합을 사용한다. for permu in permutations(targets,M) : print(*perm..

[백준15686&파이썬] 조합을 이용해 브루트포스(완전탐색)해결하기

# 문제 파이썬 15686 치킨배달 파이썬 풀이 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net # 코드 import sys from itertools import combinations board = list() N, M = map(int, sys.stdin.readline().split()) houses = list() chicken = list() def print2D(arr): for i in range(len(arr)): for j in range(len(arr[i])): prin..

[백준2294&파이썬] DP를 이용하여 동전교환문제를 해결하기, DP는 값을 재활용한다.

# 문제 백준 2294 동전2 파이썬 풀이 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주 www.acmicpc.net # 코드 ''' - DP배열을 -1로 초기화 해주는게 좋을 듯 하다. - 만일 중간에 0인 지점이 있을텐데 그 지점은 못와서 0일텐데 이걸 체크 안하면 그다음은 여기에 1더해버리기 때문이다. - 문제에서 나름 불가능할경우 -1을 출력하라는거에서 힌트처럼 느껴질수도.. ''' import sys coins = list() n,k = map(int,sys.stdin.readline().spli..