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를 써서 다음과 같이 표현해주면 완벽하다.

전깃줄 문제는 정말 어려웠다. 

결국 힌트를 얻기위해 돌아다니다가 LIS로 푸는 문제라는 것을 알았다. 

근데 LIS가 잘 구현이 안되어서 찾아보며 풀었다. 

LIS는 배열에서 최장 증가하는 부분 수열을 찾는 것이다. 

이 것을 찾는 이유는 문제를 계속 들여다보면 x값(왼쪽)을 정렬시킨 상태에서 y값들(오른쪽)이 계속적으로 증가되어야 

서로 교차되지 않는 최대의 개수를 찾을 수 있게 된다. 

우선 LIS알고리즘에 대해서 정확히 다시 숙지 할 필요가 있고, 또한 

LIS알고리즘은 구하는 즉시 정렬되어 있는 줄 알았는데 그게 아니라

가장 최대값을 구하기 위해서는 한 번 또 정렬을 해줘야 한다는 것을 알았다. 

그래서 구조체 형식으로 왼쪽 값 오른쪽 값에 대한 값들을 받아와서 

왼쪽 값을 기준으로 정렬한 후에 오른쪽 값을 기준으로 LIS 최장 증가 부분수열의 개수를 찾은 다음에

N에서 빼주면 답이 나온다. 

결국 도움을 받아 해결했다. 

이렇게 규칙을 찾는 문제를 해결하는 방법에 대해서 몇 가지 패턴에 대해서 정리해놔야겠다는 생각을 했다. 

우선 이 문제에 대해서 간단히 정리하자면

1 2 3 4 5 6 7 8 9 10

이라는 10개의 숫자가 있을 때 

3 부터 8까지의 숫자를 뒤집으면

1 2 8 7 6 5 4 3 9 10 이된다.

여기에서 다시 1 - 5까지를 뒤집으면

6 7 8 2 1 5 4 3 9 10 이 된다.

그렇다면 두 번 뒤 집은 수의 결과를 통해 어느 구간을 두 번 뒤집었는지를 알아맞춰야 하는 문제였다. 

규칙을 찾고자 엄청 노력을 했다. 

예를 들어 

1번째 위치에 있어야 할 수인 1이 그 자리에 없다면 

그 번호부터 1을 찾아 나선다. 위에서는 1이 다섯번째 자리에 있으므로

원래 있어야 할 자리 - 현재 있는 자리 까지 뒤집어 준다. 

1 2 8 7 6 5 4 3 9 10

이 되고 다시 3번째 자리수에 있어야 할 3이 없으므로 3을 찾아 나서 3을 찾으면 

3번째 자리 - 3이 현재 있는 자리(8번째) 까지 뒤집어 준다. 

답이 나온다. 

그런데 첫 번째 테스트케이스 말고는 답이 안 나온다. 

물론 이 방법으로는 어떻게든 되돌려 놓을 수는 있는데 2번만에 안된다.

그럴때는 2번을 넘어 가는 경우에는 그만 두고 이번에는 끝쪽에서 시작하여 이 과정을 해본다. 

그러면 무조건 2번안에 답이 나온다. 

어려운 문제였다. 

규칙 찾을 때 앞에서부터 해서 되는데 안되면, 뒤에서부터 시도도 해보아야 한다

2 * 2 배열에 1,2를 채우는 경우의 수하기.

2 * 2 * 2 * 2 => 16가지의 경우의 수가 나와야 한다.

그런데 내가 코딩한 거에는 96가지가 나왔다. 무엇인가 잘 못 코딩해준것이었다. 

항상 2차원 배열에 대한 경우의 수 구하는 문제를 만나면 어디선가 루프를 잘 못 돌고 

그랬었는데, 확실히 내가 잘 못된 코드를 통해 풀고 있었다는 것을 깨달았다. 

2차원 루프에서 만약에 조건을 만나면 재귀 탐색 시작하고 무조건 빠져나와야 한다는 것이 중요했다.

스도쿠 문제는 예전에는 꿈도 안꾼 문제였는데 도전해서 겨우 풀어냈다. 

우선 로직은 

0으로 입력된 자리에 들어가서 좌우방향 체크하고, 위아래 방향 체크하고, 네모난 사각형 방향 체크해서

스도쿠판에 현재 자리에 들어 갈 수 있는 후보군을 정한다. 

0 3 5 4 6 9 2 7 8 7 8 2 1 0 5 6 0 9 0 6 0 2 7 8 1 3 5 3 2 1 0 4 6 8 9 7 8 0 4 9 1 3 5 0 6 5 9 6 8 2 0 4 1 3 9 1 7 6 5 2 0 8 0 6 0 3 7 0 1 9 5 2 2 5 8 3 9 4 7 6 0

예를 들어 설명하면

위의 입력에서 

(1, 1)의 자리에 들어 갈 수 있는 후보군은 {1}이 되겠다.(좌우체크, 상하체크, 사각형 체크)

(2, 5)의 자리에 들어 갈 수 있는 후보군은 {3, 4}가 되겠다.

... 

