Simple in Complex with Simple

1. 개요

모든 괄호쌍 알고리즘은 카탈란 수 알고리즘에 속함.

카탈란 수 알고리즘이란 점화식이 다음과 같은 모습을 지닐 때를 지칭함.

Cn = 시그마(0 ~ n-1) Ci * Cn-1-i

이렇게 표현하면 정말 수학적 기호도 없고 너무 어려워 보이기에 쉽게 말로 표현하면

한 가지 경우를 시행하면, 그와 쌍이되는 다른 경우를 반드시 시행해야 하는 모든 개수.

말 또한 어렵기 때문에 괄호쌍을 예를들면,

만약 ( 괄호가 나오면 반드시 ) 괄호가 나와야 함. 

( 이 두 번 나오면 ) 도 반드시 두 번 나와야 함.

이처럼 쌍을 이루는 것들을 나열하는 모든 경우의 수를 카탈란 수라고 한다.

괄호쌍 알고리즘도 이에 속하며, 괄호쌍 2개로 예를들면 다음과 같다.

( ( ) )

( ) ( )

단, 이 두 가지 경우뿐이다.

카탈란 수의 정확한 수학적인 성질은 알 수 없지만, 카탈란 수를 나타내는 경우들이 2개 더 있다.

(1) 첫 번째는 2차원 배열에서 한 지점 A에서 B까지 가는 최단경로의 수다.

왜냐하면, A에서 B지점까지 최단경로로 도착하기 위해선 단 두 가지 방향의 쌍으로 이루어진다.

가장 간단히 다음과 같은 배열이 있다.

0 0 B

0 0 0

A 0 0

여기서 A에서 B로 최단경로로 도착하려면, 오른쪽아니면 위쪽 밖에 길이 없다. 그리고 반드시 이 방향은 대칭된다.

그렇기에 카탈란 수에 속한다.

(2) n개의 노드로 이루어진 이진 탐색트리(Binary Search Tree)

괄호쌍이나 2차원 배열 최단경로 수랑은 조금 다르다. 왜냐하면 자식노드의 왼쪽 오른쪽 쌍의 개수가 대칭을 이루지는

않는다. 하지만, 다음의 예를보면

왼쪽 자식 노드 0개, 오른쪽 자식 노드 n-1개.

왼쪽 자식 노드 1개, 오른쪽 자식 노드 n-2개.

왼쪽 자식 노드 2개, 오른쪽 자식 노드 n-3개.

..................

왼쪽 자식 노드 n-1개, 오른쪽 자식 노드 0개.

트리의 구조가 대칭쌍을 이루기에 카탈란 수에 속한다.

2. 문제

2-1) 입력한 괄호쌍 개수에 따른 경우를 모두 출력하는 알고리즘을 작성하시오.

2-2) 카탈란 수를 알고리즘을 작성하시오.

3. 코드 및 출력

3-1) 괄호쌍 코드

3-2) 괄호쌍 출력

3-3) 카탈란 수 코드

3-4) 카탈란 수 출력

4. 정리

이것으로 3장까지 독파했다. 내일부턴 4장.

참 시간은 많은데, 시간이 왜캐 부족하게 느껴질까.

주어진 시간동안 파이팅.

1. 개요

순열(Permutation)은 n개의 원소 중 k개를 뽑아서, 나열하는 것이다.

조합(Combination)이 단순히 n개의 원소 중 k개를 뽑아내는 경우만을 찾아서 부분집합을 만들 수 있었다면,

순열은 이런 부분집합들의 나열하는 방법을 일컫는다.

지금까지 set배열과 set_size를 통한 코드 구조가 안먹힌다.

재귀 코드의 형태가 조금 다른데, 문제는 단순 순열 출력이 아닌 이를 사전 순으로 출력하는데 있다.

두 가지 방식, 일반적인 순열 출력 알고리즘과 사전 순으로 순열을 출력하는 알고리즘 두 개가 있으며,

사전 순으로 순열을 출력하는 방식은 처음 보는 방식이었다.

그래서 더욱 놀랍다.

생각의 범위라는게 조금씩 확장되는 듯한 느낌? 아마 이것을 그냥 짜라고 했다면 못짰다. 틀을 알고있으니까 짜는거지.

Right_Rotate() 함수와 Left_Rotate() 함수를 이렇게 이용할 줄은 진짜 꿈에도 몰랐다. 신기하다.

아마 나같았으면 계속 정렬하는 말도 안되는 방식을 짰겠지. 대단하다. 사람의 머리란.

