Buen Camino

2017.11.02 ** 목요일 ** Solution - 1238(파티)
백준 1238 파티

풀이방법: 다익스트라

특정한 장소에 최단시간으로 모두 갔다오고, 그 중 가장 오랜시간 걸린 사람을 찾는 문제이다.

풀이방식

문제를 읽고 두 가지 풀이가 생각났다.

1.플로이드
2.다익스트라

처음에는 플로이드로 하면 금방할 것 같아 했는데 , 뭔가 오류가난다. 시간이 초과되고 그러는것 같다.

그래서 플로이드의 조건을 바꾸느냐? 아니면 다익스트라로 다시푸느냐...

다시하는게 빠를것 같아 다익스트라로 풀었다.

그냥 다익스타로 하기전에 고민을 좀 더 해봤다.

다시 생각해보면 우리는 X의 지점만 왓다리 갓다리 하면된다.

문제에서 보면 1 -> 2 가 4인데 이것을 뒤집으면 2 -> 1이된다. 보기에는 다르겠지만 의미는 같다.

따라서 두 가지의 방식을 사용하면된다.

일반적인 거리배열을 이용한것과 위처럼 뒤집은 배열을 사용한것 이 결과 두개를 더하면된다.

또한 우리는 기준이 되는 점을 알고 있기 때문에 기준점을 활용한다.

dist[i] = map{x}{i} + d[x]를 점화식으로 세운다.

나머지는 다른 다익스트라와 같다. (우선순위 큐쓰고,, 넣고 와일문 돌리고등.)

함수의 매개변수를 (int x, int{}{}map, int{} dist) 이렇게 받아주고 계산하면된다.(쓴 이유는 아래에 있다)

그리고 우리는 함수를 2번 호출한다. 왜냐하면 우리는 2개씩 배열을 만들것이기 떄문!

안뒤집은 배열, 뒤집은 배열, 안뒤집은 거리, 뒤집은 거리 이렇게 4개를 활용한ㄷ.

뒤집은 것을 넣게되면 아까 말한것처럼 1->2 를 2->1로 계산할 수 있다.

출력할때는

제일 큰 dist[i] + redist[i] 하면된다. 모두 x까지 왕복한 거리들이기 떄문이다.
코드 전체 보기

: 풀다가 잣다.. 어려웡.

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 - 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분도 안걸린다.
코드 전체 보기

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

첫 알고리즘 포스팅입니다. 잘 부탁드립니다. 

(당부의 말씀 : 저는 고민을 먼저하고 문제를 풉니다. 다풀고나서 채점을 통해 맞으면 맞는거고, 틀리면 수정을 합니다. 하지만 저는 저만의 풀이가 끝나고 다른 사람들의 풀이와 비교를 통해 최적의 풀이방법을 찾으려 노력을 하고 있습니다. 만약 마지막 수정중에 다른분들것과 너무 흡사 하면 출저를 달아놓겠습니다.)