백준 알고리즘 - 쉬운 계단 수 (10844) [Python]

문제 www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 문제 상황 - 각자리 숫자의 차가 1씩 나는 수를 만들 때 자리수마다 만들 수 있는 수의 개수를 구한다. 해결 전략 - N자리 숫자는 N-1자리 숫자의 끝에 숫자를 붙이는 구조인데, N-1자리의 1의 자리가 0 또는 9인 경우는 두가지가 아니라 1가지 숫자만 올 수 있다. 결국 number_(N) = number_(N-1) * 2 - (1의 자리가 0 또는 9인 경우의 수)가 된다. 이 때 1의 자리가 0 또는 9인 경우의 수는 N-2에서 1 또는 8의 개수가 된다. 코드 1 2 3 4 5 6 7 8 9 10 11 12..
알고리즘 학습/백준 알고리즘 2020. 9. 20. 15:53
백준 알고리즘 - 1,2,3 더하기 (9095) [Python]

문제 www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 문제 상황 - 입력받은 정수 N을 숫자 1,2,3의 합을 이용해서 표현할 수 있는 방법의 수를 구한다. 해결 전략 - N을 표현하는 방법의 수는 N-1을 표현하는 방법에 1을 더하거나, N-2를 표현하는 방법에 2를 더하거나, 아니면 N-3을 표현하는 방법에 3을 더하는 경우이므로 항이 3개인 피보나치가 된다. 코드 1 2 3 4 5 6 7 8 9 10 from sys import stdin input = stdin.readline T = int(input()) for _ in range(T): N = ..
알고리즘 학습/백준 알고리즘 2020. 9. 20. 15:19
백준 알고리즘 - 1로 만들기 (1463) [Python]

문제 www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 문제 상황 - 연산 3가지를 이용해서 주어진 정수를 1로 만드는데 필요한 최소한의 연산 횟수를 출력한다. 해결 전략 - 부분 문제의 중복이 발생하므로 동적 계획법을 활용한다. 연산이 3개이므로 각각의 경우를 나누어 연산한다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 from sys import stdin input = stdin.readline N = int(input()) cache = [0,0,1,1] + [0]*(N-3) counts = 0 for i in range(4..
알고리즘 학습/백준 알고리즘 2020. 9. 20. 14:41
백준 알고리즘 - 영화감독 숌 (1436) [Python]

문제 www.acmicpc.net/problem/1436 1436번: 영화감독 숌 666은 종말을 나타내는 숫자라고 한다. 따라서, 많은 블록버스터 영화에서는 666이 들어간 제목을 많이 사용한다. 영화감독 숌은 세상의 종말 이라는 시리즈 영화의 감독이다. 조지 루카스는 스타 www.acmicpc.net 문제 상황 - 666이 들어가게 하여 666부터 1666으로 시작하여 n번째 숫자를 찾는다. 해결 전략 - dp문제라고 안내를 받았는데 풀이의 대부분은 brute force였다. 문제는 범위인 10000 이내에 숫자의 범위를 알수가 없어 속도 이슈가 발생할지 아닌지 알 수가 없다.(결과적으로 10000번째 요소는 2666799으로 속도는 매우 여유가 있다.) 코드 1 2 3 4 5 6 7 8 9 10 1..
알고리즘 학습/백준 알고리즘 2020. 9. 20. 13:13
백준 알고리즘 - 계단 오르기 (2579) [Python]

문제 문제 상황 - 계단을 오르며 한번에 1칸, 또는 2칸만 오를 수 있을 때 얻을 수 있는 최대 점수 계산 해결 전략 - 기본적으로 피보나치이고 점수의 최대값을 계산해야하므로 dp를 사용한다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 import sys input = sys.stdin.readline N = int(input()) # 각 계단의 점수 stairs = [int(input()) for _ in range(N)] def stair(N, stairs): stairs = [0] + stairs if N == 1: return stairs[1] elif N == 2: return stairs[2]+stairs[1] elif N..
알고리즘 학습/백준 알고리즘 2020. 8. 28. 20:42
백준 알고리즘 - 로또(6603번)[Python]

😅 문제 https://www.acmicpc.net/problem/6603 🤔 문제 상황 - k개 숫자들이 있는 집합에서 로또번호를 뽑기 위해 6개의 번호를 추출하는 경우를 모두 출력한다. 🧐 해결 전략 - 백트래킹을 사용해야하지만 나는 내장함수 combinations를 사용했다.. 백트래킹으로도 풀어봐야한다. 🎰 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 # main 함수 만들때 import는 안에다 써주어야 한다. def main(): from sys import stdin from itertools import combinations testcase = [] while True: n = list(map(int, stdin.read..
알고리즘 학습/백준 알고리즘 2020. 5. 12. 17:40
백준 알고리즘 - 가장 큰 증가 부분 수열(11055번)[Python]

문제 문제 상황 - 증가하는 부분수열 중 합이 가장 큰 것을 찾아야한다. 증가하는 수열 중 어떤 선택을 할 때 다음에 올 수 있는 요소들에 영향을 미치므로 DP를 활용한다. 해결 전략 - i 와 j로 n^2의 순회를 해주며 a[i] > a[j]일 때에만 비교를 하도록 한다. 코드 1 2 3 4 5 6 7 n, a = int(input()), list(map(int, input().split())) dp = a[:] for i in range(1, n): for j in range(i): if a[i] > a[j]: dp[i] = max(dp[j]+a[i], dp[i]) print(max(dp)) Colored by Color Scripter cs 해설 새로 학습한 것 & 실수 - dp를 초기화 할 때, ..
알고리즘 학습/백준 알고리즘 2020. 5. 1. 10:01
백준 알고리즘 - 정수 삼각형(1932번)[Python]

문제 문제 상황 - 선택을 하나 했을 때, 다음 선택을 할 수 있는 경우는 2가지 뿐이고 한 선택이 다른 선택에 영향을 주며 그 상황에서 최대 값 찾는 문제이므로 DP를 사용한다. 해결 전략 - 최대값을 담는 dp 리스트를 따로 만들어 문제의 dp를 담는다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 # dp[i][j] = i행 j열 까지의 합 중 최대가 되는 경우의 합 # a[i][j] = 주어진 삼각형을 담는 리스트 n = int(input()) a = [[0] for _ in range(n)] for i in range(n): a[i] = list(map(int, input().split())) dp = [[0]*n for _ in range(n)] dp[0][..
알고리즘 학습/백준 알고리즘 2020. 4. 30. 16:13
1 ··· 4 5 6 7 8