SLENDER ANKLES's 개발블로그

분할 정복 문제였다. 

문제를 간략히 정리하자면 

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

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

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

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

2가지의 조건

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

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

을 만족하는 것 이외에는

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

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

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

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

이렇게 색종이를 쪼갠다. 

중요한 것은 

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

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

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

재귀를 통한 탐색방법에 대해서 다시 한 번 생각하고 명확히 알아야겠다는 필요성이 있었다. 

문제는

축사보안을 위한 L개 자리의 서로 다른 알파벳을 갖는 비밀번호를 생성하는 문제였다. 

입력으로 C개의 알파벳이 주어지는데, 

이 알파벳을 이용해서 L개 자리수를 가지는 알파벳을 만든다. 

조건이 있다면, 

1) 알파벳이 오름차순으로 정렬된 결과만을 도출해야 하며

2) 비밀번호에 모음이 1개 이상, 자음이 2개 이상 있어야 한다. 

완전탐색이긴 하지만 몇 가지 조건을 주어서 재귀적으로 풀어나가야 한다는 것을 알았다. 

입력의 상황

L => 4, C => 6

a t c i s w

가 주어지는데

우선 사전식 오름차순으로 먼저 정렬한다. 

a c i s t w

로 만들고

첫 번째 자리를 C - L => 2번째 인덱스까지 

배치하며 그 상황에 대해서만 완전탐색을 했다. 

4개의 알파벳 모음이 만들어 지면 모음이 한 개 이상 있는지만 검사해서 답을 내주었더니 답이 나왔다.

자음은 신경쓰지 않았다. 테스트케이스에 모음으로만 구성되어 있는 것이 없었나보다.

다시 풀어 볼 문제

그래프가 아닌 1차원 배열에서의 bfs 문제였다. 

일단 최단거리를 구하라 했을 때 순회하는 거라면 bfs를 생각 해보는 게 좋을 것 같다. 

1~100000의 범위의 1차원 배열에서

농부는 n의 위치에서 출발하고, 소는 k의 위치에 있다. 

농부는 +1 , -1, *2 만큼 이동 가능하다. 

한 번 이동하는데는 1분이 걸린다. 

소를 잡는 데 걸리는 최소 시간을 구하라는 문제였다. 

=> 소까지 가는 데 걸리는 최소 시간을 bfs로 구해보자 라는 문제와 같다고 이해하면 됐다. 

뭐 구하는 거 까지는 나름 쉬웠다. 

그런데 visual studio에서는 답이 나오는데, gcc에서는 답이 나오지 않았다???

흠. 내가 한 가지 놓친 점이 있었는데, 

현재 위치에서 * 2를 하는데, 배열의 범위는 10만개 까지 밖에 선언을 안 해놨던 것이다. 

99999 * 2는 내가 선언 해 놓은 배열의 범위를 이미 넘어서서 접근하는 것인데, 

비쥬얼 스튜디오는 이러한 예외를 인정하고 직접 접근하여 값을 갱신하는 것만 아니면 별 문제없이 

답을 구해줬는데, gcc는 그렇지가 않았다. 

**느낀점 : 배열의 탐색 범위만큼 배열을 선언해놔야 한다. 때로는 문제의 범위를 넘어서 탐색 할 수 있다는 점을 명심해야 겠다.

아.. 정말 고민하고 틀리기도 엄청 틀렸는데 이제는 

2번 정도 틀리는 문제는 과감히 포기하는 연습을 해야겠다. 어차피 여러번의 시도가 안되니까 말이다. 

-1억 ~ 1억 사이의 좌표 범위에서 

주어진 두 점의 선분에서 좌표가 정수로 떨어지는 점들의 개수를 찾는 문제였다. 

처음에는 굉장히 당황했고, 문제가 재귀라는데, 재귀를 사용하는 것에는 도무지 아이디어가 떠오르지 않았다. 

그래서 일단 시간초과를 감수하고라도 그냥 풀어야겠다고 생각했다. 

다 못 맞더라도 몇 개의 테스트케이스는 가져가는 로직을 짜야겠다는 생각을 한 것이다. 

내 소스의 치명적인 단점이 있는데, 선분이 주어지게 되는 경우의 수를 다 헤아리는데는 처음에 생각치 못한 예외가 굉장히 많았고 나는 그냥 그 것을 틀리면서 터득했다는 것이다. 좋지 않은 방법이라고 생각은 하지만 그래도 풀긴 풀어야 했다. 

예를 들어 두 점이 

(-1, -2) , (3, 4)

주어진다. 

