불곰 불곰

언어

• [Python] 깊이 우선 탐색 (Depth-First Search, DFS)

  언어/파이썬 & 장고 2021. 6. 5. 22:29

  DFS란? DFS는 깊이 우선 탐색 (Depth-First Search)로 그래프 탐색 알고리즘 중 하나입니다. 정점에서 자식들을 우선으로 탐색하는 알고리즘입니다. 자세한 내용은 https://brownbears.tistory.com/395 에서 설명이 되어 있습니다. 예제 아래와 같은 그래프가 있다고 가정합니다. 이 그래프를 DFS 알고리즘을 사용하여 모든 노드를 방문한다면 아래와 같은 구조로 탐색을 할 수 있습니다. 무조건 아래와 같은 결과가 나온다고 보장은 할 수 없습니다. (주어진 그래프(연결 노드의 순서)에 따라 방문 순서는 달라질 수 있습니다.) 여기선 방향을 아래, 왼쪽, 오른쪽 우선순위로 진행했는데 아래, 오른쪽, 왼쪽 순으로 진행해도 괜찮습니다. 아래 예시에서는 아래, 오른쪽, 왼쪽 의 ..

• [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': [..

• [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 = ..

• [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..

• [Java] 람다식 표현 (Lambda Expression)

  언어/Java 2021. 4. 4. 00:04

  자바 8에서 도입된 개념으로 함수를 변수처럼 사용하는 사용하는 개념입니다. 함수를 변수처럼 사용하므로 파라미터로 다른 메소드에 전달할 수도 있고 반환값으로 함수를 받을 수 있습니다. 자바에서 람다식은 다른 스크립트 언어처럼 완전한 함수형 프로그래밍 방식은 아닙니다. 인터페이스 형식을 빌려서 람다식을 표현하기 때문에 함수형 프로그래밍의 장점을 완벽하게 가지지 못합니다. 장단점은 아래에서 설명합니다. 사용법 (매개변수1, 매개변수2, ...) -> {실행문...}매개변수의 이름은 자유롭게 정할 수 있고 타입을 명시하지 않아도 됩니다. -> 는 실행문에서 좌변에 설정한 값들을 보내 사용한다 라고 이해하면 쉽습니다. 예시 예시를 하기 위해 사전에 아래와 같은 코드가 작성되어 있다고 가정합니다. @Function..

• [Java] Optional

  언어/Java 2021. 3. 14. 22:52

  Optional 클래스는 객체를 포장해주는 래퍼 클래스로 모든 타입의 참조 변수를 담을 수 있습니다. Optional 객체를 사용하면 복잡한 조건문 없이 NullPointerException (;NPE) 예외 처리를 할 수 있습니다. 생성 Optional 객체 생성은 .empty(), .of(), .ofNullable() 이 있습니다. .of() 메소드를 사용해서 객체를 생성할 때, 인자값으로 null이 전달된다면 NPE가 발생하므로 null이 입력될 수도 있다면 안전하게 ofNullable() 메소드를 호출하는 것이 좋습니다. Optional op1 = Optional.empty(); // Optional.empty - null을 담고 있는 빈 객체 Optional op2 = Optional.ofNul..

• [Python] divmod를 사용해 몫과 나머지 구하기

  언어/파이썬 & 장고 2021. 3. 1. 20:45

  divmod 모듈을 모른다면 몫과 나머지를 구하는 로직은 아래와 같습니다. # 몫 s = a // b # 나머지 r = a % b위와 같이 구하는 것도 좋지만 divmod를 사용하여 계산할 수도 있습니다. s, r = divmod(a, b) s, r = divmod(11, 3) # 3, 2divmod가 편해보여서 평상시에 사용해도 크게 상관은 없지만 처리 속도가 아주 중요한 프로그램에서는 사용에 지양해야 합니다. 계산하고자 하는 숫자가 작을 경우, divmod 보다 직접 연산자를 사용해서 계산하는 방식이 더 빠릅니다. 반대로 숫자가 크다면 divmod를 사용하는 것이 더 빠르게 처리됩니다. import timeit timeit.timeit('divmod(n, d)', 'n, d = ..