SLENDER ANKLES's 개발블로그

이 문제는 내가 심각하게 잘 못 길을 잡아서 고생했던 문제였다. 

이러한 아이디어는 경험을 통해서 얻어내야겠다고 생각했는데, 이번에도 방향을 조금 잘 못 잡은 듯하다. 

문제에 대해서 간단히 정리하면

배열의 경계에 스토어들과 시작해야 하는 특정 위치가 주어진다. 

그러면 특정위치에서 시계방향 또는 반시계방향으로 경계면을 

돌아 그 위치까지의 최단거리를 찾아서 모두 다 더해주는 문제였다. 

딱히 길이에 대한 방법이 떠오르지 않아 재귀로 방향을 통해 들어가서 답을 구했다. 결국은 해냈지만 

여러 사항들을 처리해주느라 조금 힘들었다. 

하지만 적절하지 않은 방법이라도 답을 낼 수는 있게 된거 같다. 

풀고나서 다른 사람들의 풀이법을 보니까 

전체 w * h의 좌표계에서 경계면을 따라 반시계 방향 또는 시계 방향으로만 돌기 때문에 

전체 길이에서 그 해당 상점까지의 길이 또는 전체 거리에서 그 상점까지의 길이를 빼준 두 개의 경우 밖에 없다는 것이다. 

매우 간단한 문제였다 ... 문제를 좀 더 잘 분석해서 해결해 나가야 겠다.

조합알고리즘

nCr 을 구현해야 됐던 적이 있었나?

경험적으로 재귀적으로 수행했을 때도 충분히 답이 나오는 문제만 풀어서 그런지 없었다. 

1010 다리 놓기 라는 문제를 통해 

그냥 재귀탐색과 DP를 통한 메모이제이션 탐색의 엄청난 시간 차이를 경험했다. 

조합알고리즘에 대해서 간단히 설명하자면

n개 중에서 r개를 뽑는 경우의 수를 nCr 이라고 표현하고 

수학에서는 (n - r)! / r!     또는      n! / r! * (n-r)!으로 계산 해주지 않았나?

=> 6C3 => 6 * 5 * 4 / 3 * 2 * 1 이었다.

하지만 수학이 아닌 컴퓨터에서는 

이렇게 팩토리얼 개념을 적용시켜주면 자칫 메모리를 엄청나게 

쓰다가 스택 오버플로우가 날 수 있다.

n이 충분히 커지게 되면 n!은 기하급수적으로 증가하게 된다. 

그래서 식을 다음과 같이 바꾸어주게 된다. 

nCr = (n - r + 1) / r * nCr-1

nC0 = 1(r ==0일때, basecase)

그렇다면 이 것을 cache를 써서 다음과 같이 표현해주면 완벽하다.