분류 전체보기
-
[Python] 최단 경로 알고리즘 - 플로이드-워셜 알고리즘 (Floyd-Warshall Algorithm)언어/파이썬 & 장고 2021. 6. 6. 20:07
플로이드 워셜 알고리즘은 다익스트라 알고리즘과 같이 최단 경로를 구하는 알고리즘입니다. 차이점은 다익스트라 알고리즘의 경우, 특정 노드에서 이동할 수 있는 모든 노드에 대해 최소 거리(이 때, 거리(edge)는 양수여야 함)를 구하는 거고 플로이드-워셜 알고리즘은 모든 노드에서 도착할 수 있는 모든 노드의 최소 거리를 구하는 알고리즘입니다. 또한 거리(edge)가 양수 뿐만 아니라 음수여도 사용할 수 있습니다. (다익스트라 알고리즘 설명: https://brownbears.tistory.com/554) 즉, 다익스트라 알고리즘은 서울에서 시작해 인천, 목포, 강릉의 최소 거리를 구하는 것이고 플로이드 워셜 알고리즘은 서울-인천, 서울-목포, 서울-강릉, 인천-목포, 인천-강릉 과 같이 모든 쌍을 한번에 ..
-
[Design Pattern] 템플릿 메소드 패턴 (Template Method Pattern)공부/디자인 패턴 2021. 6. 6. 18:13
템플릿 메소드 패턴이란 여러 클래스에서 공통적으로 호출, 사용하는 메소드들을 상위 클래스에서 정의하고 이 상위 클래스를 상속 받은 하위 클래스에서 세부 동작을 구현하는 패턴을 말합니다. 이는 객체 지향 언어로 개발할 때, 해당 패턴을 알지 못해도 많이 사용하고 접하는 패턴입니다. 템플릿 메소드 패턴을 사용하면 중복 코드를 제거할 수 있고 상속을 받은 하위 클래스의 역할이 줄어 로직 관리가 편합니다. 하지만 추상 메소드가 많아진다면 클래스의 관리가 복잡해 진다는 단점이 있습니다. 클래스 다이어그램 예제 예를 들어, 아래와 같이 공항에 도착해 티켓을 발권받는 과정을 코딩한다면 아래와 같습니다. public class IncheonAirport { public void check() { checkPasspor..
-
[Python] 깊이 우선 탐색 (Depth-First Search, DFS)언어/파이썬 & 장고 2021. 6. 5. 22:29
DFS란? DFS는 깊이 우선 탐색 (Depth-First Search)로 그래프 탐색 알고리즘 중 하나입니다. 정점에서 자식들을 우선으로 탐색하는 알고리즘입니다. 자세한 내용은 https://brownbears.tistory.com/395 에서 설명이 되어 있습니다. 예제 아래와 같은 그래프가 있다고 가정합니다. 이 그래프를 DFS 알고리즘을 사용하여 모든 노드를 방문한다면 아래와 같은 구조로 탐색을 할 수 있습니다. 무조건 아래와 같은 결과가 나온다고 보장은 할 수 없습니다. (주어진 그래프(연결 노드의 순서)에 따라 방문 순서는 달라질 수 있습니다.) 여기선 방향을 아래, 왼쪽, 오른쪽 우선순위로 진행했는데 아래, 오른쪽, 왼쪽 순으로 진행해도 괜찮습니다. 아래 예시에서는 아래, 오른쪽, 왼쪽 의 ..
-
[Design Pattern] 데코레이터 패턴(Decorator Pattern)공부/디자인 패턴 2021. 5. 31. 21:37
데코레이터 패턴이란 어떤 객체에 상황과 용도에 따라 새로운 책임을 추가하는 형식입니다. 객체에 기능을 동적으로 추가하여 서브 클래스를 생성하는 것보다 유연하게 기능을 확장할 수 있습니다. 클래스 다이어그램 Component: ConcreateComponent와 Decorator를 위한 인터페이스. ConcreteComponent: 기능 추가를 받을 기본 객체 Decorator: 기능 추가를 할 객체를 위한 추상 클래스 ConcreteDecorator: Decorator를 상속받아 구현할 객체. ConcreteComponent에 추가하기 위해 생성 예제 카페를 차려서 커피를 팔게 되어 아래와 같이 메뉴를 구성했습니다. public interface Beverage { int getCost(); String..
-
[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)를 거쳐서 호출하는 것입니다. 즉, 클라이언트 → 실제 기능을 담당하는 객체 가 아닌, 클라이언트 → 프록시 객체 → 실제 기능을 담당하는 객체의 흐름으로 진행됩니다. 클래스 다이어그램 장점 실제 기능을 담당하는 객체의 리소스가 무거운 경우, 프록시 객체에서 간단한 처리를 하거나(클라이언트의 요청에 대한 유효성 검사를 통해 유효한 경우만 메인 객체 호출) 캐싱 처리를 통해 부하를 줄일 수 있습니다. 앞에서 설명한 간단한 처리를 통해 보안의 역할을 가질 수 있습니다. 단점 아무래도 클라이언트 - 메인 객체 사이에 프록시 객체가 끼어있는 상황이기에 응답이 느리거나 에러를 발생할 수도 ..