[완료] 알고리즘 문의드립니다..
01. "1111101100110001100001100000"
02. "1111011010101001010001010000"
03. "1110110110011000110000110000"
04. "1101111001100101001001001000"
05. "1011110101010100101000101000"
06. "0111110011001100011000011000"
07. "1101001111100011000101000100"
08. "1010101111010010100100100100"
09. "0110011111001010010100010100"
10. "0001111111000110001100001100"
11. "1101001000111111000011000010"
12. "1010100100111110100010100010"
13. "0110010010111110010010010010"
14. "0001110001111110001010001010"
15. "0000001111111110000110000110"
16. "1101001000100001111111000001"
17. "1010100100010001111110100001"
18. "0110010010001001111110010001"
19. "0001110001000101111110001001"
20. "0000001111000011111110000101"
21. "0000000000111111111110000011"
22. "1101001000100001000001111111"
23. "1010100100010000100001111111"
24. "0110010010001000010001111111"
25. "0001110001000100001001111111"
26. "0000001111000010000101111111"
27. "0000000000111110000011111111"
28. "0000000000000001111111111111"
임의의 패턴에 따라 0과1이 배치된 28개의 데이터가 28줄 있습니다.
(단, 각 줄마다 1은 13개, 0은 15개로 구성되어 있습니다.)
위의 총 28줄에서 몇줄을 추출하여 OR 연산을 해서
"1111111111111111111111111111" 이 되게끔 하려고 합니다.
28줄을 전부 OR 연산해버려도 되겠지만,
[최소한의 줄]을 추출하여 원하는 값을 얻고자 합니다.
예를들어 1번,6번,15번,16번 을 추출하여 OR 연산을 하면 "11111..." 값이 나옵니다.
01. "1111101100110001100001100000"
06. "0111110011001100011000011000"
15. "0000001111111110000110000110"
16. "1101001000100001111111000001"
------------------------------------
합. "1111111111111111111111111111"
28*28을 예로 들었지만, 84*84, 210*210, .... 5005*5005 같이 큰 데이터에서도 적용 가능한 알고리즘을 찾고 싶습니다.
좋은 아이디어 있으면 좀 나눠주세요 ㅠㅠㅠ
가능한 조합이 단 하나만 존재하는가요? 아니면
가능한 조합이 반드시 하나이상 존재하는가요? 즉, 없을 수도 있나요?
가장 적은 조합만 찾으면 되는 건가요? 아니면 모든 조합을 다 찾아야 하는 건가요?
------------------------------
How many legs does a dog have?
가능한 조합은 여러개가 존재할 수 있습니다
가능한 조합은 여러개가 존재할 수 있습니다. (없을수는 없습니다)
하지만 단 하나의 결과만 있어도 충분합니다.
0~(2^n)-1 사이에 임의로 주어진 수 n개 중,
0~(2^n)-1 사이에 임의로 주어진 수 n개 중, 적당히 몇개를 골라서 더하여 2^n-1 mod 2^n를 만드는 알고리즘이 되겠군요.
배낭 문제의 응용형태가 되겠네요.
http://www.jlab.net/Jboard11/JBoard.jsp?action=read&index=18&page=3&tale=0&tablename=soft&way=0&maxrow=18&searchtype=&keyword=&category=
피할 수 있을때 즐겨라! http://melotopia.net/b
천천히 읽어보고 있는데... 어렵네요 ㅠㅠ 좀더
천천히 읽어보고 있는데... 어렵네요 ㅠㅠ
좀더 집중해서 읽어봐야겠네요..
근데 문제가 다 보이지 않네요..
어떤 도둑이 금고 안에 크기와 그 값이 다른 N개 유형의 물건들이 있음을 알았다. 그러나 그 도둑은 용량이 M인 작은 배낭 하나만을 갖고 있다. 배낭문제는 가지고 가는 물건들의 총 값어치가 최대가 되도록 물건들의 조합을 선택하는 것이다.
예로서, 배낭의 용량이 17이고, 금고 안에는 아래 그림과 같이 각기 크기와 값이 다른 물건들이 있다고 하자. 이
까지만 보이네요
암튼 답변 감사합니다.
배낭문제 에 대해서 검색해봐야겠습니다
10진수로 간주하고, 작은수부터 큰 수 순서대로
10진수로 간주하고, 작은수부터 큰 수 순서대로 오름차순으로 정렬한 후, 위에서부터 하나씩 적당히 골라가면 될 것 같은데요.
이건 욕심쟁이 방법의 응용이겠죠.
피할 수 있을때 즐겨라! http://melotopia.net/b
욕심쟁이 방법 이란것도 배낭문제랑 비슷한건가요? 좋은
욕심쟁이 방법 이란것도 배낭문제랑 비슷한건가요?
좋은 힌트 감사합니다.
검색해봐야겠네요
Greedy Method 는 배낭문제 해법 중 하나입니다.
욕심쟁이 방법 (Greedy Method) 가 배낭문제의 적정결론을 찾기 위한 방법일뿐 최적값의 해법은 아닙니다.
동적계획법 (Dynamic Programming) 도 마찬가지죠.
제가 보기엔 Dynamic Programming 같은데요.
동적계획법 (Dynamic Programming) 이 필요한 경우는 흔치 않은데 오랜만에 보네요.
공부 목적이 아니라면 뭐에 쓰는 걸까요?
개인용도의 프로그래밍을 하다 삼천포로 빠지면서 위의
개인용도의 프로그래밍을 하다 삼천포로 빠지면서 위의 문제에 맞닥드렸는데
호기심이 생겨서 최적화된 값을 계산하다보니 이렇게 kldp까지 오게되었습니다.
근데 쉽지 않네요...
동적계획법이란것도 검색해봐야겠습니다.
근데 최대 n^3 이면 된다는건 무슨 뜻인가요??
n^3은 제가 실수한 겁니다.
이건 snowall님 말대로 배낭문제의 응용입니다.
조금 더 정확히 하면 0-1 배낭문제인데 NP 완전문제죠.
다른 해법이 가능한지는 모르겠네요.
넵 조언 감사합니다
넵 조언 감사합니다
잘알려진 유형일것
잘알려진 유형일것 같긴한데요..
그냥해보라하면,
1. N개 중 1의 개수가 제일 많은 1개를 고른다.
2. 나머지 N-1개에 대하여 미리 고른 1개가 1인 자리수의 1을 모두 0으로 바꾼다.
3. 1-2 를 나머지 N-1개에 대하여 1이 하나도 남지 않을때까지 반복한다.
라고 하면 일단 어떻게든 하나의 답을 찾을 수 있을 것 같습니다.
global optimal을 찾기는 무척어려울것 같네요..
좋은 힌트 감사합니다. 쉽지는 않을거 같네요 ㅠㅠ
좋은 힌트 감사합니다.
쉽지는 않을거 같네요 ㅠㅠ
이렇게? 당연히 global optimal 절대
이렇게?
당연히 global optimal 절대 아닙니다.
user@localhost:~/kldp/ $ cat in.txt 1111101100110001100001100000 1111011010101001010001010000 1110110110011000110000110000 1101111001100101001001001000 1011110101010100101000101000 0111110011001100011000011000 1101001111100011000101000100 1010101111010010100100100100 0110011111001010010100010100 0001111111000110001100001100 1101001000111111000011000010 1010100100111110100010100010 0110010010111110010010010010 0001110001111110001010001010 0000001111111110000110000110 1101001000100001111111000001 1010100100010001111110100001 0110010010001001111110010001 0001110001000101111110001001 0000001111000011111110000101 0000000000111111111110000011 1101001000100001000001111111 1010100100010000100001111111 0110010010001000010001111111 0001110001000100001001111111 0000001111000010000101111111 0000000000111110000011111111 0000000000000001111111111111 user@localhost:~/kldp/ $ cat ./main.py #!/usr/bin/python3 import array import sys def bitLenCount(int_type): count = 0 while (int_type): count += (int_type & 1) int_type >>= 1 return count data = array.array('L') for line in open( sys.argv[1] ): v = int( line.strip(), 2 ) if v in data: print('duplicated data. exit') sys.exit(1) data.append( v ) result=[] while 1: k = 0 for i in data: k = k | i if k == 0: break max_bitlen = 0 for i in data: bitlen = bitLenCount(i) if bitlen > max_bitlen: max_bitlen = bitlen max_data = i result.append( data.index( max_data ) + 1 ) for i, v in enumerate( data ): data[i] = v & ~max_data print(result) user@localhost:~/kldp/ $ ./main.py in.txt [1, 6, 15, 16]엄청 감사합니다. 파이썬은 잘 모르지만, c를 조금
엄청 감사합니다.
파이썬은 잘 모르지만, c를 조금 할줄 알아서 어느정도 이해는 할 수 있을거 같습니다.
좋은 참고가 될거 같습니다.
감사합니다
굽신굽신
도움이 되셨다니 뿌듯하네요..ㅎㅎ 코드에서 해가없는
도움이 되셨다니 뿌듯하네요..ㅎㅎ
코드에서 해가없는 경우 무한루프에 빠지는 조건이 빠졌네요.
적당한 위치에, len(result) == len(data) 이면 해없음을 추가해야겠네요..
아! 필요없군요..ㅠ.ㅠ
아! 필요없군요..ㅠ.ㅠ
감사합니다~
소스코드 잘 보았습니다~
C++에서도 적용할 수 있을거 같습니다.
2진수를 int로 가져오는 부분을 c++에서 적용하려면
길이가 28인 이진수는 처리가 가능할테지만..
길이가 84, 210, 5005 으로 길어지면... int로 가져와서 처리할수는 없고,
문자열로 하나하나 비교를 하면서 처리를 해야할거 같습니다..
근데, 파이썬에서는 무한대의 자료형이 존재한다고 본거같은데...
111111100011100000001110000000000001110000000000000000001110000000000000000000000000
111110011010011000001001100000000001001100000000000000001001100000000000000000000000
111101010101010100000101010000000000101010000000000000000101010000000000000000000000
111100101100101100000010110000000000010110000000000000000010110000000000000000000000
110011111010000011001000001100000001000001100000000000001000001100000000000000000000
101011110101000010100100001010000000100001010000000000000100001010000000000000000000
100111101100100001100010000110000000010000110000000000000010000110000000000000000000
011011011100010010010001001001000000001001001000000000000001001001000000000000000000
010110111100001001010000100101000000000100101000000000000000100101000000000000000000
84bit길이의 이진수를 적용해 보려고 하니까... 안되는데..
v = int( line.strip(), 2 ) 부분을
v = long( line.strip(), 2 ) 으로 바꿔봐도 안되던데...
84bit길이의 이진수를 처리하려면 어느 부분을 수정하면 될까요?
std::bitset 이 가장 적절합니다.
길이를 동적으로 받을 생각이 아니라면 std::bitset으로 충분하고, 동적으로 해야 한다면 boost dynamic_bitset 을...
굳굳~
C++ 에서 std::bitset 이라는것이 있었나보군요!
오늘 정말 많은거 배워갑니다 ㅋㅋ
감사합니다~
data = array.array('L') 를 그냥
data = array.array('L') 를 그냥 data = [] 로하시면 되겠습니다.. ^^;;
python은 잘 몰라서.. ^^;;
좀 간략한 버전입니다.
아까는 python3 이고 지금은 python2.6 입니다.
#!/usr/bin/python import sys int2bstr = lambda n: n>0 and int2bstr(n>>1)+str(n&1) or '' data = [] for line in open( sys.argv[1] ): v = int( line.strip(), 2 ) if v in data: print('duplicated data. exit') sys.exit(1) data.append( v ) result=[] while 1: if reduce( lambda x,y:x|y, data) == 0 : break bitlens = map( lambda n:int2bstr(n).count('1') , data) max_idx = bitlens.index( max( bitlens ) ) max_data = data[max_idx] result.append( max_idx + 1 ) data = map( lambda x: x & ~max_data, data ) print result감사합니다.
data=[]라고 바꾸니까 바로 잘 되네요 ^^
lambda를 잘 모르겠어서 그냥 긴 코드로 사용하였습니다
감사합니다~
n-sat
쩝... 재밌는 글이었는데 벌써 완료가 달렸네요 -_-;;; 그래도 혹시나 도움 될까봐 적습니다 ㅎㅎ
먼저, 이 문제는 np 문제입니다. 이유는 n-sat 문제가 np인 것과 동치입니다.
증명을 하자면 다음과 같습니다. 만약 'i번째 데이터를 선택했는가?' 변수를 x_i라고 합시다. 만약 x_i가 true이면 i번째 데이터는 선택된 것이며 x_i가 false이면 i번째 데이터는 선택하지 않았다고 합시다.(줄은 총 28개가 있으니 i는 1 이상 28 이하겠죠 ㅎ)
데이터는 본글과 같이 주어졌다고 하겠습니다.
이 때, 우리는 j번째 bit이 1이 되기 위한 조건을 x_i에 대한 boolean expression으로 나타낼 수 있습니다.
예를 들어, 본문의 28개의 데이터에서, 1번째 bit를 1로 만들기 위한 x_i의 조합은 다음 식을 만족하는 조합입니다 :
조건 E1 = x_1 OR x_2 OR x_3 OR x_4 OR x_5 OR x_7 OR x_8 OR x_11 OR x_12 OR x_16 OR x_17 OR x_22 OR x_23
만약 E1이 true가 된다면, 1번쨰 bit이 1이 될 수 있습니다.
이와 같이 E2, E3, E4, ..., En을 식을 세울 수 있습니다.
우리가 원하는 것은 모든 bit가 1이 되는 것이니,
E1 & E2 & E3 & ... & E(n-1) & En
가 true가 되도록 x_i를 잘 고르는 것이 목적입니다. 그 다음, x_i가 true인 i에 대해서 i번째 data를 뽑으면 답이 나옵니다.
그러나 위의 경우 변수의 갯수가 3개 이상이므로 n-SAT 문제와 같습니다. 따라서 optimal solution을 구하는 것은 np 문제입니다.
approximated solution으로 greedy algorithm을 제시하셧는뎅.. greedy algorithm을 처음부터 쓰는 방법은 근사해를 구할 수 없다고 생각합니다-_-; 이유는 상한값이 없기 때문입니다..
개인적으로 추천하는 방법은 Minimum vertex cover를 사용하는 방법입니다. minimum vertex cover란, "graph에서 어떤 노드 subset N'을 선택했을 때, N'과 인접한 노드들과 N'을 합집합하면 graph의 전체 노드set과 같다. 이 때, sizeof(N')이 최소가 되는 set N'"입니다.
Minimum vertex cover는 일반적인 graph에 대해서는 np이지만, bipartite graph에 대해서는 koenig's algorithm을 이용해 O(n^3)만에 계산이 가능합니다.
음... 대략적으로 방법을 서술만 해보자면 -_-;
bipartite graph를 다음과 같이 정의해 보겠습니다.
node p_i : i번째 data를 나타내는 node
node q_j : j번째 bit를 나타내는 node
그리고 p_i의 전체 집합을 P, 노드 q_j의 전체 집합을 Q라 하겠습니다.
그리고 node p_i와 node q_j에 대해서, i번째 data의 j번째 bit가 1일 때 node p_i와 node q_j가 연결되어 있다고 정의를 합니다.
이 때, 주어진 bipartite graph에 대해 maximum bipartite matching을 계산한 뒤 koenig's algorithm을 구하면 P와 Q를 모두 포함한 node에 대한 minimum vertex cover S = P' 합집합 Q'가 나옵니다.
허나 구하고자 하는 것은 P의 subset이므로..(우리가 선택하는 것은 data이기 때문입니다) 방금 구한 P'와 Q'에서 Q'를 P쪽으로 projection 시켜야 정확한 근사해가 나옵니다. 이 과정은 '그냥' 해도 되고, 더 효율 향상을 위해서는 greedy하게 선택을 해도 됩니다.
시간복잡도는 maximum bipartite matching + koenig's algorithm이니 O(N^3)이며, 근사해의 상한값은 문제를 bipartite graph로 표현했을 떄의 minimum vertex cover 갯수입니다. 얼추 optimal solution의 2배에서 logN 배 정도 범위 안에서 놀 듯 합니다.
혹여나! pogusm님께 근사해를 구하는 것이 매우 중요한 문제가 아닐까 해서 다소 알고리즘을 생각해본 끝에 적어보았습니다 ㅎ
와.. 뭔가 엄청난 이야기인거 같습니다.
와.. 뭔가 굉장히 복잡한 이야기인것 같습니다.
제가 관련분야를 제대로 공부해보지 못해서 정말 생소합니다.
하지만 분명 저에게 중요한 자료가 될거 같습니다.
위의 다른분들의 도움 덕에 해답에 가까워 질 수 있었지만..
결과값이 분명 유효한 값이긴 하지만 "최소조합"은 아니었다는 것을 확인 할 수 있었습니다
$ cat main.py #!/usr/bin/python import array import sys def bitLenCount(int_type): count = 0 while (int_type): count += (int_type & 1) int_type >>= 1 return count data = [] for line in open( sys.argv[1] ): v = int( line.strip(), 2 ) if v in data: print('duplicated data. exit') sys.exit(1) data.append( v ) result=[] while 1: k = 0 for i in data: k = k | i if k == 0: break max_bitlen = 0 for i in data: bitlen = bitLenCount(i) if bitlen > max_bitlen: max_bitlen = bitlen max_data = i result.append( data.index( max_data ) + 1 ) for i, v in enumerate( data ): data[i] = v & ~max_data print(result) $ ./main.py in2.txt [1, 20, 84, 24, 43, 69, 4, 6, 11]84*84 크기의 데이터를 위의 프로그램으로 실행해본 결과 "9조합" 의 결과를 얻을 수 있었는데...
84줄에 대해서 84C8 에 해당하는 경우의수로 훑어보니(무식한방법이지만 혹시나 해서 돌려보았습니다)
"8조합"으로도 가능하다는 사실을 알 수 있었습니다.
8조합으로 이루어진 그해는 수백개 이상이며(중간에 루프를 중단해서..)
그중 예를 들자면 아래와 같습니다.
84줄에 대해서 84c7에 해당하는 경우의 수로 루프를 돌려보니 "7조합"으로도 가능하기도 했습니다.
각 줄마다 [1 = 19개] + [0 = 65개] = 84개 으로 구성되어 있으므로
이를 단순 계산해보면 84/19 = 4.42
즉, 최소 5조합으로도 어쩌면 가능할지도 모르겠습니다.
(하지만 6조합, 5조합의 해를 찾는 루프는 돌려보지 못했습니다 - 추가 : 6조합의 해를 찾기 위한 루프를 돌려보았으나 그 해가 없었습니다. 즉 7조합이 최소조합이었습니다.)
결론:
9조합의 결과를 얻는 알고리즘도 괜찮긴 하지만
보다 나은 방법이 있을 수도 있겠다라는 결론을 얻었습니다.
좋은글 참고로 하여 좀더 공부해봐야겠습니다.
감사합니다.
참고가 되길 바랍니다.
http://kldp.org/node/106607
이 문제는 순열이 아니라 조합이라는 차이가 있기는 합니다.
감사합니다.
n queen 이 뭔지도 모르는지라,
체스의 퀸의 역할부터 시작해서..
하스켈, minisat 까지 검색해서, 실습까지는 해보았습니다.
일단 8x8 체스판에서 겹치지 않게 퀸의 위치를 계산해 낼수 있는 프로그램이 있다는것 자체가 놀랍습니다.
알려주신 링크를 보면
$ runhaskell NQueenCNF.hs > q8.cnf 실행에 따라 생성된 q8.cnf의 내용은 아래와 같습니다.
대충 문법이 이해는 갑니다만....
제가 하려는 것을 cnf으로 작성할수 있는건지는 모르겠습니다 ㅠㅠ
저의 문제를 cnf로 작성해서 minisat으로 해결이 가능한건가요?
NP 완전문제를 하고 계셔서 참고하라는 것 뿐이었는데...
-_-.
imyejin님의 글만으로는 최적값을 찾는데 적합한지는 알 수 없습니다.
적정한 CNF 생성 program을 만드는게 더 어려울 수도 있죠.
공부하는 열정은 부러울 정도네요.
N Queen 을 모르신다는 것을 보면 컴퓨터 과학 혹은 컴퓨터 공학을 전공하신 것 같지는 않네요.
기회가 되신다면 관련 교과서적을 차근차근 공부해보는 것도 좋을 것 같습니다.
추천 서적으로는 제가 읽어본 것 중에 이정도...
http://www.aladin.co.kr/shop/wproduct.aspx?ISBN=8960550809
http://www.aladin.co.kr/shop/wproduct.aspx?ISBN=8945070117
이 문제랑은 상관없습니다.
감사합니다
맨땅에 헤딩하는건 역시 한계가 있는거 같습니다. ㅋㅋ
제대로 알려면 정말 책이라도 봐야할거 같습니다.
아무튼 이래저래 많은걸 배웠습니다.
도움주셔서 감사합니다~
참고용
.
참고용
.
댓글 달기