전체적인 알고리즘의 틀은 이렇다.

0 1 2 3의 순열은 총 4가지로 나뉘는데,

0 | 1 2 3 의 순열

1 | 0 2 3 의 순열

2 | 0 1 3 의 순열

3 | 0 1 2 의 순열

이렇게 나뉘고, 또 길이 3에서

---------------------------------

0 | 1 2 3

1 | 2 3

2 | 1 3

3 | 1 2

---------------------------------

1 | 0 2 3

0 | 2 3

2 | 0 3

3 | 0 2

---------------------------------

2 | 0 1 3

0 | 1 3

1 | 0 3

3 | 0 1

---------------------------------

3 | 0 1 2

0 | 1 2

1 | 0 2

2 | 0 1

---------------------------------

이렇게 계속 재귀적으로 풀어나간다.

이것이 순열의 기본 알고리즘이다. (나중에 아무런 참고자료없이 꼭 다시 반복해서 짜보자.)

2. 문제

순열(Permutation) 출력 알고리즘을 작성하시오. (사전 순으로도 출력하는 알고리즘도 작성하시오.)

3. 코드 및 출력

3-1) Perm()

3-2) Perm_Dictionary()

3-3) 출력

마지막 출력은 맨 처음 출력을 사전 순으로 출력할 때, 쉽게 이해되게 하기위해서 Rotate()연산 후의 변환 과정을 보인다.

4. 정리

이렇게 순열 알고리즘도 끝났다. 오늘 남은 건 이제 괄호쌍 알고리즘이다.

1. 개요

그래프 분할(Graph Partitioning)이라는 유명한 문제라고 한다.

솔직히 어떤 면에서 이 문제가 그래프 분할이라는 개념에 속하는지 모르겠다.

먼저 문제는 하나의 집단 N명을 동등하게 N/2로 나누어, A와 B에 배치해야 한다. 

이 때, 각각의 집단 서로 서로 친분 관계를 유지하는데, 이 친분 관계를 최대한 존중하는 쪽으로 분할하는 방법이다.

글로 보면 조금 어려워 보이지만, 결국은 N을 모든 N/2로 분할한 집단을 다 조사해서 가장 효율적으로 뽑아내면 된다.

즉, 모든 부분집합으로 체크하는 전수조사다.

그렇기에 전체 알고리즘의 틀은 지금껏 작성한 알고리즘과 토대를 같이한다.

단, 특징적인 점이 있다.

여기서 부분집합을 나눌 때, 원래의 집합을 이용하는 것이 아닌 이진수 비트로 각각의 사람을 대응시켰다.

이게 무슨 말이냐면, 만약 6명의 사람을 A와 B로 동등하게 나눈다고 할 때, 

0 0 0 1 1 1 이란 비트와

0 1 0 1 0 1 이란 비트가 있다고 하면,

0 0 0 1 1 1 비트는 0번 1번 2번 사람은 A에, 3번 4번 5번 사람은 B에 배치한 것을 의미한다. 마찬가지로

0 1 0 1 0 1 비트는 0번 2번 4번 사람은 A에, 1번 3번 5번 사람은 B에 배치한 것을 의미한다.

이렇게 이진수 비트로 대응시킨 이유는 입력한 N에 따라서 빠르게 만들 수 있는 모든 이진수 비트를 뽑아내서,

조건에 맞게 0의 개수와 1의 개수가 동등한 비트만을 집어넣어 알고리즘을 수행한다.

즉, 모든 부분집합을 빠르게 나열하기 위해 각각의 사람을 비트라는 체계로 분할한 것이다.

2. 문제

한 기업에 N명의 프로그래머가 있다. 훌륭한 성과를 낸 프로그래머들을 위해서 기업의 CEO께서 연회를 열기로 결정했다. 

하지만 N명을 모두 수용할 수 있는 연회장이 없어서 어쩔 수 없이 N/2명이 수용가능한 연회장 A와 B를 빌렸다. 

각각의 연회장에 프로그래머들을 분할하려고 했는데, 알고보니 각각의 프로그래머들 관계에서 온도차를 발견했다.

연회도 마음에 맞는 사람과 즐겨야 좋은 법.

그래서 CEO께선 최대한 친한 사람과 연회를 즐길 수 있도록 고심했다.

하지만 모두를 만족시킬 수 없기에, 어쩔 수 없이 친한 관계이지만 다른 연회장을 사용해야 할지도 모른다. 

