SLENDER ANKLES's 개발블로그

백준에서 똑같은 문제 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이므로 절대 완전탐색을 하면 안되는 문제였다. 

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

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

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

반복하는데 귀신인 컴퓨터에 적당한 방법이다. 가능한 경우를 모두 검사(exhaustive search)하는 무식한(?)방법이다.

답 내는 것이 문제가 아니라 얼마 만큼의 빠른 시간에 작업을 끝낼수 있는 가를 고민해야 되는 파트.

가능성이 없는 것은 미리 잘라버리는 것이 관건이다. 예를 들어, 3 번의 시합에서 2 번 우승하면 이기는 게임에서 미리 2 번 이기면 나머지 한 번은 할 필요가 없다. 이런 가능성을 생각해서 미리 많이 잘라버리면 그 만 큼의 실행시간이 빨라진다.

가능한 경우를 모두 검사하는 방법에는 보통 두 가지 유형의 문제로 나뉠수가 있다.

• 부분집합형 백트래킹
• 팩토리얼형 백트래킹

예를 들어 , 주머니 속에 7 개의 공이 있고 , 각 공에는 번호가 부여되어 있다.

부분집합형

주머니에서 몇 개의 공을 꺼내어 합이 13 이 공들을 찾는 경우에는 2^7 가지의 부분집합을 모두 검사해야 한다.

한 개 뽑는 경우

• 6
• 2
• 9
• ..

두 개 뽑는 경우

• 6 , 2
• 6 , 9
• 6 , 8
• ...

세 개 뽑는 경우

• 6 , 2 , 9
• 6 , 2 , 8
• ...

...

7 개 모두 뽑는 경우

• 6, 2, 9 , 8 , 3 , 4 , 7

팩토리얼 형

7 개의 공을 임의로 나열했을 때 인접한 수의 곱이 최대 인 경우는 어떤 경우인가를 알고자 할 때 7! 가지의 모든 경우를 생각해야 하므로 이는 팩토리얼 형 문제라고 생각할 수 있다.

• 6 2 9 8 3 4 7
• 6 2 9 8 3 7 4
• ...

(문제) sum of subset 

6 , 1 , 9 , 8 , 3 , 4 , 7

총 합은 38 , 합은 반은 19 이다.

이 수들을 적절히 뽑아 19 를 만들 수 있는 방법의 수를 구하는 문제.

부분 집합형 문제의 기본 틀

첫째 원소, 둘째 원소 2 개 있을 때 부분집합의 수는 4 개이다.

• 2 가지 모두 포함하는 경우 (o o)
• 첫 원소 포함 , 둘째 원소 포함하지 않는 경우 (o x)
• 첫 원소 포함하지 않고 , 둘째 원소 포함하는 경우(x o)
• 2 가지 모두 포함하지 않는 경우 (x x)

o 를 1 로 x 를 0 으로 놓으면 ,

• 1 , 1
• 1 , 0
• 0 , 1
• 0 , 0

원소의 수가 2 개 일 때

이를 구현하기 위해 배열(배열명을 include[] 라 하자)을 사용하여

원소의 수가 3 개일 때

(샘플 문제)수의 부분합 문제로 조금씩 실행 속도를 높여 보기로 하자. 문제는 전제 합의 반 50 이되는 원소를 골라내는 문제이다. 
주어지는 데이터는 40 20 30 10 (수의 부분합 풀이)