yoon's Devlog

이분탐색은 탐색을 반복할수록 탐색할 대상이 1/2가 되는 알고리즘이다. 따라서 시간 복잡도는 O(logN)이다. 이분 탐색은 "반드시 정렬된 상태"에서 시작되어야 한다. 파이썬으로의 구현은 재귀, 비재귀 방법이 있다. 우선 비재귀를 살펴보자. 비재귀 방법 import sys n=int(sys.stdin.readline()) arr_n = list(map(int,sys.stdin.readline().split())) m=int(sys.stdin.readline()) arr_m = list(map(int,sys.stdin.readline().split())) arr_n.sort() for i in range(m): left = 0 right = len(arr_n)-1 while left end: return..

백준 동적계획법 문제를 풀다가 동적계획법에 대해 잘 정리해놓은 게시물이 있어 공유한다. https://velog.io/@bonjaski0989/%EB%8F%99%EC%A0%81%EA%B3%84%ED%9A%8D%EB%B2%95Dynamic-Programming-%EC%A0%95%EB%A6%AC%EA%B8%80Python 동적계획법(Dynamic Programming) 정리글_Python 동적계획법에 대한 정리글입니다. (피보나치 수열 파이썬 구현) velog.io 간단히 말해, 동적 계획법은 소문제의 결과를 다른 소문제를 푸는 데에 사용하는 풀이법으로, 동적계획법을 사용하기 위해서는 부분해가 전체 문제의 해를 구하는 데 사용되는 지 여부를 가리키는 최적성의 원리를 만족하는지 우선 판단해야 한다. 점화식을 ..

https://www.acmicpc.net/problem/9184 9184번: 신나는 함수 실행 입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다. www.acmicpc.net 이 문제는 동적 계획법 문제이다. 내 풀이 import sys d_abc = [[[0]*21 for i in range(21)] for i in range(21)] def w(a,b,c): if a 20: if d_abc[20][20][20] ==0: d_abc[20][20][20] = w(20,20,20) return d_abc[20][20][20] if a < b and b < c: if d_ab..

https://www.acmicpc.net/problem/10816 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 내 풀이 import sys n=int(sys.stdin.readline()) arr_n = list(map(int,sys.stdin.readline().split())) m=int(sys.stdin.readline()) #이 알고리즘은 arr_n을 차례로 순회하여 arr_m에 있는지 체크하는 알고리즘이다. #출력 시 처음 인덱스들의 순서 알기 위해 tmp로 받고..

https://www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 내 풀이 - 1 import sys n,k = map(int,sys.stdin.readline().split()) coin = [] for i in range(n): coin.append(int(sys.stdin.readline())) len = n count= 0 coin.sort(reverse=True) #print(coin) f..

https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 내 풀이 from collections import deque line = input().split('-') res = 0 for i in range(len(line)): lst = list(map(int,str(line[i]).split('+'))) if i==0: res+=sum(lst) else: res-=sum(lst) print(res) 식의 최소값은, - 다음에 오는 식이 괄호로 ..

https://www.acmicpc.net/problem/13305 13305번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1 www.acmicpc.net 내 풀이 import sys n = int(sys.stdin.readline()) road = list(map(int,sys.stdin.readline().split())) city = list(map(int,sys.stdin.readline().split())) res = 0 min_city = city[0] for i in range(n-1): if city[i]

https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 내 풀이 - 주석 from itertools import combinations,permutations import sys n = int(sys.stdin.readline()) arr = [] for i in range(n): arr.append(list(map(int,sys.stdin.readline().split()))) #조합으로 6명이면 3명씩, 4명이면 2명씩 뽑기 combi =list(combinations..