본문 바로가기

분류 전체보기

 (328)
[백준] 7579번 : 앱 7579번: 앱 해당 문제는 다이나믹 프로그래밍 문제로 배낭문제와 비슷 합니다. dp[i][j]는 메모리의 크기라고 하면 i는 Ai번째를 추가하는경우와 추가하지 않는 경우이며 j는 j의 비활성화의 가중치 값이다. 앱 Ai를 추가할때와 추가하지 않을때의 최대값을 구한다. 메모리가 빠르게 채워지면서 메모리가 M이상 채워 졌을때 j값의 최소값을 찾으면 된다. 아래는 예제 문제 1번을 테이블로 그려보았다. import sys input = sys.stdin.readline N, M = map(int, input().split()) A = [0] + list(map(int, input().split())) C = [0] + list(map(int, input().split())) dp = [[0 for _ in ..
[백준] 9184번 : 신나는함수실행 9184번: 신나는 함수 실행 해당문제는 메모리제이션 문제로 함수 return 끝에 이미 계산한 값을 저장하는 배열을 만들어서 저장한뒤 결과를 return 하면된다. import sys input = sys.stdin.readline dp = [[[-1 for _ in range(21)] for _ in range(21)] for _ in range(21)] def dfs(a, b, c): if a 20: return dfs(20, 20, 20) if dp[a][b][c] != -1: return dp[a][b][c] if a < b < c: dp[a][b][c] = dfs(a,b,c-1) + dfs(a, b-1, c-1) - dfs(a, b-1, c) return dp[a][b][c] cost = df..
[백준] 1062번 : 가르침 1062번: 가르침 해당 문제는 조합 문제로 해결 하였습니다. 알파벳의 모든 경우의 수를 구한뒤에, 알파벳으로 읽을 수 있는 단어를 계산합니다. 알파벳을 읽을 수 있는 learned 배열을 통하여 읽을 수 있는 알파벳을 표기하고 단어중에 learned 값이 모두 있다면 카운트를 증가시킵니다. from itertools import combinations N, K = map(int, input().split()) northword = list(['a','n','t','i','c']) alpabat = list(['b','d','e','f','g','h','j','k','l','m','o','p','q','r','s','u','v','w','x','y','z']) words = list() for _ in ..
[백준] 4485번 : 녹색 옷 입은 애가 젤다지? 4485번: 녹색 옷 입은 애가 젤다지? 해당문제는 BFS혹은 데이크스트라로 문제를 해결 할 수 있습니다. BFS는 N이 충분히 작고 가중치가 9이하 이기때문에 시간복잡도 안에 충분히 풀 수 있습니다. 하지만 N이 증가하고, 가중치가 증가한다면 BFS로는 시간복잡도내에 풀 수 없습니다. 해당 문제는 데이크스트라로 문제를 해결하였고, 우선순위 큐를 활용하여 최소 방문거리를 계산 하였습니다. 💡 파이썬의 format 함수 : {}, {} 에 변수를 넣을 수 있다. 또한 소수점 개수를 출력하는 format을 사용하고 싶을 경우 {:.2f} 를 하게되면 소수점 자리가 2개 까지 가능하다. move = ((0,1), (1,0), (0,-1), (-1,0)) import heapq cnt = 1 while True..
[백준] 1162번 : 도로포장 1162번: 도로포장 해당 문제는 데이크스트라 알고리즘으로 문제를 해결 할 수 있습니다. 포장한 도로를 가는경우와 포장하지 않은 도로를 모두 방문하면서 i번째에서 N번째까지의 최단거리를 구하면 됩니다. import sys import heapq input = sys.stdin.readline INF = int(98765432109876543210) N, M, K = map(int, input().split()) dp = [[INF for _ in range(K+1)] for _ in range(N+1)] graph = [[] for _ in range(N+1)] for _ in range(M): P1, P2, T = map(int, input().split()) graph[P1].append([T, P2..
[백준] 2696번 : 중앙값 구하기 2696번: 중앙값 구하기 해당 문제는 우선순위 큐 문제로 중간값 말하기 문제와 똑같은 유형이다. 입력, 출력 포인트만 잘 잡아주면 끝이다. import sys import heapq input = sys.stdin.readline T = int(input()) for _ in range(T): N = int(input()) H = (N-1) // 10 leftq = [] rightq = [] result = [] temp = [] for _ in range(H+1): temp += list(map(int, input().split())) cnt = 1 # 홀수 짝수 체크 cnt for num in temp: if len(leftq) == len(rightq): heapq.heappush(leftq, -..
[백준] 2075번 : N번째큰수 2075번: N번째 큰 수 해당문제는 메모리를 최적화 해야하는 문제입니다. 시간복잡도는 O(N^2)으로 풀 수 있고, 메모리는 12MB로 작게 주어졌습니다. 따라서 우리가 흔히 사용하는 모든 원소를 다 넣고, 정렬을 하는 방식으로는 풀 수 없습니다. 이러한 문제를 해결하기위하여 우선순위 큐 자료구조를 사용하여 항시 큐의 첫번째 인덱스가 N번째 큰값임을 보장해야합니다. 기존 해결방식 ( O(N^) ) from collections import deque import sys input = sys.stdin.readline N = int(input()) priorty = [deque() for _ in range(N)] for _ in range(N): temp = list(map(int, input().sp..
[백준] 1655번 : 가운데를말해요 1655번: 가운데를 말해요 해당 문제는 2개의 우선순위 큐를 사용하여 문제를 해결 하였습니다. Left큐 : 최대 우선순위 힙큐 Right큐 : 최소 우선순위 힙큐 Left[0] 이 중간값 항상 임을 보장합니다. → Light큐와 RIght큐에 번갈아 가면서 삽입했기 때문입니다. Left[0] 의 뒷쪽 원소들의 값은 Left[0] 보다 작은수를 보장해야합니다. Right[0 ~ End] 원소들은 Left[0] 값보다 큰수를을 보장해야합니다. import heapq import sys leftq = [] rightq = [] N = int(input()) for _ in range(N): num = int(sys.stdin.readline()) if len(leftq) != len(rightq): hea..

티스토리툴바