분류 전체보기
-
[Python] 너비 우선 탐색 (Breadth-First Search, BFS)언어/파이썬 & 장고 2021. 5. 31. 16:43
BFS란? BFS는 너비 우선 탐색 (Breadth-First Search)로 그래프 탐색 알고리즘 중 하나입니다. 정점에서 같은 레벨에 있는 자식 또는 형제들을 탐색하면서 내려가는 알고리즘입니다. 자세한 내용은 https://brownbears.tistory.com/395 에서 설명이 되어 있습니다. 예제 아래와 같은 그래프가 있다고 가정합니다. 이 그래프를 BFS 알고리즘을 사용하여 모든 노드를 방문한다면 아래와 같은 구조로 탐색을 하게 됩니다. 이러한 그래프를 만들기 위해 아래와 같은 형태로 주어졌다고 가정합니다. graph = { 'A': ['B', 'F', 'I'], 'B': ['A', 'E', 'C'], 'C': ['B', 'E', 'D'], 'D': ['C', 'G', 'H'], 'E': [..
-
[Design Pattern] 옵저버 패턴 (Observer Pattern)공부/디자인 패턴 2021. 5. 22. 22:44
옵저버 패턴이란 한 객체의 상태가 변경이 되면 해당 객체를 의존하고 있는 모든 객체에게 의존하고 있는 객체의 상태가 변경되었다고 알려주는 디자인 패턴입니다. 여기서 상태가 변경되었는지 관찰 대상 객체를 subject라 하고 이러한 변경을 관찰하는 객체를 observer라 합니다. 즉, observer 객체들은 subject에 의존성을 갖습니다. subject 객체를 관찰하여 변경을 감지하고자 하는 객체를 observer로 등록하고 변경이 되었을 때, 이를 탐지할 수 있습니다. 이해하기 쉬운 예제를 들면, 유튜브를 생각하면 됩니다. a라는 유튜브 채널(subject)을 A, B, C 라는 사람이 구독을 하게 되면(observer) 해당 채널에 새로운 영상이나 글이 올라올 경우(객체의 상태 변경), 해당 유..
-
[Python] 최단 경로 알고리즘 - 다익스트라 알고리즘 (Dijkstra Algorithm)언어/파이썬 & 장고 2021. 5. 16. 18:49
최단 경로 알고리즘이란 주어진 노드와 간선(edge)들 중, 가장 짧은 경로를 찾는 알고리즘입니다. 즉, 서울에서 인천, 대전, 광주, 부산을 갈 수 있는 가장 짧은 경로를 찾는 것입니다. 최단 경로 문제는 아래와 같이 3가지로 주어질 수 있습니다. 특정 노드에서 시작해 특정 노드까지 도착하는 가장 짧은 경로 특정 노드에서 시작해 모든 노드까지 도착할 수 있는 가장 짧은 경로 위 예시처럼 서울에서 시작해 서울-인천, 서울-대전, 서울-광주, 서울-부산 간 가장 짧은 거리를 찾는 문제 여기서 이동 경로가 양수라 하면 Dikjstra 알고리즘이고 음수를 포함한다면 Bellman-ford 알고리즘 모든 노드에서 도착할 수 있는 가장 짧은 경로 (floyd 알고리즘) 여기서 다익스트라 알고리즘은 2번에 해당되는..
-
[Django] select_for_update를 사용해 안전하게 데이터 수정하기언어/파이썬 & 장고 2021. 5. 16. 16:20
아래에서 설명할 때 사용한 장고는 1.11 버전입니다. 테이블이 아래와 같이 있다고 가정합니다. 아직 사용하지 않은 토큰을 유저가 사용했을 때, 해당 row에 유저의 id를 입력하도록 만든 테이블입니다. 이를 위해 아래와 같이 프로그래밍을 했다고 가정합니다. from datetime import datetime class UserToken(models.Model): id = models.BigAutoField(primary_key=True, db_column='id') token = models.UUIDField() user_id = models.BigIntegerField() updated_at = models.DateTimeField(auto_now=True) class Meta: managed = ..
-
[Design Pattern] 책임 연쇄 패턴 (Chain of Responsibility Pattern)공부/디자인 패턴 2021. 5. 15. 19:13
클라이언트에게 어떠한 요청이 들어왔을 때, 요청을 받은 객체가 해당 요청을 해결할 수 없을 경우 연결된 다음 객체들에 전달하고 해당 요청을 해결할 수 있는 객체가 처리하는 방식입니다. 요청 객체와 처리 객체를 분리하거나 요청을 처리할 수 있는 객체가 여러 개인데 하나의 객체에 요청을 보낼 때 책임 연쇄 패턴을 적용할 수 있습니다. 즉, 요청을 처리할 수 있는 객체가 여러개이고 이러한 처리를 하는 객체가 명시적이지 않을 때 사용할 수 있는 패턴입니다. 클래스 다이어그램 Handler: 요청을 처리하기 위한 객체들이 가질 인터페이스 ConcreteHandler1, 2: 요청 종류에 따라 자신이 처리 할 수 있는 부분을 구현한 객체 Client : 수신자에게 처리 요청 장점 요청의 발신자와 수신자를 분리시킬 ..
-
[Design Pattern] 프록시 패턴 (Proxy Pattern)공부/디자인 패턴 2021. 5. 9. 20:13
프록시 패턴이란 프록시 의미 그대로 실제 기능을 수행하는 주체(RealSubject)를 바로 호출하는 대신 대리자(Proxy)를 거쳐서 호출하는 것입니다. 즉, 클라이언트 → 실제 기능을 담당하는 객체 가 아닌, 클라이언트 → 프록시 객체 → 실제 기능을 담당하는 객체의 흐름으로 진행됩니다. 클래스 다이어그램 장점 실제 기능을 담당하는 객체의 리소스가 무거운 경우, 프록시 객체에서 간단한 처리를 하거나(클라이언트의 요청에 대한 유효성 검사를 통해 유효한 경우만 메인 객체 호출) 캐싱 처리를 통해 부하를 줄일 수 있습니다. 앞에서 설명한 간단한 처리를 통해 보안의 역할을 가질 수 있습니다. 단점 아무래도 클라이언트 - 메인 객체 사이에 프록시 객체가 끼어있는 상황이기에 응답이 느리거나 에러를 발생할 수도 ..
-
[Python] Heap과 heapq 모듈언어/파이썬 & 장고 2021. 5. 2. 18:59
heap 에 대한 설명은 https://brownbears.tistory.com/391에서 했지만 여기서는 더 자세하게 설명을 합니다. Heap은 최댓값, 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안되었으며 완전 이진 트리 (Complete Binary Tree)를 기본으로 가집니다. 즉, 데이터가 입력이 되면 가장 말단에서 왼쪽부터 차례대로 채워져 나갑니다. 최대 힙(max heap)은 부모의 노드가 자식 노드의 값과 같거나 더 크며 최소 힙(min heap)은 부모의 노드가 자식 노드의 값과 같거나 더 작습니다. 힙과 이진 탐색 트리 (binary search tree)이 쉽게 헷갈리는데 이진 탐색 트리의 경우, 부모 노드의 값보다 작으면 왼쪽, 크면 오른쪽 이라는 규칙이 있지만 힙의 경우엔 없습..
-
[Python] 양, 음의 무한대 표시언어/파이썬 & 장고 2021. 5. 2. 16:09
파이썬에서 양의 무한대, 음의 무한대를 표시는 다음과 같습니다. int타입의 양, 음의 무한대 파이썬 3에서는 아래와 같이 int 형의 무한대를 표시할 수 있습니다. import sys max_int = sys.maxsize min_int = -(sys.maxsize + 1) # 9223372036854775807 # 9223372036854775808범위를 정확하게 할 필요가 없다면 음의 무한대에 1을 추가할 필요가 없습니다. float타입의 양, 음의 무한대 float 타입의 무한대를 표시하는 방법은 두 가지가 존재합니다. math 모듈 사용 import math max_float = math.inf min_float = -math.inf # inf # -inffloat 내장함수 사용 max_floa..
-
[Django] prefetch_related 동작과 자동 쿼리 생성 조건 알아보기언어/파이썬 & 장고 2021. 5. 1. 20:44
먼저 아래에서 사용하는 장고의 버전은 Django 1.11.5 으로 현재 최신 버전인 3.2와는 동작이 다를 수 있습니다. 기본 조건 예시 모델 class Coupon(models.Model): coupon_no = models.BigAutoField( db_column='coupon_no', primary_key=True ) coupon_name = models.CharField( db_column='coupon_name', max_length=200 ) is_deleted = models.CharField( db_column='is_deleted', max_length=1, ) ... class CouponApplyBrand(models.Model): cou..
-
[PostgreSQL] VacuumDB/PostgreSQL 2021. 4. 4. 18:41
pg에서는 주기적인 Vacuum이 필요합니다. Vacuum은 진공 청소기라는 뜻 그대로 더이상 사용하지 않는 데이터를 정리해주는 역할을 합니다. 즉, 디스크 조각 모음과 같습니다. pg는 다중 버전 동시성 제어(MVCC)를 지원하기 때문에 데이터의 삭제, 수정이 발생하면 더이상 사용하지 않는 여러 버전의 데이터가 존재합니다. 만약 Vacuum을 진행하지 않으면 이러한 데이터가 지속적으로 쌓여서 실제 테이블 데이터 자체는 적은데 테이블의 사이즈는 어마어마하게 커지는 것을 볼 수 있습니다. 이런 테이블은 당연히 조회 속도가 느려집니다. 또한 데이터베이스의 나이가 줄지 않아 트랜잭션 ID 겹침 현상이 발생해 auto vacuum이 freeze 상태에서 멈출 수 있습니다. 이러한 현상이 지속되면 트랜잭션 ID를..