본문 바로가기
728x90
반응형

개발 일기58

자료구조 - 서로소 집합 1. 서로소 집합이란? 서로소 집합(Disjoint Set)이란 교집합이 공집합인 집합들의 정보를 확인(Find)하고 조작(Union)할 수 있는 자료구조이다. - Union 연산 : 어떤 두 원소 a, b에 대해서 union(a, b)는 각 원소가 속한 집합을 하나로 합치는 연산 - Find 연산 : 어떤 원소 a에 대해서 a가 속한 집합(집합의 대표번호)을 반환 2. 서로소 집합의 표현(Disjoint Set, Union-Find) 3. 서로소 집합의 구현 및 최적화 1) 초기화 : parent 배열에 i원소에 대한 부모 노드 번호를 저장, 루트 노드인 경우 자기 자신의 번호를 저장 function initialize() for i : 1 ~ N parent[i] = i 2) Union 연산 : 하나.. 2021. 2. 2.
알고리즘 - 에라토스네스의 체 알고리즘 - 에라토스네스의 체 1보다 큰 정수 p의 양의 약수가 1과 p뿐일 때 p를 소수라고 하며 1보다 큰 정수 n이 소수가 아닐 때 n을 합성수라고 한다. 에라토스네스의 체란, 고대 그리스의 수학자 에라토스테네스가 만들어 낸 소수를 찾는 방법이다. 마치 체로 치듯이 수를 걸러낸다고 하여 '에라토스테네스의 체'라고 부른다. 특정 숫자의 배수는 소수가 아니라는 법칙에 착안하여 2 ~ N까지의 숫자에서 숫자들의 배수를 모두 제거한 뒤 제거되지 않은 숫자를 소수로 판별하는 방식으로 프로그래밍에서는 상당히 효율적인 방법론이다. 배열을 생성하여 초기화한다. 2부터 시작해서 특정 수의 배수에 해당하는 수를 모두 지운다.(지울 때 자기자신은 지우지 않고, 이미 지워진 수는 건너뛴다.) 2부터 시작하여 남아있는 수.. 2021. 2. 2.
알고리즘 - 유클리드 호제법 알고리즘 - 유클리드 호제법 유클리드 호제법은 2개의 자연수의 최대공약수를 구하는 알고리즘의 하나이다. 2개의 자연수 a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면 (단, a>b) a와 b의 최대공약수는 b와 r의 최대공약수와 같다는 성질을 이용한다. 이를 사용해 최대공배수를 구할 수 있는데, 두 수의 곱을 유클리드 호제법으로 구한 최대공약수로 나누면 그것이 최대공배수이다. jina-developer.tistory.com/77 프로그래머스 Level 2 - N개의 최소공배수 [문제 설명] 두 수의 최소공배수(Least Common Multiple)란 입력된 두 수의 배수 중 공통이 되는 가장 작은 숫자를 의미합니다. 예를 들어 2와 7의 최소공배수는 14가 됩니다. 정의를 확장해서, n개의 수 .. 2021. 2. 2.
자료구조 - 그래프 1. 그래프란? 그래프(Graph)는 현실세계의 사물이나 개념 간의 연결 관계를 수학적 모델로 단순화 하여 표현한 것이다. 수학정 정의 : 정점 집합 V = {v1, v2, v2, ..., vn} 이고, 정점간의 연결 관계들을 나타내는 간선 집합 E = {(vi, vj)/vi ∈ V, vj ∈ V} ⊆ V x V 일 때, 그래프 G = (V, E) 이다. 2. 그래프 용어 1) 무향 간선 (Undirected Edge) - 정점을 연결하는 간선에 방향이 존재하지 않는다. - 임의의 간선 (vi, vj)에 대해서 (vi, vj) = (vj, vi)이다. 2) 유향 간선 (Directed Edge) - 정점을 연결하는 간선에 방향이 존재한다. - 임의의 간선 (vi, vj)에 대해서 (vi, vj) ≠ (v.. 2021. 2. 2.
알고리즘 - 너비 우선 탐색 (Breadth First Search) 알고리즘 - 너비 우선 탐색 (Breadth First Search) BFS는 Breadth First Search, 너비 우선 탐색이라고도 부르며, 가까운 노드부터 탐색하는 알고리즘이다. BFS 구현에서는 선입선출 방식인 큐 자료구조를 이용하는 것이 정석이다. 인접한 노드를 반복적으로 큐에 넣도록 알고리즘을 작성하면 자연스럽게 먼저 들어온 것이 먼저 나가게 되어, 가까운 노드부터 탐색을 진행하게 된다. [ BFS 활용 ] 최단경로 찾기, 위상정렬 등 [ pseudocode로 BFS 구현 ] BFS(G, s) for each vertex u ∈ G.V - {s} //초기화 작업 u.color = WHITE//s를 제외한 모든 정점의 상태를 white로, u.d = ∞//거리를 무한대로 u.𝝅 = NIL .. 2021. 1. 27.
알고리즘 - 깊이 우선 탐색 (DFS, Depth-First Search) 알고리즘 - 깊이 우선 탐색 (DFS, Depth-First Search) DFS는 Depth-First Search, 깊이 우선 탐색이라고도 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. 미로에서 갈림길로 돌아가서 길을 찾는 것을 생각하면 된다. DFS를 설명하기 전에, 먼저 그래프의 기본 구조를 알아야 한다. https://jina-developer.tistory.com/108 자료구조 - 그래프 1. 그래프란? 그래프(Graph)는 현실세계의 사물이나 개념 간의 연결 관계를 수학적 모델로 단순화 하여 표현한 것이다. 수학정 정의 : 정점 집합 V = {v1, v2, v2, ..., vn} 이고, 정점간의 연결 관계들을 jina-developer.tistory.com 모든 노드를 .. 2021. 1. 27.
728x90
반응형

티스토리툴바