Simple in Complex with Simple

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의 값이 높아지면 어마어마한 수행속도가

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

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

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

1. 개요

조합과 중복조합이 가능한 모든 경우를 추출하기 알고리즘.

역시나 코드 구성과 그 내용은 앞선 57, 58 챕터와 동일하다.

이 코드에서 배운 것이 있다면, 만약 데이터를 중복해서 추출하고 싶을 때의 어떻게 하는지에 대해서이다.

하지만 결론은 단순히 조합 알고리즘에서 단순히 Index + 1을 Index로 바꾸기만 하면 되었다.

시간 측정을 해봤는데, 적어도 증가량이 지수적 증가보다는 다항 시간에 가깝다.

2. 코드 및 출력

2-1) 조합 알고리즘

2-2) 중복조합 알고리즘

2-3) 결과 출력

2-4) 시간 출력