1. 실제 최단 경로 역추적 지금까지 다익스트라 알고리즘에선 최단 경로로 가는데 걸리는 가중치의 합을 구해왔는데, 실제 최단 경로가 궁금할 수도 있다 어떻게 하면 구할 수 있을까? 결론부터 말하자면 경로를 역추적해서 구한다 어떤 정점 A에서 목적지 B로 가는데, "A,C,D,E,F,G,B로 가는게 최단 경로다" 이렇게 순방향으로 구하지 않고, 다익스트라 알고리즘에서 테이블에서 최단 거리를 가진 정점 u를 선택할때, u와 인접한 정점 b를 선택하는데, b의 거리가 테이블에서 갱신될때 "b와 가장 가까운 정점이 u이다"라고 테이블에 저장을 해놓는다 모든 과정이 종료되면 목적지 B와 가장 가까운 정점이 G이고, G와 가장 가까운 정점이 F이고 F와 가장 가까운 정점이 E이고, ... C와 가장 가까운 정점이 ..
1. 개요 선택 정렬은 실제 사용하기에는 매우 느린편이다. 그렇다면 다른 접근 방법은 없을까? "데이터를 하나씩 확인하면서 각 데이터를 적절한 위치에 삽입하면 어떨까?" 삽입 정렬은 선택 정렬처럼 동작 원리를 직관적으로 이해하기 쉽지만, 구현 난이도가 더 어려운데, 하지만 선택 정렬에 비해 실행 시간 측면에서 효율적이라고 알려져있다 특히 삽입 정렬은 필요할 때만 위치를 바꾸므로 "데이터가 거의 정렬되어 있을때" 매우 효율적이다 선택 정렬은 현재 데이터의 상태와 상관없이 무조건 모든 원소를 비교하고 위치를 바꾸는 반면, 삽입 정렬은 그렇지 않다 삽입 정렬은 특정한 데이터를 적절한 위치에 삽입한다는 의미에서 삽입 정렬(insertion sort)이라고 부른다. 더불어 삽입 정렬은 특정한 데이터가 적절한 위치..
1. 개요 인접한 두개의 원소를 비교하면서 자리를 계속 교환하면서 정렬하는 알고리즘 첫번째 원소부터 인접한 원소끼리 계속 자리를 교환하면서 맨 마지막 자리까지 이동 한 단계가 끝나면, 가장 큰 원소가 마지막 자리로 이동함 교환하면서 자리를 이동하는 모습이 물 위에 올라오는 거품 모양과 같다고 하여 버블 정렬이라고 부름 2. 예시를 통해 이해하는 버블 정렬 55, 7, 78, 12, 42를 정렬한다고 생각해보자. 먼저 55와 7을 비교하여, 55가 더 크니까 자리를 바꾼다. 다음 55와 78을 비교하여, 78이 더 크니까 자리를 바꾸지 않는다. 다음 78과 12를 비교하여 78이 더 크니까 자리를 바꾼다 마지막으로 78과 42를 비교하여, 78이 더 크니까 자리를 바꾼다. 그러면 배열에서 가장 큰 원소인 ..
1. 정렬(sorting) 데이터를 특정한 기준에 따라서 순서대로 나열하는 것 프로그램에서 데이터를 가공할 때 오름차순이나 내림차순 등 대부분 어떤 식으로든 정렬해서 사용하는 경우가 많기에, 정렬 알고리즘은 프로그램을 작성할 때 가장 많이 사용되는 알고리즘 중 하나 정렬 알고리즘으로 데이터를 정렬하면, 이진 탐색(binary search)이 가능해진다. 즉, 이진 탐색의 전처리 과정이기도 하다. 정렬을 공부하다보면 알고리즘의 효율성을 쉽게 이해할 수 있어 상황에 적절하지 못한 정렬 알고리즘을 이용하면, 당연히 프로그램은 비효율적으로 동작하면서, 필요 이상으로 시간을 많이 소요 여기 숫자 카드 10장이 있다. 7, 5, 9, 0, 3, 1, 6, 2, 4, 8 어떻게 이 카드를 정렬할 수 있을까? 보통은 ..
1. 문제 1504번: 특정한 최단 경로 (acmicpc.net) 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 1번부터 n번까지 최단 경로로 이동하고 싶은데, 특정한 정점 v1,v2를 반드시 거쳐서 최단 경로로 가고 싶다면 어떻게 해야할까? 2. 풀이 다익스트라는 어떤 정점에서 나머지 정점까지 도달하는 최단 경로를 제공하는데, 여기 중간에 어떤 정점을 거칠지는 말해주지 않는다... 근데 어떤 정점을 반드시 거쳐가게 할려면 어떻게 해야할까? 생각보다 간단하다 1번..
1. 문제 4195번: 친구 네트워크 (acmicpc.net) 4195번: 친구 네트워크 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진 www.acmicpc.net 친구관계인 간선이 주어질때마다 각 사람(노드)에 속한 집합의 크기를 구하는 문제 2. 풀이 이 문제가 어렵게 느껴지는 이유는 일단 노드 수가 주어지지 않는다.. 간선의 수 f만 주어지는데.. 이럴 경우 최대 노드 수는 2f개 일 것이다. 사실 최대 노드 수만 알아도 문제를 푸는데 상관이 없다. 왜냐하면 union이 일어날때마다 각 노드에 속한 집합의 크기만 구하면 되니까 parent = [..
딥러닝/머신러닝, 통계학, IT프로그래밍, 알고리즘을 좋아하는 사람 https://github.com/yundaehyuck
