돌이 코딩하는 방

너무 잉여롭게 시간을 보내는 것 같아서 사람을 모아서 셋을 돌기로 했다. rkm0959님의 추천해주신 Latin America Regional을 돌게 되었다. 2020/2/5 8:10 ~ 2/6 1:10 (5시간), karuna, youngbear과 함께 했다. 결과는 다음과 같다. 내가 J,L,M 을 풀고, youngbear가 K를 풀었으며, Karuna가 D,E,F,G,I 를 풀었다. 카루나 그는 신인가? 복기 글은 자주 쓸 것 같아서 거창한 풀이와 코드는 생략하고 각 문제별로 문제에 대한 간단한 설명과 풀이에 대한 간단한 설명을 적으려고 한다. B. Build A Perfect House 문제 : N과 점 N개가 주어졌을 때 원점을 중심으로 하고 어떠한 점도 포함하고 있지 않은 최대 정사각형의 크기..

완벽하다고 이야기하지는 못하겠지만, 거의 DP 원툴로 해온 사람으로서 그래도 나름 좋은 문제들이라고 생각한다. DP에 대한 기본 지식은 이전글에 나름 자세히 나와있다. DP 문제를 공부하는 법은 이 글에 나와있다. 문제 소개는 간단히 하고 스포는 최대한 안하려고 노력했다. 배치는 대충 난이도 순이다. DP를 처음 하신다고요? DP라는 것을 처음 접해보는 사람들을 위한 입문자용 문제 모음 - BOJ 2748 피보나치 수 2 유명하기 때문에 감을 잡기 쉽다. - BOJ 1463 1로 만들기 DP 태그의 첫 문제 - BOJ 9095 123 더하기 123 더하기 시리즈는 많고 대부분 나쁘지 않다! - BOJ 2579 계단 오르기 조금 비 직관적인 형태에서 DP식을 끄집어 내보자! - BOJ 11276 2xn 타..

이번에는 DP(Dynamic Programing)에 대해 말해보려고 한다. 사전적으로 동적 계획법이란 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다. 동적 계획법에 대해서는 딱히 내용은 없지만 할 말이 많아서 차근 차근 진행해 보려고 한다. 0. DP란? 위에서 서술한 것 처럼 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다. 간단하게 예시를 들어보자. 피보나치 수의 100번째 수를 구해야 한다고 해보자. 하지만 P(100)=P(99)+P(98)이기 때문에 우리는 피보나치 수의 100번째 수를 구하는 대신 99번째와 98번째 수를 구하는 것으로 대체할 수 있다. 이런 식으로 더 부분 문제에 대한 답을 구해 놓아 이를 통해 더 큰 문제의 답을 계산 하여 구하는 과정을 반복하여 최종 ..