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/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net import sys sys.setrecursionlimit(100000) input = sys.stdin.readline n, m = map(int, input().split()) arr = [[] for _ in range(n)] visited = [False] * n for _ in range(m): u, v = map(int, i..

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/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 어떤 날은 상담을 하는 것이 좋고, 어떤 날은 오히려 상담을 안하는 것이 좋다. 안하는 것이 좋은 날은 이후에 상담을 하게 되는 것이 수익이 더 많은 경우이다. 이것은 상황에 따라 그때그때 다르니 모두 해보는 것이 좋다. sum: day-1일까지의 수익 1. 상담을 한다: go(day+T[day], sum+P[day]) - 현재 날짜에서 상담을 할 경우 걸리는 날짜를 더해준다. - 현재까지 얻은 수익에서 상담을 할 경우 얻게 되는 수익을 더해준다. 2. 상담을 안한다: go(day+1, sum) - 상담을 안하고 다음날로 넘어가므로 ..

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,..