훈훈훈

이번에는 이진 탐색 트리 개념과 이진 탐색 트리에서 최소합을 찾는 문제에 대하여 정리해보려고 한다. 이진 탐색 트리는 이진탐색과 연결리스트의 장점을 합친 개념으로 그림으로 간단히 그리면 아래와 같다. # 이진탐색트리 예시 이진 트리는 위 그림과 같은 형태로 표햔된다. 구조는 최상위 노드(위 그림에서는 8)를 기준으로 아래에 자식 노드가 존재 한다. 자식노드의 왼쪽은 노드 보다 작은 수, 오른쪽은 노드 보다 큰 수가 배치된다. 그리고 그 하위 노드들도 위와 같은 방법으로 중복 없이 정렬하면 트리가 완성된다. 이진트리는 중복 없이 최상위 노드를 기준으로 크기에 따라 정렬하기 때문에 효율적으로 탐색할 수 있다. 탐색 유형에는 총 3가지가 있으며 간단히 정의하면 아래와 같다. 1. 전위순회 : 부모 방문 -> ..

이번에는 페이지네이션에 대하여 정리해보려고 한다, 해당 기능을 설명하기 위해 회원 목록 조회 API를 예시로 설명하려고 한다. 회원 목록은 회원 수가 늘어날 수 록 계속 쌓이는 데이터이기 때문에 일정 개수 이상 조회 시, 다음 페이지로 넘어가서 조회하는 기능이 필요하다. 이때, 사용하는 기능이 페이지네이션이다. Django에는 페이지네이션 기능에 관련된 모듈을 제공하는 것으로 알고 있지만, 이번에는 모듈을 사용하지 않고 구현하려고 한다. 이제 아래 구현 코드를 살펴보자. # 구현 코드 class AccountList(View): def get(self, request): ''' 회원정보 리스트로 조회 ''' offset = int(request.GET.get('offset', 0)) limit = int..

이번에는 탐색 문제 유형 중 하나인 봉우리 개수 찾는 문제에 대하여 정리를 해보려고 한다, 문제는 다음과 같다. > N*N 격자판이 주어지고, 각각의 격자에는 높이가 들어가 있다. 각 격자를 기준으로 상하좌우를 비교했을 때 가장 큰 높이가 봉우리일 때, 봉우리 개수를 구하라. (단 격자판의 가장자리는 모두 0으로 초기화 한다.) # 접근 방법 위 그림과은 3*3 행렬이 주어진 후, 격자판 가장자리를 0으로 초기화 했을때의 그림이다. 2차원 배열을 탐색하는 문제이기 때문에 이중 for문으로 2차원 배열을 탐색한다. 배열의 각 요소를 탐색하면서 상하좌우로 크기 비교를 진행한다. 만약 matrix[i][j] 를 탐색한다고 했을때, matrix[i+1][j] matrix[i-1][j] matrix[i][j+1]..

이번에는 탐색 유령 중 하나인 너무 유명한 괄호 문제에 대하여 정리해보려고 한다. 문제는 다음과 같다. > 괄호로 이루어진 문자열이 주어지고, 짝이 맞으면 YES, 틀리면 NO를 반환, (단, 문자열의 길이는 6으로 가정한다.) # 접근 방법 접근 방법은 위 그림과 같다. 먼저 주어진 문자열의 처음 길이를 저장 후, 반복문을 돌려 짝이 맞는 괄호를 발견하면 공백으로 제거해주는 작업을 반복한다. 그 다음 처음 문자열 길이와 나중 문자열 길이를 비교 후 YES, NO를 판별한다. # 풀이 def check_func(values): answer = [] str_list = ['[]', '{}', '()'] # 인자로 받은 문자열로 이루어진 리스트 탐색 for element in values: first = 0..

이번에는 Django-mptt에 대하여 정리해보려고 한다. 해당 모듈을 사용하게된 계기는 ERD 설계 시, Categorya 항목들에 대하여 계층형으로 구성하기 위해 사용하게 되었다. 카테고리 항목들을 계층형으로 작성하는 이유는 다음과 같다. 만약 카테고리가 main, sub 두 가지로 구성이 되어 있다고 가정해보자, 이렇게 구축된 환경에서 category가 1개 2개 3개 늘어날 때마다 각각 독립적인 관계가 아니기 때문에 구조가 점점 복잡해지게 된다. 하지만 계층형으로 설계시 아래와 같이 만들 수 있으며, 확장에 용이하다. # 카테고리 예시 # 예제 코드 from mptt.models import MPTTModel, TreeForeignKey class Category(MPTTModel): name =..

이번에는 Django를 사용하여 crontab을 사용하는 방법에 대하여 정리하려고 한다. crontab을 사용하게된 계기는 매 특정 주기마다 가격이 변동시키고 싶어서 적용해보게 되었다. 이제 Django에서 crontab을 사용하는 방법에 대하여 알아보자 # 모듈 설치 pip install django-crontab 먼저 pip로 "django-crontab" 모듈을 설치하자 설치가 되면 아래와 같이 settings.py에 INSTALLED_APPS에 추가해주면 사용할 수 있다. # settings.py INSTALLED_APPS = [ 'django_crontab', ] # 매 3시간 마다 cron.py 실행 CRONJOBS = [ ('0 */3 * * *', 'my_cron.schedule_03hr_..

이번에는 Selected_related와 Prefetch_related에 대해 정리 해보려고 한다. Django ORM으로 DB에 쿼리 시 get, filter, all 이외에 Selected_related와 Prefetch_related를 적절히 사용하면 아주 강력한 무기가 될 수 있다. 이제 Selected_related와 Prefetch_related가 무엇인지 알아보도록 하자. Selected related # Selected_related 란 ? Selected_related는 SQL Query 문의 JOIN 을 사용하여 foreign-key(one to one, many to one)를 사용하여 정참조할 때 사용하며 QuerySet을 가져올 때, 미리 related objects까지 불러오는 ..

이번에는 알고리즘 유형 중 하나인 큐 유형에 대하여 정리 해보려고 한다. 문제 유형으로는 숫자로 이루어진 문자열과 임의의 숫자 m을 입력 받은 후 문자열에서 1부터 m 까지 카운트 하며, 차례대로 배열 뒤로 배치 후, m번째 있는 숫자를 제거하는 과정을 반복 수행하여 최종적으로 남은 숫자를 반환하는 문제이다. 아래 그림은 1 부터 8까지 숫자들을 정렬 후, 3번째에 위치한 숫자들을 차례대로 제거하는 로직이다. # 풀이 과정 큐는 자료구조는 FIFO(First in First out) 구조를 가지고 있기 때문에 리스트의 가장 앞에 있는 인덱스 부터 제거하는 해당 문제 유형에서 적용하기 알맞다. 파이썬에서는 deque라는 모듈을 지원하기 때문에 리스트 앞에 있는 인덱스를 제거할때는 popleft( ) 모듈을..