CS_알고리즘
1.[알고리즘] 거품 정렬
버블 정렬 또한 반복문이 이중으로 들어가 있기 때문에 O($$n^2$$)입니다. https://github.com/gyoogle/tech-interview-for-developerhttps://laurent.tistory.com/entry/%EC%9
2.[알고리즘] 선택정렬
배열에 9, 6, 7, 3, 5가 저장되어 있다고 가정하고 자료를 오름차순으로 정렬해 보자.첫 번째 자료 9를 두 번째 자료부터 마지막 자료까지와 비교하여 가장 작은 값을 첫 번째 위치에 옮겨 놓는다. 이 과정에서 자료를 4번 비교한다.두 번째 자료 6을 세 번째 자료
3.[알고리즘] 삽입정렬
배열에 8, 5, 6, 2, 4가 저장되어 있다고 가정하고 자료를 오름차순으로 정렬해 보자. 시간복잡도를 계산한다면최선의 경우비교 횟수이동 없이 1번의 비교만 이루어진다.외부 루프: (n-1)번Best T(n) = O(n)최악의 경우(입력 자료가 역순일 경우)비교 횟수
4.[알고리즘] 퀵정렬
퀵정렬(Quick Sort)은 퀵이라는 이름답게 평균 속도 O(N\*logN)을 자랑하는 매우 빠른 정렬 알고리즘이다.퀵정렬은 분할정복(Divide & Conquer) 알고리즘의 하나로, 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬에 속하는 알고리즘이다.퀵정렬은
5.[알고리즘] 병합정렬이란
‘존 폰 노이만(John von Neumann)’이라는 사람이 제안한 방법일반적인 방법으로 구현했을 때 이 정렬은 안정 정렬 에 속하며, 분할 정복 알고리즘의 하나 이다.분할 정복(divide and conquer) 방법문제를 작은 2개의 문제로 분리하고 각각을 해결한
6.[알고리즘] 힙정렬
힙 정렬은 1964년 J.W.J 윌리엄스에 의해 발명되었고, 같은 해 R.W. 플로이드가 제자리 정렬을 할 수 있는 개선판을 출판하였고 이 방법이 바로 트리정렬 알고리즘을 이용한 방식이다.힙 자료구조를 안다고 가정하고 과정을 설명하겠습니다.1️⃣ n개의 노드에 대한 완
7.[알고리즘] 기수 정렬
기수정렬은 낮은 자리수부터 비교하여 정렬해 간다는 것을 기본 개념으로 하는 정렬 알고리즘입니다. 기수정렬은 비교 연산을 하지 않으며 정렬 속도가 빠르지만 데이터 전체 크기에 기수 테이블의 크기만한 메모리가 더 필요합니다.1\. 0~9 까지의 Bucket(Queue 자
8.[알고리즘] 계수정렬
정렬하고자 하는 배열의 최댓값을 구한다최댓값 크기의 배열에 각 원소를 순회하며 해당 값이 몇 개 인지 저장한다저장된 데이터를 순서대로 출력한다이제 예시를 한번 살펴보도록 하겠다.EX) 1, 3, 2, 4, 3, 2, 5, 3, 1 , 2, 3, 4, 4, 3, 5, 1
9.[알고리즘 ] 이분탐색
이진 탐색(이분 탐색) 알고리즘은 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법이다. (정렬이 돼있어야 가능)이진 탐색은 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘이다.변수 3개(start, end, mid)를 사용하
10.[알고리즘] BFS와 DFS란?
스택 자료 구조에 기초하며, 구현할 때 재귀 함수로 구현하는 것이 좀더 간편합니다.DFS를 구현할 때, 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 검사하지 않을 시 무한 루프에 빠질 위험이 있으므로 반드시 검사해야합니다. ( visitedindex = true
11.[알고리즘] LIS(최장 증가 부분 수열)이란 ?
LIS를 구현하는 방법으로는 두가지가 있습니다.Dynamic Programming (동적 계획법)Binary Search (이분 탐색)DP를 활용할 시 이중 반복문을 사용하여 O(n^2)의 시간 복잡도를 가집니다. 그렇기에 입력 값의 크기가 작을 경우에 유용합니다.dp
12.[알고리즘] 최소 공통 조상(LCA)
최소 공통 조상은 트리 구조에서 임의의 두 정점이 갖는 가장 가까운 조상 정점을 의미한다.트리에서 이러한 최소 공통 조상을 찾으려면 어떤 방식을 사용해야 할까?가장 단순한 방법으로는, 두 포인터를 두고 가리키는 정점이 같아질 때까지 부모 노드로 거슬러 올라가면 될 것이
13.[알고리즘] 동적 계획법(Dynamic Programming)
DP라고 불리는 동적 계획법은 코딩 테스트에 단골 문제 유형으로 나오고 있다.코딩 테스트 문제를 풀다보면 아래와 같은 제한사항이 종종 나오곤 한다.제한사항이 1초이고, 파이썬 기준(정확하지 않습니다) 1초에 2000만 = 20,000,000 번 연산이 가능한데, O(N
14.[알고리즘] 다익스트라 알고리즘(Dijkstra Algorithm)
다익스트라 알고리즘은 하나의 node에서 다른 node로 가는 최단경로를 구하고 싶을때 사용한다.즉, 시작점에서 다른 모든 정점까지의 최단 경로의 길이를 찾는 알고리즘이다.다익스트라 알고리즘을 사용할 수 있는 몇가지 조건이 있다.방향 그래프 \- 0 이상 가중치여야 한
15.[알고리즘] 비트마스크(BitMask)
비트마스크(BitMask)란? 비트마스크(BitMask)는 이진수를 사용하는 컴퓨터의 연산 방식을 이용하여, 정수의 이진수 표현을 자료 구조로 쓰는 기법을 말한다. 이진수는 0 또는 1을 이용하므로 하나의 비트(bit)가 표현할 수 있는 경우는 두 가지이다. 보통