본문 바로가기

알고리즘124

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이다. 메모리 초과로 바로 실패했다. 쉽사리 방법을 떠올리지 못했고 다른 분들의 블로그를.. 2021. 12. 19.
가장 긴 증가하는 부분 수열 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. 거리 배.. 2021. 12. 18.
치킨 배달[백준 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.. 2021. 12. 17.
평범한 배낭[백준 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] 2021. 12. 16.
퍼즐[백준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[.. 2021. 12. 15.
리모컨[백준-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 =.. 2021. 12. 14.

티스토리툴바