Data Structure & Algorithm
1.[Python] 완전 탐색 알고리즘 - 순열
순열(Permutations) 개념 n개 중에서 r개를 뽑아서 나열하는 경우의 수 서로 다른 n개의 원소를 가지고 중복 없이 순서에 상관없이 r개의 원소를 선택하는 것
2.[Python] 완전 탐색 알고리즘 - 조합
조합(Combinations) 개념 n개 중에서 순서에 상관없이 r개를 뽑는 경우의 수 서로 다른 n개의 원소를 가지고 중복 없이 순서에 상관있게 r개의 원소를 선택 혹은 나열 하는 것
3.[Python] 완전 탐색 알고리즘 - 중복 순열, 중복 조합
중복 순열() : 서로 다른 n개에서 중복이 가능하게 r개를 뽑아서 정렬하는 경우의 수 중복 조합() : 서로 다른 n개에서 순서 없이, 중복이 가능하게 r개를 뽑는 경우의 수
4.[Python] 동적 계획법 (DP)
하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용한다.주어진 문제를 여러 개의 소문제로 분할하여 각 소문제의 해결안을 바탕으로 주어진 문제를 해결, 이때 각 소문제는 다시 또 여러 개의 소문제로 분할 가능하다. 각 소
5.[Python] 백트래킹(Backtracking)
= 퇴각 검색해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾아가는 기법최적화 문제와 결정 문제를 푸는 방법DFS: 가능한 모든 경로(후보)를 탐색한다.: 따라서, 불필요할 것 같은 경로를 사전에 차단하거나 하는 등의 행동이 없으므로 경우의 수를 줄이지
6.[Python] 완전 탐색,브루트 포스(Brute Force)
브루트(Brute) : 무식한 + 포스(Force) : 힘: 발생할 수 있는 모든 경우를 무식하게 탐색: 가능한 모든경우의 수를 모두 탐색하면서 요구 조건에 충족되는 결과만을 가져온다.: 예외 없이 100%의 확률로 정답만을 출력한다.= 알고리즘 설계의 가장 기본적인
7.[Python] 해시 (Hash)
데이터를 빠르게 넣거나 가져올 때 사용하는 기법최솟값/최댓값을 찾을 때 (전체 자료를 모두 검색하는 경우) 효율이 떨어짐파이썬의 딕셔너리가 해시 테이블로 구현되어 있음리스트를 쓸 수 없을 때 사용 = 인덱스 값을 숫자가 아닌 다른 값 '문자열, 튜플'을 사용할 때 딕셔
8.[Python] 깊이/너비 우선 탐색 알고리즘 (DFS/BFS)
: "수직 방향"으로 원하는 노드를 탐색하는 알고리즘루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방식1\. 모든 노드를 방문하고자 하는 경우에 이 방법을 선택함2\. 깊이 우선 탐색(DFS)이 너비 우선 탐색
9.[Python] 이진/이분 탐색(Binary Search)
오름차순으로 정렬된 배열에서 찾고자 하는 수(target)를 두 부분으로 나눠서 찾는 알고리즘 기법순차 탐색(Linear Search)보다 더 빠른 성능을 보인다.탐색 리스트가 정렬되어 있지 않으면 정렬left(리스트 첫번째), right(리스트 마지막), mid(리스
10.[Python] 트리 동형 (Tree Isomorphism)
두 트리는 간선의 방향만 잘 조절해주면 완전히 동일한 트리가 된다.즉, 두 트리는 Isomorphic 한다.예시를 보자!두 트리는 2와 3, NULL과 6, 7, 8과 같은 하위 트리가 뒤집힌 동형이다.두 트리를 동시에 탐색한다.순회 중인 두 트리의 현재 내부 노드를
11.[Python] 강한 연결 요소 (Strongly Connected Component)
노드들이 서로 자유롭게 이동 가능한 모음집이다.하나의 그래프에서 여러 개의 SCC가 존재할 수 있고, 같은 SCC 내에서는 어느 두 노드를 선택하더라도 한 노드에서 다른 한 노드로 이동이 가능해야 한다.그림에서의 그래프에는 3개의 SCC가 존재한다.a, b가 같은 SC
12.[Python] 유니온 파인드 (Union Find)
그래프 알고리즘, 두 노드가 같은 그래프에 속하는지 판별하는 알고리즘서로소 집합, 상호 베타적 집합(Disjoint-Set = 서로 공통 원소가 없는 집합)으로도 불린다.노드를 합치는 Union 연산과 노드의 루트 노드를 찾는 Find 연산으로 이루어진다.=> 즉, 노
13.[Python] 최소 신장 트리 (MST, Minimum Spanning Tree)
그래프 내의 모든 정점을 포함하는 트리= 신장 트리: 최소 연결 부분 그래프최소 연결 = 간선 수가 가장 적다.n개의 정점을 가지는 그래프의 최소 간선의 수는 (n-1)개이고, (n-1)개의 간선으로 연결되어 있으면 필연적으로 트리 형태가 되고 이것이 Spanning
14.[Python] 플로이드 와샬 (Floyd Warshall)
플로이드 와샬 알고리즘은 모든 노드에서 모든 노드로의 최단 경로를 구하는 알고리즘이다. 거쳐가는 노드를 기준으로 알고리즘을 수행한다는 특징이 있다.다이나믹 프로그래밍 기법을 사용한 알고리즘이고, 인접 행렬을 이용하여 각 노드 간 최소의 비용을 계산한다.다익스트라 알고리
15.[Python] 힙 (Heap)
: 최댓값과 최솟값을 빠르게 찾기 위해 고안된 자료구조각 노드의 key값이 해당 노드의 자식노드의 key값보다 작지 않거나 크지 않은 완전 이진트리키 값의 대소관계는 부모-자식 노드 사이 간에만 성립하며 형제 노드 사이에는 영향을 미치지 않음자식노드의 최대 개수는 힙의
16.코딩 테스트 관련
시간 복잡도 분석은 문제 풀이의 핵심이다.문제를 해석하기 전에 조건을 먼저 본다.문제의 조건부터 확인하면 문제를 풀기 위해 얼마나 효율적인 알고리즘을 눈치챌 수 있기 때문이다.예를 들면, 데이터의 개수 N이 1,000만 개를 넘어가며 시간 제한이 1초라면, 대략 최악의
17.비트마스크
비트마스크를 이용한 집합 구현은 가장 대표적이고, 중요한 사례이다. "하나의 bit가 하나의 원소"를 의미하게 된다. bit가 켜져 있으면 해당 원소가 집합에 포함되어 있다는 의미이고, 꺼져 있으면 포함되어 있지 않다는 의미이다. 따라서 N비트 정수 변수라면 N개의 원