알고리즘

N번째 큰 수[백준 2075번] - python

정답코드 먼저 살펴보자 import sys, heapq def BOJ2075(): n = int(input()) array = list(map(int, sys.stdin.readline().split())) for _ in range(n-1) : for i in list(map(int, sys.stdin.readline().split())): if array[0] < i : heapq.heappop(array) heapq.heappush(array, i) print(array[0]) BOJ2075() 맨 처음에는 배열로 입력받지 않고 배열에 값을 하나씩 넣은다음에 전체를 정렬후 값을 출력했었다. 문제의 조건은 12mb이다. 메모리 초과로 바로 실패했다. 쉽사리 방법을 떠올리지 못했고 다른 분들의 블로그를..

가장 긴 증가하는 부분 수열 3

import sys from bisect import bisect_left input = sys.stdin.readline def BOJ12738(): N = int(input()) A = list(map(int, input().split())) dist = [-1000000001] index = [0] * (N + 1) for i in range(len(A)): num = A[i] if dist[-1] < num: dist.append(num) else: index[i] = bisect_left(dist, num) dist[index[i]] = num max_length = len(dist) - 1 print(max_length) BOJ12738() 접근 방법 0. 거리 배열을 하나 두자 1. 거리 배..

치킨 배달[백준 15686] - python

정답 코드 import sys from itertools import combinations def BOJ15686() : N, M = map(int, sys.stdin.readline().split()) graph = [] for _ in range(N) : graph.append(list(map(int, sys.stdin.readline().split()))) chiken_store_list = [] house_list = [] for x in range(N) : for y in range(N) : if graph[x][y] == 1 : house_list.append([x+1, y+1]) elif graph[x][y] == 2 : chiken_store_list.append([x+1, y+1]) c..

평범한 배낭[백준 12865] - python

dp를 접하게 되면 꼭 나오는 냅색(knapsack) 문제이다. 예전에 제대로 학습해두지 않았었고 결국 다른 분들의 코드를 참고했다 import sys def BOJ12865() : n, k = map(int, sys.stdin.readline().split()) item_list = [[0,0]] dp = [[0] * (k+1) for _ in range(n+1)] for _ in range(n) : w,v = map(int, sys.stdin.readline().split()) item_list.append([w,v]) for i in range(1, n+1) : for j in range(1, k+1) : weight, value = item_list[i] if item_list[i][0]

퍼즐[백준1525] - python

배열 자체를 bfs에 넣고 매번 꺼낸 배열을 string으로 변환해서 비교를 하려고 시도했었다가. 이건 아니다 싶어서 bfs에 문자열을 넣고 x,y의 좌표를 이용해서 배열에서 바꿔야 하는 0의 인덱스를 계산해서 다음 값과 바꿔주는 형식으로 시도했었다. 근데 이 방법은 메모리 부족으로 통과 하지 못했고. 결국 다른 분들의 코드를 참고했다. 정답코드 먼저 살펴보자 dx = [0, 0, 1, -1] dy = [1, -1, 0, 0] def bfs(): while q: now = q.popleft() if now == "123456789": return cntDict[now] pos = now.find("9") x = pos // 3 y = pos % 3 for i in range(4): nx = x + dx[..

리모컨[백준-1107] - python

정답코드 먼저 살펴보자 def BOJ1107(): n = int(input()) m = int(input()) count = abs(100 - n) button = [True] * 10 if m != 0 : for errored in list(map(int, input().split())) : button[errored] = False for i in range(1000001) : listed_number = list(str(i)) listed_number_length = len(listed_number) flag = True for number in listed_number : if button[int(number)] == False : flag = False break if flag : count =..

병든 나이트[백준 1783] - python

예전에 무진장 겁먹고 못풀었던 문제 정답코드 먼저 살펴보자 n,m = map(int, input().split()) if n == 1 : print(1) elif n == 2 : print(min((m + 1) // 2, 4)) else : if m < 7 : print(min(m, 4)) else : print(m - 2) 핵심은 1,2,3,4 조건의 경우 무조건 오른쪽으로 움직인다는 거다.(왼쪽으로는 돌아올수 없다.) 4번 다 완료하면 오른쪽으로 이동한 수는 6이 된다. 왠지 6이 기준점이 될것 같았다. n이 1이면 이동은 불가능해서 1 n이 2이면 최대 4의 경우이거나 m을 2로 나눈 경우중 최솟값의 가지수를 가지게 된다 n이 3이상이면 위로 혹은 아래로 이동하는 경우의 수는 제약을 받지 않으므로 ..

RGB거리[백준 1149] - python

정답 코드 먼저 살펴보자 n = int(input()) cost = [] for _ in range(n) : cost.append(list(map(int, input().split()))) for i in range(1, len(cost)) : cost[i][0] = min(cost[i-1][1], cost[i-1][2]) + cost[i][0] cost[i][1] = min(cost[i-1][0], cost[i-1][2]) + cost[i][1] cost[i][2] = min(cost[i-1][0], cost[i-1][1]) + cost[i][2] print(min(cost[n-1][0], cost[n-1][1], cost[n-1][2])) 너무 어렵게 생각했었다. 각 라운드에 빨강, 파랑, 초록을 색..

RGB거리2[백준 17404] - python

너무 어려웠다. 결국 다른 분들의 잘 짜신 코드를 참고했다. ㅠㅠ 정답코드 먼저 살펴보자 n = int(input()) cost = [] INF = 1e9 for _ in range(n): cost.append(list(map(int, input().split()))) result = INF for start_number in range(3) : dist = [[0] * 3 for _ in range(len(cost))] for i in range(3) : if i != start_number : dist[0][i] = INF else : dist[0][i] = cost[0][i] for i in range(1, len(cost)): dist[i][0] = min(dist[i-1][1], dist[i-1..

숨바꼭질3[백준13549] - python

숨바꼭질 시리즈 3번째 문제다 정답 코드 먼저 살펴보자 from collections import deque n, k = map(int, input().split()) location = [-1] * 100001 time = 0 queue = deque() queue.append([n, time]) location[n] = 0 while queue : curr_n, curr_time = queue.popleft() next_n = curr_n * 2 if 0 3 -> 6 -> 12 ii) 4 -> 5 -> 6 -> 12 6에 접근을 하는 경우가 i)의 경우 1, ii)의 경우 2이다. 내 코드에서는 ii)의 경우가 먼저 6에 접근이 되었고 i)의 경우에서 6에 접근할때 기존 6에 업데이트를 해주어야 했다..