1) 좌측 점을 0, 0으로 평행 이동시키면서 우측 점도 갱신한다.

-1, -2 => x 우측으로 1칸 위쪽으로 2칸 이동 시키면 0, 0이 되면 우측 끝 점은 (4, 6) 점이 된다.

2) 이렇게 나의 입맛에 맞추어 놓은 직선 y = ax 라는 방정식에서 a(기울기)를 구한다. 4,6을 대입하면 된다. 

a = 2/3이 된다. 

3) 이렇게 나의 입맛에 맞추어 놓은 직선을 x = 0 부터 ~ 우측 끝 점 4까지 순회하면서 정수를 찾는다.

모든 점들은 double형으로 선언했기 때문에

(a * i) == (int)(a * i) 가 참이 되면 이 것은 정수라는 것이다. 

4) 이렇게 개수를 구해줘서 출력해주면 된다.

다시 정리하자면

나의 방법은 좌측에 있는 점을 0, 0으로 평행이동 시키면서 0부터 우측점의 x 좌표 까지 순회하면서 

정수를 찾는 방법이었다. 

평행이동 시켰을 때는 

직선의 방정식은 y = ax 가 만들어진다. 0, 0을 한 점으로 가지고 있기 때문에, 

+b는 생략가능하다. 

이렇게 a라는 기울기를 구하고 x를 0 부터 우측 끝점까지 돌면서 x가 정수일 때 y도 정수인 점의 개수를 찾는 것이다.

다소 복잡하게 푼 점이 있지만 아이디어가 떠오르질 않아서 이렇게 푸는 수밖에 없었다. 

2차원 배열을 통한 재귀는 끝끝내 성공하지 못하고, 

1차원배열을 통한 완전탐색을 통해서 답을 도출해내었다.

어떻게든 답을 구해냈으니 된거지만 뭔가 찜찜한 마음이 든다. 

더 좋은 방법을 택한 것이 아니라, 내가 구현 할 수 있는 부분으로 구현해서인거 같다. 

처음에 생각한 방법은 이러했다.

각 팀을 인덱스로 가지는 배열을 만들어냈다.

총 여섯 가지

[1][2]    => 1팀이 2팀과 붙은 결과

[1][3]    => 1팀이 3팀과 붙은 결과

[1][4]

[2][3]

[2][4]

[3][4]

이런식으로 생각하고, 이미 결과가 나온 게임을 제외하고 

완전 탐색을 시도했다. 

이기거나, 지거나, 비기거나 3가지의 경우가 있으므로

3가지의 경우를 6가지

3 * 3 * 3 * 3 * 3 * 3가지의 총 경우가 나오는데,

이미 진행된 게임을 제외하면 이보다는 적게 된다. 

이렇게 경우의 수가 만들어 질 때마다 

각 점수를 계산해준다. 

그리고 나의 팀이 가장 높은 점수를 기록한 경우에는 카운트를 증가시켜

최종적인 답을 구했다. 

문제를 제대로 읽고 답하면 어렵지 않게 풀 수 있는 문제였다. 

책의 ISBN은 10자리수로 구성되는데 

1~9번째 자리까지는 0~9의 수들로 이루어져있고

10번째 자리는 0~10(10은 X로 표현됨)으로 이루어져 있다. 

입력 받은 수에 ?가 끼어있는데 이 물음표를 구하는 문제였다. 

우선 캐릭터 배열보다는 INT형이 관리하기 쉬웠으므로 INT형으로 바꿔주어 입력 받고, 

물음표는 -1로 배열에 저장하였다. 

규칙에 맞게 각 자리수를 더해서 SUM을 만들고, 

물음표가 들어온 자리의 인덱스를 저장해두었다가

순회하며

SUM + (물음표자리수에 해당 하는 숫자 * 맞출숫자)   를 11로 나누어서 0이 되는 값을 찾았다. 

코딩 해줘야 할 것이 많지만 , 그리 어려운 문제는 아니었다. 

다만 구현하는데 시간이 좀 걸렸다. 이런 문제는 시간 싸움인 것 같다. 

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

19 * 19 배열을 오목판으로 생각하고 흰돌, 검은돌이 배열 위에 그려지게 되는데

지금 상황에서 흰돌이 이긴 것인지, 검은 돌이 이긴 것인지 판별한다. 알 수 없으면 0을 출력한다.

오목은 반드시 돌 5개가 나란히 놓여야지 이기는 것, 6개가 놓이면 이기는 것이 아니다. 

만약 돌 5개가 놓인 지점의 가장 끝 부분(좌우 라면 가장 좌, 상하라면 가장 상)의 좌표도 출력하라.

