Buen Camino

2017.11.02 ** 목요일 ** Solution - 1699(제곱수의 합)
백준 1699 제곱수의합

풀이방법: 동적계획법

엄청 시간이 걸렸던 문제다.

처음에 생각했던 것은 d[2-1] = d[1]+1.. 이런식으로 했었다.

그런데 여기서 4=2의 제곱이 되니 카운트가 바껴야 하는데 그 포인트를 못구했다.

그래서 중간에 월드시리즈 7차전을 잠깐보고 다시 문제를 풀었다.

오늘따라 다저스 타자들이 힘이 없어 보였다..나처럼 ㅜ

풀이방식

한번 생각해보자 ,

처음에 생각했던 방식 d[N - (N-1)] = d[N-1]+1 에 대해서 한번더 생각해보았다.

이렇게 하다보면 d[4]일때가 1차적으로 문제가 생기는데 ,

d[4-4] = d[0]+1을 만들어 줘야하기 때문이다.

자세히 식을 들여다보니 4 =2*2 가 된다. 그렇다면 1은 1x1이 된다는 것을 알 수 있다.

이제 반복문에 대해서 생각을 해보았다.

먼저 우리는 동적계획법을 할꺼고 bottom-up 방식을 사용하기 때문에 1부터 n까지 계산을

해줘야 된다.

for(int i = 1; i < n+1; i++) 로 시작하여

for(int j = 1l; j*j<i; j++)를 만든다. jxj < i 가 포인트인데 이유는

이렇게 하면 2의 제곱은 4부터 등장하게 되고, 처음 방식을 하면서 문제였었던 8은

d[8-4] = d[4] +1 = d[0] +1 +1 = 2가 될 수 있다.

따라서 조건에 의해 제곱수의 범위를 잘 나눌 수 있다. (손으로 해보는 것을 추천한다.)

점화식은 간단하다.

d[i] = Math.min(d[i],d[i-j*j]+1)

여기서 답을 놓칠뻔했다.

왜냐하면 d[i]를 초기화 해주지 않았다. d[i]의 초기화는 모두 d[i]=i로 해야된다.

이유는 모든 수는 1의 제곱으로 구성되어있기때문에, 1의 개수가 최대 개수가 된다.
코드 전체 보기

: 알고리즘은 항상 어렵다.

2017.11.01 ** 수요일 ** Solution - 1012(유기농배추)
백준 1012 유기농배추

풀이방법: dfs

문제 해석

알고보니 예전에 틀렸던 문제이다, 왜 틀렸을까..

어렵지는 않다.

상하좌우 움직임 / dfs 만 알면된다.

풀이방식

한번 생각해보자 ,

지렁이는 움직인다. 지렁이가 이동하면서 모든 배추를 보호한다.

=> 다시말해서, 1이 모여있는 구역당 지렁이가 한마리면 된다.

상하좌우로 움직인다.

=> x,y가 움직일 두 개의 이동배열을 만든다.

int nx = x + dx[i];

int ny = y + dy[i];

1일때 dfs탐색을 시작한다.

=> map{i}{j}==1이면 탐색을 시작한다. 탐색을 시작할때마다 카운팅한다.

for (int i = 0; i < M ; i++) {

for (int j = 0; j < N ; j++) {

if (mapi == 1&&!visitedi) {

visitedi = true;

dfs(i, j);

cnt++;

}

}

}

방문했던것은 방문하지 않는다. (안하면 스택오버플로우)

=> 각 칸당 boolean 타입의 visited배열을 만들어 방문하면 true바꿔준다.

if (isRange(nx, ny)&& !visitednx&&mapnx==1) {

visitednx = true;

dfs(nx,ny);

}

이게 전부다. 그리고 재귀해주자,

코드 전체 보기

: 예전엔 왜 틀렸을까.. 중간에 10분정도 오류를 못찾았다.. 이유는..예제를 카운팅하면서 6으로 숫자를 세가지고

왜 5가 안되는거지 하면서 고민했다. 맞다 바보다..

2017.11.01 ** 수요일 ** Solution - 11051(이항 계수2)
백준 11051 이항 계수2

풀이방법: 동적계획법

문제 해석

이항 계수 문제이다. 고등학교때 수학을 배웠다면, 쉽게 생각할 수 있다.

단 .. 기억을 하고있다면 ...

역시 나는 기억하지 못하고 있었다(공부는 못해도 수학은 좀 했다 신승범짱!)

네이버 검색을 해서 이항계수의 공식을 보는데 이렇게 풀면 되겠구나 하는게 있었다.

출처 : https://ko.wikipedia.org/wiki/%EC%9D%B4%ED%95%AD_%EA%B3%84%EC%88%98

이 공식을 보고 풀이를 시작했다.

풀이방식

한번 생각해보자 ,
우리는 n과 k를 안다.
두가지로 나눠져있다.

=> 두개의 경우로 나눠서 합치자!

순열,조합을 풀다보면 항상 재귀를 떠올리게 된다.

이것 또한 재귀적 방법으로 풀면된다. 또한 메모이제이션을 통해 효율성을 높여주면된다.

그리고 공식에서는 우측이 n+1이지만, 우리는 굳이 저렇게 할필요없다. 모든 항목을 -1해주자

이제 끝이다. 뽑기만 하면된다.

그리고 베이스 케이스 설계를 해야되는데, 한 번 생각을 해보자, 뽑을때마다 각 케이스 별로 -1씩을 해줄것이다.

dp {n}[k} = solution(n-1,k-1) + solution(n-1,k);

이렇게 식을 세우게 되면 어느순간 k==n 또는 k==0이된다. 수학시간에 배웠다. nCn =1 , nC0 = 1이다.

그러면 우리는 베이스 케이스를 설계 할 수 있다.

if(n==k||k==0) return 1;

이렇게 설계하면 될 것이다.

그리고 메모이제이션

if(dp{n}{k}>0) return dp{n}{k}

이제 끝이다 !

이렇게 3줄이면 끝난다. 검증을 하고 싶다면 예제를 손으로 하면된다. 5분도 안걸린다.
코드 전체 보기

: 나이를 먹더니 수학을 다 까먹은 것 같다..