티스토리 뷰
알고리즘을 공부하기 위해서 종만북을 읽어 내려가며 포스팅을 할 예정입니다.
앞부분에 이론적인 이야기들을 읽고 처음 마주친 내용은 완전탐색에 관한 이야기입니다.
첫번째로 화두로 던진것이 n개중 m개를 뽑는 모든 경우의수를 출력하는 것입니다.
알고리즘에서 모든 경우를 일단 다 탐색해봐야하는 경우가 비일비재한데요 이러한 방법을 딱 틀로 만들어두면 좋다고 생각했습니다.
책에서는 만약 번호매겨진 n개중 4개를 고르는 경우를 어떻게 짤 수 있을까 물음을 던졌습니다.
for(int i = 0; i < n; i++){
for(int j = i+1; j < n; j++){
for(int k = j+1; k < n; k++){
for(int l = k+1; l < n; l++){
cout << i << j << k << l << endl;
}
}
}
}
이러한 방법을 쉽게 생각할 수 있습니다. 하지만 4개를 뽑는 것이 아니라 5개를 뽑는다면 ? 6개를 뽑는다면 ? 코드의 양이 점점 증가 할 수 밖에 없겠죠.
그래서 해답으로 제시한것은 재귀함수를 이용하는 것입니다. 코드의 각 부분은 남은 묶음에서 하나를 고르는 일을 하는 것입니다. i j k l 각각 원소 하나를 선택하는 것입니다. 이것을 함수 하나로 만들고 자기 자신을 호출하면서 이뤄집니다.
#include <iostream>
#include <vector>
using namespace std;
void pick(int n, vector<int> &picked, int topick) {
if(topick == 0) {
for (int i = 0; i < picked.size(); ++i) {
cout << picked[i] << " ";
}
cout << endl;
return;
}
int smallest = picked.empty() ? 0 : picked.back() + 1;
for (int j = smallest; j < n; ++j) {
picked.push_back(j);
pick(n, picked, topick-1);
picked.pop_back();
}
}
int main() {
vector<int> a;
pick(5, a, 3);
}
만약 n까지의 자연수에서 고르는 것이 아니라 arr[10] = {10, 20, 30, 40, 50, 60, 70, 80, 90, 100} 으로 되어있다면 arr의 길이를 먼저 구한 후 pick함수로 뽑은 숫자들이 인덱스가 되면 될것입니다.
하지만 저 코드도 나에겐 복잡해 보인다..
파이썬의 외장함수를 이용하면 쉽게 할수있다 c++도 있는걸로 압니다만
from itertools import combinations
if __name__ == "__main__":
arr = [10, 20, 30, 40]
print(list(combinations(arr, 3)))
#[(10, 20, 30), (10, 20, 40), (10, 30, 40), (20, 30, 40)]
간단하게 arr배열에 대해서 3개를 선택하는 모든 경우를 출력해줍니다.
여기서 아~ 잘되는구나 하고 넘어갈게 아니라 한번 어떻게 구현이 되어있나 documentation를 찾아봤습니다.
def combinations(iterable, r):
# combinations('ABCD', 2) --> AB AC AD BC BD CD
# combinations(range(4), 3) --> 012 013 023 123
pool = tuple(iterable)
n = len(pool)
if r > n:
return
indices = list(range(r))
yield tuple(pool[i] for i in indices)
while True:
for i in reversed(range(r)):
if indices[i] != i + n - r:
break
else:
return
indices[i] += 1
for j in range(i+1, r):
indices[j] = indices[j-1] + 1
yield tuple(pool[i] for i in indices)
자... 파이썬 어렵네요 ㅋㅋㅋ 일단 yield라는 키워드가 무엇인지 몰라 검색을 해봤습니다.
Python의 yield 키워드 알아보기
이 글은 Stackoverflow "What does the yield keyword do in Python? (Python에서 yield 키워드는 무엇을 하나요?)"의 번역문입니다. 예재를 포함한 원문은 링크에서 확인해보실 수 있습니다. Python의 yield 키워드 알아
tech.ssut.me
알아야하는것이 yield -> generator > iterables 로 깊이가 깊어지네요
거꾸로 알아가보겠습니다. 먼저 iterable 많이 들어본 단어일 수 있습니다. 말그대로 순환할 수 있는 변수를 말하는 데요
- 대표적으로 iterable한 타입 - list, dict, set, str, bytes, tuple, range
그다음 제너레이터가 조금 어렵습니다. 저는 이곳을 읽고 이해했습니다.
제가 읽은 바를 정리하자면 핵심은 generator입니다. generator는 iterator를 생성하는 함수입니다. 하는일은 iterator와 비슷합니다. 하지만 한가지 다른점은 yield라는 키워드가 있는데요 이것은 어떻게 보면 return과 같습니다.
generator는 한마디로 상태가 있는 함수 입니다. 기본함수는 자기가 하는 일을 다 마치고 return을 하면 모든 메모리가 초기화 됩니다. 하지만 generator는 모든 메모리가 초기화 되는 것이 아니라 자기가 어디서 멈춰있는지 상태를 갖고있습니다. 그 지점이 yeild 입니다. yeild에서 값을 반환 하고 대기하고 있습니다.
함수가 불릴때마다 계산해서 값을 던져주는 방식입니다. 그렇다면 왜 이렇게 복잡하게 한단계 꼬아서 진행하냐 하시면 핵심은 메모리입니다. 모든 리스트를 다 저장하는것이 아니라 필요할때마다 계산해서 던져주기 때문에 메모리를 상당히 효율적으로 사용할 수 있습니다.
from itertools import combinations
if __name__ == "__main__":
arr = [10, 20, 30, 40]
print(combinations(arr,3))
print(list(combinations(arr, 3)))
#<itertools.combinations object at 0x00800CF8>
# [(10, 20, 30), (10, 20, 40), (10, 30, 40), (20, 30, 40)]
그렇다면 위에서 봤던 코드에서 왜 list로 변환을 해줬는지 이해가 됩니다 ~ combination함수는 generator로써 매번 불러줘야 값을 하나씩 내뱉는 놈이였던 것이죠 이것을 한번에 보고 싶어서 list로 감싸준것입니다. 하지만 이러면 generator의 의미가 사라지긴 합니다. 따라서 올바른 사용 방법은
from itertools import combinations
if __name__ == "__main__":
arr = [10, 20, 30, 40]
combi = combinations(arr, 3)
for val in combi:
print(val)
#(10, 20, 30)
#(10, 20, 40)
#(10, 30, 40)
#(20, 30, 40)이것입니다. !
한가지 문제점은 generator는 한번 사용하면 없어진 다는 것입니다.
from itertools import combinations
if __name__ == "__main__":
arr = [10, 20, 30, 40]
combi = combinations(arr, 3)
print(next(combi))
print("==========")
for val in combi:
print(val)
print("==========")
print(next(combi))
"""
(10, 20, 30)
==========
(10, 20, 40)
(10, 30, 40)
(20, 30, 40)
==========
Traceback (most recent call last):
File "C:/Users/chea1/workspace/boj/pick/main.py", line 11, in <module>
print(next(combi))
StopIteration
"""stopiteration 에러를 발생합니다.
이제 조금 원리를 알았으니 다시 combination 함수로 돌아가겠습니다.
def combinations(iterable, r):
# combinations('ABCD', 2) --> AB AC AD BC BD CD
# combinations(range(4), 3) --> 012 013 023 123
pool = tuple(iterable)
n = len(pool)
if r > n:
return
indices = list(range(r))
yield tuple(pool[i] for i in indices)
while True:
for i in reversed(range(r)):
if indices[i] != i + n - r:
break
else:
return
indices[i] += 1
for j in range(i+1, r):
indices[j] = indices[j-1] + 1
yield tuple(pool[i] for i in indices)
조금씩 잘라서 확인해보겠습니다.
def combinations(iterable, r):
# combinations('ABCD', 2) --> AB AC AD BC BD CD
# combinations(range(4), 3) --> 012 013 023 123
pool = tuple(iterable) # (10, 20, 30, 40)
n = len(pool) # 4
if r > n:
return
indices = list(range(r)) # [1, 2, 3]
yield tuple(pool[i] for i in indices) # (10, 20, 30)
처음엔 iterable에 들어있는 가장 앞에서 부터 (10,20,30) 반환을 하고 멈춥니다. 그 후에 while문에 진입합니다.
indices = [0, 1, 2] 입니다.
while True:
for i in reversed(range(r)):
if indices[i] != i + n - r:
break
else:
return
indices[i] += 1
for j in range(i+1, r):
indices[j] = indices[j-1] + 1
yield tuple(pool[i] for i in indices)그 다음이 어렵습니다. 또 처음 보는 문법이 있네요.. ㅋㅋㅋ else 가 for과 붙어있습니다. 처음엔 오탄가 싶기도 한데 맞습니다 for else입니다. for 다음에 else부분은 break가 되지 않는 다면 실행되는 부분입니다.
indices 끝자리부터 더 뒤로 갈수면 가는 형식입니다. 뒤로간다음 그 다음애들도 +1 해주는 식으로 나아갑니다.
처음 indices = [0,1,2] for문에서 2,1,0 순으로 i가 들어오게 됩니다. 끝에자리부터 n - r 은 전체에서 몇개가 남냐 이것이고 여기서는 4개중에 3개를 뽑는것이기 때문에 1입니다. 그러므로 우변은 3 좌변은 2 이므로 더 갈 수 있으므로 break하고 넘어갑니다.
그다음 indices = [0,1,3] 이므로 3은 이미 최대 이고 1을 비교하게됩니다. 2까지 갈 수 있으므로 올라갑니다 ~ 그다음은 0이 1까지 가고 그런식으로 올라가면서 더이상 올라가지못하면 return으로 종료하게됩니다.
'Programming > Python' 카테고리의 다른 글
| 파이써닉(pythonic)을 위한 5가지 팁! (0) | 2020.06.17 |
|---|