백준 (104) 썸네일형 리스트형 백준 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.. 백준 1504 특정 최단 경로 - 파이썬 문제. 풀이. 저번 포스트에서 풀었던 다익스트라 알고리즘에서 거쳐야하는 정점들이 추가되었다. 우선 시작 정점, v1, v2정점의 최단경로들을 구하고 start -> v1 -> v2 -> end start -> v2 -> v1 -> end 중에서 짧은 경로를 출력하면된다. 소스코드. import sys import heapq def route(start): dijkstra = [INF] * V heap = [] dijkstra[start] = 0 # 시작하는 정점 가중치는 0으로 heapq.heappush(heap,[0, start]) # 우선순위 큐에 가중치과 시작 정점 삽입 while heap: now_weight, now = heapq.heappop(heap) # 현재 테이블과 비교하여 더 가중치가 .. 백준 1753 최단경로 - 파이썬 문제. 풀이. 다익스트라 알고리즘을 숙지하고 있어야한다. https://ko.wikipedia.org/wiki/%EB%8D%B0%EC%9D%B4%ED%81%AC%EC%8A%A4%ED%8A%B8%EB%9D%BC_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98 데이크스트라 알고리즘 - 위키백과, 우리 모두의 백과사전 컴퓨터 과학에서, 데이크스트라 알고리즘(영어: Dijkstra algorithm) 또는 다익스트라 알고리즘은 도로 교통망 같은 곳에서 나타날 수 있는 그래프에서 꼭짓점 간의 최단 경로를 찾는 알고리즘이다. ko.wikipedia.org 다익스트라 알고리즘을 알지못한다면 위의 링크를 참조하면된다. 다익스트라 알고리즘은 모든 플로이드 와셜 알고리즘과 달리 해당 정점에서 모든 정점까.. 백준 1707 이분그래프 - 파이썬 문제. 풀이. 이분 그래프는 연결된 정점마다 색을 칠한다고 하면 연결된 정점 끼리의 색이 서로 달라야한다. 즉 예를 들어 (1,3), (2,3) 이 연결되어 있다면 1은 빨간색 3은 파랑색 2는 빨간색 이런식으로 연결된 정점끼리의 색이 달라야한다. 풀이. from collections import deque def bfs(n): visited[n] = 1; queue=deque() queue.append(n) while queue: x = queue.popleft() for i in matrix[x]: if visited[i] == 0: visited[i] = -visited[x] queue.append(i) else: if visited[i] == visited[x]: return False retur.. 백준 7562 나이트의 이동 - 파이썬 문제. 풀이. BFS를 해서 문제를 풀면된다. 나이트의 이동 범위만 잘 정해서 하면되는데 Y축으로 2칸 올라갈때는 X축이 -1, +1 만큼 움직이고 Y축으로 1칸 올라갈떄는 X축이 -2, +2 만큼 움직인다 소스코드. import sys from collections import deque def BFS(matrix, start, end): if start == end: return 1 queue = deque() queue.append([start[0], start[1]]) while queue: x, y = queue.popleft() for i in range(8): nx = x + dx[i] ny = y + dy[i] if 0 이전 1 ··· 4 5 6 7 8 9 10 ··· 13 다음
