본문 바로가기

알고리즘/백준

 (263)
[백준] 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..
[백준] 7662번 : 이중우선순위 큐 7662번: 이중 우선순위 큐 처음 이 문제를 풀때 이분탐색법으로 문제를 해결하려고 했으나 시간 초과 판정을 받았습니다. 큐를 하나두고 이분탐색으로 큐를 삽입할 인덱스를 결정하여 해당 인덱스에 값을 삽입한다면 큐의 첫번째 원소값은 최소값 큐의 마지막 원소는 최대값을 갖게 됩니다. T = int(input()) for _ in range(T): k = int(input()) queue = deque() for _ in range(k): cmd , num = map(str, input().split()) number = int(num) if cmd == 'I': # 삽입 if queue: if number > queue[-1]: queue.append(number) else: idx = bisect_left..

티스토리툴바