SLENDER ANKLES's 개발블로그

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

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

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

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

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

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

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

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

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

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

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

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

백준에서 똑같은 문제 7570_줄세우기는 실패했다.. 이유는 무엇일까? 

이 문제는 정말 어떻게 푸는지를 몰라서 헤맸고, 결국 인터넷을 통해 풀이법을 공유 받았는데도 이해가 안 가는 문제다. 

학생들의 번호를 인덱스로 가지는 배열을 가지고 동적계획법을 활용한 문제인 것은 같으나

그 로직에 대해서 100% 이해가 가지 않는다. 

우선, 문제의 핵심은 

줄을 세울 때 맨 뒤로 보내거나, 맨 앞으로 보내는 개수의 최소 값을 구하라는 것인데

가장 긴 증가하는 학생들의 수열을 구한 후에 전체 학생 수에서 빼주면 그 것이 최소로 학생들을 맨 뒤로 보내거나,

맨 앞으로 보내게 되는 것이었다. 

대충 이해는 가겠으나, 이 것을 코드를 옮기는데 잘 되지 않아,,,(예제 테스트케이스는 맞았으나 그 다음부터 잘 안되어서

다른 코드를 참고 했는데, 보고도 잉?)

나와는 다르게 입력 받은 번호를 인덱스로 활용해서 동적으로 학생들의 증가하는 수열을 구하는 방법이었다. 

예제의 테스트케이스를 이용해 설명하자면

5

5 2 4 1 3

1) 입력 5가 들어왔을 때

dy[5] = dy[5 - 1] + 1   // 4번째 학생까지 연속되는 수열 개수 + 1

dy[2] = dy[2 - 1] + 1    // 1번째 학생까지 연속되는 수열 개수 + 1

dy[4] = dy[4 - 1] + 1    // 3번째 학생까지 연속되는 수열 개수 + 1

dy[1] = dy[1 - 1] + 1    // 0번째학생까지(0번째학생은 없다) 연속되는 수열 개수 + 1 => 1

..

입력되는 순서 대로 값이 들어갈 것이므로 완전 머리를 잘 쓰신 분이 짜신 코드 같다. 

오래전에 풀어봤다가 포기한 문제였는데, 이번에 역시 어렵게 풀었다. 

n의 범위가 10000인 n * n 영역에서 (이미 배열을 잡을 수 없다는 것을 캐치)

l ( 4 <= l <= 100)길이의 그물을 쳐서

m(1 <= m <= 100)개의 물고기를 최대로 가져오게 할 때

그 물고기 어획량이 최대가 되는 마리 수를 계산하는 문제였다. 

그물은 우측으로, 아래쪽으로 칠 수 있다는 조건이 희망적이었다.

우선 대충 문제만 봐도 토가 나오는 문제였지만, 겁먹은 점도 많은 것 같다. 

이번에 느낀 문제 접근 방법은

[1] 규칙이 있나?

[2] 완전탐색 가능한가?

[3] 완전히 탐색하는데, 범위를 현저히 줄일 수 있는가?

이다. 

1번은 모르겠고, 2번은 안되었고, 3번의 방법을 적절히 선택해서 풀어야 하는 문제였다. 

맨 처음에는 문제 예시의 그림을 보고 

물고기 위치보다 그물을 쳐보면 되잖아? 개쉽네 이랬는데 

다음의 예외를 생각 못했었다. 

위와 같은 경우 물고기 좌표가 있지 않은 곳에서 그물을 쳐야 최대를 수확할 수 있다. 

그 다음 생각한 방법은 물고기의 입력 범위의 x, y의 최대 최소

4개의 값을 받아와서 

그 범위만큼 완전 탐색하는 것이었다. 

이 방법은 시간 초과가 났다. 

마지막 방법은 내가 완벽히 생각해내진 못 했다. 

이렇게 하는 것이다. 

 x좌표, y좌표를 각각 따로따로 sorting 한 후에 

그 좌표들을 이중 포문 돌리면서 탐색하니까 답이 나왔다. 

머리를 잘 굴려서 최대한 범위를 적게 하는 팁이 필요한 문제였다. 

실행 시간은 망이었지만..

어쨋든 꿀팁, x좌표, y좌표 정렬한 후에 완전탐색

느낀 점은 

*생각은 간단하고 명료하게 해야 된다. 

*너무 많은 조건으로 필요없이 시간을 허비하거나 코드 수를 늘릴 필요는 없다는 것이다.

