SLENDER ANKLES's 개발블로그

어떻게 구해야 하나 고민을 쫌 했는데 이리저리 생각해보다가

너무 작게 생각하지 않고 전체 게임에서 도출 해 낼 수 있는 점수와 실제 팀들이 받은 점수들을 비교하면 답을 구할 수 있을 것 같았다. 

조금 더 자세히 설명해보자면

이기면 3점, 비기면 1점, 지면 0점의 스코어를 각 팀들이 가져간다고 했다. 

경기는 두 개의 팀이 있어야만 이루어지는 것이다. 그렇다면 한 경기에서 

이기거나 지는 경기에서는 두 팀 중 어느 한팀이 3점을 반드시 가져가게 된다. 

하지만 비기게되면? 두 팀은 각자 1점씩을 가져가게 되어 2점이 발생하게 된다. 

대회 주최측 입장이라면 이기거나 지는 게임은 3점, 비기는 게임은 원래 발생할 수 있는 점수에서 1점이 부족하게 발생한다. 

모든 경기의 수에서 3점을 곱해준 값은 대회측에서 모든 경기에서 발생할 수 있는 승점을 의미하며, 

모든 경기에서의 승점 - 실제 각 팀들의 점수들의 합 = 예상치에서 손실된 점수(비긴 경기의 승점)

을 의미한다. 한 개의 비긴 경기는 이기거나 진 경기와 1점 차이가 나므로 

위의 계산 값이 비긴 경기의 수를 의미한다. 

설명을 잘 못해서 쉬운 문제를 어렵게 설명한 듯하지만 실제로는 간단하게 풀 수 있는 문제다. 

서로 소라는 단어에 대해서 로직을 생각해내는 것이 핵심인 문제 같다. 

더 좋은 방법이 있을 수도 있지만(서로소의 성질을 이용해서 답을 도출해내는 등등)

나는 단순하고 무식하게 풀었다. 

두 숫자 input_a, input_b가 있다면

1) 두 숫자 중에 더 작은 수를 찾아냈다.

=> 작은 숫자의 약수를 구하는 이유는 작은 숫자가 큰 숫자보다 for문을 조금이라도 덜 돌수있기때문이다. 큰상관은 없다.

2) 1부터 작은 수까지 for문을 돌면서 작은 수의 약수를 모두 구해서 배열에 담아 두었다. 

3) 큰 숫자를 구해진 작은 수의 약수들로 나누어보아서 나누어지면 두 수는 서로소가 아니다.

어느 숫자로도 나누어지지 않으면 두 수는 서로소이다. 

물론 구해진 약수 중 1은 제외이다. 1은 어느 숫자라도 약수로 가지기 때문이다.

답이 제대로 나온다. 

이렇게 1000까지는 다소 후한 제약조건이 있는 경우에는 위와 같은 방법으로도 충분히 풀 수 있으므로 

크게 고민 할 필요가 없다. 

다만 숫자가 커지거나 하면 다른 방법을 생각해봐야 한다.  

정말 dp로 문제를 풀어나가는데 어려움을 느낀다.

시험이 끝나고 dp문제를 많이 풀어봐야겠다. dp를 잘 풀어야 문제해결능력이 높다고 할 수 있다는 것을 깨달았다. 

이 문제는 dp에 대한 풀이경험이 많다면 충분히 풀 수 있는 문제였다.

우선 문제에 대해서 정리하자면

1~34까지의 숫자가 적힌 카드가 있다. 

어느 한 숫자들 문제에서 보면 27123을 이 숫자카드를 나열하여 만들 수 있는 경우의 수를 구하는 문제였다. 

처음에는 dp인지도 모르고 백트래킹으로 풀어냈다. 

처음에 2인 카드를 놓는 경우에 그 다음 카드부터 7 또는 27카드를 놓을 수 있는 경우의 수와 함께

분기시켜며 결국 답을 구해냈다. 하지만 시간초과 ㅜㅜ 

이 문제는 찾아보니 dp문제였다. 

1~40자리의 수 이므로 백트레킹으로는 아무리 줄이더라도 정말 어마어마한 숫자가 나온다. 

그래도 1자리와 2자리 조건이 있으므로 충분히 시간 안에 답이 나올 수 있을 것이라 생각했는데 

아니었다. 

그 이후로는 도저히 방법이 생각 안나 막혔는데, 도움을 얻고 풀어냈다 생각의 전환이 필요했다. 

27123을 나열할 때 

2 -> 27 , 1 -> 12 -> 123 이 피보나치 수열의 형태로 경우의 수를 가진다는 것을 알았다. 

0으로 끊키거나, 2자리수가 34가 넘는 수는 피보나치의 형태를 깨뜨리고 다시 시작하게 되었다. 

예전에 풀었던 자리배치 dp문제와 완벽히 비슷한 문제였는데, 풀어내지 못 해서 아쉽다. 

자리배치 문제는 고정석을 경계로 피보나치의 값을 가지는데 이 경우는 10, 20, 30과 34를 넘는 수에서 피보나치가 끊키고

약간의 조건만 걸어주면 되는 문제였다. 

경우의 수 문제에서는 시간 안에 풀 수 없다면 피보나치를 한 번 생각해보자!!

이 문제는 내가 심각하게 잘 못 길을 잡아서 고생했던 문제였다. 

이러한 아이디어는 경험을 통해서 얻어내야겠다고 생각했는데, 이번에도 방향을 조금 잘 못 잡은 듯하다. 

문제에 대해서 간단히 정리하면

배열의 경계에 스토어들과 시작해야 하는 특정 위치가 주어진다. 

그러면 특정위치에서 시계방향 또는 반시계방향으로 경계면을 

돌아 그 위치까지의 최단거리를 찾아서 모두 다 더해주는 문제였다. 

딱히 길이에 대한 방법이 떠오르지 않아 재귀로 방향을 통해 들어가서 답을 구했다. 결국은 해냈지만 

여러 사항들을 처리해주느라 조금 힘들었다. 

하지만 적절하지 않은 방법이라도 답을 낼 수는 있게 된거 같다. 

풀고나서 다른 사람들의 풀이법을 보니까 

전체 w * h의 좌표계에서 경계면을 따라 반시계 방향 또는 시계 방향으로만 돌기 때문에 

전체 길이에서 그 해당 상점까지의 길이 또는 전체 거리에서 그 상점까지의 길이를 빼준 두 개의 경우 밖에 없다는 것이다. 

매우 간단한 문제였다 ... 문제를 좀 더 잘 분석해서 해결해 나가야 겠다.

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

결국 힌트를 얻기위해 돌아다니다가 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번안에 답이 나온다. 

어려운 문제였다. 

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

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

우선 로직은 

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개의 부등호를 만드는 재귀적 호출도 금방 수행을 할 수 잇게 된다.