본문 바로가기

⏳ 알고리즘/python 알고리즘 개념

 (21)
순열과 조합 목차 순열 중복순열 조합 중복 조합 순열 # permutations 이용 from itertools import permutations items = ['A', 'B', 'C'] for i in range(1, len(items)): print(list(permutations(items))) print('--------------------------------') for i in range(1, len(items)): print(list(permutations(items, 2))) #2개의 원소를 가지고 순열을 만듦 출력 〉 [('A', 'B', 'C'), ('A', 'C', 'B'), ('B', 'A', 'C'), ('B', 'C', 'A'), ('C', 'A', 'B'), ('C', 'B', 'A'..
런너(runner) 기법이란?? 런너(Runner) 기법 런너 기법이란 연결 리스트 순회 시 2개의 포인터를 동시에 사용하는 기법이다. 한 포인터가 다른 포인터보다 앞서게 하여 병합 지점이나 중간 위치, 길이 등을 판별할 때 유용하게 사용할 수 있다. fast runner와 slow runner 간의 step을 2배 차이를 두는 식으로 (ex. fast, slow = 2,1) 지정한 후 fast runner가 리스트의 끝지점에 도착하면 slow는 정확히 리스트의 중간 지점에 도달하게 된다. 런너 기법을 사용하는 문제 leetcode.com/problems/palindrome-linked-list/submissions/ Palindrome Linked List - LeetCode Level up your coding skills and ..
탐욕 알고리즘(Greedy) 목차 탐욕 알고리즘(Greedy) 탐욕 알고리즘(Greedy) 예시 1. 탐욕 알고리즘(Greedy) 탐욕 알고리즘은 지역적으로 최적인 선택을 계속 이어나가서 전역적 해답을 얻는 방식의 알고리즘이다. 순간마다 하는 선택은 그 순간에 대해 지역적으로는 최적이지만, 그 선택들을 계속 수집하여 최종적(전역적)인 해답을 만들었다고 해서, 그것이 최적이라는 보장은 없다. 위와 같은 그래프의 S 에서 E 까지 도달할 수 있는 방법 중 가중치 합이 가장 낮은 방법을 찾는데에 탐욕 알고리즘을 쓴다면 S -> A -> B -> D -> E 의 경로를 선택하게 될 것이다. S 에서 A 로 가는 것이 이 후의 선택에서 어떤 영향을 미치게 될지는 고려하지 않고 그냥 단순히 그때 그때의 상황에서 가장 가중치가 낮은 길로만 진행..
그래프·트리 순회(깊이우선탐색, 너비우선탐색) 책 을 기본으로 배운 알고리즘 내용입니다 목차 깊이 우선 탐색(DFT, Depth First Search) DFS의 순회 너비 우선 탐색(BFS, Breadth First Search) BFS의 순회 순회 알고리즘은 그래프·트리에 저장된 모든 값을 중복이나 빠짐없이 살펴보고 싶을 때 사용한다. 순회 방법 중 깊이 우선 탐색(DFT, Depth First Search)으로는 전위 순회(Pre-order traversal), 정위 순회(In-order traversal), 후위 순회(Post-order traversal)가 있으며, 너비 우선 탐색(Breadth First Search)으로는 레벨 순회가 있다. 깊이 우선 탐색(DFT, Depth First Search) 진행 가능한 노드가 없을 때까지 깊게..
트리(3) - 자가 균형 이진 탐색 트리 책 을 기본으로 배운 알고리즘 내용입니다 목차 자가 균형 이진 탐색 트리의 종류 1. AVL 1-1) AVL의 회전(LL, LR, RR, RL) 1-2) AVL의 삽입 구현 1-3) AVL의 구현 2. 레드-블랙 트리 3. 이진 힙 자가 균형 이진 탐색 트리 트리에서 노드의 삽이과 삭제가 이루어질 때 자동으로 균형 트리를 유지하는 이진 탐색 트리 균형 트리 : 모든 하위 트리의 높이 차가 1이하인 트리 균형도 : 왼쪽 서브 트리의 높이 - 오른쪽 서브 트리의 높이 균형 조정 방법으로는 ① 노드 분할 및 병합 : 노드의 자식은 2개 이하이다. 노드가 많으면 두 개의 서브 노드로 나뉜다. ② 노드 회전 : 간선을 회전한다. x가 y의 부모이면, y를 x의 부모로 만들고, x는 y의 자식 중 하나늘 거둔다. ..
트리(2) - 이진탐색트리 책 을 기본으로 배운 알고리즘 내용입니다 목차 이진 탐색 트리 구축, 탐색 과정을 그림으로 이해 이진 탐색 트리 구현 이진 탐색 트리(BST, Binary search tree) 이진탐색(binary search)과 연결리스트(linked list)를 결합한 트리 이진탐색의 효율적인 탐색 능력을 유지하면서도, 빈번한 자료 입력과 삭제를 가능하게끔 고안됨. - 이진탐색의 경우 탐색에 소요되는 계산복잡성은 O(logn)으로 빠르지만 자료 입력, 삭제가 불가능하다. - 연결리스트의 경우 자료 입력, 삭제에 필요한 계산복잡성은 O(1)로 효율적이지만 탐색하는 데에는 O(n)이다. 이진 탐색 트리의 속성 각 노드의 왼쪽 서브트리에는 해당 노드의 값보다 작은 값을 지닌 노드만 존재한다. 각 노드의 오른쪽 서브트리에..
트리(1) - 이진트리 책 을 기본으로 배운 알고리즘 내용입니다 목차 이진 트리의 종류(완전 이진 트리,포화 이진 트리) 이진 트리 구현 1) 개념 계층적인 구조를 표현 트리는 노드(node)들과 노드들을 연결하는 링크(link)들로 구성됨 2) 용어 더보기 루트 노드(root node) : 부모가 없는 노드. 트리는 하나의 루트 노드만을 가진다. 단말 노드(leaf node) : 자식이 없는 노드 내부(internal) 노드 : 리프 노드가 아닌 노드 노드 크기(size) : 자신을 포함한 모든 자손 노드의 개수 노드 깊이(depth) : 루트에서 어떤 노드로 가는 경로의 길이 노드 레벨(level) : 노드 깊이(depth) + 1 노드 차수(degree) : 각 노드가 지닌 가지의 수 트리 차수(degree of tree..
그래프 책 을 기본으로 배운 알고리즘 내용입니다 목차 1. 그래프(Graph) 2. 그래프(Graph)의 특징 3. 그래프(Graph) 관련 용어 4. 그래프(Graph)의 종류 5. 그래프와 트리의 차이 6. 그래프(Graph)의 구현 2가지 1. 그래프(Graph) 그래프(Graph)는 일련의 노드(node, 정점) 집합 V와 간선(arc, 아크) 집합 E로 구성된다. 일반적으로 노드엔 데이터, 간선엔 노드와 노드 사이의 관계 정보가 포함되어 있다. 2. 그래프(Graph)의 특징 그래프는 네트워크 모델 이다. 2개 이상의 경로가 가능하다. 즉, 노드들 사이에 무방향/방향에서 양방향 경로를 가질 수 있다. self-loop 뿐 아니라 loop/circuit 모두 가능하다. 루트 노드라는 개념이 없다. 부모-..
동적 계획법(Dynamic Programming) 책 을 기본으로 배운 알고리즘 내용입니다 목차 동적 계획법(Dynamic Programming) 메모이제이션(memoization) 메모이제이션을 활용한 피보나치 수열 동적 계획법(Dynamic Programming) 동적 계획법은 복잡한 문제를 재귀를 통해 간단한 하위 문제로 분류하여 단순화하여 해결하는 방법이다. 어떤 문제가 최적 부분 구조, 중복되는 문제를 가지고 있으면 동적 계획법으로 해결 가능하다. 메모이제이션(memoization) 메모이제이션은 동적 계획법의 핵심이다. 프로그램이 동일한 계산을 반복할 때, 이전에 계산한 값을 메모리에 저장하여 동일한 계산의 반복 수행을 제거하는 것. ex) 메모이제이션을 활용한 피보나치 수열 피보나치 수열은 제 0항을 0, 제 1항을 1로 하고, 그 다음 항..
검색 알고리즘(순차 검색, 이진 검색) 책 을 기본으로 배운 알고리즘 내용입니다 목차 정렬되지 않은 배열 - 순차 검색(Linear Search) 정렬된 배열 - 이진 검색(Binary Search) 리스트가 정렬되어 있다고 할 때, 이진 검색(binary search)이 순차 검색(linear search)보다 더 효율적이다. 정렬되지 않은 배열 순차 검색(Linear Search) 순차 검색은 키(key)라는 요소를 가지고 순차적으로 리스트의 각 요소들을 비교하는 검색방법이다. 리스트 요소의 수가 커지면 커질수록 선형 검색 시간이 증가하므로, 큰 리스트에서는 비효율적이다. (시간복잡도 O(1),O(n/2),O(n)) 키(key)가 찾고자 하는 요소와 일치 할 때 까지 수행을 진행하고, 매치되었다면, 순차 검색은 매칭된 요소의 위치(inde..

티스토리툴바