Python
[BOJ] 13398 연속합 2 (Pyhton / 파이썬)
[BOJ] 13398 연속합 2 (Pyhton / 파이썬)
2021.08.23🧷 문제 https://www.acmicpc.net/problem/13398 n개의 정수로 이루어진 임의의 수열이 주어질 때, 연속된 몇개의 수를 선택해서 구할 수 있는 합 중 가장 큰 값을 구하는 문제이다. (단, 수열에서 수를 하나 제거할 수 있다(제거하지 않아도 된다.)) 🛠 풀이 이 문제는 2차원의 DP table을 구성하여 해결할 수 있다. Step 1. 먼저 수열에서 수를 하나 제거했을 때 (dp[i][1])와 그렇지 않은 경우 (dp[i][0])로 나누어준다. dp[0][0], dp[0][1] 은 sequence[0]으로 초기화 해준다. Step 2. 1부터 n-1까지 for문을 돌면서 1. dp[i][0]은 아무런 원소를 제거하지 않았을 때를 비교하면 되므로, (이전까지의 연속합 + i번째..
[BOJ] 9465 스티커 (Python / 파이썬)
[BOJ] 9465 스티커 (Python / 파이썬)
2021.08.18🧷 문제 https://www.acmicpc.net/problem/9465 각 스티커에 점수를 매기고, 점수의 합이 최대가 되게 스티커를 떼어내는 문제이다. (단, 뗀 스티커의 왼쪽, 오른쪽, 위, 아래에 있는 스티커는 사용할 수 없게 된다.) 🛠 풀이 이 문제 또한 혼자 풀다가 해결하지 못해 다른 사람들의 풀이를 참고했다. 여러 사람들의 풀이를 보는데도 이해가 힘들었는데, 거의 다 같은 풀이여서 조금 더 생각을 해봐야할 것 같다. 이 중 내가 이해한 코드의 풀이는 두 가지다. 1. Step 1. 스티커의 점수 리스트를 입력받은 후에, 위쪽 스티커를 뗀 경우(up), 아래쪽 스티커를 뗀 경우(down), 아무것도 떼지 않은 경우(non) 세 가지로 나누어 값을 구해간다. Step 2. for문을 돌면서 ..
[BOJ] 2225 합분해 (Python / 파이썬)
[BOJ] 2225 합분해 (Python / 파이썬)
2021.08.17🧷 문제 https://www.acmicpc.net/problem/2225 0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 프로그램을 작성하는 문제이다. 🛠 풀이 혼자 풀다가 해결하지 못해 다른 사람들의 풀이를 참고했다. 여러 사람들의 풀이를 보니 이 문제는 DP로 푸는 것과 중복조합을 이용해 푸는 두 가지 방법이 존재한다. 1. DP Step 1. 먼저 DP table을 (K x K)의 2차원 테이블로 정의하고, 0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 dp[N][K]에 넣어준다. ex) N = 0, K = 2 일 경우 : 0부터 2까지의 정수 1개를 더해 합이 2가 되는 경우의 수이다. 만들 수 있는 경우의 수는 0+0 한 가지 밖에 없을 것이다...
[BOJ] 1699 제곱수의 합 (Pyhton / 파이썬)
[BOJ] 1699 제곱수의 합 (Pyhton / 파이썬)
2021.08.17🧷 문제 https://www.acmicpc.net/problem/1699 주어진 자연수 N을 제곱수들의 합으로 표현할 때에 그 항의 최소개수를 구하는 문제이다. 🛠 풀이 이 문제는 Bottom-Up 방식의 DP로 해결할 수 있다. Step 1. 먼저 DP table을 길이 n의 1차원 리스트로 만들어준다. 모든 항은 최대 i의 길이를 가지므로 (1+1+1+...+1) 값은 i로 초기화해준다. d = [i for i in range(n+1)] Step 2. 주어진 숫자가 제곱수라면 제곱수 항의 최소 개수는 항상 1이므로, 1부터 i까지 제곱수들을 빼가면서 뺀 숫자 + 1과 기존의 최소 개수를 비교하여 답을 구해준다. if dp[i] > dp[i - j*j] + 1: dp[i] = dp[i - j*j] +..
[BOJ] 11053 가장 긴 증가하는 부분 수열 (Pyhton / 파이썬)
[BOJ] 11053 가장 긴 증가하는 부분 수열 (Pyhton / 파이썬)
2021.08.04🧷 문제 https://www.acmicpc.net/problem/11053 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 문제이다. 🛠 풀이 이 문제는 DP로 해결할 수 있는 보편적인 문제 중 하나이다. Step 1. 먼저 DP table을 길이 n의 1차원 리스트로 만들어준다. 모든 부분수열은 최소한 1의 길이를 가지므로 값은 1로 초기화해준다. d = [1] * n Step 2. 주어진 sequence리스트를 순회하면서 해당 인덱스 i까지 더 작은 값을 갖는 sequence[j] 중 DP table의 값이 가장 큰 d[j]에 1을 더해준다. Step 3. 위의 방법으로 구해진 DP table의 값들 중 가장 큰 값을 출력한다. 🖊 나의 코드 import sys if __name__ ..
[BOJ] 10844 쉬운 계단 수 (Python / 파이썬)
[BOJ] 10844 쉬운 계단 수 (Python / 파이썬)
2021.08.04🧷 문제 https://www.acmicpc.net/problem/10844 정수 n이 주어졌을 때, 길이가 n인 모든 자리수의 차이가 1이 나는 계단수의 개수를 구하는 문제이다. 🛠 풀이 이 문제는 DP table을 1차원이 아닌 2차원으로 구성해야 해결할 수 있다. Step 1. 먼저 DP table을 d[자리수][끝자리 숫자] = 경우의 수로 구성한다. Step 2. 자리수 0 1 2 3 4 5 6 7 8 9 1 0 1 1 1 1 1 1 1 1 1 2 1 1 2 2 2 2 2 2 2 1 3 1 3 3 4 4 4 4 4 3 2 자리수가 1일때부터 보면, 자리수가 1일때는 당연하게도 경우의 수가 1이다. 자리수가 2일때부터는 맨 뒤에 0 또는 9가 오는 경우 특수하다. 첫번째로, 0으로 끝나는 경우 자..
[BOJ] 15990 1, 2, 3 더하기 5 (Python / 파이썬)
[BOJ] 15990 1, 2, 3 더하기 5 (Python / 파이썬)
2021.08.01🧷 문제 https://www.acmicpc.net/problem/15990 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 과정에서 같은 수를 두 번 이상 연속해서 사용하지 않는 방법의 수를 구하는 문제이다. 🛠 풀이 이 문제는 DP table을 1차원이 아닌 2차원으로 구성해야 해결할 수 있다. Step 1. 먼저 각 인덱스의 DP table을 길이 4의 리스트로 받는데 0번 인덱스에는 n을 만들 수 있는 방법의 수, 1 ~ 3번 인덱스에는 각 인덱스로 끝나는 방법의 수를 넣어준다. 예를 들면 d[3]의 경우 2 + 1, 1 + 2, 3 이렇게 총 3가지의 경우를 가지고 있고 1, 2, 3으로 끝나는 방법이 각 1개씩 존재하므로 d[3] = [3, 1, 1, 1]로 초기화해준다. 같은 ..
[BOJ] 11052 카드 구매하기 (Python / 파이썬)
[BOJ] 11052 카드 구매하기 (Python / 파이썬)
2021.08.01🧷 문제 https://www.acmicpc.net/problem/11052 카드 팩의 가격이 주어졌을 때, N개의 카드를 구매하기 위해 지불해야 하는 금액의 최댓값을 구하는 문제이다. 🛠 풀이 이 문제는 Bottom-Up 방식의 다이나믹 프로그래밍(DP)를 이용하여 해결할 수 있다. Step 1. 이 문제를 풀기 위해 생각을 해보면 n개의 카드를 구매하기 위한 최대 금액 d[n]은 d[n], d[1] + d[n-1], d[2] + d[n-2], ... , d[j] + d[n-j]중 가장 큰 값과 같다. Step 2. for문을 돌기 전 d[i]의 값을 입력으로 받은 card_pack[i]로 초기화 시켜준 후에 j == 1와 j == i-1은 같으므로 j는 i의 절반까지만 돌도록 한다. Step 3. f..
[BOJ] 2004 조합 0의 개수 (Python / 파이썬)
[BOJ] 2004 조합 0의 개수 (Python / 파이썬)
2021.07.30🧷 문제 https://www.acmicpc.net/problem/2004 조합 nCm의 끝자리 0의 개수를 출력하는 문제이다. 🛠 풀이 이 문제는 시간초과를 신경써야 하는 문제이다. Step 1. 이 문제를 단순히 nCr = n! / r!(n-r)!을 계산한 후에 10으로 나눠서 계산하면 문제에서 주어진 입력의 범위때문에 시간초과가 난다. Step 2. 그렇다면 끝자리가 0이 나올 수 있는 경우를 생각해본다. 끝자리가 0이 되려면 2와 5의 곱으로 이루어져야한다. 즉, 2와 5의 쌍의 갯수를 구하면 끝자리 0의 개수를 구할 수 있다. Step 3. 다시 한번, 10이 만들어지려면 2와 5가 쌍을 이뤄야 하므로 2의 갯수와 5의 갯수 중 더 작은 것을 선택하면 된다. 🖊 나의 코드 import sys i..
[BOJ] 1929 소수 구하기 (Python / 파이썬)
[BOJ] 1929 소수 구하기 (Python / 파이썬)
2021.07.30🧷 문제 https://www.acmicpc.net/problem/1929 M이상 N이하의 소수를 모두 출력하는 문제이다. 🛠 풀이 이 문제는 '에라토스테네스의 체' 를 이용해 해결할 수 있다. Step 1. 에라토스테네스의 체를 이용해 소수를 판별한다. 에라토스테네스의 체 : 소수를 판별할 범위만큼 배열을 할당하고 그 인덱스에 해당값을 넣어준 후에, 2부터 시작해서 그 값이 True라면 그 수의 배수에 해당하는 숫자들을 모두 False로 바꿔주는 것을 반복해 대량의 소수를 한꺼번에 판별하는데 용이한 알고리즘이다. 🖊 나의 코드 import sys input = sys.stdin.readline def is_prime(x, y): prime_num = [True] * (y+1) for i ..
[BOJ] 2609 최대공약수와 최소공배수 (Python / 파이썬)
[BOJ] 2609 최대공약수와 최소공배수 (Python / 파이썬)
2021.07.30🧷 문제 https://www.acmicpc.net/problem/2609 두 개의 자연수를 입력받아 최대공약수와 최소공배수를 출력하는 문제이다. 🛠 풀이 이 문제는 유클리드 호제법을 이용해 최대 공약수와 최소 공배수를 구하면 된다. Step 1. 유클리드 호제법을 이용해 최대공약수를 구한다. 유클리드 호제법 : 2개의 자연수의 최대공약수를 구하는 알고리즘이다. "a와 b의 최대공약수는 a를 b로 나눈 나머지와 b의 최대공약수와 같다."두 수 x와 y가 있을 때, (단, x >= y) def gcd(x, y): while b > 0: a, b = b, a % b return a 🖊 나의 코드 import sys input = sys.stdin.readline def GCD(a, b): while b > ..
[BOJ] 1918 후위 표기식 (Python / 파이썬)
[BOJ] 1918 후위 표기식 (Python / 파이썬)
2021.07.30🧷 문제 https://www.acmicpc.net/problem/1918 주어진 중위 표기식(infix)을 후위 표기식(postfix)로 바꾸는 문제이다. 문제에 나와있다시피 연산자의 우선순위에 따라 스택에서 push, pop의 과정을 통해 해결할 수 있다. 🛠 풀이 이 문제의 중요한 포인트는 연산자의 우선순위를 비교할 때, 우선순위가 같다면 stack안에 들어있는, 즉 식에서 왼쪽에 위치한 연산자를 처리해준다는 것이다. Step 1. expression리스트를 처음부터 한 문자씩 탐색한다. expression[i]가 알파벳이라면 res라는 결과 리스트에 append해준다. Step 2. expression[i]가 알파벳이 아니고 연산자라면 우선순위에 맞게 처리를 해준다. expression[i]가 (..