파이썬

코딩테스트에서는 각 문제 당 메모리와 시간이 제한되어 있다. 비교적 적은 입력이나 짧은 알고리즘에서는 이러한 제한이 큰 장애가 되지는 않는다. 그러나 입력이 많은 문제 (예를 들어 10억개의 입력 등) 거나 재귀적인 알고리즘에서는 메모리 혹은 시간 제한에 걸리게 된다. 따라서 우리는 최대한 연산 속도와 메모리 공간을 효율적으로 활용하는 알고리즘을 구현해야 한다. 몇몇 문제에서는 메모리 공간을 조금 더 사용할 수록 비약적으로 연산속도를 줄일 수 있는 경우가 존재한다. 이는 뒤에서 설명할 다이나믹 프로그래밍 기법을 사용하는 경우이다. 다이나믹 프로그래밍이란 동적 계획법이라고도 표현하며 2가지 방식이 존재한다. 이는 아래와 같다. 탑다운 방식 바텀업 방식 먼저 다이나믹 프로그래밍의 기본적인 아이디어는 다음과 ..

이진 탐색이란 데이터가 모두 정렬된 상태에서 탐색 범위를 절반씩 쪼개면서 탐색을 진행하는 알고리즘이다. 즉, 이진 탐색은 중간지점 (이하 중간점) 의 데이터를 찾고자 하는 데이터와 비교하여 탐색 범위를 좁힌다는 특징을 갖고 있다. 여기서 중간점 = (시작점 + 끝점) // 2 의 식으로 구하게 되며, 이때 // 는 버림 나눗셈 연산자로 나눗셈을 진행하고 몫의 정수 부분만 취하는 파이썬 연산자이다. 이진 탐색을 진행하는 과정을 살펴보자. 0 1 2 3 4 5 6 7 8 9 위와 같이 오름차순 정렬되어 있는 데이터가 있다고 가정하자. 여기서 우리는 3이라는 데이터가 어디에 위치해있는지를 탐색하고 싶다. 가장 먼저 시작점 = 0, 끝점 = 리스트의 마지막 인덱스 로 초기화 한다. 중간점 = (시작점 + 끝점)..

이진 탐색 알고리즘을 들어가기 전에 먼저 순차 탐색 (Sequential Search) 에 대해서 알아보자. 순차 탐색이란 말 그대로 리스트 내에서 특정 데이터를 찾고 싶을 때, 앞에서부터 순차적으로 데이터를 비교해서 탐색하는 알고리즘이다. 즉, 리스트내의 모든 데이터에 접근하며 차례대로 확인하게 된다. 따라서 시간이 여유롭다면 데이터의 개수가 아무리 많더라도 반드시 원하는 데이터를 찾아낼 수 있다는 장점이 있다. 순차 탐색 알고리즘이 수행되는 곳은 정말 다양하다. 아래의 경우에도 순차 탐색이 사용된다. 리스트에 특정 값의 원소가 있는지 체크할 때 리스트에서 특정 값을 가지는 원소의 개수를 구할 때 ( count() 메서드 ) 순차 탐색 알고리즘의 소스코드는 아래와 같다. 순차 탐색의 시간 복잡도는 다음..

정렬 알고리즘은 앞선 게시물에서 다양하게 배웠고, 또한 그보다 많은 수의 알고리즘이 존재하기도 한다. 이러한 알고리즘을 사용해서 정렬을 수행하는 것도 좋지만 많은 경우에서 파이썬에서 기본적으로 제공하는 정렬 알고리즘을 사용하는 편이 유리할 수 있다. - 파이썬은 기본 정렬 라이브러리인 sorted() 함수를 제공한다. 이는 퀵 정렬과 비슷한 정렬 방식인 병합 정렬을 기반으로 만들었는데 일반적으로 퀵 정렬보다는 느리지만 최악의 경우에서도 O(NlogN)을 보장한다는 장점을 가지고 있다. sorted() 함수는 리스트, 딕셔너리, 집합 자료형 등을 입력받아서 정렬된 리스트를 반환한다는 특징을 가지고 있다. 리스트 = sorted(정렬하려는 자료형) - 이와는 조금 다르게 리스트에서 내부적으로 정렬을 수행하는..

