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 타일로 채우는 방법의 수 D[n] = 2 X n 직사각형을 채우는 방법의 수 2*n 직사각형이 있을 때, 가장 오른 쪽에 타일을 놓을 수 있는 방법은 총 2가지가 있다. 1) 세로 블록이 하나 오는 경우 : D[n-1] 2) 가로 블록 두개 오는 경우 : D[n-2] D[n] = D[n-1] + D[n-2] 2*5의 경우 수는 (1) 2*3경우에서 블록 두 개를 더 붙이는 것과 (2)..

https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 이 문제는 큰 문제를 작은 문제를 통해 풀 수 있으므로 DP를 이용해 풀 수 있다. 예를 들어보면, 4가 입력 되었을 때 4 -> 2 -> 1 이므로 정답은 2가 된다. 이번에는 12가 입력된다면 12/3 = 4이므로 4를 입력으로 했을 때의 정답에서 1을 더하면 된다. 이와 같이 이 문제는 작은 문제들을 통해 큰 문제를 해결 할 수 있다. 또한 큰 문제를 작은 문제로 쪼갤 수 있다. D[N] = N을 1로 만드는 최소 연산 횟수 n = int(input()) dp = [0] * (n+1) dp[1] = 0 f..

1. Overlapping Subproblem - 큰 문제와 작은 문제를 같은 방법으로 풀 수 있다. - 문제를 작은 문제로 쪼갤 수 있다. 2. Optimal Substructure - 문제의 정답을 작은 문제의 정답을 합하는 것으로 구할 수 있다. 3. Dynamic Programming - 다이나믹 프로그래밍에서 각 문제는 한 번만 풀어야 한다. - 정답을 어딘가에 메모해놓는다. => Memoization - 모든 문제를 풀어야 한다. - 모든 문제는 1번만 플어야한다. - 두 가지 구현방식 1. Top-down : 큰 문제를 작은 문제로 나누어서 풀어간다(재귀) 2. Botton-up : 가장 작은 문제를 통해서 큰 문제를 풀어간다(반복문) 4. 다이나민 문제 풀이 전략 글로 점화식의 정의를 세운..

https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net from collections import deque import sys input=sys.stdin.readline n, m, v = map(int, input().split()) visited=[0] * (n+1) graph=[[0]*(n+1) for _ in range(n+1)] for _ in range(m): a, b=map(int, input().s..

https://www.acmicpc.net/problem/13023 13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net import sys n, m = map(int, input().split()) edges = [] a = [[False] * n for _ in range(n)] g = [[] for _ in range(n)] for _ in range(m): u, v = map(int, input().split()) # 방향이 없는 그래프로 양방향 모두 입력 edges.append((u, v)) edges.append((v, u)) # a: 서로 연결되어 있으며 True a[u][v] = a[v][u] = True ..

https://www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 이 문제의 조건은 다음과 같다. 암호의 길이는 L이다. 암호는 C 개의 알파벳으로만 이루어진다. 최소 한 개의 모음과 최소 두 개의 자음이 포함되어 있어야한다. 3번의 조건을 맞추기 위해 check를 만들었다. check 함수는 자음과 모음 갯수를 세서 3번 조건에 맞는지 확인하는 함수이다. import sys input = sys.stdin.readline def check(password): ja ..

https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 문제의 조건은 간단하다. 숫자 n을 입력받고 1, 2, 3을 이용해 N을 만들 수 있는 경우의 수를 만들면 된다. 나는 이 문제를 두가지 방법으로 풀었다. 1. DP 테이블 활용 2. 재귀함수 활용 1. DP 테이블 활용 주어지는 N이 11보다 작은 수이기에 DP 테이블을 활용하여 충분히 풀 수 있을 것이라고 생각했다. DP[i]에는 1, 2, 3 으로 i를 만들 수 있는 경우의 수가 들어간다. 예를들어, 4를 1, 2, 3으로 만드는 경우의 수는 다음과 같다. 1+1+1+1 1+1+2 1+2+..

https://www.acmicpc.net/problem/18290 18290번: NM과 K (1) 크기가 N×M인 격자판의 각 칸에 정수가 하나씩 들어있다. 이 격자판에서 칸 K개를 선택할 것이고, 선택한 칸에 들어있는 수를 모두 더한 값의 최댓값을 구하려고 한다. 단, 선택한 두 칸이 인접 www.acmicpc.net 앞서 풀었던 N과 M 문제의 심화 버전이다. N과 M문제는 1차원 배열이었다면, 이 문제는 2차원 배열이다. 그러나 풀고자 하는 원리는 같으므로 재귀를 통해 해결할 수 있다. 그러나 문제는 시간복잡도이다..🥲 시간을 줄이는 가장 좋은 방법은 중복해서 계산하는 값을 찾아내서 없애는 것이다. 이 문제에서는 go함수에서의 for문에서 중복 계산이 일어날 수 있다. 이를 해결하기 위해 (px,..

https://www.acmicpc.net/problem/15657 15657번: N과 M (8) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net N개의 자연수 중에서 M개를 고른 수열 같은 수를 여러 번 골라도 된다. 고른 수열은 비내림차순이어야 한다. 길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다. import sys input = sys.stdin.readline def go(index, start, n, m): if index == m: print(' '.join(ma..

https://www.acmicpc.net/problem/15656 15656번: N과 M (7) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 이 문제의 조건은 다음과 같다. N개의 자연수 중에서 M개를 고른 수열 같은 수를 여러 번 골라도 된다. 중복을 허용했으므로 visited 배열은 필요없다. arr: 입력받은 배열 result: 출력할 배열 import sys input = sys.stdin.readline def go(index, n, m): if index == m: print(' '.join(map(str, resu..