Leta Learns

문제 https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 처음에 Prim으로 풀었는데 예제만 맞고 또 일반화에 실패했다. ㅋㅋ 찾아보니까 Prim은 우선순위큐를 쓰더라고.. 복잡하길래 그냥 Kruskal로 풀었다. 유니온 파인드 공부해놨더니 별로 안 어려워서 풀만 했다. import sys input = sys.stdin.readline def find(a): if a == parent[a]: retu..

문제 https://www.acmicpc.net/problem/18126 18126번: 너구리 구구 텔레토비 동산에 사는 너구리 구구는 입구, 거실, 주방, 안방, 공부방, 운동실, 음악실, 음식 창고 등 N개의 방을 가지고 있다. 입구를 포함한 모든 방은 1부터 N까지의 번호가 있고, 입구는 1번이 www.acmicpc.net 일반적인 dfs 문제들과 비슷하다. 거리의 최댓값을 구해서 갱신해주기만 하면 되는 문제이다. 최댓값들을 리스트에 저장한 후 그 리스트에서의 최댓값을 출력하면 된다. 최댓값 저장할 때 뻘짓을 좀 했는데 2021.07.24 - [HUFS/HUFS 모각코 캠프] - [모각코] 210724 Today I Learned 여기에 그 내용을 자세히 적어놓았다. import sys sys.se..

1. Tree DP Tree : cycle이 없는 그래프 (서로 다른 두 노드를 잇는 길이 하나) => 그래프처럼 DP 기법 적용 가능 트리에서 DP는 서브트리에서 구한 해를 이용하여 전체 트리의 해를 구하는 방식으로 진행된다. 트리는 비선형 구조이므로 DP를 하기 전에 탐색 순서를 미리 정해주는 것이 일반적. => 보통 탐색 순서는 DFS를 돌면서 나오는 트리를 기준으로 함. 기본적으로 Top-down 방식으로 코드 작성. => 보통의 DFS처럼 leaf 노드까지 순회하고, leaf 노드의 값을 알아낸 뒤 상위 노드의 값들을 알아내는 방식. Tree DP 예제 https://www.acmicpc.net/problem/15681 15681번: 트리와 쿼리 트리의 정점의 수 N과 루트의 번호 R, 쿼리의 ..

문제 https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 모각코에서도 얘기했듯이 이번 문제는 m, n을 구별하는 게 어려웠다.. 선형대수학 공부해야되나봐... row, col 왜 이리 헷갈리지.. 어제 스터디 할 때 관련 얘기 해서 row랑 col에 대해서 10분 동안 토의했는데 꼭 잘 기억해야지.. 이 문제는 모각코 Today I Learned에서 이미 리뷰를 했기 때문에 조금만 더 덧대려고 한다. 2021.07.22 - [HUF..

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

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 중에서 사용된 간선들의 가중치 합이 최소인 트리 각 간선의 가중치가 상이할 때 단순히 간선 수를 가장 적게 사용한다고 해서 ..

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

문제 https://www.acmicpc.net/problem/5014 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net 1697번 숨바꼭질 문제랑 알고리즘이 거의 같았다. 2021.07.12 - [Coding/백준] - [Python] 백준 1697번 - 숨바꼭질 비슷한 구조의 bfs문제를 한 번 더 풀 수 있어서 bfs 이해하는데 더 도움이 됐다. count를 처음에는 그냥 변수로 만들어서 갱신해줬는데 그렇게 하다보니 갈라지는 부분이라고 해야하나... 쨌든 그런 곳에서 count가 여러 개로 나뉘어져야 하는데 변수 하나..