✏️ 알고리즘

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

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

[07강] 정렬 알고리즘

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

기본 알고리즘 정리

안녕하세요 Gliver 입니다. 이번 글은 제 블로그의 기초적인 개념 카테고리에 대해 설명하는 글입니다. 목차 기초적인 개념 카테고리 카테고리 내의 글에 대한 개요 1. 기초적인 개념 카테고리 기초적인 개념 카테고리는 프로그래밍 문제를 푸는 데에 있어 직접적으로 쓰이는 알고리즘은 아니지만, 보조적으로 쓰이는 알고리즘이나 개념에 대해 다루는 카테고리입니다. 보조적으로 쓰이긴 하지만, 모르면 문제를 못 풀기 때문에 기본적으로 알아둬야 함. 2. 카테고리 내의 글에 대한 개요 [글의 제목] 을 클릭하시면 해당 페이지로 이동합니다. [시간 복잡도] 시간 복잡도 글은 시간 복잡도의 의미, 자주 쓰이는 시간 복잡도, 실제 문제에서 시간 복잡도 로 구성되어 있습니다. 시간 복잡도는 프로그램이 돌아가는 데 걸리는 시간..

[06강] 순열 알고리즘

안녕하세요 Gliver 입니다. 이번 글에서는 순열 알고리즘에 대해 알아보겠습니다. 목차 순열 알고리즘 실제 문제에서 순열 알고리즘 '순열(Permutation)과 조합(Combination)의 차이점'은 이전 글(조합 알고리즘)에서 설명했기 때문에 생략하겠습니다. 순열 알고리즘 순열은 수식으로 나타내면 nPr 입니다. 즉, 순열의 수식은 전체 원소의 개수 n 과 나열할 원소의 개수 r 로 구성되어 있습니다. 순열 알고리즘 순열 알고리즘은 n개의 원소 중에서 r개를 나열하는 모든 경우에 대해 살펴보는 알고리즘입니다. 예를 들어, 1~11의 숫자가 있고 이 중에서 2개를 나열하는 경우라고 하면 $_{11}\mathrm{P}_{2}(110)$가지 경우에 대해 살펴보는 거임. 순열 알고리즘은 원소 n개 중에서..

[05강] 조합 알고리즘

안녕하세요 Gliver 입니다. 이번 글에서는 조합 알고리즘에 대해 알아보겠습니다. 목차 조합 알고리즘 실제 문제에서 조합 알고리즘 조합과 순열 먼저, 조합(Combination)과 순열(Permutation)의 차이점에 대해 간단히 짚고 넘어가겠습니다. 조합과 순열의 가장 큰 차이점은 순서라는 개념의 존재 여부입니다. 조합은 순서라는 개념이 존재 x, 순열은 순서라는 개념이 존재 o 이해가 안 되시는 분들은 '더보기'를 눌러 예시를 참고해주시기 바랍니다. 더보기 [예시] 숫자 카드 1, 2, 3이 있습니다. 이때 카드 3장을 가지고 만들 수 있는 순열과 조합은 다음과 같습니다. ㆍ 조합의 경우 : 조합에는 순서라는 개념이 존재하지 않으므로, {1, 2, 3}, {1, 3, 2}, {2, 1, 3}, {..

[04강] 유클리드 알고리즘

안녕하세요 Gliver 입니다. 이번 글에서는 유클리드 알고리즘에 대해 알아보겠습니다. 목차 유클리드 알고리즘 실제 문제에서 유클리드 알고리즘 유클리드 알고리즘 유클리드 알고리즘은 최대공약수(GCD, Greatest Common Divisor)를 구하는 알고리즘입니다. 유클리드 알고리즘은 유클리드 호제법을 코드로 구현했다고 생각하면 됨. 유클리드 알고리즘 Logic 자연수 A, B (A > B) 에 대해 아래의 과정을 반복합니다. ㆍ tmp 에 A 를 B 로 나눈 나머지를 할당합니다. ㆍ A 에 B 를 할당합니다. ㆍ B 에 tmp 를 할당합니다. ㆍ 만약, B 가 0 이면 A 를 최대공약수로 하고 프로그램을 종료합니다. Example 보기 [A=32, B=6 인 경우] step1) ㆍ tmp 에 A(3..

[03강] 에라토스테네스의 체 알고리즘

안녕하세요 Gliver 입니다. 이번 글에서는 에라토스테네스의 체 알고리즘에 대해 알아보겠습니다. 목차 에라토스테네스의 체 알고리즘 실제 문제에서 에라토스테네스의 체 알고리즘 에라토스테네스의 체 알고리즘 에라토스테네스의 체 알고리즘은 소수(Prime Number)를 판별하는 알고리즘입니다. 소수 : 약수가 1과 자기 자신뿐인 자연수 좀 더 자세히 말하자면, 자연수 N에 대해 에라토스테네스의 체 알고리즘을 수행하고 나면, 2~N 범위의 자연수는 O(1) 만에 소수(Prime Number)인지를 판별할 수 있습니다. 에라토스테네스의 체 알고리즘을 알아보기 전에, 약수의 성질에 대해 알아보겠습니다. 약수의 성질 어떤 자연수 n이 있을 때, n의 약수 A, B에 대해 n = A x B 형태로 나타낼 수 있습니다..

[02강] 나머지(모듈러, modulo) 연산

안녕하세요 Gliver 입니다. 이번 글에서는 나머지(모듈러, modulo) 연산에 대해 알아보겠습니다. 목차 나머지(모듈러, modulo) 연산의 의미 나머지(모듈러, modulo) 연산의 특징 실제 문제에서 나머지(모듈러, modulo) 연산 나머지(모듈러, modulo) 연산의 의미 모듈러 연산이란 어떤 한 숫자를 다른 숫자로 나눈 나머지를 구하는 연산입니다. 예를 들어, 두 정수 A, B에 대해서 A를 B로 나누어 나머지가 C가 나왔다면 "A mod B = C" 또는 "A % B = C"라고 표현할 수 있습니다. C는 A를 B로 나누었을 때의 나머지에 해당하므로, "0 ≤ C ≤ B-1"을 만족 나머지(모듈러, modulo) 연산의 특징 이러한 나머지(모듈러, modulo) 연산의 특징은 크게 다..