알고리즘
1.탐색 알고리즘 - 순차 탐색
데이터가 모인 배열의 처음부터 끝까지 순서대로 비교하여 원하는 데이터를 찾아내는 알고리즘.단방향으로 탐색을 수행하므로 선형 탐색(Linear Search)라고도 한다.자료의 집합에서 처음 원소 부터 시작하여 찾으려는 값과 일치하는지 비교한다.찾는 값이 일치하는 원소를
2.탐색 알고리즘 - 이진 탐색
전체 배열에서 가운데에 존재하는 원소의 값과 비교하여 다음 탐색 위치를 결정하는 알고리즘.순차 탐색과 달리 배열의 원소들이 커지는 순서대로 정렬이 되어 있어야 하는 조건이 있다.자료의 집합에서 n/2 번째 원소가 찾으려는 값과 일치하는지 비교한다.찾는 값이 원소의 값
3.탐색 알고리즘 - Upper Bound, Lower Bound
Upper bound, Lower bound 알고리즘에 대하여 이해해보자.이진 탐색 알고리즘은 정렬된 배열에서 특정한 값의 위치를 찾는 알고리즘이다.Upper bound, Lower bound 알고리즘은 이진 탐색에서 파생된 것으로, 이진탐색과 마찬가지로 배열 안의 숫
4.정렬 알고리즘 - 삽입 정렬
왼쪽에서 오른쪽의 순서로 비교를 진행하여 요소를 정렬하는 방식.최선의 경우 : O(n), 이미 정렬이 되어있는 경우최악의 경우 : O(n^2), 정렬이 하나도 안되어있는 경우삽입 정렬 역시 버블 정렬과 같이 in place 알고리즘으로 메모리가 절약된다.구현이 매우 간
5.정렬 알고리즘 - 선택 정렬
요소들 중에서 최솟값을 찾아 맨 앞의 요소와 비교하여 정렬한다.맨 앞을 제외한 요소들 중에서 다시 최솟값을 찾아 제외된 요소 다음의 위차와 비교 정렬 반복한다.버블 정렬과 반대로 각 회전이 끝날 때마다 맨 앞의 데이터 위치가 정해진다.O(n^2) : 선택 정렬은 매번
6.정렬 알고리즘 - 버블 정렬
서로 인접한 두 원소를 비교하며 순서대로 정렬하는 알고리즘(여기선 오름차순 기준 정렬)최선의 경우 : O(n), 이미 정렬이 되어있는 경우최악의 경우 : O(n^2): 정렬이 하나도 안되어있는 경우버블 정렬은 in place 알고리즘이기 때문에 메모리가 절약된다는 장점
7.정렬 알고리즘 - 병합 정렬
병합 정렬 혹은 합병 정렬이라고 불리며 데이터들을 잘게 쪼갠 다음에 하나로 합치는 과정에서 정렬하는 방식의 분할 정복 알고리즘.배열을 쪼개는 과정이 분할단계(빨간 배열)에 해당하며 합치는 과정이 정복단계(초록 배열)에 해당한다.최선의 경우 : O(nlog₂n)최악의 경
8.정렬 알고리즘 - 퀵 정렬
병합 정렬과 마찬가지로 분할 정복 알고리즘을 이용한 정렬 알고리즘이며 가장 빠른 정렬 알고리즘 중 하나이다.정렬하는데 가장 간단한 배열인 요소가 없거나 요소가 하나만 있는 배열이 될 때까지 큰 배열을 나눠야한다.요소 하나를 기준 원소인 pivot으로 설정한다. 그리고
9.정렬 알고리즘 - 쉘 정렬
쉘 정렬은 일정 간격으로 떨어진 원소들끼리 부분집합을 구성하고 각 부분집합의 원소들에 대하여 삽입 정렬을 수행하는 작업을 반복하여 전체 원소들을 정렬하는 알고리즘이다.전체 비교 정렬이며, 삽입 정렬을 개선한 정렬방법이다.멀리 떨어진 원소들 끼리 정렬 한 다음 비교할 원
10.정렬 알고리즘 - 힙 정렬
힙 정렬은 비교 기반 정렬 알고리즘이다.선택 정렬 알고리즘과 비슷하게 정렬 된 영역과 아닌 영역을 나누어 가장 큰 요소를 찾아 정렬된 영역으로 배치시킨다.(오름차순 기준)선택 정렬 보다 개선된 점은 선형 시간이 소요되는 선택 정렬의 탐색과 달리 힙 자료구조를 사용하여
11.정렬 알고리즘 - 계수 정렬
계수 정렬 알고리즘은 특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠른 정렬 알고리즘이다.데이터의 개수가 N, 데이터 중 최댓값이 K일 때, 계수 정렬은 최악의 경우에도 O(N + K)의 시간 복잡도를 보장하므로 빠른 정렬 알고리즘으로 유명한 퀵 정렬의 시간복잡도
12.정렬 알고리즘 - 비교 분석 정리
각각의 정렬 알고리즘의 세부 내용을 반드시 이해하고(상단 목록 참고) 아래 글을 참고하자.무조건 어느 정렬법이 좋다라고 말할 수 있는 정렬법은 없다. 상황별로 장단점이 각각의 정렬법에 존재하기 때문이다.그러므로 우리는 각 정렬 알고리즘들의 특징을 이해하여 상황에 맞는
13.조합 알고리즘
이 글에서는 조합을 재귀를 통해서 구현하는 방법에 대해서 알아보자.브루트포스 알고리즘에서 가장 많이 사용되는 방법이 순열과 조합 등으로 모든 경우의 수를 모두 계산해본 뒤에 원하는 결과 값을 찾는 방식이다.조합은 순서가 상관이 없는 모임을 의미한다. 순서가 상관 없기
14.순열 알고리즘
이 글에서는 순열을 재귀를 통해서 구현하는 방법에 대해서 알아보자.순열은 주어진 수열에서 순서에 따라 결과가 달라지는 방식을 순열이라고 한다. 순서가 존재하는 열 이라는 것 이다.즉, 순열에서 { 1, 2, 3 } 과 { 1, 3, 2 } , { 2, 1, 3 } .
15.중복 조합 알고리즘
이 글에서는 중복 조합을 재귀를 통해서 구현하는 방법에 대해서 알아보자.조합은 순서에 상관없이 중복을 허용하지 않고 나올 수 있는 모든 수열을 조합이라고 하였다.중복조합은 조합에서 중복을 허용한다는 것 이다.우리가 알던 조합에서 { 1, 2, 3 } 중에 2개를 뽑는
16.중복 순열 알고리즘
이 글에서는 중복 순열을 재귀를 통해서 구현하는 방법에 대해서 알아보자.순열은 순서에 상관이 있고 중복을 허용하지 않고 나올 수 있는 모든 수열을 순열이라고 하였다.중복순열은 말그대로 순열에서 중복을 허용한다는 것이다.즉, { 1, 2, 3 } 에서 2개를 뽑을 때
17.투 포인터, 슬라이딩 윈도우, 구간 합 알고리즘
투 포인터와 슬라이딩 윈도우 알고리즘은 선형 공간(1차원 배열)을 2회 이상 반복적으로 탐색해야 할 경우 O(N^2) 이상 걸릴 시간 복잡도를 부분 배열을 활용하여 O(N)으로 줄일 수 있다는 공통점이 있습니다. 그렇다면 이 두 알고리즘의 차이점은 무엇일까요 ?바로,
18.그리디 알고리즘
그리디 알고리즘(욕심쟁이 알고리즘, Greedy Algorithm)은 매 선택에서 지금 이 순간 당장 최적인 답을 선택하여 적합한 결과를 도출하는 알고리즘 설계 기법가장 이득을 볼 수 있는 조건을 유추하여 최대의 이득을 보기 위한 알고리즘이다.당장 순간의 선택에만 최적
19.BFS와 DFS
그래프의 탐색 알고리즘인 BFS(Breadth-First Search)와 DFS(Depth-First Search)를 알아보자. 백준 저지의 단계별풀어보기에서 해당 알고리즘 문제를 풀어보자.너비 우선 탐색이라 하며 BFS(Breadth-First Search)라 부른
20.비트마스크(BitMask) 알고리즘
비트마스크는 이진수를 사용하는 컴퓨터의 연산 방식을 이용하여, 정수의 이진 표현을 자료 구조로 사용하는 기법을 말한다.이진수는 0 또는 1을 이용하므로 하나의 비트로 표현할 수 있는 경우의 수는 두 가지이다.보통 어떤 비트가 1이면 "존재한다", 0이면 "존재하지않다"
21.LCS 알고리즘
22.페이지 교체 알고리즘 - LRU(Least Recently Used Algorithm)
페이지 교체 알고리즘은 페이징 기법으로 메모리를 관리하는 운영체제에서, 페이지 부재가 발생 하여 새로운 페이지를 할당하기 위해 현재 할당된 페이지 중 어느 것과 교체할지를 결정하는 방법입니다.페이지 교체 알고리즘의 예로, FIFO, LFU, LRU 알고리즘 등이 있습니