우선 맵의 범위도 1~40000 (2차원 배열이기때문에 배열 선언하는 것은 불가)

목적지까지의 거리도 20억이 주어지므로 배열을 한칸씩 재귀적으로 탐색하는 방법은 절대 하면 안 되는 문제였다. 

그래서 예전에 풀어본 경험으로 한 번의 이동은 2차원 배열의 하나의 요소가 아니라 

벽에서 부터 ~ 벽까지 라는 것을 생각했다. 

다만 반복되는 루프를 만나면 계산을 좀 더 손쉽게 해줄려고 했는데, 사실 이 것은 별로 필요없었다. 

오히려 코딩시간과 디버깅의 시간을 더욱 잡아 먹었던 듯 하다. 

방향에 대한 처리가 중요한데, x축 진행 방향의 증가, 감소, y축 진행 방향의 증가 감소를 판별해

벽까지의 정확한 이동 경로와 거리를 측정해야 한다. 

우선 처음 진행방향은 x축 진행 방향도 +(증가), y축 진행 방향도 +(증가) 이다.

다음 벽까지의 거리가 더 가까운 축의 이동거리를 측정해서 

x, y모두 그 만큼 이동해주고, 이 과정을 반복한다. 

답이 잘 나온다. 

입력 좌표는  행 >> 열 >> 1행의 시작 열

이렇게 주어진다. 

그리고 좌표 정보가 주어지는 데 각 좌표는 로봇이 해당 좌표에서 어디로 이동할지에 대한 정보를 말한다. 

로봇이 밖으로 빠져나가면 빠져나갈때까지의 거리를 출력

로봇이 무한 루프에 빠지면 어디서부터 어디까지가 무한 루프인지 판단해서 출력하면 된다. 

1) 맨 처음에 초기화를 모든 좌표에 'a'를 것을 초기화해놓고, 입력을 받았으므로 n, s, w, e를 제외한

a로 진입하게 되면 빠져나간 것이라고 판단하여 답을 구했다. 

2) 무한 루프에 빠지는 것에 대해서는 visited배열을 놓고 이미 방문 한 곳으로 가면 루프를 도는 것이기 때문에 

그렇게 처리했다.

비교적 쉬운 문제

문제 이해가 제대로 안되 애를 먹은 문제다. 

카드 6장이 주어지면 카드 6장이 모두 베이비 긴 상태로 없어져야 한다. 

이 것을 이해하지 못해

처음에 베이비긴이 하나라도 있으면 되는 것인가? (X)

베이비긴을 만족하는 것이 2개 있으면 되는 것인가?(X)

베이비긴을 만족하는 것이 2개 이상 있으면 되는 것인가?(X)

모두 일정 테스트케이스에서 막혔다.

베이비 긴을 run상태 이든 트리플리트 상태이든

어쨋든 6장을 모두 써서 없애야 한다.

이 것이 문제에 핵심이었다. 

0~9까지의 배열을 가지고

각 입력 받은 숫자의 개수를 저장해놓았다. 

그리고 베이비긴을 만족시키는 연산을 통해 답을 도출해내었다. 

백트래킹 문제에 대해서 조금씩 감을 잡아가는 느낌이다.

이 문제는 완전 탐색을 하는 도중 첫 번째 답이 나오면 종료하는 것이 포인트다. 

나의 백트래킹 가지치기는 1부터 3으로 한 칸씩 늘려나가면서 만들어 가므로 

가장 먼저 나오는 첫 번째 답이 최소값이다. 그렇다면 더 이상 트래킹을 그만둬도 답을 도출해낼 수 있다. 

백트래킹에 대한 문제는 어느 정도 해소가 되었는데,

좋은 수열을 판별하는 방법이 의외로 까다로웠다.

처음에는 좋은 수를 판별하는 방법은 너무 복잡하고 까다롭고 분명 시간 소비를 많이 할 것 같아 

규칙을 찾아야 된다고 생각했는데, 그 것이 아니었다. 

좀 더 연구해보니까 분명 좋은 수열을 판별하는 것은 

인덱스 장난을 치는 부분이 조금 복잡하지만 절대 시간이 오래 걸리지는 않다는 것을 알았다. 

예를 들어 123123 이라는 수가 있으면

맨 끝의 인덱스부터 시작해서 length를 1부터 시작해서

length : 1

2-3 비교

-----------------------

length : 2

3 - 1

2 - 3

비교

-----------------------

length : 3

3 - 3 

2 - 2

1 - 1

비교 ===>(이 것은 나쁜 수열로 판별남)

