본문 바로가기

알고리즘6

[boj-1504]특정한 최단경로 dijkstra 알고리즘을 사용하여 최단경로의 길이를 찾는 문제지만,특정 정점 두개(e1, e2)는 반드시 경유해야 함지나갔던 정점이나 간선을 다시 지나갈 수 있음이 두가지 조건이 추가된 문제였다. 시작점이 1이고 n이 도착점일 때, 이 두가지 조건을 만족하는 최단거리를 구해야 하는 것이 이 문제이다.처음에는 단순하게 문제를 3가지 작은 문제로 나누었다. 시작점 1부터 e1까지 dijkstra를 수행하여 e1까지의 최단경로를 찾음e1부터 e2까지 최단경로를 찾음. 이 때 전에 수행한 최단경로의 정보는 사용하지 않는다. 지나갔던 간선이나 정점을 다시 방문할 수 있으니까..마찬가지로 e2부터 도착점 n까지 dijkstra 수행..이렇게 했더니 당연 꽝... 빠뜨린 조건이 있나 이짓 저짓하면서 반례를 찾아보았.. 2017. 7. 31.
[graph]위상정렬 위상 정렬이란?DAG(Directed Acyclic Graph), 즉 방향 사이클이 없는 방향그래프에서 노드들의 순서화를 진행하는 것을 말한다. 즉 노드들간의 순서를 정렬한다는 의미이다. 위상정렬 알고리즘첫번째TopologicalSort(G) {for 1 to n{indegree가 0인 임의의 정점 u를 선택A[i] 2017. 7. 25.
[graph] BFS,DFS graph를 나타내는 2가지 방식인접 행렬(Adjacency matrix)nxn 형태의 행렬로 나타냄. M(i,j)는 정점 i와 j를 연결하는 간선이 존재한다는 의미가 된다. 무방향그래프라면 i와 j가 서로 연결된 상태이며 M(i,j)=M(j,i)인 상태이다.저장공간은 O(n^2)이며, 어떤 노드 v에 인접한 모든 노드를 찾는것은 행렬의 한 row를 전부 탐색하는 것과 같기 때문에 O(n)이고, 어떤 간선 E(u,v)가 존재하는지 확인하는 것은 M(i,j)를 확인하면 되므로 O(1)이다.인접 리스트(Adjacency list)정점 집합을 표현하는 하나의 배열과 각 정점마다 인접한 정점들의 연결리스트이다. 예를 들면 간선 E(1,2), E(1,5), E(5, 4)가 존재한다고 할 때 정점의 배열의 원소 중.. 2017. 7. 23.
[boj-4811]알약 나는 항상 보면 접근 자체를 복잡하게 생각하는 경우가 많다. 부족한 두뇌로 복잡한 계산을 생각하다보니 스스로 지쳐서 머리 회전이 멈추는 듯 하다. 재귀는 항상 기억할 것은, 상태공간트리를 그려가며 작은 sub-problem으로부터 base case를 먼저 생각하고 그 후 recursion case를 정해 나가는 것이다. 이 과정만 제대로 할줄 안다면 정말 완벽할텐데.. 어쨌든 문제는 다음과 같다. 70세 박종수 할아버지는 매일 매일 약 반알을 먹는다. 손녀 선영이는 종수 할아버지에게 약이 N개 담긴 병을 선물로 주었다. 첫째 날에 종수는 병에서 약 하나를 꺼낸다. 그 다음, 그 약을 반으로 쪼개서 한 조각은 먹고, 다른 조각은 다시 병에 넣는다. 다음 날부터 종수는 병에서 약을 하나 꺼낸다. (약은 한 .. 2017. 7. 15.