SLENDER ANKLES's 개발블로그

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

결국 힌트를 얻기위해 돌아다니다가 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[세로][가로][높이]