가장 널리 알려진 알고리즘 중의 하나인 피보나치(Fibonacci) 알고리즘에 대해서 알아보겠습니다. 알고달레에서 코딩 테스트/인터뷰 준비에 좀 더 특화된 컨텐츠를 만나보세요! 📝 피보나치 수열 피보나치 수열에서는 첫 번째 항은 0, 두 번째 항은 1, 그 다음부터는 바로 전 두 항의 숫자의 합이 현재 항의 값이 됩니다. 따라서 피보나치나 수열은 다음과 같은 모습을 가지게 됩니다. 재귀 알고리즘 피보나치 수열을 구현하는 가장 흔한 알고리즘은 재귀(recursion)를 사용하는 것입니다. 이 재귀 알고리즘의 시간과 공간 복잡도는 모
이번 포스팅에서는 데이터의 개수를 셀 때 매우 유용한 파이썬의 collections 모듈의 Counter 클래스에 대해서 알아보겠습니다. Counter 기본 사용법 collections 모듈의 Counter 클래스는 별도 패키지 설치 없이 파이썬만 설치되어 있다면 다음과 같이 임포트해서 바로 사용할 수 있습니다. Counter 생성자는 여러 형태의 데이터를 인자로 받는데요. 먼저 중복된 데이터가 저장된 배열을 인자로 넘기면 각 원소가 몇 번씩 나오는지가 저장된 객체를 얻게 됩니다. Counter 생성자에 문자열을 인자로 넘기면 각
파이썬의 내장 자료구조인 사전(dictionary)를 사용하다 보면 어떤 키(key)에 대한 값(value)이 없는 경우에 대한 처리를 해야 할 때가 많죠? 이번 포스팅에서는 이러한 경우 일반적으로 어떻게 처리하는지 살펴보고, 관련해서 파이썬에서 제공하는 몇 가지 접근법에 대해서 알아보도록 하겠습니다. 일반적인 사전 기본값 처리 그럼 파이썬에서 사전을 다룰 때 어떤 경우에 기본값 처리가 필요한지 간단한 실습을 통해 알아보겠습니다. 단어가 주어졌을 때 각 알파벳에 대한 글자의 수를 세어서 사전에 저장해주는 함수를 작성해볼께요. 그럼
파이썬에서 힙(heap)이나 우선순위 큐(PriorityQueue)를 사용하다 보면 다음과 같은 에러를 만날 수 있습니다. 이번 포스팅에서는 위 에러를 해결하는 방법에 대해서 알아보록 하겠습니다. 객체 정렬 기준 힙과 우선순위 내부적으로 이진 트리를 이용해서 데이터를 정렫된 상태로 유지하고 있습니다. 그런데 이 정렬이라는 게 가능하려면 원소 간의 대소 비교가 가능해야합니다. 예를 들어, 숫자나 문자와 같은 기본형 데이터는 대소 비교가 간단합니다. 1보다 2가 크고, a보다 b가 크다는 것은 일반적으로 알려진 사실이기 때문에 자료구조
데이터를 정렬된 상태로 저장하기 위해서 사용하는 파이썬의 PriorityQueue(우선순위 큐)에 대해서 알아보겠습니다. 우선순위 큐 자료구조 우선순위 큐는 데이터를 추가한 순서대로 제거하는 선입선출(FIFO) 특성을 가진 일반적인 큐의 자료구조와 달리, 데이터 추가는 어떤 순서로 해도 상관이 없지만, 제거될 때는 가장 작은 값을 제거하는 독특한 특성을 지닌 자료구조입니다. 이 말은 내부적으로 데이터를 정렬된 상태로 보관하는 메커니즘이 있다는 뜻이고, 좀 더 구체적으로 얘기하면 heapq 모듈을 통해 구현되어 있습니다. 파이썬의 h
데이터를 정렬된 상태로 저장하기 위해서 사용하는 파이썬의 heapq(힙큐) 내장 모듈에 대해서 알아보겠습니다. 힙 자료구조 heapq 모듈은 이진 트리(binary tree) 기반의 최소 힙(min heap) 자료구조를 제공합니다. 자바에 익숙하신 분이라면 PriorityQueue 클래스를 생각하시면 이해가 쉬우실 것 같습니다. min heap을 사용하면 원소들이 항상 정렬된 상태로 추가되고 삭제되며, min heap에서 가장 작은값은 언제나 인덱스 0, 즉, 이진 트리의 루트에 위치합니다. 내부적으로 min heap 내의 모든 원
enumerate() 내장 함수에 리스트를 넘기면 next() 메서드가 index와 value로 이뤄진 튜플을 반환합니다. 따라서 다음과 같이 for 루프를 돌릴 때 enumerate()를 조합해서 사용하면 인덱스와 값을 동시에 접근할 수 있습니다. 추가로, enumerate() 내장 함수를 호출할 때 start 파라미터를 사용하면 0이 아닌 다른 시작 번호를 사용할 수 있습니다.
파이썬에 기본적으로 내장되어 있는 데이터베이스인 sqlite3 모듈를 사용하는 방법에 대해서 알아보겠습니다. 자바스크립트에서 SQLite 데이터베이스를 사용하는 방법에 대해서는 관련 게시물을 참고 바랍니다. 데이터베이스 접속 sqlite3 내장 모듈을 임포트 후에 connect 메서드를 통해 커넥션 객체를 생성합니다. 메모리 DB 접속 (일회성) 파일 DB 접속 테이블 생성 커서 객체를 받아와서 execute 메서드로 CREATE TABLE 쿼리를 전송합니다. 데이터 삽입 마찬가지로 커서 객체로 작업합니다. 기본 String Que
파이썬에 내장된 random 모듈은 랜덤 숫자를 생성 뿐만 아니라 다양한 랜덤 관련 함수를 제공합니다. 모듈 임포트 우선 random 모듈을 사용하려면 임포트해야 합니다. random() 함수 0부터 1사이의 랜덤 실수를 리턴합니다. uniform() 함수 2개의 숫자 사이의 랜덤 실수를 리턴합니다. randint() 함수 2개의 숫자 사이의 랜덤 정수를 리턴합니다. (2번째 인자로 넘어온 정수도 범위에 포함시킴) randrange() 함수 range(start, stop, step) 함수로 만들어지는 정수 중에 하나를 랜덤하게 리
이번 포스팅에서는 파이썬에서 진수를 다루는 여러 가지 방법에 대해서 알아보겠습니다. 다른 진수의 형태로 숫자를 표현하기 파이썬에서는 기본적으로 10진수 형태로 숫자를 표현하기 때문에 다른 진수의 형태로 숫자를 표현하려면 다음과 같이 숫자 앞에 접두어를 붙여줘야 합니다. 2진수: 0b 8진수: 0o 16진수: 0x 해당 진수에서 허용하는 범위에서 벗어난 숫자를 사용하면 SyntaxError가 발생하니 주의해야 합니다. 숫자에서 다른 진수의 문자열로 변환하기 파이썬은 bin(), oct(), hex()라는 내장 함수를 제공합니다. 이
이번 포스팅에서는 가장 유명한 정렬 알고리즘 중 하나인 퀵 정렬(Quick Sort)에 대해서 알아보겠습니다. 알고달레에서 코딩 테스트/인터뷰 준비에 좀 더 특화된 컨텐츠를 만나보세요! 📝 기본 컨셉 병합 정렬과 마찬가지로 퀵 정렬도 분할 정복 (Devide and Conquer) 기법과 재귀 알고리즘을 이용한 정렬 알고리즘입니다. 쉬운 이해를 위해서 다음과 같이 1부터 7까지 총 7개의 숫자가 들어있는 배열을 기준으로 설명하겠습니다. 항상 정 가운데를 기준으로 분할을 하는 병합 정렬과 달리, 퀵 정렬은 흔히 피봇(pivot)이라
대표적인 O(logN) 알고리즘인 병합 정렬(Merge Sort)에 대해서 알아보겠습니다. 알고달레에서 코딩 테스트/인터뷰 준비에 좀 더 특화된 컨텐츠를 만나보세요! 📝 기본 컨셉 병합 정렬은 분할 정복 (Devide and Conquer) 기법과 재귀 알고리즘을 이용해서 정렬 알고리즘입니다. 즉, 주어진 배열을 원소가 하나 밖에 남지 않을 때까지 계속 둘로 쪼갠 후에 다시 크기 순으로 재배열 하면서 원래 크기의 배열로 합칩니다. 예를 들어, 다음과 같이 1부터 8까지 총 8개의 숫자가 들어있는 배열에 있다고 가정해보겠습니다. 먼
선택 정렬, 거품 정렬과 더불어 대표적인 O(N^2) 정렬 알고리즘인 삽입 정렬(Insertion Sort)에 대해서 알아보겠습니다. 알고달레에서 코딩 테스트/인터뷰 준비에 좀 더 특화된 컨텐츠를 만나보세요! 📝 기본 컨셉 삽입 정렬은 한마디로 표현하면 정렬 범위를 1칸씩 확장해나가면서 새롭게 정렬 범위에 들어온 값을 기존 값들과 비교하여 알맞은 자리에 꼽아주는 알고리즘입니다. 예를 들어, 다음과 같이 1부터 5까지 총 5개의 숫자가 들어있는 배열에 있다고 가정해보겠습니다. 맨 처음에는 첫번째 2개의 값만 정렬 범위에 포함시키고
선택 정렬(Slection Sort)과 더불어 대표적인 O(N^2) 정렬 알고리즘인 거품 정렬(Bubble Sort)에 대해서 알아보겠습니다. 알고달레에서 코딩 테스트/인터뷰 준비에 좀 더 특화된 컨텐츠를 만나보세요! 📝 기본 컨셉 거품 정렬은 큰 그림에서 보았을 때 뒤에서 부터 앞으로 정렬을 해나가는 구조를 가지고 있습니다. 즉, 맨 뒷자리에 제일 큰 값을 제일 뒤로 보내고, 제일 큰 값 바로 앞에 두번째로 큰 값을 보냅니다. 이를 위해 배열 내의 값들을 앞뒤로 서로 비교해서 자리를 바꾸는 작업을 지속적으로 수행해야 합니다. 이
정렬 알고리즘 중에서 가장 직관적이고 쉽게 구현이 가능한 선택 정렬(Selection Sort)에 대해서 알아보겠습니다. 알고달레에서 코딩 테스트/인터뷰 준비에 좀 더 특화된 컨텐츠를 만나보세요! 📝 기본 아이디어 선택 정렬은 알고리즘에 대해 배워본 적이 없는 사람도 쉽게 생각해낼 수 있는 정렬 알고리즘입니다. 왜냐하면 우리가 일상에서 무언가를 크기 순으로 나열할 때 흔히 사용되는 사고 방식이기 때문입니다. 예를 들어, 위와 같이 키를 알고 있는 네 친구들을 키 순으로 세우려면, 우선 4명의 키를 모두 비교하여 키가 제일 작은 1