문제에 나온 조건 대로 코딩해줬다. 

코드는 100줄을 넘어가게 되었지만 나름대로 줄인다고 줄여봤는데 문제의 조건을 표현하는데만해도 꽤 많은 코드가 

필요하므로 당연한 것 같다. 

문제를 푸는데는 약 1시간 넘게 걸린 것 같다. 

중요한 조건이라고 생각되는 것은 오목에서 이기기 위해서는 반드시 돌 5개가 연결되어야만 한다는 것이다.

그래서 반드시 5개만 연결된 것만 답이라고 생각하고 구현했다. 5개 이상은 아니다!

처음부터 끝까지 접근방법은 

어느 한 돌을 만나면 

돌을 색깔을 인자로 가지는 재귀 호출을 하는 것이었다. 

방향은 

1) 좌우, 2) 상하, 3) 좌상우하 , 4)좌하우상

이렇게 크게 4가지의 단위로 검색을 하면 된다. 

그래서 맞으면 값을 도출하고, 재귀호출시에 가장 최소 좌표를 찾아놓으므로 맞춰서 같이 출력해주면 답이 나왔다.

하지만 더블릿에서 다른 사람의 맞춘 소스를 보고 느낀 것은 내 코드에 쓸데없는 조건들이 좀 많이 들어간 거 같다. ㅜㅜ 

담백한 코드를 짜고 싶었는데,,

소수관련 문제였다. 

4보다 큰 수는 반드시 소수 2개의 합으로 표현된다는 것이 골드바하의 추측이라고 한다. 

이러한 수는 

n = a + b 로 표현가능한데, 여러개의 답이 나올 수 있으므로 b - a가 최대인 것을 찾으라는 것이다.

수행시간이 깡패적으로 많이 나온 방법을 택했는데, 그래도 모두 테스트케이스 당 1초안에 문제를 풀어내었다.

소수에 대한 데이터베이스를 만들어서 답을 만드는 방법이었다.

1) 1~n까지, 소수를 만들어 줬따.

2) 답은 b - a가 최대인 값이라고 했으므로

a는 소수모임의 처음부터 for문을 돌고, 

b는 소수모임의 끝에서부터 for문을 돌았다. 

답이 나오면 바로 종료하게끔 해주기 위한 것이었다. 

이 문제를 통해서 소수를 만드는 방법에 대해서 좀 더 정확하게 구현하고 알게 된 것 같다.

DP를 통해서 답을 도출해야되는 문제였는데, 

나는 생각해내지 못 해서 안타깝다. 같은 스터디를 하는 사람 코드와 설명을 듣고 풀게 되었다. 

문제정리)

다음의 두 조건을 만족시키게 색종이를 쌓아야 한다. 

1) 새로 올려 놓는 색종이는 맨 위의 색종이보다 크지 않아야한다. 맨 위의 색종이 밖으로 나가서는 안 된다. 

2) 새로 올려 놓는 색종이와 맨 위의 색종이의 변들은 서로 평행해야 한다. (색종이를 90도로 회전은 가능하다)

문제풀이)

입력으로 주어지는 색종이들의 개수의 제한은 100개이다. 

모든 경우의 수를 완전탐색으로 할려고 했는데 좋은 방법은 아닌거 같다고 생각했다. 

우선 몇 가지 이슈에 대해서 정리해보자면, 

구조체를 정렬해야 한다. 

근데 문제에서 가로(x), 세로(y)의 입력이 주어지는데 

색종이는 90도로 회전 가능하다고 했으므로 x와 y가 바뀔 수 있고, 그 순서가 큰 의미가 없다고 판단 할 수 있겠다.

그래서 입력의 가로 세로 중 큰 값을 x에, 작은 값을 y에 넣어주었다. 

또는 그 반대로 해도 상관 없다.  

그리고 다음과 같은 방법으로 구조체를 정렬해주는 팁이 있는데, 진선이를 통해서 알게 됐다.

위 방법은 구조체를 작은 수를 앞쪽(오름차순으로 정렬을 하고자 할 때 사용한다)

이 방법은 <algorithm>헤더의 sort를 충분히 이용 할 수 있어서 좋은 것 같다. 

이렇게 준비가 다 끝나면 

첫번째 색종이 이후에 두번째 색종이부터 순회하면서 

매번 자신 색종이 전까지를 체크하면서 

앞의 색종이보다 자신이 크면 색종이 쌓는 개수를 1개씩 증가시켜주어 결과값에 저장시켜주는 

메모리에 저장하는 일종의 dp방법을 사용하여 답을 구해주면 된다.