만약 후보군이 한 개라면 비교적 쉽게 도출 되겠지만 후보군이 여러개라면 원하는 답을 위해 많은 재귀함수를 

수행 할 수도 있을 것이다. 

어쨌든 재귀함수를 수행하면서 스도쿠 판에 0이 없을 때까지 값들을 채워나가면서 

다 채워졌을 때 조건에 맞는 스도쿠가 완성되는 것을 판별해주면 되는데(백트래킹)

만약 0을 채워야 되는데 조건에 앞조건에 맞물린 후보군이 없을 경우, 

다시 앞으로 회귀해서 다른 값을 대입해보고 또 재귀를 수행하면 되는데, 

(백트래킹)

그렇게 해서 모든 배열을 다 채우면서 

조건을 만족하는 답이 나왔을 때는  더 이상 백트래킹 재귀를 수행 할 수 없으므로

기존에 동작하는 재귀함수들을 다 끄면된다(전역으로 flag만들어놓고 완성되면 모든 스택의 재귀함수 다 종료시키면 된다)

그리고! 중요한 것이자 내가 계속 답을 못 냈던 이유 중에 하나가 

2차원 배열에 모든 경우의 수를 구하는데 어려움이 있어서였다. 

2차원 배열을 돌면서 0을 만나면 답을 자기 자신의 재귀함수를 호출하는데, 이 코딩에서 잘 못 된 점이 있었다.

2차원 배열을 순회하면서 0을 찾고 재귀를 수행한 후에 바로 break 두번 걸어서 for문을 완전히 빠져나와야 한다. 

그렇지 않으면 무한 루프에 빠지게 된다. 

이 개념에 대해서 부족해서 제대로 된 경우의 수를 못 구한 것이었다. 

이 부분에 대해서는 따로 정리해야겠다.

2차원 토마토의 발전 문제? 인

3차원 토마토다. 

2차원 배열 토마토 문제의 풀이 방법과 완벽히 동일하다. 

큐에 모든 토마토를 돌려주고, bfs를 수행해서 걸리는 시간 중에 최대값이 토마토를 다 익는데 걸리게 하는 시간이다.

입력 받는 방법에서 거의 오랜만에 3차원 배열을 다루어보았다. 

첫 번째 루프에서 높이, 두 번째 루프에서 세로, 세 번째 루프에서 가로의 범위를 설정해서 입력받고, 

활용했다. 

arr[세로][가로][높이]

소수를 구하는 알고리즘을 통해 답을 구했는데 계속 틀렸다고 나왔다. 

그래서 for문을 통한 완전탐색 방법으로 다시 풀었는데 성공했다. 

소수를 구하는 알고리즘에서 1에 대한 예외처리를 안해서였다. 

소수구하는 알고리즘을 다시 정리하자면

1) 2가 아닌 수에서 2로 나누어 떨어지면 소수가 아니다

2) n 은 2부터 시작에서 n보다 작은 i * i를 만족하는 i로 나누어 떨어지면(합성수)이면 소수가 아니다. 

이 모든 필터링을 넘어가면 소수이다. !

부등호의 개수와 부등호가 입력으로 주어지면

각 위치에 0~9로 구성된 조건을 만족하는 수열을 찾아내어 

그 것을 정수로 환산하여 가장 큰 정수와 가장 작은 정수를 찾는 것이다. 

완전탐색의 방법으로 수행한다. 

다행이도 중복되는 수를 제외하고라는 조건이 있으므로 10^10이 아니라

10! 이다. 10!은 1초안에 1억번 안으로 수행횟수를 조절 할 수 있으므로 충분히 완전탐색 가능한 숫자이다. 

수열을 만들어 나갈 때 

조건을 만족 시키지 않으면 바로 재귀호출을 끊어버리는 방법을 통해 

9개의 부등호를 만드는 재귀적 호출도 금방 수행을 할 수 잇게 된다. 

오랫동안 풀지 못했던 문제를 겨우겨우 풀어내었다. 

물론 약간의 힌트를 얻고 나서였다. 

격자 모양의 상자에 토마토가 들어있는데, 토마토는 한 시간당 주위의 것을 익혀나간다. 

모든 토마토가 익는데 걸리는 시간을 구하여라 였다. 

토마토는 여러 군데 익은 상태의 것이 있을 수 있었고,

어쨋든 나는 bfs로 수행하는 데까지는 잘 방향을 잡았다. 

익은 토마토마다 bfs함수를 한 번씩 실행하게 했는데, 이 것이 미쓰였다. 

맨 처음에 이미 익은 토마토를 한 번에 큐에 담았다가 bfs를 한 번만 수행하면 되는 것이 포인트였다. 

여러 예외 처리를 할 필요도 없고, 그리고 더군다나 이 것이 가장 정확한 방법이었다. 

bfs의 원리에 대해서 정확히 알지 못 한채 문제를 풀어서 못 푼 것이었다. 

bfs에 대해서 좀 더 정확히 이해할 수 있게 해준 문제

여러 군데에서 동시에 bfs를 수행해야 하는 경우 한번에 큐에 담아 내는 방법에 대해서 활용 할 줄 알고 이해해야 한다.