계수 정렬 (Count Sort) 은 매우 빠른 정렬 알고리즘이다. 그러나 한 가지 치명적인 약점이 있는데 바로 특정한 조건이 부합할 때만 사용할 수 있다는 것이다. 그 약점은 바로 '데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때만 사용가능하다' 라는 것이다. 만약 데이터가 무한한 범위를 가질 수 있는 실수형 데이터라면 이 계수 정렬을 사용하기 힘들다는 것이다. 또한 일반적으로 가장 작은 데이터와 가장 큰 데이터의 값의 차이가 1,000,000을 넘지 않을 때 효과적으로 사용할 수 있다. 계수 정렬은 일반적으로 별도의 리스트를 선언하고 그 안에 정렬에 대한 정보를 담는다는 특징이 있다. 즉, 앞서 다루었던 정렬 알고리즘과는 다르게 직접 데이터의 값을 비교한 뒤에 위치를 변경하는 정렬 방식..

퀵 정렬 (Quick Sort) 는 매우 빠른 정렬 알고리즘으로 널리 알려져 있으며 대부분 프로그래밍 언어에서 정렬 라이브러리의 근간이 되는 알고리즘이다. 퀵 정렬이란 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방식으로 정렬을 진행하는 알고리즘이다. 퀵 정렬에서는 기준이 필요하다. 이 기준은 피벗 (Pivot) 이라고 부른다. 먼저 피벗을 설정하고 피벗보다 큰 수와 작은 수를 교환한 후 리스트를 반으로 분할하는 방식으로 진행된다. 피벗을 선정할 때는 명확한 기준이 필요하고 그 기준을 명시해야 한다. 리스트의 첫 번째 데이터를 피벗으로 설정하는 호어 분할 (Hoare Partition) 방법으로 퀵 정렬을 이해한다. 먼저 아래와 같은 데이터가 있다고 가정한다. 5 7 9 ..

삽입 정렬 (Insertion Sort) 는 데이터를 하나씩 확인하며 각 데이터를 적절한 위치에 삽입하여 정렬하는 알고리즘이다. 따라서 삽입 정렬 또한 선택 정렬과 마찬가지로 직관적으로 동작원리를 이해하기 쉬운 알고리즘이라고 할 수 있다. 삽입 정렬은 선택 정렬에 비해 구현 난이도가 다소 높은 편이지만 실행시간 측면에서 더 효율적인 알고리즘으로 알려져 있다. 또한 필요할 때만 위치를 바꾸기 때문에 '데이터가 거의 정렬 되었을 때' 사용하면 그 효율은 배가 된다. 삽입 정렬은 특정한 데이터가 적절한 위치에 들어가기 이전에 그 앞까지의 데이터는 이미 정렬되어 있다고 가정한다. 아래와 같은 데이터를 삽입 정렬을 통해서 정렬하는 모습을 보자. 7 5 9 0 3 1 6 2 4 8 삽입 정렬은 두 번째 데이터부터 ..

먼저 코딩 테스트의 중요 알고리즘 중 하나인 정렬에 대해서 알아보자. 정렬이란 말 그대로 데이터를 특정한 기준에 따라서 순서대로 나열하는 것을 의미한다. 프로그램에서 주어진 데이터를 정렬하고 사용하는 경우가 많기 때문에 프로그램을 작성할 때 자주 사용되는 알고리즘 중 하나이다. 또한 정렬 알고리즘이 중요한 이유 중 하나는 이진 탐색의 전처리 과정이기 때문이다. 선택 정렬 (Selection Sort) 란 데이터가 무작위로 나열되어 있을 때, 이 중에서 가장 작은(혹은 가장 큰) 데이터를 가장 앞의 데이터와 바꾸고, 두 번째로 작은 데이터를 두 번째에 위치한 데이터와 계속 바꾸는 방법으로 데이터를 정렬하는 알고리즘이다. 선택 정렬은 가장 원시적인 방법으로 매번 '가장 작은 데이터를 선택한다'는 의미에서 이..