Leta Learns

Union - Find (합집합 찾기) 대표적인 그래프 알고리즘 상호 배타적 집합 (Disjoint-Set) 알고리즘 (서로소 집합) 여러 개의 노드가 존재할 때 두 개의 노드를 선택하여, 이 두 노드가 서로 같은 그래프에 속하는지 판별 2가지 연산으로 이루어져 있다. Find : x가 어떤 집합에 포함되어 있는지 찾는 연산 Union : x와 y가 포함되어 있는 집합을 합치는 연산 그림으로 이해하기 모두 연결되지 않고 각자 자기 자신만을 집합의 원소로 가지고 있을 때, 모든 값이 자기 자신을 가리키도록 만든다. i : 노드번호 P[i] : 부모 노드 번호 ( => 자기 자신이 어떤 부모에 포함되어 있는지를 의미, parent) 지금 현재는 모든 값이 자기 자신을 가리키므로 P[i] = i 이다. Uni..

https://www.acmicpc.net/problem/7576 요새 dfs, bfs를 공부 중이었는데 익숙치 않아서 한 문제 푸는데 2-3일 걸리고 그랬다. 이 문제도 일요일에 처음 풀었는데 못 풀어서 모각코 때 다시 풀어야지. 하고 다른 공부했다. bfs는 그냥도 어려운데 이번 문제는 다른 문제들과 달리 n, m 으로 입력받는 게 아니라 m, n으로 입력 받아서 헷갈렸다. 그거 뭐 얼마나 바뀌었다고 헷갈리냐고 하면.. 할 말이 없다. 저는 코딩 바보예요. 종이에 계속 쓰면서 n이 row고, m이 col이다 라는 걸 계속 상기시켜주었다. 1. 기본 틀은 다른 bfs 문제들이랑 거의 비슷했는데 이 문제에서 좀 특별한? 점은 q.popleft()하기 전에 range(len(q))로 for문을 돌려준 것이..

4. User 모델 확장 장고의 기본 User 모델은 실제 서비스에서 사용하기에는 매우 한정적이다. 따라서 필요한 부분을 User 모델에 추가해 줄 것이다. 장고의 User 모델을 확장하기 위해 AbstractUser 클래스를 상속하였다. account/models.py from django.db import models from django.contrib.auth.models import AbstractUser # Create your models here. class CustomUser(AbstractUser): nickname = models.CharField(max_length=100) university = models.CharField(max_length=50) location = models..

1. 새로운 account 프로젝트 세팅 account 앱 생성 (기존의 blog앱과 분리하기 위해) python manage.py startapp account 앱을 추가했으니 settings.py에 새 앱을 알려주어야 한다. INSTALLED_APPS = [ 'django.contrib.admin', 'django.contrib.auth', 'django.contrib.contenttypes', 'django.contrib.sessions', 'django.contrib.messages', 'django.contrib.staticfiles', 'blog', 'account', ] account/urls.py 정의 from django.urls import path from . import views ..

Kruskal Algorithm : 그리디 방법을 사용하여 그래프의 모든 정점을 최소 비용으로 연결하는 최적 해답을 구하는 것 각 단계에서 사이클을 이루지 않는 최소 비용 간선을 선택 간선 선택을 기반으로 하는 알고리즘 이전 단계에서 만들어진 신장 트리와 무관하게 무조건 최소 비용 간선 선택 Kruskal 알고리즘 과정 그래프의 간선들을 가중치를 기준으로 오름차순 정렬 정렬된 간선 리스트에서 순서대로 사이클을 형성하지 않는 간선 선택 -> 최소 가중치 먼저 선택, 사이클 형성하는 간선은 제외 해당 간선을 현재의 MST 집합에 추가 Kruskal 알고리즘 예 주의할 점 ! 간선을 선택할 때 사이클을 생성하는지 확인 => 추가할 간선의 양 정점이 같은 집합에 속하면 안 된다. 사이클 생성 여부 확인 방법 :..

