min

1. DP의 탄생 배경 : DP는 완전탐색의 단점을 보안하기 위해서 생겼다. 그럼 여기서 완전탐색은 무엇일까? 완전 탐색이란 말 그대로 처음부터 끝까지 다 돌면서 조건에 부합하는 경우를 고르는 탐색 알고리즘이다. 따라서 완전 탐색을 쓰게 되면 데이터가 많아질 수록 시간이 오래 걸린다. 그래서 나온 알고리즘이 DP이다. 즉 DP는 완전 탐색 보다 빠르며 정확한 알고리즘이다. 하지만 DP는 구현하는데에서 굉장한 어려움이 발생한다. 우리가 완전탐색을 구현하는 것도 힘든데 완전탐색을 효율적으로 처리하기 위해서는 당연히 더 힘들 수 밖에 없다. 그래서 나는 백준의 피보나치 함수를 통해서 한번 DP를 구체적으로 살펴볼까 한다. 2. DP의 구현방법 문제 다음 소스는 N번째 피보나치 수를 구하는 C++ 함수이다. i..

문제 카지노에서 제일 인기 있는 게임 블랙잭의 규칙은 상당히 쉽다. 카드의 합이 21을 넘지 않는 한도 내에서, 카드의 합을 최대한 크게 만드는 게임이다. 블랙잭은 카지노마다 다양한 규정이 있다. 한국 최고의 블랙잭 고수 김정인은 새로운 블랙잭 규칙을 만들어 상근, 창영이와 게임하려고 한다. 김정인 버전의 블랙잭에서 각 카드에는 양의 정수가 쓰여 있다. 그 다음, 딜러는 N장의 카드를 모두 숫자가 보이도록 바닥에 놓는다. 그런 후에 딜러는 숫자 M을 크게 외친다. 이제 플레이어는 제한된 시간 안에 N장의 카드 중에서 3장의 카드를 골라야 한다. 블랙잭 변형 게임이기 때문에, 플레이어가 고른 카드의 합은 M을 넘지 않으면서 M과 최대한 가깝게 만들어야 한다. N장의 카드에 써져 있는 숫자가 주어졌을 때, ..

문제 준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다. 동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) 출력 첫째 줄에 K원을 만드는데 필요한 동전 개수의 최솟값을 출력한다. 이 문제를 처음 접했을 때는 약수를 먼저 알아야 한다는 것을 알았다. 그럼 먼저 약수에 대해서 살펴보자 내가 생각하는 약수는 다음과 같다. 약수는 1과 자기 자신을 ..

지민이는 N개의 원소를 포함하고 있는 양방향 순환 큐를 가지고 있다. 지민이는 이 큐에서 몇 개의 원소를 뽑아내려고 한다. 지민이는 이 큐에서 다음과 같은 3가지 연산을 수행할 수 있다. 첫 번째 원소를 뽑아낸다. 이 연산을 수행하면, 원래 큐의 원소가 a1, ..., ak이었던 것이 a2, ..., ak와 같이 된다. 왼쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 a2, ..., ak, a1이 된다. 오른쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 ak, a1, ..., ak-1이 된다. 큐에 처음에 포함되어 있던 수 N이 주어진다. 그리고 지민이가 뽑아내려고 하는 원소의 위치가 주어진다. (이 위치는 가장 처음 큐에서의 위치이다.) 이때, 그 원소..

큐2 백준 18258 문제 이 문제를 보았을때는 저번에 스택 문제가 떠올랐다. 그래서 나는 리스트를 사용하였다. 근데 처음에 시간 초과가 나왔다. 해당 코드는 다음과 같다. # 시간 초과 코드 import sys n = int(input()) q = [] for i in range(n): data = list(map(str,sys.stdin.readline().split())) if data[0] == "pop": if len(q) != 0: print(q.pop(0)) else: print(-1) if data[0] == "size": print(len(q)) if data[0] == "empty": if len(q) == 0: print(1) else: print(0) if data[0] == "fr..

백준 11047문제 동전0 일단 이 문제를 보았을 때는 최솟값,최댓값등 극단적인 상황을 물어보고 있기 때문에 그리디 알고리즘으로 보았다. 그럼 일단 그리디 알고리즘에 대해 간단하게 설명하겠다. 그리디 알고리즘은 상황을 극단적으로 몰고 가서 가장 간단한 해법을 도출하는 방법이다. 그럼 가장 간단한 해법을 도출해보겠다!! 1. 알고리즘 여기서 핵심이 되는 알고리즘은 바로 동전 리스트를 내림차순으로 배치하는 것이다. 즉 동전 리스트에 원소들을 큰거부터 비교를 하면서 만약 동전값과 주어진 수를 비교하는 작업을 하면 됩니다! 2. 구현 N, K = map(int,input().split()) # 입력 받기 coins = [None] * N cnt = 0 for i in range(N, 0, -1): coins[i..

: 백준 1929번 소수 구하기 문제 이 문제를 보면서 처음 들었던 생각은 소수를 구하는 알고리즘을 생각했다. 근데 들어오는 데이터가 크기 때문에 여러 알고리즘을 비교하면서 필요한 알고리즘을 선택해야 한다고 생각했다. 먼저 데이터를 담은 리스트를 생성한다. => 데이터들 = [11,30,55,100,1000] 그리고 소수를 구하는 알고리즘을 돌아가면서 연산횟수를 각 데이터에 맞는 리스트를 생성한다. 1. 가장 비효율적인 알고리즘 for 데이터 in 데이터들: for n in range(2, 데이터 + 1): for i in range(2,n): cnt += 1 if n % i == 0: break 출력데이터.append(cnt) # 출력데이터 = [24, 159, 568, 1701, 79723] 2.덜 ..

백준 acm 호텔 10250번 문제 오늘은 2개의 조로 나누어서 각 조마다 2일차 문제를 하나씩 잡아서 풀었다. 나는 탁승현님과 함께 acm 호텔에 대해서 풀게 됐다. 탁승현님이 네비게이터 맡게 되었고 나는 드라이버 역할 맡게 되었다. 처음 문제를 읽어봤을 때는 나누기를 통한 몫과 나머지를 이용할려고 했다. 즉 몫과 나머지를 층과 호로 나누어서 생각을 했고 다음과 같은 코드로 작성했다. n = int(input()) for _ in range(n): H,W,N = map(int,input().split()) 몫,나머지 = divmod(N,H) print(나머지*100 + 몫 + 1) 하지만 위 코드는 통과하지 못했다. 왜냐하면 만약 2 5 8이라는 데이터가 주어지면 5라는 답이 출력되기 때문이다. 즉 나..