Algorithm

🗂️ 문제링크: https://www.acmicpc.net/problem/1874 💡 접근법제시하는 입력값의 수열을 만들기 위해 1~N까지 차례로 숫자가 입력될 때 스택에서 어떤 순서로 push와 pop을 해야할 지를 결정해야 하는 문제이다. 풀이는 다음과 같다. 1부터 N까지 숫자를 차례대로 입력한다.스택의 top이 현재 비교하는 수열보다 작다면 현재 숫자를 스택에 push한다.스택의 top이 현재 비교하는 수열과 같다면 스택에서 pop하고, 반복 수행한다.위 과정을 while 문을 통해 반복 수행하는 이유는, pop한 뒤 수열의 top과 다음 수열이 같을 수 있기 때문이다.모든 숫자를 입력한 뒤 만약 스택이 비어있다면 만들 수 있는 수열이 되고, 스택이 비어있지 않다면 만들 수 없는 수열에 해당한..

🗂️ 문제문제효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규칙이 있다.포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다.연속으로 놓여 있는 3잔을 모두 마실 수는 없다.효주는 될 수 있는 대로 많은 양의 포도주를 맛보기 위해서 어떤 포도주 잔을 선택해야 할지 고민하고 있다. 1부터 n까지의 번호가 붙어 있는 n개의 포도주 잔이 순서대로 테이블 위에 놓여 있고, 각 포도주 잔에 들어있는 포도주의 양이 주어졌을 때, 효주를 도와 가장 많은 양의 포도주를 마실 수 있도록 하는 프로그램을 작성하시오.예를 들어..

🗂️ 문제링크: https://www.acmicpc.net/problem/1904 💡 접근법00과 1을 조합하여 N자리의 수를 만드는 문제이다.문제에서는 제시하는 자릿수에 따라 만들 수 있는 수의 개수가 달라진다. 규칙을 찾아보기 위해 다음과 같이 N에 따라 가능한 경우를 나열해보았다. N=1일 때, 1 ⇒ 1개 N=2일 때, 11, 00 ⇒ 2개 N=3일 때, 001, 100, 111 ⇒ 3개 N=4일 때, 1111, 0011, 1001, 1100, 0000 ⇒ 5개 N=5일 때, 11111, 00111, 10011, 11001, 11100, 00001, 00100, 10000 ⇒ 8개 규칙을 보니 DP인 걸 단숨에 알아낼 수 있었다. 하지만 왜 DP인가를 생각해보면, 그 이유는 다음과 같다. 2진..

🗂️ 문제링크: https://www.acmicpc.net/problem/14002 💡 접근법DP를 통해 LIS를 푸는 문제의 응용편이다. i번째까지 순열에 대해 증가하는 순열인 경우이면서 부분 순열의 길이가 더 길어질 때, dp에 현재까지의 부분 순열을 저장한다.이후, 가장 길이가 큰 부분 순열에 대해 부분 순열의 길이와 부분 순열을 출력한다. 😎 내 코드import sysN = int(sys.stdin.readline())arr = list(map(int, sys.stdin.readline().split()))dp = [[arr[i]] for i in range(N)]for i in range(1, N): for j in range(i): if arr[i] > arr[j] an..

🗂️ 문제링크: https://www.acmicpc.net/problem/2579  💡 접근법i번째 계단까지 오르는 데 최댓값을 구해야한다는 DP 관점은 이해했으나, 점화식을 제대로 세우지 못했다. 계단에 오를 수 있는 경우는 1. i-1번째 계단에서 오르는 경우, 2. i-2번째 계단에서 오르는 경우이다.하지만 i-1번째 계단에서 오르는 경우가 연속된다면, 최종적으로는 i-2 → i-1 → i번째 순으로 계단에 오르게 된다.이를 처리하기 위해 i-1번째 계단에서 오르는 경우에 대해서는 무조건 그 이전에는 i-3번째 계단을 거쳐야 한다. 따라서 이를 고려한 최종적인 점화식은 다음과 같다.dp[i] = max(dp[i-3] + stairs[i-1], dp[i-2]) + stairs[1] (i ≥ 2) ..

🗂️ 문제문제김형택은 지금 몰래 Spider Solitaire(스파이더 카드놀이)를 하고 있다. 형택이는 이 게임을 이길 때도 있었지만, 질 때도 있었다. 누군가의 시선이 느껴진 형택이는 게임을 중단하고 코딩을 하기 시작했다. 의심을 피했다고 생각한 형택이는 다시 게임을 켰다. 그 때 형택이는 잠시 코딩을 하는 사이에 자신의 게임 실력이 눈에 띄게 향상된 것을 알았다.이제 형택이는 앞으로의 모든 게임에서 지지 않는다. 하지만, 형택이는 게임 기록을 삭제 할 수 없기 때문에, 자신의 못하던 예전 기록이 현재 자신의 엄청난 실력을 증명하지 못한다고 생각했다.게임 기록은 다음과 같이 생겼다.게임 횟수 : X이긴 게임 : Y (Z%)Z는 형택이의 승률이고, 소수점은 버린다. 예를 들어, X=53, Y=47이라..

🗂️ 문제문제현우는 용돈을 효율적으로 활용하기 위해 계획을 짜기로 하였다. 현우는 앞으로 N일 동안 자신이 사용할 금액을 계산하였고, 돈을 펑펑 쓰지 않기 위해 정확히 M번만 통장에서 돈을 빼서 쓰기로 하였다. 현우는 통장에서 K원을 인출하며, 통장에서 뺀 돈으로 하루를 보낼 수 있으면 그대로 사용하고, 모자라게 되면 남은 금액은 통장에 집어넣고 다시 K원을 인출한다. 다만 현우는 M이라는 숫자를 좋아하기 때문에, 정확히 M번을 맞추기 위해서 남은 금액이 그날 사용할 금액보다 많더라도 남은 금액은 통장에 집어넣고 다시 K원을 인출할 수 있다. 현우는 돈을 아끼기 위해 인출 금액 K를 최소화하기로 하였다. 현우가 필요한 최소 금액 K를 계산하는 프로그램을 작성하시오.입력1번째 줄에는 N과 M이 공백으로 ..

🗂️ 문제https://www.acmicpc.net/problem/2512 💡 접근법총 예산이 예정 예산을 초과할 경우 예산의 상한액을 설정해야 하며, 이때 이분탐색을 사용한다.하지만 만약 모든 예산이 배정될 수 있는 경우에는 상한액을 설정할 필요가 없으니 예산의 최댓값을 리턴한다. 이분탐색을 위해 low=1, high는 예산들 중 최댓값으로 설정한다. 이때 mid를 통해 상한액을 정하고,상한액보다 적은 예산은 그대로 예산을 적용하되, 상한액을 초과하는 예산은 상한액으로 금액을 산정하여 예산의 합을 계산한다. 만약 예산의 합이 총 예산보다 크다면, 상한액을 더 내려야 하므로 high 값을 mid-1로 조정한다. 만약 예산의 합이 총 예산보다 작다면, 이는 상한액을 더 올려야 하므로 low 값을 mid..