n . n

https://www.acmicpc.net/problem/1516 1516번: 게임 개발 첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. 건물의 번호는 1부 www.acmicpc.net 먼저 지어져야 하는 건물 -> 순서 존재. => 위상 정렬!! 원래 연결 리스트 값을 만들 때 out -> in 형태로 만드는데, 여기에서 주어진 값은 in -> out 형태여서 헷갈렸다.. 참고 https://steady-coding.tistory.com/86 [BOJ] 백준 1516번 : 게임 개발 (JAVA) 문제 숌 회사에서 이번에 새로운 전략 시뮬레이션 게임 세준 크래프트를 개..

https://www.acmicpc.net/problem/1949 1949번: 우수 마을 N개의 마을로 이루어진 나라가 있다. 편의상 마을에는 1부터 N까지 번호가 붙어 있다고 하자. 이 나라는 트리(Tree) 구조로 이루어져 있다. 즉 마을과 마을 사이를 직접 잇는 N-1개의 길이 있으며, www.acmicpc.net 헛발질만 몇시간을 한건지??! 처음 생각한 방식 : 아무 노드나 루트로 잡고, 자식 트리가 가질 수 있는 최댓값을 재귀적으로 구하여 루트의 최댓값을 구하기.. 였는데 여기서는 노드가 colored/uncolored 두 가지 상태로 나뉘므로 위처럼 계산하는 건 불가능하다. 상태가 두 가지로 나뉘어야 하니까 최댓값도 두 가지로 나뉜 경우의 최댓값을 구하면 되는데.. 왜생각을못하냔말이다?? 아..

https://www.acmicpc.net/problem/11066 11066번: 파일 합치기 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본 www.acmicpc.net 보자마자 생각난 건 분할 정복이었다..!!!! 예전에 어떤 문제에서 풀은 방식이었던 것 같은데(무슨 문제였는지 기억은 안남..) i장부터 j장까지의 파일을 합쳤을 때의 최소를 구하여 1장부터 K장까지의 최소를 구하는 방식으로 풀이했다. (값들은 재귀 방식으로 구해짐) (챕터 수의 최대가 500이었고 이는 널널하게 계산 가능할거란 생각이 들어 전수 조사를 하게 되었다.) 주의할 점 범위의 ..

https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 대표적인 0-1 knapsack 문제이다. https://kikikiwiii10.tistory.com/86 knapsack problem 작년.. 이 아니라 재작년 수업 때 배운 건데 완 전 까먹어서 문제 풀 때 써먹지 못했다ㅠ Fractional Knapsack 0-1 Knapsack "배낭 채우기 문제" 로 알려져 있으며 위와 ..

https://programmers.co.kr/learn/courses/30/lessons/43105 코딩테스트 연습 - 정수 삼각형 [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]] 30 programmers.co.kr 다이나믹 프로그래밍. 현재 위치를 [row][col]이라고 할 때, 현재 위치에서 가질 수 있는 합은 (왼쪽 상단에서 온 값 or 오른쪽 상단에서 온 값) + 현재 위치의 숫자 이므로 두 값을 비교하여 더 큰 값을 dp[row][col] 위치에 저장하는 식으로 탐색하면 리프 위치에서의 최댓값을 구할 수 있음 public class Solution { public static int solution(int[][] triangle) { in..