728x90 Quality control (Univ. Study)/Algorithm Design40 Algorithm Design - Genetic Algorithm GAGA(Genetic Algorithm)는 이름 그대로 유전의 개념을 기본 개념으로 디자인된 알고리즘이다.생물은 생존과 번식에 이로운 방향으로 진화하는데 이 컨셉을 알고리즘에 갖고 온 것이다. 따라서 GA도 시간이 흐를수록 정답에 접근한다. 실제 유전학에서 T,A,C,G, DNA, RNA등이 있듯이 유전알고리즘에서도 염색체, 적응도(fitness), 교차(crossover), 돌연변이(mutation)등의 개념이 존재한다. 과정을 한번 살펴보자.1. 어떤 문제의 답이 될 수 있는 후보를 인코딩 (인코딩 결과는 일종의 디지털 염색체)임의의 염색체들 집합을 생성(population)2. 가장 적응도가 높은 것을 선택(selection)3. 교배 시킴(crossover)4. 돌연변이 (mutation) 유전.. 2024. 6. 16. 알고리즘 설계 실습 - Dijkstra algorithm 문제상원이는 네비게이션 개발자입니다. 상원이는 사용자들이 다양한 경로로 가기를 원해서 가장 빠르게 갈 수 있는 최단 경로가 아니라, k번째로 빠르게 갈 수 있는 경로를 구해서 사용자들에게 제 하려합니다. n개의 위치와 m개의 도로에 대한 정보가 주어졌을 때, k번째로 빠르게 도착할 수 있는 경로를 구하는 프로그램을 작성하세요.입력첫째 줄에 n, m, k가 주어집니다. (1≤n≤1,000, 0≤m≤250,000, 2≤k≤50) n과 m은 각각 위치들의 개수와, 위치 간에 존재하는 도로의 수입니다. 이어지는 m개의 줄에는 각각 도로의 정보를 제공하는 세 개의 정수 a, b, c가 주어집니다. 이것은 a번 위치에서 b번 위치로 이동하는 도로를 사용할 때, c의 시간이 걸린다는 의미입니다. (1≤a, b≤n,.. 2024. 6. 5. Algorithm design - P-NP P-NP problemP-NP problem의 P는 polynomial-time algorithm의 P이고 polynomial-time algorithm은 입력의 크기가 n일 때, 최악의 경우 수행시간이 W(n)∈O(p(n))인 알고리즘을 뜻한다. 여기서 p(n)은 n의 다항 함수이다. 예를 들어 아래와 같은 알고리즘들이 존재한다.정렬문제: Θ(nlogn)정렬된 배열 검색 문제: Θ(logn)행렬곱셈 문제: Θ(n^2.38) NP는 Nonpolynomial이 아니라 Nondeterministic Polynomial이다. 이는 nondeterministic한 guessing으로 해답을 추측하고 해당 답이 정답인지 검증하는 과정이 polynomial하다는 것이다.변환(reduction)을 통해 알고 있는 문.. 2024. 6. 4. 알고리즘 설계 실습 - DFS와 BFS 문제그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하세요. 단, 방문 할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료하세요. 정점 번호는 1번부터 N번까지입니다. 입력첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점 의 번호 V가 주어집니다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어집니다. 어 떤 두 정점 사이에 여러 개의 간선이 있을 수 있습니다. 입력으로 주어지는 간선은 양방향입니다. 출력첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력하세요. V부터 방문된 점을 순서대로 출.. 2024. 5. 30. Algorithm design - 최단경로 Dijkstra가중치가 있는 그래프에서 한 시작 정점에서 다른 모든 정점까지의 최단 거리를 계산하는 데 사용되는 알고리즘이다. 아래와 같이 정의된다고 했을 때 알고리즘의 작동 과정을 살펴보자.S: 최단경로가 발견된 정점들의 집합weight[i, j] : 아크 의 가중치Dist[i]: S에 속하지 않은 i에 대해서, v에서 시작하여 S에 있는 정점만을 거쳐 정점 i에 이르는 최단 경로의 길이 1. 처음 S에는 시작점 v만 포함, Dist[v]=02. 가장 최근에 S에 첨가한 정점을 u로 설정3. u의 모든 인접 정점 중에서 S에 포함 되지 않은 w에 대해 Dist[w]를 다시 계산Dist[w]=min{Dist[w],Dist[u]+weight[u,w]}4. S에 포함되지 않은 모든 정점 w중에서 dist[w.. 2024. 5. 30. Algorithm design - MST 신장 트리신장 트리(spanning tree)는 무향그래프 G=(V,E)에서 V는 그대로 두고 간선을 |V|-1개만 남겨 트리가 되도록 만든 것이다. DFS,BFS에사용된 간선 집합 T는 그래프 G의 신장 트리를 의미한다. 주어진 그래프 G에 대한 신장 트리는 유일하지 않다.MSTMST는 최소 비용 신장 트리(minimum cost spanning tree)의 준말이다. 신장트리가 되는 G의 부분그래프 중에서 가중치가 최소가 되는 부분그래프를 최소비용신장트리(MST, minimum spanning tree)라고 한다. 여기서 최소의 가중치를 가진 부분그래프는 반드시 트리가 되어야 한다. 왜냐하면, 만약 트리가 아니라면, 순환경로(cycle)가 있을 것이고, 그렇게 되면 순환경로 상의 하나의 이음선을 제거.. 2024. 5. 28. Algorithm design - BFS / DFS GraphGraph는 현상이나 사물을 정점(vertex)과 간선(edge)으로 표현한 것이다. Graph G = (V, E)으로 표현이 되고 이때 V는 정점 집합 E는 간선 집합이다. 두 정점이 간선으로 연결되어 있으면 인접하다고 한다. 인접은 adjacent라고 하고 간선은 두 정점의 관계를 나타낸다. 간단한 예시를 통해 다양한 그래프를 살펴보자.인간관계를 그래프로 표현한 그래프다.간선에 weight가 생겨 관계의 깊이를 표현한 그래프다.방향을 고려한 유향 그래프이다.두 요소가 결합된 가중치를 가진 유향 그래프이다. 이러한 그래프 구조를 traversal하는 대표적인 두가지 기법 BFS, DFS를 살펴보자.BFSBFS는 너비 우선 탐색(breadth first search)의 준말이다. 말그대로 한 정.. 2024. 5. 28. 알고리즘 설계 실습 - 최적 경로 찾기 문제n(2 ≤ n ≤ 100)개의 도시가 있습니다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 m(1 ≤ m ≤ 100,000)개의 버스가 있습니다. 각 버스는 한 번 사용할 때 필요한 비용이 있습니다. 모든 도시의 쌍 (A, B)에 대해서 도시 A에서 B로 가는데 필요한 비용의 최솟값을 구하는 프로그램을 작성하세요. 입력첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어집니다. 그리고 셋째 줄 부터 m+2줄까지 다음과 같은 버스의 정보가 주어집니다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어집니다. 버스의 정보는 버스의 시작 도시 a, 도착 도시 b, 한 번 타는데 필요한 비용 c로 이루어져 있습니다. 시작 도시와 도착 도시가 같은 경우는 없습니다. 비용은 100보다.. 2024. 5. 23. Algorithm design - TSP(Traveling Salesperson Problem) 오일러오일러(Leonhard Euler, 1707 - 1783)는 일생동안 800편에 육박하는 논문을 냈다고 하는데 그만큼 다양한 주제에 화두를 던진 학자이다. 그가 제시한 유명한 내용중 하나가 오일러 경로와 순회이다.오일러 경로(Euler tour(path)): 어떤 그래프의 모든 간선을 정확하게 한 번씩만 지나가는 경로오일러 순회(Euler cycle(circuit)): 어떤 그래프의 모든 간선을 정확하게 한 번씩만 지나 시작점으로 다시 돌아오는 경로다시 말해 오일러 순회는 시작점과 끝점이 똑같은 오일러 경로이다. 한붓그리기의 대표적인 예시인 쾨니히스베르크 다리 건너기 문제가 유명하다.TSP해밀턴 경로(Hamiltonian Circuit)는 모든 정점을 한 번씩만 방문하고 시작점으로 돌아오는 경로를 .. 2024. 5. 21. 이전 1 2 3 4 5 다음 728x90
