알고리즘
1.[Algorithm] 탐색 알고리즘 (선형, 이분)
오늘은 탐색을 위해 사용되는 알고리즘인 선형탐색과 이분탐색에 대해서 알아보고 이 알고리즘을 사용하는 리트코드의 문제들도 함께 풀어보겠습니다. 선형 탐색 (= 순차 탐색, Linear Search) 선형 탐색 알고리즘은 원하는 데이터를 찾기 위해 한 쪽 끝에서 다른 쪽 끝까지 모든 요소를 차례로 순환하며 탐색하는 알고리즘입니다. 순서대로 순환하기 때문에 ...
2.[Algorithm] 소수 판별하기 (+ 에라토스테네스의 체)
소수란 1보다 큰 자연수 중 3, 5, 7, 11처럼 1과 자기자신으로만 나누어지는 수를 말합니다. 코딩테스트에도 종종 등장하는 주제로 소수를 판별하는 방법은 어떤것들이 있는지 알아보겠습니다. 선형 탐색 (2 ~ N-1까지 반복문) 가장 단순한 방법으로 반복문을 사용해서 2부터 N-1까지 반복하며 나머지가 0으로 나오는 경우가 있는지를 확인하는 방법입니...
3.[Algorithm] 정렬 - 버블 정렬 (Bubble Sort)
버블 정렬 과정 > 출처: Wikipedia 버블 정렬은 서로 인접한 두 개의 요소를 차례로 비교해가며 정렬이 필요한 경우 두 개의 요소를 스왑(서로의 위치를 변경)하는 형태로 정렬을 해나갑니다. 이렇게 순환과정에서 두개씩 비교해 나가는 모습이 거품과 같다고 하여 버블 정렬이라는 이름을 가지게 되었습니다. 직관적이며 구현이 쉽다는 장점은 있지만 그만큼...
4.[Algorithm] 정렬 - 선택 정렬 (Selection Sort)
선택 정렬 과정 > 출처: Wikipedia 선택 정렬은 첫번째 요소부터 순환하며 자신의 뒤쪽에 위치한 요소(정렬되지 않은 요소)들 중 최솟값을 찾아 선택하여 스왑하는 형태로 정렬이 진행됩니다. 선택 정렬 또한 버블 정렬과 같이 직관적이고 구현이 비교적 쉽지만 마찬가지로 성능이 좋지 않습니다. 구현 아래 로직은 오름차순으로 정렬한다는 가정하에 작성하...
5.[Algorithm] 정렬 - 삽입 정렬(Insertion Sort)
삽입 정렬 애니메이션 > 출처: Wikipedia 삽입 정렬은 두 번째 인자부터 시작하여 이전 요소들과 값을 비교한 후 적절한 위치를 찾아 삽입하는 방식으로 정렬을 진행합니다. 삽입 정렬도 이전에 다뤘던 버블, 선택 정렬과 마찬가지로 2중 반복문을 사용하지만 차이점이 있습니다. 바깥쪽 for문을 outer, 안쪽 for문을 inner라고 했을 때 버...
6.[Algorithm] 정렬 - 병합정렬 (Merge Sort)
정렬 - 병합정렬 (Merge Sort) 오늘 다룰 정렬 알고리즘은 병합정렬입니다. 병합정렬은 합병정렬이라고도 부르는데 분할정복 알고리즘으로 안정적인 정렬이라는 특징을 가지고 있습니다. > * 분할정복 알고리즘(Divide-and-conquer algorithm)이란? 분할 정복 알고리즘은 복잡한 기존 문제를 단순화하기 위해 재귀적으로 접근해 2개 이...
7.[Algorithm] 정렬 - 퀵 정렬(Quick Sort)
퀵 정렬 애니메이션 퀵 정렬은 많이 사용되는 정렬 알고리즘 중 하나로 분할 정복 알고리즘이자 불안정 정렬이라는 특징을 가지고 있습니다. 분할 정복 알고리즘의 특성상 정렬을 위해 요소들을 먼저 분할하게 되는데 퀵 정렬은 이 과정에서 기준이 되는 요소인 "피봇"을 정합니다. 오름차순 정렬이라고 가정했을 때 피봇을 제외한 나머지 요소들을 순환하며 피봇과 값...
8.[Algorithm] 투포인터와 슬라이딩 윈도우
오늘 다룰 알고리즘은 투포인터와 슬라이딩 윈도우 알고리즘입니다. 투포인터와 슬라이딩 윈도우 알고리즘은 배열, 리스트와 같은 선형 자료구조뿐만 아니라 문자열에서도 응용해서 사용할 수 있으며 특정 구간을 탐색할 때 유용합니다. 일반적으로 이 두 알고리즘을 적용할 수 있는 문제에서 알고리즘을 사용하지 않고 문제를 푸는 경우 O(n^2)까지의 시간 복잡도를 가...