전체 글152 순열과 조합(Permutation & Combination) 목차 순열(Permutation) 순열은 서로 다른 n개의 원소에서 r개를 중복 없이 순서에 상관있게 선택하는 것입니다. 수식은 다음과 같습니다. (팩토리얼로 표현) 기본적으로 위의 수식이 조금 더 이해하기가 쉽습니다. n장중에서 r장을 선택하면 처음 뽑을때는 n개중 선택, 두 번째로 뽑을 때는 (n-1) 개 중 선택, ... , 마지막으로 (n-(r-1))개 중 선택이므로 경우의 수는 위와 같은 수식이 나오게 됩니다. 조합(Combination) 조합은 서로 다른 n개의 원소에서 r개를 순서에 상관없이 선택하는 것입니다. 수식은 다음과 같습니다. 순열에서 r!를 나눠주는 이유는 조합은 순서를 고려하지 않기 때문입니다. 하나의 조합에 대해서 총 r! 만큼 표현이 가능하게 됩니다. 따라서 순열에서 r! 를.. 2023. 10. 11. 탐욕법(Greedy) 목차 탐욕법(Greedy) 탐욕법 또는 그리디 알고리즘은 문제 해결의 각 단계에서 그 순간에 최적이라고 생각되는 선택을 하는 방법입니다. 하지만 그리디 알고리즘으로 최적의 해를 구할 수 있는 문제는 많지 않습니다. 그 이유는 항상 눈앞의 가장 큰 이익만을 쫓기 때문입니다. 따라서 그리디 알고리즘을 적용할 때는 잘못된 방향으로 가고 있지 않는지 꼼꼼히 확인이 필요합니다. 문제의 성질이 동일하게 보존되고, 같은 전략을 반복적으로 취할 수 있을 때만 그리디 알고리즘을 적용할 수 있습니다. 그리디 알고리즘의 대표적인 문제인 동전 문제를 예시로 들어보겠습니다. 그와 동시에 그리디 알고리즘의 한계도 살펴보겠습니다. 동전 문제 : 10원, 50원, 100원, 500원짜리 동전들을 사용해서 어떤 금액을 표현하려고 할 .. 2023. 10. 10. 큐(Queue), 스택(Stack) 목차 큐(Queue) 큐(queue)는 먼저 집어 넣은 데이터가 먼저 나오는 FIFO(First In First Out)구조로 저장하는 형식입니다 출처 : 위키피디아 줄 서기 개념을 생각하면 됩니다. (먼저 줄 선 사람이 먼저 나가게 됩니다.) 파이썬에서는 deque를 이용하면 쉽게 구현이 가능합니다. from collections import deque q = deque() for i in range(5): q.append(i) while q: print(q.popleft()) """ 0 1 2 3 4 """ 스택(Stack) 스택(stack)은 한쪽 끝에서만 자료를 넣거나 뺄 수 있는 LIFO(Last In First Out)으로 되어 있습니다. 출처 : 위키피디아 책 쌓기 개념을 생각하면 됩니다. .. 2023. 10. 10. 완전 탐색(Brute-force) 목차 완전 탐색(Brute-force) 완전 탐색 또는 브루트포스(Brute-force)는 문제의 모든 가능한 경우를 직접 탐색하여 해결하는 방법을 의미합니다. 문제를 해결할 때, 먼저 문제에서 주어진 범위를 토대로 시간복잡도를 계산합니다. 그 후, 해당 시간복잡도가 문제에서 제시한 제한시간을 초과하지 않는지 확인합니다. 파이썬에서는 대략적으로 1초에 2000만 번의 연산을 처리할 수 있다고 가정하며, 이를 기준으로 완전 탐색을 사용할지의 여부를 결정합니다. 완전 탐색으로 풀 수 있는 문제임에도 불구하고 문제를 보고 어떤 알고리즘들을 적용할 수 있을까 생각하다가 막히는 경우가 있을 수 있습니다. 그래서 저 같은 경우는 문제를 읽고 먼저 완전 탐색을 생각해 보고 시간을 줄일 수 있는 부분들을 찾아가는 방식.. 2023. 10. 10. 이전 1 ··· 33 34 35 36 37 38 다음
