Algorithm/Baekjoon

🗂️ 문제링크: https://www.acmicpc.net/problem/11051  💡 접근법이항 계수란 그냥 조합이다. 즉, (5, 2)란 5C2를 구하는 것이다.이항계수의 성질을 이용하여 동적계획법으로 문제를 풀었으며, 이항계수의 성질은 다음과 같다. nCk = nCn-knCk = n-1Ck + n-1Ck-1파스칼의 삼각형을 본다면 더 쉽게 이해가 가능할 것이다.  위 두 성질을 기반으로 세운 DP 점화식은 다음과 같다.dp[i][k] = dp[i-1][k] + dp[i-1][k-1] (i≥1, k≥1) 추가적으로 코드에서는 1번 성질을 이용해서 for문의 반복횟수를 줄일 수 있다.예시로, 5C2 == 5C3이므로 5//2까지만 순회한다면 5에 대한 모든 조합의 경우를 구할 수 있다.5C0 ==..

🗂️ 문제 링크: https://www.acmicpc.net/problem/9237  💡 접근법최대한 빠르게 모든 묘목을 심고 다 자라게하기 위해서는 자라는 데 오래 걸리는 묘목부터 심어야 한다.따라서 묘목이 자라는 기간을 내림차순으로 정렬한다. 묘목 하나를 심는 데 1일이 소요된다. 이 말은 묘목은 하루에 하나만 심을 수 있다는 말로 해석된다.따라서 묘목을 구입한 1일부터 바로 묘목을 심도록 하자.또한 묘목을 심은 날짜에 묘목이 자라는 데 걸리는 기간을 더한다면 해당 묘목이 모두 자라는 날짜를 구할 수 있다. 예시를 들어 살펴보자.1일에 첫 번째 묘목을 심는다. 이때 첫 번째 묘목이 자라는 데 4일이 걸린다면, 해당 묘목은 5일까지 모두 자란다.2일에 두 번째 묘목을 심는다. 이때 두 번째 묘목이 ..

🗂️ 문제링크: https://www.acmicpc.net/problem/4948  💡 접근법n보다 크고, 2n보다 작거나 같은 소수의 개수를 구하는 문제이다.이때 여러 케이스에 대해 소수를 판별할 때, 동일한 수에 대한 소수 판별 로직이 반복 수행될 수 있다. 이 과정을 없애고자 is_prime_num 리스트를 생성하여 한 번 소수 판별을 수행한 수에 대해서는 True or False로 값을 저장해두어 로직이 재수행되지 않도록 한다. 😎 내 코드import sysdef is_prime(x): if x == 1: return False for i in range(2, int(x**0.5)+1): if x % i == 0: return False..

🗂️ 문제링크: https://www.acmicpc.net/problem/1929  💡 접근법소수는 1과 자기 자신을 제외한 약수가 존재하지 않아야 한다.소수를 판별하기 위해서는 2부터 √x까지만 나눠보면 된다. x = a * b라고 했을 때 a와 b 중 하나는 반드시 √x 이하이기 때문이다. 예를 들어 x = 36 이라고 할 때약수 쌍: (1, 36), (2, 18), (3, 12), (4, 9), (6, 6), (9, 4), (12, 3), (18, 2), (36, 1)즉, 보면 알 수 있듯이, (4, 9) 이후부터는 대칭적으로 반복된다. 😎 내 코드import sysdef gcd(x): if x == 1: return False elif x == 2 or x == 3: ..

🗂️ 문제링크: 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..