SLENDER ANKLES's 개발블로그

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

문제는

축사보안을 위한 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가지의 총 경우가 나오는데,

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

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

각 점수를 계산해준다. 

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

최종적인 답을 구했다.