1. 문제 4195번: 친구 네트워크 (acmicpc.net) 4195번: 친구 네트워크 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진 www.acmicpc.net 친구관계인 간선이 주어질때마다 각 사람(노드)에 속한 집합의 크기를 구하는 문제 2. 풀이 이 문제가 어렵게 느껴지는 이유는 일단 노드 수가 주어지지 않는다.. 간선의 수 f만 주어지는데.. 이럴 경우 최대 노드 수는 2f개 일 것이다. 사실 최대 노드 수만 알아도 문제를 푸는데 상관이 없다. 왜냐하면 union이 일어날때마다 각 노드에 속한 집합의 크기만 구하면 되니까 parent = [..
1. 힙(heap) 프로그램 실행중에 내가 사용할 수 있는 메모리 양이 변할 수 있는 경우, 그 때 사용하는 메모리 공간을 힙이라고도 하는데.. 여기서는 자료구조를 말한다. 기본적으로 "완전 이진 트리"를 이용한 자료구조이다. 특히 "완전 이진 트리"에 있는 노드 중에서 키값이 가장 큰 노드나 가장 작은 노드를 찾기 위해 특별히 만든 자료구조 완전 이진 트리니까, n개의 노드가 주어진다면 길이 n+1의 단순 배열로 저장할 수 있다 처음에 만들때, 키값이 가장 큰 노드를 찾는 자료구조를 만들 것이냐, 키값이 가장 작은 노드를 찾는 자료구조를 만들 것이냐,를 정하고 들어간다. 2. 최대힙(max heap)과 최소힙(min heap) 2-1) 최대힙(max heap) 키값이 가장 큰 노드를 찾기 위한 완전 이..
1. 완전이진트리 기본 순회 3가지 다음과 같은 완전이진트리에서 전위순회, 중위순회, 후위순회를 구해본다면..? ##노드 번호로 순회함수 정의 ##완전이진트리의 왼쪽 자식은 2*v ##오른쪽 자식은 2*v+1 ##전위순회 def preorder(v): if v
1. 기본 union find 알고리즘의 문제점 기본적인 union find 알고리즘을 사용할 경우 union을 수행하면.. 예를 들어 최악의 경우 위와 같은 union이 형성될 수 있다. 1의 대표자를 찾을 때, 2번, 3번, 4번을 확인하고 나서야 5번을 확인하여 1의 대표자가 5이구나 라는 것을 알 수 있다 이렇게 구성되는 경우 노드의 개수가 v개이고 간선의 개수가 m개이면 최악의 경우 O(VM)이라는 비효율적인 알고리즘이 된다. 특히 모든 1,2,3,4,5의 루트 노드가 5번인데 굳이 하나씩 거슬러 올라가서 전부 확인해야하나? union 그래프가 위와 같이 구성된다면, 2,3,4의 루트 노드는 단 1번만 5를 검사하면 바로 알 수 있으므로 효율적이다. 2. 경로압축(path compression)..
1. 사이클 판별 서로소 집합 알고리즘은 무방향 그래프에서 사이클을 판별할 때 사용할 수 있다. 방향 그래프에서 사이클 여부는 DFS로 확인할 수 있다고 한다 핵심 원리는 union 연산이 그래프에서의 간선으로 표현될 수 있는데(두 노드를 합치므로) 간선을 하나씩 확인하면서 두 노드가 포함되어 있는 집합을 합치는 과정을 반복하는 것만으로 사이클을 판별할 수 있다. 2. 알고리즘 2-1) 각 간선을 확인하면서 두 노드의 루트 노드를 확인 2-1-1) 루트 노드가 서로 다르다면, 두 노드에 대해 union 연산을 수행 2-1-2) 루트 노드가 서로 같다면 사이클이 발생 2-2) 그래프에 포함된 모든 간선에 대해 위 과정을 반복 3. 예시로 이해하는 사이클 판별 알고리즘 3-1) 초기 단계에서는 모든 노드에 ..
1. 그래프 기본 개념 간단히 복습 크루스칼 알고리즘 >>> 그리디 알고리즘 위상 정렬 알고리즘 >>> 큐, 스택자료구조를 이용 ---------------------------------------------------------------- 그래프(graph)란 노드(node)와 노드 사이 연결된 간선(edge)의 정보를 가지고 있는 자료구조 알고리즘 문제를 풀 때, "서로 다른 개체(객체)가 연결되어있다"라고 한다면 그래프 알고리즘을 가장 먼저 떠올려야한다. 예를 들어 "여러개의 도시가 연결되어 있다"라고 한다면 그래프 알고리즘을 의심할 필요가 있다 ----------------------------------------------------------------- 그래프 자료구조 중 트리 자료구조..
딥러닝/머신러닝, 통계학, IT프로그래밍, 알고리즘을 좋아하는 사람 https://github.com/yundaehyuck
