김머성 블로그

[Spanning Tree]

스패닝 트리란:: 1. 그래프에서 최소 간선만을 사용하여 그래프의 모든 정점을 잇는 부분 그래프이다. 즉 v - 1개의 간선을 사용해 모든 정점을 이어야 하며 내부 사이클이 없어야한다. 2. 한국말로 신장트리 최소 비용 스패닝 트리 1. 간선에 가중치가 주어졌을 때 스패닝 트리를 완성하면서 최소비용을 구하는 알고리즘을 말한다. 2. 문제는 대부분 이걸로 나온다. 구현:: 최소 비용 스패닝 트리를 구축하는 방법은 2가지가 있다. 1. 정점 위주 연결 ㄱ. 시작 정점에 이어진 정점중 비용인 최소이고 연결되지 않은 정점을 하나 골라 연결하고 [연결된 정점]으로 분류한다. ㄴ. [연결된 정점]에 이어진 정점 중 하나를 골라 연결하고 [연결된 정점]으로 분류한다. v - 1개의 [연결된 정점]이 추가 될 때 까지..

[기타] 라인 스윕

위처럼 위치가 표시되어이있는 직선에 임의의 점 2개를 찍고 직선을 긋는다. 직선끼리 일부분이 겹칠 수도 있다. 총 N개의 직선을 그었을 때 그어진 선의 전체 길이를 구하는 문제이다. 간단하게 직선마다 배열에 1을 찍으며 길이를 구할 수도 있지만 그렇게 하면 선분의 수가 많아졌을 때 매우 비효율적인 알고리즘이 되어버린다. 극단적인 예를 들었을 때 위 문제의 최대 데이터가 +-10,0000이고 길이 최대인 선분 1,0000개를 그린다고 하면 총 20,0000,0000번 반복하는 알고리즘이 되어버리는 것이다. 위 문제는 대부분 주어지는 N과 전체 구간의 크기가 크기 때문에 O(n) 복잡도를 가지도록 구현 해야한다. a. 기본 개념 풀이 직선의 양 끝단을 받을 때 a가 b보다 작다면 a와 b를 바꿔 저장한다. ..

[DP] DDR

[문제 출처 : 하늘바다 컴퓨터 학원 수지점] 요즘 원장님의 고민은 뱃살을 뺴는 것이다. 친구에게 DDR게임을 하면 뱃살이 빠진다는 말을 듣던 그 날부터 DDR게임을 하루도 빼먹지 않고 열심히 하고 있다. 하지만 워낙 몸이 무거워 게임을 잘 하지는 못한다. 그럼에도 불구하고 원장님은 살을 뺄 수 있다는 일념으로 게임을 아주 열심히 하고 있다. DDR게임의 게임판 모양은 아래 그림과 같다. 시작은 두발을 모두 중앙(0의 위치)에서 모으고 있다가 게임이 시작되면, 지시에 따라 왼쪽,또는 오른쪽 발을 움직인다. 하지만 두 발이 동시에 움직이지는 못한다. 이게임에는 이상한 규칙이 하나 더있다. 시작할 때를 제외하고 두 발이 같은 지점에 있는 것을 허락하지 않는 것이다. 만약, 한 발이 1의 위치에 있고, 다른 ..

[DP] 주식투자

우선 동적 계획법은 현업에서 가장 안쓰이는 알고리즘 중 하나이다. 하지만 DP를 활용한 모든 문제가 사고력을 바탕으로 풀도록 설계된 문제가 많기 때문에 대회 입상에서는 가히 필수적이라고 말 할 수 있겠다. 동적 계획법은 분할 정복이다. 문제를 재귀적 구조를 가진 작은 문제들로 분할을 한 뒤, 그 답을 이용해 더 큰 문제의 답을 찾아 나가는 식으로 푸는 문제이다. 쪼갠 작은 문제와 합쳐진 문제 사이의 관계를 [점화식]이라고 하며 이 식을 찾는 것이 DP문제의 핵심이다. 예제 문제를 통해 DP 알고리즘을 작성하고 점화식이 무엇인지 더 정확하게 알아보겠다. 1. 투자 첫줄에 돈 M과 회사수 N이 주어진다. 이후에 M줄에 걸쳐서 N번째 회사에 투자했을 때 얻을 수 있는 수익금이 주어진다. 해당 정보를 가지고 최..

[Dijkstra] 거리간 최단거리

다익스트라란:: 가치 그래프에서 임의의 두 정점간의 최단 거리를 찾아내는 알고리즘이다. 기본적으로 n제곱 알고리즘이며 최소힙을 사용해 과정을 줄이면 n log n까지 최적화가 가능하다. 모든 최단 경로는 정점과 정점 사이에 있는 정점들의 최단거리로 이루어져 있다는 것을 이용해 정점간의 1차적인 최단 거리를 계산하고 새로운 정점에 이어보며 최종적인 최단거리 여부와 거리값을 계산한다. 의사코드:: 1. 현재 정점에서 미방문이며 가장 짧은 거리를 가지고 있는 정점 X를 정한다.(정해지면 X는 방문한 정점으로 표시한다) 2. 정점 X에서 갈 수 있는 정점들을 탐색하며 다음 조건을 만족하는 정점들을 탐색한다. ::현재 정점까지의 거리 > 현재 정점에서 X까지의 거리 + X에서 탐색한 정점까지의 거리 3. 2에서 ..

플로이드

for(i=0;i 1 + 1 ->3 반복문 : 간접경로 이거 인덱스 헷갈리지 말고 잘 적어야 한다.