Prim 알고리즘 대표적인 최소신장트리 알고리즘 ex) Prim, Kruskal 알고리즘 시작 정점에서부터 출발하여 신장 트리 집합을 단계적으로 확장하는 방법 정점 선택을 기반으로 하는 알고리즘 이전 단계에서 만들어진 신장 트리를 확장하는 방법 시작 정점을 선택한 후, 정점에 인접한 간선 중 최소 가중치로 연결된 정점을 선택. 해당 정점에서 다시 최소 가중치로 연결된 정점을 선택. => 그리디 알고리즘 Prim 알고리즘 예 임의의 정점을 선택. 연결된 노드 집합에 삽입. 현재 정점에 연결된 간선들을 간선 리스트에 삽입 간선 리스트에서 최소가중치를 가지는 간선 추출 추출한 간선은 간선 리스트에서 삭제 간선 리스트에 더 이상 간선이 없을 때 까지 3,4번 반복 3번 과정에서, if 해당 간선에 연결된 정점이..

Spanning Tree (신장 트리) : 그래프의 최소 연결 부분 그래프. 최소 연결 -> 간선의 수가 최소 n개의 정점을 가지는 그래프의 최소 간선의 수: n-1 n-1개의 간선으로 연결되어 있으면 필연적으로 트리 형태가 된다. => ST 즉, 그래프에서 일부 간선을 선택해서 만든 트리. Spanning Tree의 특징 하나의 그래프에는 여러 개의 신장 트리가 존재 가능. ST는 트리의 특수 형태 => 모든 정점들 연결 => 사이클 포함 x => N개의 정점을 정확히 n-1개의 간선으로 연결 Minimum Spanning Tree (최소 신장 트리) : Spanning Tree 중에서 사용된 간선들의 가중치 합이 최소인 트리 각 간선의 가중치가 상이할 때 단순히 간선 수를 가장 적게 사용한다고 해서 ..

장고 진도를 다 나가고 두 번째 과제가 주어졌다. 첫 번째 과제인 CRUD 과제 할 때는 티스토리를 안 하고 있었어서 그때 공부한 것들을.. 기록해 놓지 않았다.... 이번 과제부터... 열심히 기록해야지.... 이번 과제는 지난 번 과제로 만든 My Playlist 사이트에 Static, Media, Form , User Authentication 등을 이용해 로그인 한 사람만 글을 쓸 수 있는 기능 (접근 제한) 댓글 기능 추가 (로그인/로그아웃 무관) 블로그 전체적인 디자인하기 (CSS) 이 세 가지를 구현하면 된다. 1. Static, Media, NavBar 수정 지난 과제 때 home은 좀 꾸몄었다. 하이퍼링크 색도 바꾸고 이것저것.. 근데 이번 과제 하는 중에 그런 것들을 좀 날렸다. 뼈대 ..

문제 https://www.acmicpc.net/problem/17220 17220번: 마약수사대 최근들어 세계적으로 마약과 관련한 사회적 문제들이 많이 발생하고 있다. 이에 따라 경찰은 마약 수사대의 한정된 인력이 허용하는 선에서 최대한 마약공급을 막고자 한다. 마약 공급책들은 www.acmicpc.net dfs 골드3은 무리였나.. ㅋㅋㅋ 인접리스트 입력을 문자열로 받는 것부터가 어려워서 헤맸다. 아스키 코드 써서 간신히 해결. 2021.07.20 - [Python] - 아스키코드 변환 함수 ord(), chr() 유향그래프 문제도 거의 처음 푸는 것 같다. check에 맨 마지막 줄에서 입력 받은 2 b c 를 리스트로 넣고 인덱싱 사용해서 문제를 풀었다. check는 경찰이 소재를 파악하고 있기 ..

ord() : 문자열을 아스키 코드로 변환 chr() : 아스키 코드를 문자열로 변환