Programming Intermediate

1. List

완전 탐색
- 브루트 포스 기법이라고도 함
- 모든 경우의 수를 테스트하고 최종 해법을 도출함
- 일반적으로 경우의 수가 상대적으로 작을 때 유용함
- 모든 경우의 수를 생성하고 테스트 하기 때문에 수행 속도는 느리지만, 해답을 못찾을 확률은 적으
- 일단 완전 탐색으로 해답 도출한 후에 성능 개선을 위해 다른 알고리즘으로 확인하는 것이 바람직함

순열
- 서로 다른 것들 중 몇개를 뽑아서 한줄로 나열
- 1,2,3 을 포함하는 모든 순열을 생성하는 함수?
ex) 
def permutations(array, r):
    for i in range(len(array)):
        if r == 1:
            yield [array[i]]
        else:
            for next in permutations(array[:i] + array[i + 1:], r - 1):
                yield [array[i]] + next


result = permutations([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 3)


그리디 알고리즘
- 최적해를 구하는데 사용되는 근시안적인 방법
- 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식
- 하지만 최종적으로는 최적이라고 할 수 없음
- 해답을 찾아내지 못하는 경우도 있음. 유의해서 써야함

1) 현재 상태에서 부분 문제의 최적 해를 구한 뒤, 이를 부분해 집합에 추가
2) 새로운 부분 해 집합이 실행 가능한지를 확인. 문제의 제약 조건을 위반하지 않는지 검사
3) 새로운 부분에 집합이 문제의 해가 되는지 확인. 아니라면 해 선택부터 다시 시작