SLENDER ANKLES's 개발블로그

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

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 (수의 부분합 풀이)

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

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

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

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

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

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

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

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

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

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

5의 9승 => 1953125번

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

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

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

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

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

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

분할 정복 문제였다. 

문제를 간략히 정리하자면 

2의 7승까지의 크기를 갖는 정사각형 모양의 색종이를 

규칙에 맞게 잘랐을 때의 흰색부분, 핑크색 부분의 개수를 알아내는 문제였다. 

분할정복의 재귀함수의 인자를 가장 위, 가장 아래, 가장 왼쪽, 가장 오른쪽

이렇게 4가지의 인자를 가지고 있게 했다. 

2가지의 조건

1) 현재의 사각형이 같은 색깔이면 색종이 확정

2) 사각형이 더 이상 쪼갤 수 없이 1개이면 색종이 확정

을 만족하는 것 이외에는

// - 세로 시작 - 세로 중간 - 가로시작 - 가로중간

// - 세로시작 - 세로 중간 - 가로중간 - 가로끝 

// - 세로중간 - 세로끝 - 가로시작 - 가로중간

// - 세로 중간 - 세로끝 - 가로중간 - 가로끝

이렇게 색종이를 쪼갠다. 

중요한 것은 

[1] [2] [3] [4]

(1 + 4) / 2 => 2, (1 + 4) / 2 + 1 => 3

과 같이 왼쪽 오른쪽, 위 아래의 자르는 사각형의 범위를 신경써주면 된다.