카운팅 정렬, 혹은 계수 정렬은 O(n + k)의 시간복잡도를 가진 정렬이다. 여기서 다소 낯선 k는 정렬을 수행할 배열의 가장 큰 값을 의미한다. k가 단순히 상수로 취급되어 생략되지 않고 남아있는 것은 그만큼 k에 따라 수행시간에 영향을 미치기 때문이다. 만약 k가 n보다 작다면 정렬의 수행시간은 O(n)이 되겠지만, 무한대로 크다면 정렬의 수행시간도 무한대가 된다. 작동 방식 1. 배열을 이용한 방식 계수 정렬은 counting이라는 말 답게 배열에 존재하는 수의 개수를 세어주고, 이 정보를 바탕으로 정렬을 수행한다. 그리고 여기서 수와 수의 개수는 배열 혹은 딕셔너리의 인덱스와 해당 값을 통해서 기록할 수 있다. 먼저 배열을 통한 계수 정렬은 누적합의 개념을 적용하여 구현할 수 있다. 배열을 이용..
알고리즘/이론
똑같은 수나 문자를 여러 번 곱하는 것을 거듭제곱이라고 한다. 흔히 우리가 말하는 2의 4제곱(2^4=16), 5의 3제곱(5^3=125) 등은 거듭제곱을 표현한 것이다. 당연히 코드를 통해서 이를 빠르게 계산할 수 있다. 반복문 사용 a의 n제곱 값을 구하고 싶을 때, for문을 사용해 직관적으로 다음과 같은 코드를 작성할 수 있다. def power(a, n): ans = 1 for _ in range(n): ans *= a return ans 재귀함수 사용 반복문이 아닌 재귀적 방식으로도 위 코드를 구현할 수 있다. a의 n제곱을 쭉 풀어보면 다음과 같다. 위 식은 부분문제로 나눌 수 있다. 만약 a의 n제곱이 아닌 a의 n+1제곱을 구하고자 할 땐 a^n의 값에 a를 한 번 더 곱해주면 되는데, ..
투 포인터 알고리즘은 주로 수열의 연속된 값들의 합을 다룰 때 사용되는 알고리즘이다. 여기서 두 개의 포인터란 말 그대로 시작점과 끝 점을 포인터로 잡아 해당 포인터들이 움직이면서 동작을 수행해준다. 백문이불여일견. 이미지로 한 번 살펴보자 동작 방식 우리가 배열에서 연속된 값의 합이 5가 될 때의 경우를 찾고 싶다고 가정해보자. 물론 반복문을 두 번 중첩시켜 모든 배열의 값들에 대해 완전탐색을 진행할수도 있지만, 그러한 방식은 O(n^2) 만큼의 시간이 소요된다. 배열이 커지면 커질수록 연산시간은 기하급수적으로 증가할 것이다. 따라서 사용되는 방식이 이 글에 포스팅하는 투 포인터 방식이다. 앞서 설명한 것과 마찬가지로, 투 포인터 방식에선 start와 end라는 두 개의 포인터를 정의해준다. 처음엔 두..
알고리즘 문제를 풀다보면 특정 수들이 소수인지 판단하도록 요구하는 문제들이 줄곧 있다. 아예 대놓고 소수찾기라는 문제만 쳐봐도 꽤 많은 문제들이 나올 것이다. 소수는 영어로 Prime Number라고 부르며 1과 자기자신 외에는 어떠한 수로도 나누어 떨어지지 않는 수를 말한다. 특정 수 N이 소수인지 아닌지 구하는 법은 바로 이 특징을 활용하여 2부터 N-1 까지의 수로 해당 수를 나눠보고, 이 과정에서 어떠한 수에 의해 나누어 떨어지는지 확인하는 것이다. 나누어떨어지지 않는다면 해당 수는 소수인 것이고, 도중에 다른 수에 의해 나누어 떨어진다면 그 수는 소수가 아닐 것이다. 이를 코드로 표현하면 다음과 같다. def is_prime_num(n): for i in range(2, n): if n % i ..
대부분의 프로그래밍 언어에 내장된 정렬 함수들은 이 퀵 정렬 알고리즘과 병합 알고리즘을 기반으로 만들어졌다. 그 중 하나인 퀵 정렬 알고리즘에 대해 학습해보자. 선택 정렬, 삽입 정렬이 데이터들을 순차적으로 비교하는 것과 다르게, 퀵 정렬 알고리즘에선 기준 데이터(Pivot)를 설정해 해당 값보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방식으로 정렬을 수행한다. 퀵 정렬 알고리즘이 작동하는 방식의 순서도는 다음과 같다. 1. 비교 기준이 될 pivot 인덱스를 설정한다. (기본적인 퀵 정렬 알고리즘에선 배열의 맨 처음 값을 pivot으로 설정한다.) 2. arr[pivot]부터 왼쪽부터 +1 씩 순차적으로 이동하며 arr[pivot]보다 큰 값을 찾는다. 3. 배열의 맨 뒤 값부터 순차적으로 -1 씩 ..
정렬 알고리즘은 값들을 특정 조건에 따라 정렬하기 위해 사용되는 알고리즘이다. ex) 오름차순, 내림차순 대부분의 언어들에서는 원소들을 정렬하는 내장함수들이 존재하기 때문에 자연스럽게 그 함수들을 사용하지만, 당연히 이 과정은 자동으로 이루어지는 것이 아니라 내부적으로는 일련의 과정들을 거친다. 선택 정렬 알고리즘 선택 정렬 알고리즘은 수 많은 정렬 알고리즘 중 하나이다. 선택 정렬 알고리즘의 아이디어는 그림과 같이, 첫 번째 값부터 맨 마지막 값까지 쭉 돌면서 가장 작은 값들을 하나씩 배열의 맨 앞으로 가져오는 것이다. 파이썬을 통해 구현한 선택 정렬은 다음과 같다. arr = [5, 10, 9, 33, 21, 7, 2, 3, 0] # 정렬되지 않은 array for i in range(len(arr)..
재귀함수란 함수 내에서 그 함수를 다시 사용하는 것을 말한다. 약간 인셉션 느낌이 드는 방식의 이 함수는 실제 코드를 보면 더 쉽게 이해될 수 있다. def recursive(): print("이것은 재귀함수입니다.") recursive() recursive() #함수 호출 이 함수는 "이것은 재귀함수입니다." 를 무한히 출력하는 재귀함수이다. recursive라는 재귀함수가 호출되면 print문을 수행하고 다시 recursive함수를 호출하는 모습이다. 하지만, 재귀적으로 진행되는 함수들은 모두 메모리의 스택에 지속적으로 쌓인 후 하나씩 pop하는 형식으로 실행된다. 그러나, 이렇게 쌓이는 데이터가 컴퓨터가 제어해놓은 스택의 제한(recursion depth라고도 부른다)을 초과하게 되면 해당 함수는 ..
유튜브, SNS, 광고 등 인터넷 서비스 등에서 종종 접할 수 있는 알고리즘은 일반인들에게도 꽤 친숙한 개념이 됐다. 알고리즘이란 간단히 말해 어떠한 문제를 해결하기 위해 필요한 논리기반의 방식이라고 할 수 있는데, 실제로 우리는 일상생활 속에서도 우리도 모르게 많은 알고리즘을 만들고 수행하고 있다고 할 수 있다. 요리를 할 때, 여자친구와의 데이트 코스를 짤 때, 집안일을 할 때 우리가 정하는 나름대로의 순서와 행동의 이유가 모두 알고리즘에 기반되어 있다고 할 수 있다. 사실상 넓은 의미에서 우리가 하는 모든 행동은 우리만의 내제적인 알고리즘에 기반하여 이루어 지고 있다고 해도 과언이 아닐 것이다. 개발자에게 알고리즘이란? 개인의 행동을 결정하기 위한 알고리즘은 가끔 조금 효율적이지 못하더라도 잠시 후..