-----------------------

이런식으로 판별했다. 

(현재의 점)을 기준으로 현재 점과 (현재의 점 - length)을 비교하는 과정을 통해

판별하는 것이다. 이 경우는 길이가 80이어도 40번만 수행 횟수는 정말 얼마 되지 않는다. 40번정도?

수를 완전탐색하면서 좋은 수열인지 판별하고 답이 나오면 최소값이므로 바로 종료하면 되는 문제였다.

<소스코드>

직관적으로 이 것은 점들의 평균 값이겠다 했는데, 평균 값이 아니라 중앙값을 선택하는 문제였다. 

x, y를 각각 정렬 한 후에 그 배열의 중간 값이 최소거리를 갖게하는 점이다. 

각 점들에게 이 점까지의 거리를 구하면 답이 나온다. 

정확하게 증명하기는 어렵지만 이러한 문제가 나오면 평균값이 안되면 중앙값으로 시도해보는 것도 한 패턴일 것 같다.

n의 범위는 10000, m의 범위는 100000이었는데,

계속 x,y의 범위를 10000까지만으로 해서 ... 계속 틀렸다. 

문제를 잘 읽어봐야 하겠다.

완전탐색으로 구현하다가 낭패 본 문제

11122 ####*

위 쪽의 입력은 자신의 인덱스의 좌, 자신, 우의 지뢰의 개수를 가르쳐준다.

입력의 윗 부분만 보면 된다. 

첫 번째 입력이 2인 경우

result[0] = 1, result[1] = 1 로 세팅 한 후에 

result[idx - 1] + result[idx] + x == mine[idx] 인 x를 찾아서 result[idx + 1]에 대입시켜주며 재귀 함수를 수행하면 된다.

첫 번재 입력이 0인 경우

result[0] = 0, result[1] = 0 로 세팅 한 후에 

result[idx - 1] + result[idx] + x == mine[idx] 인 x를 찾아서 result[idx + 1]에 대입시켜주며 재귀 함수를 수행하면 된다.

첫 번째 입력이 1인 경우

result[0] = 1, result[1] = 0 으로 세팅 한 후에

위의 재귀 동작을 수행 시켜서 마지막 인덱스의 답이 맞으면 넘어가고

틀리면

result[0] = 0, result[1] = 1으로 세팅 한 후에 

위의 재귀 동작을 수행 시키면 된다.

이렇게 하면 무조건 답이 나온다. 

범위가 100까지 이므로

완전탐색의 최악의 경우 2^100이므로 절대 완전탐색을 하면 안되는 문제였다. 

분명 규칙을 찾아야 하는 문제였는데, 

백트래킹으로 풀려다가 계속 안 풀린 문제였다. 

계산해봐서 절대 시간안에 풀수 없는 문제이면 완전탐색 시도를 하면 안되고 무조건 규칙을 찾아야 한다는 것을 깨달았다.

12시 3시 6시 9시만 가르킬 수 있는 시계들이 9개 있다.

각 시계를 90도 회전 할 수 있는 9개의 버튼을 선택적으로 눌러서 모든 시계들이 12시를 가르킬 때

의 경우의 수 중에 사전 순으로 가장 빠른 것을 찾아라.

많이 헤맸지만 몇 가지 힌트를 듣고 풀 수 있게 되었다. 

시계는 많이 돌릴 필요도 없고 4번을 돌리면 제 자리로 돌아온다.

그대로 놔두던지, 1번, 2번, 3번, 4번(다시제자리로)

버튼에 대한 동작 5개만 있으면 된다. 

이 버튼을 누르는 경우의 한해서 완전탐색을 해주면 답이 나온다. 

for문을 9개써서 시간 안에 답이 나올 수 있는지에 대한 의문이 드는데, 

직접 몇 개 계산을 해보면 된다. 

5의 9승 => 1953125번

최악의 경우 2천만번 정도 순회하면 완전 탐색을 모두 수행 할 수 있다. 

사전 순으로 앞에 것을 출력하라고 했으므로 실제로 다 돌 필요도 없다. 

나와 같은 경우 맨 처음에 스위치의 ABCD를 string으로 표현해서 인덱스에 접근했는데, 

이렇게 하면 시간 안에 답이 안나온다.....

한 번 스트링을 인트형으로 표현해볼까 해서 해봤는데

시간 안에 답이 나온다. 물론 2.xxx초가 걸리는 무지막지한 코드이지만 시간안에 답만 나오면 되므로 문제는 없다.