본문 바로가기

프로그래밍

 (187)
백준 15654 N과 M(5) - 파이썬 문제. 풀이. 파이썬의 내장 라이브러리 itertools의 permutation으로 순열을 구한 뒤 정렬 후 출력하면 된다. 소스코드. import sys from itertools import permutations input = sys.stdin.readline n, m = map(int, input().split()) numbers = list(map(int, input().split())) result = list(permutations(numbers, m)) result.sort() for i in result: for j in i: print(j, end=' ') print()
백준 10217 KCM Travel - 파이썬 문제. 풀이. 우선 처음에는 다익스트라를 이용하여 풀이를 했다. 처음에는 답이 틀렸다. 그 이유는 비용으로 비교했을때 거리와, 거리로 비교했을때 최소거리 2가지 경우를 모두 생각해야 했었다. 그래서 두 가지 경우를 나눠서 제출을 했는데 이번에는 메모리 초과로 틀렸다. 우선 기존 소스코드를 첨부하겠다. 기존 소스코드. import sys import heapq def dijkstra(start): global dp visited = [False for i in range(N+1)] dp_time[start] = [0, 0] dp_cost[start] = [0, 0] heap = [] heapq.heappush(heap, [0, start, 0]) #[비용, 위치, 시간] while heap: now_cos..
백준 1956 운동 - 파이썬 문제. 풀이. 플로이드-와샬 알고리즘을 통해 최단 거리를 구한 뒤 자기 자신에게 돌아오는 값 중 최솟값을 출력한다. 사이클이 없으면 -1 소스코드. import sys input = sys.stdin.readline def floyd_whashall(): # k = 경유지 for k in range(1, V+1): # i = 출발지 for i in range(1, V+1): # j = 목적지 for j in range(1, V+1): if graph[i][j] > graph[i][k] + graph[k][j]: graph[i][j] = graph[i][k] + graph[k][j] V, E = map(int, input().split()) inf = float('inf') graph = [[inf for..
파이썬 2629 양팔저울 - 백준 문제. 풀이. 양팔 저울이 잴 수 있는 무게는 양팔에 올라간 추의 무게 차이이다. 예를들어 1,3,7 무게의 추가 있다면 잴 수 있는 경우는 1, 2, 3, 4, 6, 7, 8, 10, 11의 무게를 잴 수 있다. 여기서 2, 4, 6 같은 경우에는 |왼쪽 저울 - 오른쪽 저울|의 값이다. 즉 dp[i][j] = i번쨰 추를 놓으려고 할때 현재의 무게차이 j 이다. 소스코드. import sys def scale(weight, n, now, left, right): new = abs(left - right) # possible에 현재 무게차이가 들어 있지 않다면 추가 if new not in possible: possible.append(new) if now == n: return # 방문하는 dp가 이..
백준 7579 앱 - 파이썬 문제. 풀이. 냅색 알고리즘을 이용하는 문제이다. 우선dp 배열을 행은 켜진 app의 개수, 열은 cost들을 다 더한 값 만큼 생성해준다. 그리고 반복문으로 dp배열을 돌면서 다음과 같은 조건을 체크한다. 1) 현재 앱의 i번째 앱의 코스트가 j보다 크다면 끄지 못하므로 이전 행의 값을 가져온다. dp[i][j] = dp[i-1][j] 2) 현재 앱의 cost가 j보다 작거나 같을 경우 현재 앱을 껏을때의 메모리와 그렇지 않을 경우의 메모리 중 큰 값을 dp에 입력한다 dp[i][j] = max(memory+dp[i-1][j-cost] 3) 현재 dp[i][j[의 값이 M 이상이라면 현재 cost와 이전의 result 값을 비교해 더 작은 값을 저장한다. dp[i][j[ = min(result, j) ..
백준 2580 스도쿠 - 파이썬 문제. 풀이. DFS와 백트래킹을 섞어서 풀었다. 정답 리스트 중에 골라서 정답을 대입하고 답이 틀리다면 다시 돌아와 다른 정답 리스트를 넣어서 정답이라면 출력하는 방식이다. PYTHON으로 제출하면 시간초과가 떠서 pypy3로 제출을 하였다. 소스코드. import sys def DFS(x): global isTrue # 이미 답이 출력된 경우 if isTrue: return if x == len(zero): for i in matrix: for j in i: print(j, end=' ') print() isTrue = True return else: (dx, dy) = zero[x] answers = check(dx, dy) # 정답 리스트 for i in answers: matrix[dx][dy]..
백준 12015 가장 긴 증가하는 부분 수열2 - 파이썬 문제. 풀이. 이분 탐색을 이용하여 dp배열의 최댓값과 비교하여 큰 값이면 오른쪽에, 낮은 값이면 dp배열의 값에서 이분 탐색을 이용하여 해당 값이 들어갈 위치를 결정하여 dp 배열에 넣고 dp 배열의 길이를 출력한다. 소스코드 import sys from bisect import bisect_left input = sys.stdin.readline n = int(input()) arr = list(map(int, input().split())) dp = [] for i in arr: k = bisect_left(dp, i) if len(dp)
백준 2004 조합 0의 개수 - 파이썬 문제. 풀이 10은 2와 5로 이루어져있다. 즉 nCm 에서 2와 5중 최솟 값의 갯수를 출력하면 된다. 소스코드. import sys def count_two(n): answer = 0 while n >= 2: n = n // 2 answer += n return answer def count_five(n): answer = 0 while n >= 5: n = n // 5 answer += n return answer input = sys.stdin.readline n, m = map(int, input().split()) result = min(count_two(n) - count_two(m) - count_two(n-m), count_five(n) - count_five(m) - count_five..

티스토리툴바