✏️ 알고리즘/기본 알고리즘

기본 알고리즘 정리

안녕하세요 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) 연산의 특징은 크게 다..

[01강] 시간 복잡도

안녕하세요 Gliver 입니다. 이번 글에서는 시간 복잡도에 대해 알아보겠습니다. 목차 시간 복잡도의 의미 자주 쓰이는 시간 복잡도 실제 문제에서 시간 복잡도 시간 복잡도의 의미 시간 복잡도는 프로그램이 돌아가는 데 걸리는 시간을 표기한 것입니다. 프로그램의 기본 연산의 횟수는 상수와 변수로 표현 가능합니다. 따라서, 시간 복잡도를 표현할 때 사용하는 문자도 상수와 변수뿐입니다. ex) "3n + 1000" 번의 기본 연산이 이루어지면, 변수 n과 상수 1000으로 시간 복잡도를 나타낼 수 있음. 자주 쓰이는 시간 복잡도 저희는 Big-O 표기법에 대해서만 다룰 것입니다. Big-O 표기법은 프로그램 동작 시간에 가장 큰 영향을 주는 값을 중심으로 시간복잡도를 표기합니다. 큰 영향을 주는 값이라는 것은 ..