이런 경우를 바로 단절을 의미하는 Cut이라고 한다.

이 Cut이 최소가 되게끔, 하는 알고리즘을 작성하라.

3. 코드 및 출력

3-1) Partition()

3-2) Check_Friends()

3-3) Check_Half()

3-4) 출력

4. 정리

점점 재귀적인 방법 풀이에서 새로운 개념이 깃든다. 점점 최초의 틀에서 조건을 추가하는 방법들을 어떻게 하는지 알겠다.

물론 이 틀은 재귀 방식이기에 데이터가 커지면 거의 수행속도가 기하급수적으로 증가할 것이라고 생각한다. 아직 더 좋은

방법들에 대해 잘 모르기에 계속 공부해나가자. 또한, 이제 재귀 방식에 그래프 개념이 새로 연결되고 있다. 발전하고 있다.

이번에 내 주변의 기대들을 깨고 싶지 않다. 정말. 그리고 어제 전화는 너무 감사했다. 항상 힘들고 주저앉고 싶을 때마다

지탱해주는 이들이 있다. 나중에 다 내가 잡아준다. 안 무너지게.

1. 개요

드디어 부정방정식 알고리즘 풀이다.

이 풀이는 무척 간단하다.

하지만 난 몰랐다.

멍청이다 난.

먼저 부정방정식이란 이런 형태를 말한다.

x0+x1+x2+x3+ ... xn = K

이런 식이 있을 때, K가 주어질 때, 이를 만족하는 x0, x1, x2, x3 ... xn을 찾는 것이다.

항상 궁금했었다. 이 부정방정식 풀이를 어떻게 해나가는지.

특히, 예전에 어머니가 일하는 시는 복지회관의 설문 조사에서 값을 정해주고 통계를 내달라는 부탁을 받았다.

왜 이걸 직접 받아야지, 마음대로 조작하냐고물어보니까,

거기 복지회관 분들이 시각장애인분들 도움주는 복지회관이고, 또한 연세가 많으셔서 이 설문받기가 어렵다고 한다.

물어봐서 답변하는 방식으로는 다들 좋다고만 하셔서 오히려 이렇게 직접 일정 기준을 만들어놓고 하는게 신뢰성있다고 한다.

그래서 뭐 어쩔 수 없이, 이 통계를 내려고하는데 일단 나는 엑셀을 못한다.

수학적으로 하나하나 접근하려고 하니, 머리가 안돌아갔다.

여러 번 고심하다 그냥 프로그램 만들어서 다 돌려버렸다.

하지만 그 때 만들었던 방식은 5중첩 for 루프 방식이었다.

5점 4점 3점 2점 1점 식으로 다 돌면서, 점수를 만점에서 95% 유지할 수 있는 조건들을 추출했다.

결과야 잘 나왔지만, 마음에 안들었다.

5중첩 for 루프라니.

코딩을 막 시작할 때나 쓰던 방법이었다.

그래서 어떻게하면 부정방정식을 깔끔하게 풀 수 있는지 궁금했는데, 오늘에서야 조금 더 깊게 알아간다.

결국 전수조사밖에 답이 없긴한데, 각 부정방정식에 걸린 조건에 따라 조금씩 최적화를 시킬 수 있다고 생각한다.

2. 문제

미지수 x의 개수 N을 입력하고, 구해야 할 값 K를 입력했을 때, 가능한 모든 경우의 수를 구하고 그에 따른 값을 출력하시오.

(순서를 구분하는 경우, 순서를 구분하지 않는 경우 두 가지 방식 모두 풀이하시오.)

3. 코드 및 출력

3-1) 순서를 구분하는 모든 부정방정식 풀이

3-2) 순서를 구분하지 않는 모든 부정방정식 풀이

3-3) 합계가 K와 일치 판단 알고리즘

3-4) 출력

4. 정리

이렇게 부정방정식 풀이의 아주 기초 알고리즘을 알아냈다. 다만, 이 방식은 K의 값이 높아지면 어마어마한 수행속도가

걸린다. 왜냐하면 재귀적 풀이니까. 퍼즐에서 부정방정식과 비슷한 방식의 퍼즐이 있다. 복면산 퍼즐이라는 방식인데

흔히 인적성 검사에서 많이 보던 문제 유형이다. 나중에 이 복면산 퍼즐 알고리즘을 작성하면서 부정방정식에 대해

더 정리하자. 배고프다. 점심먹자.