알고리즘-Concept
1.[알고리즘] 선택 정렬(Selection Sort)
정렬 알고리즘은 2가지 방법으로 나뉘어진다.단순하지만 비효율적인 방법 : 선택 정렬, 삽입 정렬, 버블 정렬복잡하지만 조금 더 효율적인 방법 : 퀵 정렬, 힙 정렬, 합병 정렬, 기수 정렬해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 어떤 원소를 넣을지 선택하는
2.[알고리즘] 거품 정렬 (Bubble Sort)
정렬 알고리즘은 아래와 같이 2가지로 나뉜다.단순하지만 비효율적인 방법 : 선택 정렬, 삽입 정렬, 버블 정렬복잡하지만 조금 더 효율적인 방법 : 퀵 정렬, 힙 정렬, 합병 정렬, 기수 정렬그 중 버블 정렬을 다뤄보자.서로 인접한 두 원소를 검사하여 정렬하는 알고리즘인
3.[알고리즘] 병합 정렬 (Merge Sort)
정렬 알고리즘은 아래와 같이 2가지로 나뉜다.단순하지만 비효율적인 방법 : 선택 정렬, 삽입 정렬, 버블 정렬복잡하지만 조금 더 효율적인 방법 : 퀵 정렬, 힙 정렬, 합병 정렬, 기수 정렬그 중 병합 정렬을 다뤄보자.합병 정렬. 분할 정복 방법을 통해 구현한다.빠른
4.[알고리즘] 이진트리의 순회
이진트리의 순회에는 총 3가지가 있다.루트를 서브 트리에 앞서 먼저 방문한다.위의 그림에서 보면 전위 순회 라면 방문 순서는6, 3, 1, 5, 9, 7, 11이 된다.루트를 왼쪽과 오른쪽 서브 트리 중간에 방문한다.위의 그림에서 보면 중위 순회 라면 방문 순서는1,
5.[알고리즘] 퀵 정렬 (Quick Sort)
퀵 정렬 !? 분할 정복 방법을 통해 주어진 배열을 정렬한다. 분할 정보 : 문제를 작은 2개의 문제로 분리하고 각각을 해결 한 다음, 결과를 모아서 원래의 문제를 해결하는 전략 불안정 정렬에 속하며, 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬이다. 불안정
6.[알고리즘] 힙 정렬 (Heap Sort)
완전 이진 트리를 기본으로 한느 힙 자료구조를 기반으로 한 정렬 방식.불안정 정렬완전 이진 트리삽입할 때, 왼쪽부터 차례대로 추가하는 이진 트리평균 : O(NlogN)최선 : O(NlogN)최악 : O(NlogN)최대 힙을 구성한다.현재 힙 루트는 가장 큰 값이 존재한
7.[알고리즘] 삽입 정렬 (Insertion Sort)
손 안의 카드를 정렬하는 방법과 같다.새로운 카드를 기존의 정렬된 카드 사이에 올바른 위치게 끼워 넣는다.2번째 원소부터 시작해서 그 앞(원소)와 비교하며 삽입할 위치를 찾고, 원소를 뒤로 옮기고 지정된 자리에 자료를 삽입하여 정렬하는 알고리즘이다.최선의 경우, O(N
8.[알고리즘] 각 정렬 알고리즘 비교 📝
비교 표 출처 : \[Algorithm] 각 정렬의 특징 및 장단점 & 시간복잡도비교 표 출처 : \[Algorithm] 각 정렬의 특징 및 장단점 & 시간복잡도" 인접 값끼리 비교하며 정렬. i를 length-i-1까지 올리는 정렬 "구현이 쉽다. 인접값만 비교하기에
9.[알고리즘] 플로이드 와샬 (Floyd-Warshall) 알고리즘
플로이드 와샬은 모든 정점에서 모든 정점으로의 최단 거리를 구하는 알고리즘 이다.다익스트라(Dijkstra) 알고리즘은 어떠한 정점을 기준으로 잡고 다른 모든 정점으로의 최단 거리를 구하는 알고리즘이다.다익스트라는 가장 적은 비용을 가지는 간선을 하나씩 선택하여 알고리
10.[알고리즘] DFS(깊이우선탐색), BFS(너비우선탐색)
정점(node)과 그 정점을 연결하는 간선(edge)로 이루어진 자료구조의 일종그래프를 탐색한다는 것은 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것아주 간단한게만 말하자면, 그래프 중에서 방향성이 있는 비순환 그래프루트 노드에서 시작해서 다
11.[알고리즘] 최소 신장 트리(MST)
Spanning Tree = 신장 트리 = 스패닝 트리Spanning Tree는 그래프의 최소 연결 부분 그래프이다.최소 연결 = 간선의 수가 가장 적다.n개의 정점을 가지는 그래프의 최소 간선의 수는 (n-1)개이고, (n-1)개의 간선으로 연결 되어 있으면 필연적으
12.[알고리즘] 완전 탐색(Brute-force)
컴퓨터의 빠른 계산 능력을 활용하여 가능한 경우의 수를 일일이 나열하면서 답을 찾는 방식무식하게 풀어서 Brute-Force"10개의 정수 원소로 이루어진 수열이 존재한다.이 수열에서 두 원소를 선택해서 구한 합의 최대값을 구하시오"위의 질문에 대한 방법은 결국 모든
13.[알고리즘] 비트마스크(BitMask)
집합의 요소들의 구성 여부를 표현할 때 유용한 테크닉DP, Permutation 등 배열 활용으로만 해결이 불가한 문제작은 메모리와 빠른 수행시간으로 해결 가능(원소가 적다는 가정 하)집합을 배열의 인덱스로 표현 가능코드가 간결해짐컴퓨터에서 사용되는 데이터의 최소 단위
14.[알고리즘] 이진탐색(Binary Search Tree)
우선 코드부터.정렬이 되어 있어야 이진 탐색을 할 수 있다.O(logn)으로 빠르게 탐색이 가능하다.정렬이 되어 있지 않다면 정렬을 하는데 시간이 걸린다.
15.[알고리즘] 투 포인터(Two Pointers)
가장 단순하게는 2중 반복문을 돌리는 것이다. 아주 쉽게 볼수 있는 형태이다.근데 이렇게 하면 시간복잡도가 O(N^2)이 나온다. (2중 반복문이니까)배열의 크기가 커질 수록 느려지게 된다.결국, 1차원 배열의 연속된 구간에 대해 2중 반복문을 개선하기 위해 나온 것이