CS
[BaekJoon] 백준 11052 카드 구매하기
[BaekJoon] 백준 11052 카드 구매하기 문제: https://www.acmicpc.net/problem/11052 내코드 -DP 문제였다. 주어진 문제에 따르면 점화식은 아래와 같다. 카드 N개를 구매할 때 최대 비용 = MAX(i=1~N)(카드 i개 들어있는 카드팩 구매하는 비용 + 카드 N-i개 들어있는 카드팩 구매하는 비용) import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int[] result = new int[N+1]; int[] prices = new int[N+1]; fo..
[BaekJoon] 백준 2011번 암호코드
[BaekJoon] 백준 2011번 암호코드 문제: https://www.acmicpc.net/problem/2011 내코드 다이나믹 프로그래밍에 익숙하지 않아서 다이나믹 프로그래밍 문제를 찾다가 발견해서 풀었다. 즉, 다이나믹 프로그래밍 문제인 것을 알고 풀었다. 우선 점화식을 찾았다. f("25114")가 25114에서 나올 수 있는 암호의 개수라고 하자. f("25114") = f("2511") + f("251")이 된다. 즉, f(n) = f(n[:-1]) + f(n[:-2]) 이다. 이렇게 금방 점화식을 찾을 수 있다. 두번째로 생각해야 할 부분은 메모이제이션이다. 시간 초과를 피하기 위해 딕셔너리를 만들어 줬다. 여기서는 f(n)에서 n의 길이가 같다면 f(n)이 같다는 특징이 있다. 즉, 길..
[Algorithm] 다이나믹 프로그래밍 Dynamic Programming
다이나믹 프로그래밍 (Dynamic Programming, DP)란? 다이나믹 프로그래밍 (이하 DP)란 여러개의 하위 문제를 먼저 푼 후 그 결과를 쌓아올려 주어진 문제를 해결하는 알고리즘이다. 분할정복과 비슷하다고 생각할 수 있지만 분할정복은 작은 문제가 중복이 일어나지 않고, DP는 반복(작은 문제의 결과가 같다)된다. 그래서 DP에서는 작은 문제들이 반복되는 것을 이용해 문제를 풀어나간다. 포인트는 모든 작은 문제들은 중복을 제거하고 한번만 풀어야 한다는 점이다. 따라서 정답을 구한 작은 문제들을 어딘가에 메모(Memoization)해둔다. 다시 그보다 큰 문제를 풀 때 똑같은 작은 문제가 나타나면 앞서 메모한 작은 문제의 결과값을 이용한다. 많이 언급하는 피보나치 수열 문제를 예시로 들어보자. ..
[BaekJoon] 백준 14719 빗물
[BaekJoon] 백준 14719 빗물 문제: https://www.acmicpc.net/problem/14719 내코드 처음에는 왼쪽부터 시작해서 start, end 변수를 갱신해가며 구해줬다. 하지만 28 100 10 20 과 같이 마지막에 작은 값으로 끝나는 경우 저리가 어려워 실패했다. 그래서 서칭을 통해 찾은 방식은 다음과 같다. 1. for문으로 가로 전체를 돌아준다. 2. 현재 위치(i)의 왼쪽과 오른쪽 각각에서 최대값을 찾는다. 3. 2에서 찾은 두 값 중 더 작은 값을 찾는다. 4. 3에서 찾은 값과 현재 위치(i)의 높이의 차를 계산한다. 5. 4에서 계산한 값이 현재 위치에서 물이 차오르는 정도이다. 따라서 결과 값에 더해준다. 구현 문제가 나오면 대응을 잘 못하는 것 같다. 아무래..
[BaekJoon] 백준 1913번 달팽이
[BaekJoon] 백준 1913번 달팽이 문제: https://www.acmicpc.net/problem/1913 내코드 - 시간이 부족했던 문제가 아니라 단순 코딩으로 구현할 수 있었다. - 상하좌우로 이동하는 횟수에서 규칙을 찾아서 구현했다. # BaekJoon1913.py N = int(input()) num = int(input()) arr = [[0 for _ in range(N)] for _ in range(N)] value = 1 a = int(N / 2) b = int(N / 2) arr[a][b] = value tmp = int((N - 1) / 2) for i in range(tmp): # 위로 이동 for _ in range(2 * i + 1): value += 1 a -= 1 ar..
[BaekJoon] 백준 1325 효율적인 해킹
[BaekJoon] 백준 1325 효율적인 해킹 문제: https://www.acmicpc.net/problem/1325 내코드 관계로 엮여져 있고, 하나의 컴퓨터에서 시작해서 가장 많이 연결된 컴퓨터의 수를 구한다는 것에서 dfs로 풀어야겠다고 생각했다. 따지자면 방향성이 있는 그래프를 dfs로 탐색하는 문제다. bfs로도 풀 수는 있겠지만 bfs는 최단 시간에 더 적합한 알고리즘이어서 dfs로 풀어봤다. 간단한 dfs 문제였지만 파이썬으로 푸니 시간초과가 나서 pypy로 채점했다. # BaekJoon1325.py import sys input = sys.stdin.readline N, M = map(int, input().split()) relation = [[] for i in range(N)] s..
[BaekJoon] 백준 20444번 색종이와 가위
[BaekJoon] 백준 20444번 색종이와 가위 문제: https://www.acmicpc.net/problem/20444 내코드 처음으로 규칙을 찾아보았다. 6(n)번 가위질을 하는 것을 예시로 들었을 때 모든 경우의 수는 다음과 같다. 7(1X7, 가로0 세로6), 12(2X6, 가로1 세로5), 15(3X5, 가로2 세로4), 16(4X4, 가로3 세로 3) 즉, 가로로 자르는 횟수와 세로로 자르는 횟수에 의해 잘라진 색종이의 개수(k)가 정해진다. 여기서 색종이의 개수를 두 수의 곱으로 표현해 뒀는데 각각의 수를 a, b라고 하자. 이를 식으로 표현해보면 a + b = n + 2 a x b = k 이다. 문제에서 입력으로 n과 k는 주어지므로 위의 식을 만족하는 a와 b를 구하면 된다. b =..
[BaekJoon] 백준 1182번 부분수열의 합
[BaekJoon] 백준 1182번 부분수열의 합 문제: https://www.acmicpc.net/problem/1182 내코드 문제를 봤을 때 N의 최대값이 100,000이었고 배열 전체를 다 돈다고 해도 시간초과가 나지 않을 것 같아서 백트래킹으로 풀어야 겠다고 생각했다. dfs로 첫번째 숫자부터 탐색을 하면서 합이 S가 되면 결과값에 1을 더해줬다. 처음에는 이런 류의 문제가 어려웠는데 풀면서 익숙해지는 것 같다:) # BaekJoon1182.py N, S = map(int, input().split()) arr = list(map(int, input().split())) visited = [False] * N result = 0 # 방문하지 않은 처음은 제외하기 위해 사용 def check_fa..