기본 knapsack 문제이다. import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer;public class boj_12865 { static int N, K, A; static int dp[][]; static int items[][]; static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); static StringTokenizer st; public static void main(String[] args) throws IOException { st..

1차원 dp로 해결할 수 있는 문제이다.요즘 이런 유형이 많이 나오는 거 같다. 얼마 전 본 코테에서도 비슷한 문제가 나왔는데..대충 아래 -> 위 or 위 -> 아래 로만 가면서 인접한 칸과 대각에 위치한 칸 중에 최선의 값으로 가는그런 유형이라고 보면되겠다for문을 한번만 돌면서 max, min을 한 사이클에 처리하도록 짰다.import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer;public class boj_2096 { static int N; static BufferedReader br = new BufferedReader(..

플로이드 워셜 알고리즘을 연습하기 좋은 문제였다.import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Arrays;import java.util.StringTokenizer;public class boj_11404 { static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); static StringTokenizer st; static int N, M; static int[][] dist; public static void main(String[] args)..

음수사이클이 있는지 판단하는 문제이다.어려운 점은 특정 지점에서 시작했을 때 사이클이 존재하는지 판단하는게 아니라전체 그래프에서 음수사이클이 발생하는경우가 있는지 체크해야한다.1) 모든 지점에서 벨만포드 수행- 이렇게도 풀 수 있다고 한다.2) 가상 시작점 만들기- 나는 이렇게 풀었는데,안쓰는 0번에서 단방향으로 모든 vertex에 가중치 0으로 연결해줬다.그리고 나서 벨만포드의 시작점을 0번으로 해서0->1,2,3,4.... ->0 (사이클발생) -> 1,2,3,4... (갱신 과정에서 사이클 탐지)이런 방식으로 벨만포드를 한번만 수행하고 풀 수 있었다.import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamR..

문제 링크 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 문제 접근 3을 만들 수 있는 경우의 수에서 1을 더한 것과 2를 만들 수 있는 경우의 수에서 2를 더한 것, 1을 만드는 경우의 수에서 3을 더한 것을 모두 합한다. d[5]는 d[4] + d[3] + d[2] 로 정리할 수 있고, 이는 곧 d[n] = d[n-3] + d[n-2] + d[n-1] 이다. 11 이하인 수이므로 for문을 10회 반복한다. 정답 코드 import sys X = int(sys.stdin.readline()) dp = [0] * (X + 1) for i in range(2, X + 1): dp[i] = dp[i - 1]..

문제 링크 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 문제 접근 DP 테이블을 이용한다. 현재 자신(숫자)를 만들기 위해 필요했던 연산의 개수를 저장한다. 각 수 연산을 다 해주고, 이 연산을 거친 결과를 서로 비교해서 가장 최솟값을 DP 테이블에 순차적으로 저장한다. 정답 코드 import sys X = int(sys.stdin.readline()) dp = [0] * (X + 1) for i in range(2, X + 1): dp[i] = dp[i - 1] + 1 if i % 2 == 0: dp[i] = min(dp[i], dp[i // 2] + 1) if i % 3 == 0: dp[i] = min(dp[i],..

동적 계획법 (Dynamic Programming) 동적 계획법, DP는 복잡한 큰 문제를 여러 개의 작은 문제로 나누어 푸는 방식이다.다이나믹 프로그래밍이라는 이름은 고안자인 Richard Bellman이 붙인 이름인데 Dynamic이라는 단어가 멋져서 그렇게 지어졌으며 실제 원리와는 전혀 상관없다고 한다.반복되어 나오는 작은 문제들을 저장해 두었다가 재활용하기 때문에 직관적으로 '기억하며 풀기' 로 생각하는 것이 좋다. 왜 사용하는가? 피보나치 수를 구하는 재귀함수를 생각해 볼 수 있다. f(n-1)에서 구한 값을 f(n-2)에서 한번 더 구하기 때문에 실행되는 함수의 횟수가 기하급수적으로 증가하게 된다. 그러나 한번 구한 작은 문제의 값을 저장해놓는다면 연산 수가 급격히 감소하여 효율성이 증가한다...

문제 접근 재귀 문제이다. 0 -> (0000) -> (0(0011)00)… 함수가 호출되고, 매트릭스가 모두 같은 요소로 채워져 있지 않다면 해당 문자를 (xxxx)형태로 변경하고 각 x마다 재귀호출을 한다. 정답 코드 #1992번: 쿼드트리 import sys def quad_tree(matrix): size = len(matrix) start_point = matrix[0][0] flag = 0 for i in range(size): for j in range(size): if matrix[i][j] != start_point: flag = 1 break if flag == 1: new_matrices = [] new_size = size // 2 for k in range(2): # k = 0,1..

문제 접근 bfs로 이차원 배열을 탐색해야 한다. 1) 이차원 배열을 차례대로 순회하면서, 1이 등장할 때마다 bfs를 호출한다. 2) bfs를 진행하면서 해당 영역의 그림 칸 수를 카운트함과 동시에 바로 0으로 바꿔준다. 3) bfs에서 반환된 카운트 값을 가지고 max와 비교해 업데이트 4) 2)에서 방문한 부분은 0으로 바꿔줬기 때문에 1)에서는 또다른 영역의 그림만을 인식하여 bfs를 호출하게 된다. 정답 코드 #1926번: 그림 import sys from collections import deque def bfs(map, x, y): queue = deque() queue.append((x, y)) map[x][y] = 0 dx = [-1, 1, 0, 0] dy = [0, 0, -1, 1] c..

문제 링크 16987번: 계란으로 계란치기 원래 프로그래머의 기본 소양은 팔굽혀펴기를 단 한 개도 할 수 없는 것이라고 하지만 인범이는 3대 500을 넘기는 몇 안되는 프로그래머 중 한 명이다. 인범이는 BOJ에서 틀린 제출을 할 때마다 턱 www.acmicpc.net 문제 접근 치는 계란과 맞는 계란을 잘 다뤄야 한다. 치는 계란은 항상 왼쪽 첫 번째 계란이고, 이 계란이 깨지면 다음 계란이 치는 계란이 된다. 재귀를 하면서 배열 자체에서 깨진 계란을 삭제해 버리면 복잡해지므로 알고리즘 내에서 조건으로 깨짐 여부를 체크하고 그에 따라 처리해준다. 정답 코드 # 16987번: 계란으로 계란치기 import sys def count(eggs): cnt = 0 for i in eggs: if i[0]