[알고리즘] Traveling Salesman Problem

Traveling Salesman Problem은 NP 알고리즘 중 하나로 최적의 경로를 찾기 위해서는 2n의 시간이 필요합니다 따라서 최적의 해가 아닌 approximate(근사해)를 통해 접근하도록 한다 1. Traveling Salesman Problem (TSP) 여행자가 임의의 한 도시에서 출발하여 다른 모든 도시를 1번씩만 방문하고 다시 출발한 도시로 돌아오는 여행 경로의 길이를 최소화하는 문제이다 A에서 B까지의 경로는 B에서 A까지의 경로가 같다는 대칭성 A에서 B로 가는 거리는 A에서 C를 경유하여 B로 가는 거리보다 짧다는 삼각 부등식의 특성 2. 문제 해결을 위한 아이디어 주어진 여행 장소를 MST(최소 신장 트리)로 나타내어 모든 점을 연결한다 TSP를 만들기 위해 MST의 경로를 ..

• format_list_bulleted Computer Science/Data Structure & Algorithm
• · 2023. 12. 2.
• textsms

[알고리즘] 모든 쌍에 대한 최단 경로 구하기

최단 경로를 구하는 알고리즘을 이용하여 모든 쌍에 대해 최단 경로를 구하도록 코드를 구현해보자 1. Dijkstra 알고리즘 이용 다익스트라 알고리즘은 Greedy 알고리즘을 이용하여 현재 선택된 정점 그래프에서 다음 노드까지의 가중치가 제일 적은 노드를 선택 > MST의 Prim's Algorithm과 유사 MST와 유사하지만 모든 정점을 시작 정점으로 선택하도록 반복해야함 거리와 방문 여부를 체크해야함 > 거리는 그래프 안에서 찾기 import time # 실 실행시간 측정을 위한 타임 모듈 추가 INF=int(1e9) # 무한대 설정 n, m = map(int, input().split()) # 정점의 개수(n), 간선의 개수(m) 입력 graph = [[INF] * n for _ in range(..

• format_list_bulleted Computer Science/Data Structure & Algorithm
• · 2023. 10. 31.
• textsms

[알고리즘] Merge Sort(합병 정렬)

오늘은 분할 정복을 사용하여 정렬하는 Merge Sort에 대해 알아보겠습니다 Merge Sort는 말 그대로 합치는 정렬입니다 각 부분을 합치는 과정 중에서 해당 값을 비교하여 작은 수와 큰 수를 정렬하는 방법입니다 분할 정복 (Divide and Conquer) 주어진 문제의 입력을 분할하여 작은 부분 문제로 만들고 해당 문제를 해결하여 마지막으로는 전체 문제를 해결하는 알고리즘 → 부분 문제로 나눌 수 없을 때까지 나누어 해결하여 큰 문제를 해결하는 방식 MergeSort의 경우 각 부분을 입력의 1/2로 나누어 총 분할 횟수는 log2n 입니다 위 그림처럼 자잘한 문제로 나누어 해당 문제를 풀어해결하는 알고리즘 합병정렬 (MergeSort) 병합 정렬이라고도 부르며 해당 정렬 알고리즘은 부분 문제..

• format_list_bulleted Computer Science/Data Structure & Algorithm
• · 2023. 10. 15.
• textsms

[알고리즘] Kruskal & Prim Algorithm in Python

Kruskal & Prim Algorithm을 Python으로 구현해보고 해당 알고리즘에 대해 분석해보자 Kruskal Algorithm 그래프 이론에서 사용되는 그래프 최소 신장 트리 (Minimum Spanning Tree,MST)를 찾는 알고리즘 중 하나 그래프의 모든 정점을 연결하면서 가중치가 작은 간선들로 이루어진 트리를 구성 간선의 가중치 기반 선택 사이클 방지 그리디 알고리즘 그래프의 모든 간선을 가중치 순으로 정렬 정렬된 간선 목록을 처음부터 순회하면서 사이클을 형성하지 않는 간선 선택 선택한 간선을 트리에 추가 > 해당 알고리즘을 통해 MST를 리턴 G = { 'vertices' : [], 'edges': [] } parent = dict() rank = dict() def initial..

• format_list_bulleted Computer Science/Data Structure & Algorithm
• · 2023. 10. 11.
• textsms

[알고리즘] 벨만-포드 알고리즘 vs 존슨 알고리즘

그래프에서 한 정점에서 다른 모든 정점으로의 최단 경로를 구하는 방법은 여러 가지가 있습니다. 그 중에서도 벨만포드 알고리즘과 존슨 알고리즘은 음의 간선이 포함된 그래프에서 최단 경로를 찾는 데 효과적인 두 가지 알고리즘입니다. 벨만-포드 알고리즘 벨만포드 알고리즘은 그래프의 모든 간선을 반복적으로 순회하면서, 해당 간선을 거쳐가는 경로의 거리가 현재까지 알려진 최단 거리보다 짧다면 최단 거리를 갱신하는 방식으로 최단 경로를 구합니다. def bellman_ford(graph, start): """ 그래프에서 한 정점에서 다른 모든 정점으로의 최단 경로를 구하는 알고리즘 Args: graph: 그래프 start: 출발 정점 Returns: 각 정점까지의 최단 경로 """ dist = [float("inf..

• format_list_bulleted Computer Science/Data Structure & Algorithm
• · 2023. 9. 21.
• textsms

[컴퓨터 구조] 명령어 집합

명령어는 컴퓨터가 작업을 하기 위해 필요한 언어로 명령어 집합에 대한 의미와 특성을 살펴보고 학습해보자 명령어 집합 명령어 집합의 의미 요즘의 대부분의 프로그램은 고급언어로 작성 → 컴파일러와 인터프리터를 통해 기계어로 변환하여 사용해야함 #1 명령어 cpu가 수행할 동작을 2진수 코드로 정의한 것 2진수코드 대신 연상 부호를 사용한 어셈블리 형태의 명령어로 표현 #2 명령어 집합 특정 cpu를 위해 정의된 명령어의 모음 명령어 집합 구조 (Instruction Set Architecture) 작성된 프로그램과 그 프로그램을 수행할 컴퓨터 하드웨어 사이의 인터페이스에 대한 완전한 정의 또는 명세 어떤 연산을 수행할 수 있고 어떤 데이터가 필요한 지 명시 사용할 수 있는 데이터의 표현 방식, 데이터 형식 ..

• format_list_bulleted Computer Science/Computer Architecture
• · 2023. 9. 6.
• textsms