본문 바로가기

Computer195

[알고스팟] 눈치게임 문제: 눈치게임 이 문제는 문제를 잘 이해하면 쉽게 풀 수 있다. 간단하게 생각하면 어떤 번호 순서에 가장 빨리 숫자를 말하는 사람(말하기 위해서 기다리는 시간이 짧은 사람)이 중복되는 것이 있는지 체크하면 된다. 문제를 잘 이해하는 것이 핵심 2016. 9. 26.
[알고스팟] 남극기지 > 최소신장트리 (MST) > 프림 알고리즘 문제: 남극기지 이 문제는 최소신장트리 문제이다. 각 기지를 연결하는 최소 신장 트리에서 각 기지간의 연결 거리 중 가장 큰 값을 찾으면 된다. 이전 포스팅 에서는 Kruskal 알고리즘을 이용해서 문제를 풀었었는데, 본 포스팅에서는 Prim 알고리즘을 이용해서 풀어보겠다. 프림 알고리즘은 다음과 같이 동작한다. 1) 시작점을 선택하고 시작점을 추가된 정점의 집합인 MST_V 에 추가한다. 2) MST_V에 속해 있는 정점과 그렇지 않은 정점 중 최소 간선을 가지는 정점을 MST_V에 추가한다. 3) 2)를 모든 정점이 MST_V에 들어가게 될 때까지 방복한다. 다음 그림에서 상세하게 설명한다. 다음은 PriorityQueue를 이용해서 구현한 버전이다. 다음은 정점을 추가할때 다른 정점들과의 거리의 최.. 2016. 9. 24.
[알고스팟] 남극기지 > 최소신장트리 (MST) > 크루스컬 알고리즘 문제: 남극기지 이 문제는 최소신장트리 문제이다. 각 기지를 연결하는 최소 신장 트리에서 각 기지간의 연결 거리 중 가장 큰 값을 찾으면 된다. 최소 신장 트리는 각 노드 들간의 거리 값이 주어졌을 때, 이 노드의 거리 값이 최소인 트리를 구성하는 것이다. 프림과 크루스컬 알고리즘이 있다. 이번 포스팅은 크루스컬 알고리즘으로 이 문제를 풀어 보겠다. 일단 크루스컬 알고리즘은 다음과 같이 동작한다. 1) 간선 중 비용이 적은 순으로 소트 2) 1)의 간선 중 사이클을 생성하는 간선을 제외하고 최소 비용의 간선을 추가 3) 2)를 반복함 다음은 WiKi의 내용이다. (크러스컬_알고리즘) 여기에서 핵심은 간선 추가하는데, 간선을 추가할때 Cycle이 생성되는지 확인하는 것이 필요하다. 이를 위한 방법 중 하나.. 2016. 9. 24.
[알고스팟] 신호 라우팅(ROUTING) - 시간초과 문제: 신호라우팅(ROUTING) 언어: 자바 이 문제는 다익스트라 알고리즘을 이용해서 풀면 된다. 다익스트라 알고리즘은 그래프가 주어졌을 때, 특정 시작점에서 도착점까지의 최소 비용을 구하는 것이다. 다익스트라 알고리즘에 대한 설명은 다음의 링크로 대체하겠다. 워낙 유명한 알고리즘이니 쉽게 찾을 수 있다. 링크1 링크2 이 문제는 다익스트라의 최소 비용 문제를 + 에서 *로 바꾼 것인데 이 문제는 시간과 메모리 제약을 해결하는 것이 문제이다. 일단 자바로 풀긴 푼것 같은데, 시간초과 오류가 발생한다. 자바로는 어떻게 더 최적화 할수 있을 것인지, 더 고민이 필요하다. 2016. 9. 17.
[알고스팟] 외판원 문제 1 (TSP1) 문제: TSP1, TSP2, TSP3 언어: 자바 난이도는 TSP1, TSP2는 중, TSP3는 상이다. TSP3는 풀지 못하였다. 외판원 문제(Traveling Salesman Problem) 은 NP-Hard로 유명한 알고리즘 문제이다. Wiki에도 정의 되어 있는데, 여러 푸는 방법이 기술되어 있어 참고할 만 한다. WiKi Link: Traveling Salesman Problem 정확한 해를 구하기 위해서는 모든 조합을 계산해 보는 brute force search 의 경우 실행 시간이 O(n!) 가 되어 실질적으로 사용이 불가능하게 된다. 개선된 버전은 Dynamic Programming 기법을 이용하는 것인데 이때 실행 시간은 O(n^2*2^n) 이 된다. 이번 포스팅에서는 dynamig p.. 2016. 9. 16.
[알고스팟] 외발 뛰기 문제: 외발뛰기언어: 자바 난이도는 중 정도 되는 듯 하다. 실행 시간 제약이 있어서 사용하는 알고리즘에 주의를 해야 한다. 처음에 사용했던 방법은 (0,0) 위치를 Queue에 삽입하고 1) Queue에서 위치를 하나 꺼내서 (n-1,n-1)에 도달하였는지 확인한다. 2) 1)에서 도달하지 않았으면 해당 위치에서 이동할수 있는 다음 위치를 계산하여 그 위치를 Queue에 넣는다. [1] 다음은 그 코드이다. 이 코드로 제출 하면 시간 초과가 발생한다. 최적화 할수 있는 방법이 없을까?연산을 줄이려면, 다음 위치가 방문 했었는지를 판단해서 방문하지 않았을 경우만 Queue에 넣으면 된다. 즉 어떤 위치를 Queue에 넣을때 이 위치를 Queue에 넣은 적이 있는지 flag를 두고 Queue에 넣은 적이 .. 2016. 9. 14.

티스토리툴바