algorithm/문제
-
[Python]백준 15649/N과 M(1)(2)(3)(4) / itertoolsalgorithm/문제 2022. 3. 12. 01:19
https://www.acmicpc.net/problem/15649 https://www.acmicpc.net/problem/15650 ⚡️ 문제 설명 자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성 ⚡️ 해결 방법 파이썬 내장 모듈 itertools를 이용한다 2022.03.12 - [algorithm/개념] - [알고리즘] 완전탐색 / itertools / 순열 중복순열 조합 중복조합 [알고리즘] 완전탐색 / itertools / 순열 중복순열 조합 중복조합 itertools 모듈 순열 permutations(list, r=None) 중복순열 product(list, repeat=1) 조합 combinations(list, r) 중복조합 combi..
-
[Python]백준 9184/신나는 함수 실행/dp정리/top-downalgorithm/문제 2022. 3. 10. 19:04
https://www.acmicpc.net/problem/9184 9184번: 신나는 함수 실행 입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다. www.acmicpc.net ⚡️ 문제 설명 다음과 같은 재귀함수 w(a, b, c)가 있다. if a 20, then w(a, b, c) returns: w(20, 20, 20) if a < b and b < c, then w(a, b, c) returns: w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c) otherwise it returns: w(a-1, b, c) + w(a-1, b-1, c..
-
[Python]백준 1309/동물원/dpalgorithm/문제 2022. 3. 3. 22:16
https://www.acmicpc.net/problem/1309 1309번: 동물원 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. www.acmicpc.net ⚡️ 문제 설명 2*N 배열에 사자를 배치하는 경우의 수가 몇 가지인지를 알아내는 프로그램 ⚡️ 해결 방법 #왼쪽에 있는 경우 dp[i][0]=(dp[i-1][1]+dp[i-1][2])%9901 #오른쪽에 있는 경우 dp[i][1]=(dp[i - 1][0] + dp[i - 1][2])%9901 #둘다 없는 경우 dp[i][2]=(dp[i - 1][0]+ dp[i - 1][1] + dp[i - 1][2])%9901 🟢 왼쪽에 있는 경우 = 전단계에서 오른쪽에 있는 경우 ☑️ + 그 전단계에서 둘다 없는 경우 dp[i][0]=(dp[..
-
[Python]백준 2579/계단오르기/dpalgorithm/문제 2022. 3. 3. 00:30
https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net ⚡️ 문제 설명 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다. 마지막 도착 계단은 반드시 밟아야 한다. 각 계단에 쓰여 있는 점수가 주어질 때 이 게임에서 얻을 수 있는 총 점수의 최댓값을 구하는 프로그램 ⚡️ 해결 방법 dp[..
-
[Python]백준 2644/촌수계산/dfs/bfsalgorithm/문제 2022. 2. 27. 12:05
https://www.acmicpc.net/problem/2644 2644번: 촌수계산 사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어 www.acmicpc.net ⚡️ 문제 설명 여러 사람들에 대한 부모 자식들 간의 관계가 주어졌을 때, 주어진 두 사람의 촌수를 계산하는 프로그램을 작성하시오. ⚡️ 해결 방법 visited 배열은 촌수를 계산할 때 사용할 것이다. 입력받은 두 사람의 친척 관계가 전혀 없어 촌수를 계산할 수 없을 때는 -1을 출력해야 한다. 그러므로 초기 배열을 -1로 해준다. 그리고 처음시작하는 자기자신을 0으로 바꿔준..
-
[Python]백준 11726번/2×n 타일링/dpalgorithm/문제 2022. 2. 23. 17:16
https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net ⚡️ 문제 설명 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. ⚡️ 해결 방법 ⚡️ 코드 import sys input=sys.stdin.readline n=int(input()) dp=[0]*(n+1) for i in range(1,n+1): if(i==1): dp[i]=1 elif(i==2): dp[i]=2 else: dp[i]=dp[i-1]+dp[i-2] pri..
-
[Python]백준 1541번/잃어버린 괄호/greedyalgorithm/문제 2022. 2. 23. 11:59
https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net ⚡️ 문제 설명 괄호를 적절히 쳐서 이 식의 값을 최소로 만드는 프로그램 ⚡️ 해결 방법 이 입력을 예시로 설명해보면 55-50+40 1. -기준으로 나누기 n = input().split('-') 2. 1.에서 -를 기준으로 나누었을 때 첫번째 숫자들 모두 더하기 for i in n[0].split('+'): sum += int(i) 3. 1.에서 -를 기준으로 나누었을 때 뒤에 있는 숫자..
-
[Python]백준 1339번/단어수학/greedyalgorithm/문제 2022. 2. 22. 12:04
https://www.acmicpc.net/problem/1339 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 www.acmicpc.net ⚡️ 문제 설명 단어 수학 문제는 N개의 단어로 이루어져 있으며, 각 단어는 알파벳 대문자로만 이루어져 있다. 이때, 각 알파벳 대문자를 0부터 9까지의 숫자 중 하나로 바꿔서 N개의 수를 합하는 문제이다. 같은 알파벳은 같은 숫자로 바꿔야 하며, 두 개 이상의 알파벳이 같은 숫자로 바뀌어지면 안 된다. 예를 들어, GCF + ACDEB를 계산한다고 할 때, A = 9, B = 4, C = ..