분류 전체보기184 쿠키 구입 - level 4 해결방법 이 문제는 두 아들에게 똑같은 쿠키를 줄 경우 가장 큰 쿠키의 개수를 구하는 문제이다. 아들 1에게는 N - M번째까지의 쿠키를 주었다면, 아들2에게는 M+1 - K번째까지의 쿠키를 준 쿠키가 같아야 되고 가장 큰 수를 return해야 된다. 까지의 배열에는 쿠키의 수가 임의의로 존재한다. 만약 이 문제를 경우의 수마다 합을 한다면 Time Compexity는 우주까지 간다. 그래서 배열을 이용해 M번째 까지의 합을 미리 저장해 놓는 것이 좋다. 만약 I - J까지의 합을 구하고 싶다면 J번째 합에서 I - 1번째의 합을 빼주면 된다. int sum[N+1]; for (int i = 0; i < cookie.size(); ++i) sum[i+1] = sum[i] + cookie[i]; 먼저 아들.. 2019. 4. 5. 도둑질 - level 4 해결방법 이 문제는 처음에 0번을 터는 수와 1번을 터는 수로 나눌 수 있다. 인접한 집을 털 수 없기 때문에 이전전 집과 현재와 이전 집중에 누가 큰지가 현재 값이 된다. $$ dp[0][i] = max(dp[0][i-1], dp[0][i-2] + money[i]) $$ $$ dp[1][i] = max(dp[0][i-1], do[0][i-2] + money[i]) $$ 위의 점화식을 보면 똑같이 보이겠지만 위에 점화식은 처음 집을 털 경우이므로 마지막집은 항상 털면 안되고, 아래 점화식은 2번째 집부터 털기 때문에 마지막집을 털어도 된다. 점화식을 통해 dp는 2 * 집의 수만큼 2차원 배열로 정의했다. int dp[2][1000001]; 아래는 초기화 코드이다. dp[0][1]에도 넣어준 이유는 반복.. 2019. 4. 5. Artistic Style Transfer이해하기 1. INTRO 졸업작품으로 썼던 모델이다. 구현하는 데 고생했다. 이름(Transfer)처럼 단순히 그림의 패턴을 전달해 주는 모델로 학습모델은 아니다. 학습되는 것으로 바꾸는데 지식도 모자르고 코팅실력도 모자라서 죽을뻔 했다. 나온지 한 5년 정도된 모델로 5년이면 이제 잊혀지지 않을까 했던 모델인데 게임이나 여러분야에 아직 응용되어 사용되고 있는 거 같다. 그래서 복습겸 다시 읽어보았다. 코드는 조금씩 다시 짜봐야겠다. 이해하기는 안 어려운데 이상하게 학습이 잘 안됬었는데, 학습말고 논문에 나온 그대로만 짜서 Git에 올려보아야겠다. 요즘 해커톤 대회 나가는데 Git아이디 적으라고 한다. 진작에 한 것들 조금씩 올려놓을 껄... 난 이 논문을 보면서 CNN이 내부에서 이런식으로 행동하는 구나를 눈으.. 2019. 4. 5. Brute Force vs Dynamic Programming 1. Brute Force(완전탐색) Brute Force의 이름을 살펴보자면, Brute는 짐승을 의미한다. 일반적으로 짐승은 본능에 의지해 '무식함'을 나타낸다. 그렇다면 여기서 '무식함'은 무엇일까? 그것은 모든 경우의 수를 찾아보는 것이다. 아주 간단한 예로 1 ~ 100가지 숫자 중에서 원하는 숫자 하나를 찾아본다고 하자! 100을 찾고 싶다면, 1부터 쭉 조사해서 100번을 찾을 때까지 반복한다. 이런 알고리즘적 '무식함'을 Brute라고 표현한 것이다. 가장 유명한 문제로 '외판원 순회'라는 문제가 있다. 1,2,3,4,5라는 노드가 있고 모든 노드를 1번씩 방문하고 출발했던 노드로 되돌아 오는 최소의 경로를 찾는 문제이다. 아래와 같.. 2019. 4. 1. 이전 1 ··· 4 5 6 7 다음