본문 바로가기

알고리즘124

최대 힙[백준 11279] - python 최대 힙을 이용하여 구현하는 문제이다. 정답코드 먼저 살펴보자 import heapq import sys n = int(sys.stdin.readline()) heap = [] for i in range(n) : num = int(sys.stdin.readline()) if num == 0 and len(heap) == 0: print(0) elif num == 0 : print(heapq.heappop(heap)[1]) else : heapq.heappush(heap, (-num, num )) 문제에 나와있듯이 힙을 이용해야 겠다는 생각이 들었고 우선순위를 큰 값이 가장 먼저 나올수 있도록 -를 곱해서 거꾸로 넣어주었다. python에서 heapq를 사용하는 방법은 따로 포스팅을 할 예정이다. http.. 2021. 12. 5.
AC [백준 5430] - python 이 문제는 구현이 어려웠던 문제는 아니고 그 안에 개념을 떠올리기가 쉽지 않았었던것 같다.(모든 알고리즘 문제가 그런건가...) 끝에 출력 이슈도 있었다..... t = int(input()) def func(x) : if x != '' : return int(x) for _ in range(t) : commands = list(input()) n = input() array = list(filter(lambda x : x != None, list(map(func, input().replace('[', '').replace(']', '').split(','))))) flag = True reverse_count = 0 for cmd in commands : if cmd == 'R' : reverse_co.. 2021. 12. 5.
버블 소트[백준 1377] - python 버블 소트가 배열의 원소 별로 사이클이 몇번 시행되어야 하는 지를 출력하는 문제다 하나의 숫자가 제위치로 가는 순간을 사이클 하나로 정의해보자 당연히 그냥 버블소트를 생으로 구현해서 출력하면 시간초과이다. 10 1 5 2 3 의 예시를 보면 10과 5에 대한 버블소트 사이클이 시행되어야 한다. 정렬된 상태는 1이 되므로 두번 버블소트 사이클이 시행되면 결과는 3이 된다. 1 3 5 7 9가 입력으로 주어지면 1을 출력하면 된다. 정답 코드 먼저 살펴보자 n = int(input()) array = [] for i in range(n) : n = int(input()) array.append((n, i)) sorted_array = sorted(array) answer = 0 for i in range(n.. 2021. 12. 5.
후위 표기식[백준 1918] - python 꽤나 애를 먹었었던 문제 정답 코드 먼저 살펴보자 n = list(input()) operator = {'(': 1, '+': 2, '-': 2, '*': 3, '/': 3} result = "" stack = [] for i in n : if i == '(' : stack.append(i) elif i == ')' : top = stack.pop() while stack and top != '(' : result += top top = stack.pop() elif i in operator : while stack and operator[stack[len(stack) - 1]] >= operator[i] : top = stack.pop() if i != '(' : result += top stack.a.. 2021. 12. 5.
가장 긴 증가하는 부분 수열 2 [백준 12015] - python 결국 풀지 못했다. 다음번에 틀리지 않기 위해 기록해두자! 설명이 정말 잘되어 있는 블로그를 찾았다. 해당 블로그를 보고 이해한 내용을 정리해두자! 정답코드 먼저 살펴봅시다 import sys from bisect import bisect_left def find(target): start, end = 1, len(dist) - 1 while start target : end = mid else : start = end = mid return end n = int(input()) array = list(map(int, sys.stdin.readl.. 2021. 12. 2.
팩토리얼 0의 개수[백준1676] - python 정답 코드 먼저 살펴보자 import sys n = int(sys.stdin.readline()) two_count = 0 five_count = 0 two = 2 while two 2021. 11. 30.

티스토리툴바