✏️ 알고리즘/필수 알고리즘

[12강] 투 포인터 알고리즘

안녕하세요 Gliver 입니다. 이번 글에서는 투 포인터 알고리즘에 대해 알아보겠습니다. 목차 투 포인터 알고리즘 실제 문제에서 투 포인터 알고리즘 1. 투 포인터 알고리즘 투 포인터 알고리즘은 두 개의 포인터(지점)를 이용하는 알고리즘이다. 정의는 간단하지만, 단순히 두 개의 포인터를 이용하는 것만으로 문제가 쉽게 풀리는 경우가 종종 있다. 투 포인터(Two Pointer) 알고리즘을 어떤 상황에서 사용할 수 있는지와 어떻게 동작하는지 문제를 통해서 살펴보자. [문제] (백준 2003번) 크기가 N인 양의 정수로 이루어진 배열이 있다고 해보자. 이때, 부분 구간의 합이 M인 부분 구간이 몇 개인지 구하여라. (1 ≤ N ≤ 10,000, 1 ≤ M ≤ 300,000,000) (시간 제한: 1초) 먼저,..

[11강] 이분 탐색 알고리즘

안녕하세요 Gliver 입니다. 이번 글에서는 이분 탐색 알고리즘에 대해 알아보겠습니다. 목차 이분 탐색 알고리즘 파라매트릭 서치 알고리즘 실제 문제에서 이분 탐색 알고리즘 1. 이분 탐색 알고리즘 이분 탐색 알고리즘은 정렬된 배열에서 특정한 원소를 찾는 알고리즘이다. 정렬된 배열이 아니라면 이분 탐색을 시행할 수 없음. 이분 탐색(binary search)은 범위를 반으로 줄여가며 특정 원소를 찾는 알고리즘으로 예시를 통해서 어떻게 동작하는지 살펴보자. 아래와 같이 정렬된 배열이 있을 때 이분 탐색 알고리즘을 통하여 10을 찾아보자. 방법1 [1단계] left = 0, right = 11 처음에는 배열의 첫 인덱스를 left(0), 끝 인덱스를 right(11)로 지정하고 시작한다. mid = (lef..

[10강] DP 알고리즘

안녕하세요 Gliver 입니다. 이번 글에서는 DP 알고리즘에 대해 알아보겠습니다. 목차 DP 알고리즘 실제 문제에서 DP 알고리즘 접근 방식과 알고리즘 접근 방식과 알고리즘 내용은 브루트 포스 알고리즘, 그리디 알고리즘, DP 알고리즘 글에 동일하게 존재합니다. 접근 방식은 문제의 핵심 아이디어를 찾는 것을 도와주는 방법론이고 알고리즘은 문제를 해결하는 과정을 일련의 순차적인 절차로 만들어놓은 방법론입니다. 구체적인 예를 들어 설명해보겠습니다. 에라토스테네스의 체 알고리즘은 소수(prime number)를 판별하는 알고리즘이고 그리디 알고리즘은 매 순간에서 가장 최선의 선택을 하여 답을 구해내는 알고리즘입니다. 에라토스테네스의 체 알고리즘은 언제 쓰면 될까요? → 소수(prime number)를 판별할..

[09강] 그리디 알고리즘

안녕하세요 Gliver 입니다. 이번 글에서는 그리디 알고리즘에 대해 알아보겠습니다. 목차 그리디 알고리즘 실제 문제에서 그리디 알고리즘 접근 방식과 알고리즘 접근 방식과 알고리즘 내용은 브루트 포스 알고리즘, 그리디 알고리즘, DP 알고리즘 글에 동일하게 존재합니다. 접근 방식은 문제의 핵심 아이디어를 찾는 것을 도와주는 방법론이고 알고리즘은 문제를 해결하는 과정을 일련의 순차적인 절차로 만들어놓은 방법론입니다. 구체적인 예를 들어 설명해보겠습니다. 에라토스테네스의 체 알고리즘은 소수(prime number)를 판별하는 알고리즘이고 그리디 알고리즘은 매 순간에서 가장 최선의 선택을 하여 답을 구해내는 알고리즘입니다. 에라토스테네스의 체 알고리즘은 언제 쓰면 될까요? → 소수(prime number)를 ..

[08강] 브루트 포스 알고리즘

안녕하세요 Gliver 입니다. 이번 글에서는 브루트 포스 알고리즘에 대해 알아보겠습니다. 목차 브루트 포스 알고리즘 실제 문제에서 브루트 포스 알고리즘 접근 방식과 알고리즘 접근 방식과 알고리즘 내용은 브루트 포스 알고리즘, 그리디 알고리즘, DP 알고리즘 글에 동일하게 존재합니다. 접근 방식은 문제의 핵심 아이디어를 찾는 것을 도와주는 방법론이고, 알고리즘은 문제를 해결하는 과정을 일련의 순차적인 절차로 만들어놓은 방법론입니다. 구체적인 예를 들어 설명해보겠습니다. 에라토스테네스의 체 알고리즘은 소수(prime number)를 판별하는 알고리즘이고, 그리디 알고리즘은 매 순간에서 가장 최선의 선택을 하여 답을 구해내는 알고리즘입니다. 에라토스테네스의 체 알고리즘은 언제 쓰면 될까요? → 소수(prim..

[07강] 정렬 알고리즘

안녕하세요 Gliver 입니다. 이번 글에서는 정렬 알고리즘에 대해 알아보겠습니다. 목차 정렬 알고리즘 정렬 알고리즘 종류 실제 문제에서 정렬 알고리즘 1. 정렬 알고리즘 정렬 알고리즘(Sorting Algorithm)은 어떤 기준에 대해 원소들을 정렬하는 알고리즘입니다. 여기서 "어떤 기준" 이라는 것은 오름차순, 내림차순 등을 의미함. 기본적으로 프로그래밍 언어에서 지원하는 sort() 함수는 오름차순을 기준으로 구현돼 있고, 내림차순으로 하려면 sort() 함수 입력 부분에 less()를 넣어주면 됩니다. (C++ 기준) 자세한 사용법은 구글에 "내림차순 sort" 라고 검색하면 됨. 오름차순, 내림차순 말고 사용자가 원하는 기준에 맞게 정렬을 하고 싶다면, compare 함수를 만들어서 sort(..