알고리즘

숨바꼭질2[백준 12851] - python

방문한 곳의 최소 시간과 방법의 수를 출력해주어야 한다. 각 지점마다 두개의 정보를 가지고 있어야 하므로 이차원 배열로 선언해 주었다. 정답 코드 먼저 살펴보자 n, k = map(int, input().split()) MAX_LENGTH = 100001 visited = [[-1, 0] for _ in range(MAX_LENGTH)] queue = [] queue.append(n) # 처음 방문한 곳은 방문정보와 방법의 수를 업데이트 visited[n][0] = 0 visited[n][1] = 1 while queue : x = queue.pop(0) for i in [x-1, x+1, x*2] : if 0

최소공배수 [백준 1934] - python

앞으로 글을 작성할때 근거를 같이 작성하려고 한다. 코드를 작성한 근거나, 자료구조를 선택한 근거, 어떤 논리를 적용한 근거... 너무 무지성으로 진행하고 있었지 않나 싶다. 개인적인 이야기는 각설하고 코드를 같이 살펴보자 def gcd(first, second) : array = [0] * (first + 1) for i in range(1, first+1) : if first % i == 0 : array[i] = 1 max_num = 0 for i in range(len(array)): if array[i] == 1 and second % i == 0: max_num = i return max_num t = int(input()) for _ in range(t) : a,b = map(int, inp..

최대 힙[백준 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..

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..

버블 소트[백준 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..

후위 표기식[백준 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..

가장 긴 증가하는 부분 수열 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..

팩토리얼 0의 개수[백준1676] - python

정답 코드 먼저 살펴보자 import sys n = int(sys.stdin.readline()) two_count = 0 five_count = 0 two = 2 while two

합분해[백준 2225] - python

기본적인 다이나믹 프로그래밍이다. 배열을 그리고 초반 몇개를 직접 시도해보면 규칙이 보일거다 정답 코드 먼저 보자 n, k = map(int, input().split()) dp = [[0] * (k+1) for _ in range(n+1)] dp[0][0] = 1 for i in range(0, n+1) : for j in range(1, k+1) : dp[i][j] = dp[i-1][j] + dp[i][j-1] print(dp[n][k] % 1000000000) k = 1 인경우 모든 숫자는 1이다. k = 2 인경우 모든 숫자는 (n+1)을 가진다. n=2: (0,2)(1,1)(2,0) n=3: (0,3)(1,2)(2,1)(3,0) n=4: (0,4)(1,3)(2,2)(3,1)(4,0) k= 3 인..

2로 몇 번 나누어질까[백준 1407] - python

이 문제는 크로아티에서 고등학생 대상으로 나온 문제다. 상당히 애를 먹었던 문제다.(아직 멀었나 보다) 코드 먼저 살펴보자 a,b = map(int, input().split()) def calc(number) : if number == 0 : return 0 elif number == 1 : return 1 elif number % 2 == 0 : return number // 2 + 2 * calc(number // 2) elif number % 2 == 1 : return number // 2 + 2 * calc(number // 2) + 1 print(calc(b) - calc(a-1)) 애를 먹었던 거에 비해서는 굉장히 간단하다. 규칙만 잘 찾으면 절대 어렵지 않은 문제다. 그 규칙에 대해서 아..