[Python] 파이썬의 순열과 조합 알고리즘

파이썬 라이브러리 순열과 조합의 경우 파이썬 내부의 라이브러리를 사용하면 직접 구현하는것 보다 훨씬 빠른 속도로 구현할 수 있다. 알고리즘 문제의 경우 빠른 속도를 요구하므로, 순열과 조합의 라이브러리를 꼭 숙지해야 한다. 순열과 조합은 매우 비슷해서 구분이 어렵고 헷갈리기 때문에 차이를 알고 구별할 수 있도록 학습한다. 파이썬에서는 itertools를 사용해서 순열과 조합을 구현할 수있다. from itertools import permutations https://docs.python.org/ko/3/library/itertools.html itertools — Functions creating iterators for efficient looping This module implements a nu..

• format_list_bulleted Algorithm
• · 2023. 9. 17.
• textsms

[알고리즘] 에라토스테네스의 체

에라토스테네스의 체 소수를 찾을 때 가장 적은 시간 복잡도를 소요하는 알고리즘이다. 여러 개의 수가 소수인지 아닌지를 판별하며, N보다 작거나 같은 모든 소수를 찾을 때 사용할 수 있다. 에라토스테네스보다 시간 복잡도가 높은 알고리즘과 비교하여 해당 알고리즘의 이점을 파악한다. 일반적인 소수 찾기 알고리즘 소수의 판별법을 사용한다. 소수란 2보다 큰 자연수 중에서 1과 자기 자신을 제외한 자연수로는 나누어 떨어지지 않는 자연수이다. 6의 경우 1,2,3,5을 약수를 가지므로 소수가 아니고, 7의 경우 1,7만을 약수로 가지므로 소수라고 할 수 있다. 가장 간단한 소수 판별법은 아래와 같으며, 어떤 수의 소수를 찾을 때 시간 복잡도가 O(n)이 된다. # 가장 간단한 소수 판별법 # 모든 수를 나누어서 소..

• format_list_bulleted Algorithm
• · 2023. 5. 17.
• textsms

알고리즘 - 동적 프로그래밍 : Dynamic Programming

Dynamic Programming 큰 문제를 작은 문제로 나누어 푸는 문제를 일컫는 말 분할정복과 유사함 분할 정복과 동적 프로그래밍의 차이는 작은 문제가 중복이 일어나는지의 차이이다. 분할 정복은 큰 문제를 작게 나누어 푸는 방법이며, 동적 프로그래밍은 작은 문제들이 반복되는 것이다. 동적 프로그래밍의 답은 일정하면 바뀌지 않는다. 동적 프로그래밍 방법과 조건 모든 작은 문제들을 한번만 풀어야 한다. 정답을 구한 작은 문제들을 어딘가에 메모하고 큰 문제를 풀 때 작은 문제가 나타나면 앞에서 메모한 결과를 이용해서 큰 문제를 푼다. 동적 프로그래밍의 사용 조건은 아래와 같다. 작은 문제가 반복이 일어나는 경우 문제가 구할 때마다 정답이 같은 경우 Memoization 메모제이션은 동적 프로그래밍에서 작..

• format_list_bulleted Algorithm
• · 2023. 5. 11.
• textsms

[알고리즘] 그래프 - 위상 정렬(Topology Sort)

위상 정렬 알고리즘 (Topology Sort) 위상 정렬이란 사이클이 없는 방향 그래프의 모든 노드를 방향성에 거스리지 않도록 순서대로 나열하는 것이다. ex> 선수 과목을 고려한 학습 순서 결정 (우선순위) 선수 과목구조란 여러 수강 과목이 존재하는 경우 "c언어 과목을 들어야 알고리즘 강의를 수강할 수 있다" 라는 규칙을 지켜서 수강 신청을 하는 것을 말한다. 즉 어떤 그래프를 위상 정렬하면 그 결과로 정점들을 원소로 가지는 위상적 순서대로 정렬된 배열이 된다. 진입 차수 : 특정 노드로 들어오는 간선의 수 진출 차수 : 특정 노드에서 나가는 간선의 수 큐를 이용한 위상 정렬 알고리즘 파이썬을 통해서 위상정렬을 구현할 경우 큐를 활용한다. 위상 정렬 알고리즘의 규칙은 아래와 같다. 1. 모든 정점을..

• format_list_bulleted Algorithm
• · 2023. 5. 10.
• textsms

[알고리즘] Union-Find (합 집합 찾기) 알고리즘 이해

[Union-Find 알고리즘 이해 (합 집합 찾기)] - 원소들의 연결 여부를 확인하며, 부모가 더 작은 원소를 부모로 삼도록 함 - 대표적인 그래프 알고리즘으로 합집합 찾기라는 의미를 가짐 - 여러 노드가 존재할 때, 두 개의 노드를 선택해서 현재 노드가 서로 같은 그래프에 속하는지 판별 [Union-Find 알고리즘 방식 ] 서로 원소들을 연결할 때 같은 값을 가리키도록 하며, 처음에는 아무런 원소도 연결되어 있지 않으므로 모든 값이 자기 자신을 가리키도록 한다. P는 Parent(부모 노드)를 뜻하며 원소가 어떤 부모를 가리키는지 나타낸다. P[i] = i 로 나타낼 수 있으며 이 방식으로 같은 부모 노드를 가진 원소들의 집합도 얻을 수 있다. [1- 4 노드를 합칠 경우 ] 1과 4의 부모 노드..

• format_list_bulleted Algorithm
• · 2022. 12. 15.
• textsms

[알고리즘] 백 트래킹 기법 이해하기

[백 트래킹 기법 이해 (BackTracking)] - 백트래킹 혹은 퇴각 검색으로 부르며, 제약 조건 만족 문제에서 해를 찾기 위한 전략이다. * 제약조건 만족 : 해를 찾기 위해 후보군에 제약 조건을 점진적 체크, 해당 후보군이 제약 조건을 만족할 수없다고 판단되면 즉시 backtrack으로 넘어가서 이 후보군을 탐색 후보군에서 완전 제외 시킴* 즉 가능성이 없는 후보군을 삭제한 후, 해당 후보군을 다시는 체크하지 않으며, 이를 통해 최적의 해를 찾는 방법이다. 행렬에서 각 행이 0,1,2,3... 과 같이 점진적 증가인 경우를 카운트해서 반환한다면,그 행의 맨 뒤까지 탐색할 때 점진적인 증가가 발생되지 않은 시점에서 해당 후보군을 제외시키고, 다른 탐색 후보군을 탐색하는 방법 또 퇴각 검색 기법 중..

• format_list_bulleted Algorithm
• · 2022. 12. 6.
• textsms