[알고리즘] 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

[백준] 2667 - 단지번호붙이기

문제 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. 는 을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오. 입력 첫 번째 줄에는 지도의 크기 N (정사각형이므로 가로와 세로의 크기는 같으며 5≤N≤25)이 입력되고 그 다음 N줄에는 각각 N개의 자료(0혹은 1)가 입력된다. 출력 첫 번째 줄에는 총 단지수를 출력하시오. 그리고 각 ..

• format_list_bulleted Problem Solving/C++
• · 2023. 11. 21.
• textsms

[프로그래머스] 이진 변환 반복하기

문자열 x 를 입력받아 이진 변환을 반복하여 걸리는 값을 출력 문제 설명 0과 1로 이루어진 어떤 문자열 x에 대한 이진 변환을 다음과 같이 정의합니다. x의 모든 0을 제거합니다. x의 길이를 c라고 하면, x를 "c를 2진법으로 표현한 문자열"로 바꿉니다. 예를 들어, x = "0111010"이라면, x에 이진 변환을 가하면 x = "0111010" -> "1111" -> "100" 이 됩니다. 0과 1로 이루어진 문자열 s가 매개변수로 주어집니다. s가 "1"이 될 때까지 계속해서 s에 이진 변환을 가했을 때, 이진 변환의 횟수와 변환 과정에서 제거된 모든 0의 개수를 각각 배열에 담아 return 하도록 solution 함수를 완성해주세요. 제한 사항 s의 길이는 1 이상 150,000 이하입니다..

• format_list_bulleted Problem Solving/Python
• · 2023. 11. 13.
• 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

[프로그래머스] k번째 수 in python

입력받은 배열의 i번부터 j번 안에서 k번째로 작은 수를 출력하는 프로그램을 작성하는 문제 1. 문제 설명 배열 array의 i번째 숫자부터 j번째 숫자까지 자르고 정렬했을 때, k번째에 있는 수를 구하려 합니다. 예를 들어 array가 [1, 5, 2, 6, 3, 7, 4], i = 2, j = 5, k = 3이라면 array의 2번째부터 5번째까지 자르면 [5, 2, 6, 3]입니다. 1에서 나온 배열을 정렬하면 [2, 3, 5, 6]입니다. 2에서 나온 배열의 3번째 숫자는 5입니다. 배열 array, [i, j, k]를 원소로 가진 2차원 배열 commands가 매개변수로 주어질 때, commands의 모든 원소에 대해 앞서 설명한 연산을 적용했을 때 나온 결과를 배열에 담아 return 하도록 ..

• format_list_bulleted Problem Solving/Python
• · 2023. 10. 27.
• 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