Adore__

Source: inflearn 'Do it! 알고리즘 코딩테스트 with python' ▪️트리의 특징 트리는 그래프의 형태 중 하나로, 다음과 같은 특징이 있다. 순환구조(cycle) 이 없고, 1개의 root node 가 존재한다 root node를 제외한 노드는 단 1개의 부모 노드를 갖는다. subtree 또한 트리의 모든 특징을 따른다. 연결된 트리에서 임의의 두 노드를 이어주는 경로는 유일하다 그래프 트리 방향성 방향, 무방향 방향만 존재 사이클 순환, 비순환, 자기순환 비순환만 허용 루트 노드 루트 개념이 없다. 한개의 루트만 존재 부모-자식 관계 이런 개념이 없다 1개의 부모노드에여러개의 자식 노드 가능 단, 각 자식 노드는 하나의 부모노드만 가짐 모델 네트워크 모델 계층모델 간선 수 제한..

Source: inflearn 'Do it! 알고리즘 코딩테스트 with python' 최소 신장 트리란, 그래프의 모든 노드를 한번씩 방문할 때, 거쳐가는 edge들의 가중치의 합이 최소가 되도록 하는 트리이다. ▪️특징 - 트리이므로 사이클을 포함하지 않는다. (만약 모든 노드를 연결해서 순환되는 구조가 만들어지면, 최소의 가중치가 될 수 없다. 하나의 엣지를 제거하더라도 모든 노드를 거치는 경로를 만들 수 있기때문이다.) - N개의 node가 있으면, MST를 구성하는 edge의 수는 N-1개이다. - 구현하는 방법은 크루스칼 / 프림 알고리즘이 있다. * 크루스칼 알고리즘 * 프림 알고리즘 크루스칼은 처음부터 모든 간선의 가중치를 오름차순으로 정렬한 후에 작은 가중치의 간선부터 연결하지만, 프림 ..

Source: inflearn 'Do it! 알고리즘 코딩테스트 with python' Union-Find는 말 그대로 두개의 연산으로 구성되어 있는 알고리즘이다. ▪️수학적 연산 기법 ▷ Union 연산: 각 node가 속한 집합을 1개로 합치는 연산. node a, b가 각각 집합 A,B에 속할 때, union(a,b)는 A U B를 말한다. 우리가 집합연산에서 배웠던 합집합과 같다. ▷ Find 연산: 특정 노드 a가 속한 집합의 대표 node를 반환해준다. 노드 a가 A집합에 속할 때, find(a) 는 A집합의 대표 노드(루트 노드)를 반환한다. ▪️그림으로 과정 이해하기 union-find는 집합을 표현하는 배열, 리스트, 트리로 표현할 수 있지만, 우선 빠른 이해를 위해 1차원 배열로 살펴보..

Source: inflearn 'Do it! 알고리즘 코딩테스트 with python' 최단 거리를 구하는 알고리즘으로, 특정 노드에서 다른 노드까지 최단 거리는 몇인가?라는 문제에서 사용한다. 딴, edge의 가중치가 양수여야 한다. 기능 특징 시간 복잡도(node:V, edge:E) 출발 노드에서 모든 노드간의 최단 거리 탐색 Egde의 가중치는 모두 양수여야 한다. O(E*logV) ▪️과정 1. 인접 리스트로 그래프 구현 인접 행렬도 가능하지만, 시간복잡도를 고려할 때 N의 크기가 커지는 것을 방지하기 위해 인접 리스트를 선택하자. 2. 최단 거리 배열 초기화 최단거리를 저장해주는 배열을 노드 개수만큼 만든다. 에서 출발하므로 노드1까지의 최단거리는 0, 그리고 나머지 노드들의 최단거리는 무한대(..

Source: inflearn 'Do it! 알고리즘 코딩테스트 with python' 그래프의 기본 그래프란 노드와 노드 사이에 연결된 간선의 정보를 가지고 있는 자료구조를 말한다. 즉, 두 노드가 연결되어 있으면 그래프라고 말할 수 있다. 먼저 그래프의 종류를 한번 쭉 훑고 가보자 그래프 종류 개념 그림 유니온 파인드 그래프 문제에서는,사이클이 생성되는지 판별하는 알고리즘이다. 위상 정렬 이 알고리즘을 사용하기 위해서는 선 조건이 있다. 1) 전후관계가 있어야 한다. 2) 즉, 방향이 있는 그래프여야 한다. 3) 이를 위해서는 사이클이 없어야 한다 이 조건에서 그래프의 각 노드를 선형으로 정렬해주는 알고리즘이다. 단, 위상 정렬로 나오는 값이 유일하지 않다는 특징이 있다. ex) 수강신청 - 수1을 ..

Source: inflearn 'Do it! 알고리즘 코딩테스트 with python' 4장은 정수론이다 이 부분은 손으로 직접 써보고 풀어보는 것이 더 효과적인 것 같아서 필기로 대체한다. 글씨체를 좀 예쁘게 쓰고 싶은데 어렵다하핫 1) 소수 구하기 우리가 잘 아는 '소수'를 구하는 알고리즘이다. '소수'란, 약수를 1과 자기자신 만 갖는 수를 말한다. 이를 판별하는 방법으로 가장 대표적인 것이 '에라토스테네스의 체' 이다. 구하고자 하는 범위만큼 배열을 생성한 후, 각 숫자의 배수를 지워가다보면 남은 수는 소수들 뿐이다. 이 지우는 과정때문에 시간 복잡도는 O(Nlog(logN))을 갖는다. 2) 오일러 피 오일러피 함수는 1~N까지 수에서 N과 서로소인 자연수의 개수를 말한다. P[6] = 2의 뜻..