본문 바로가기

알고리즘26

1504번 특정한 최단 경로 G4 문제는 간단하다. 1번 정점부터 N번 정점까지 최단 거리를 구하는데, U정점과 V정점을 반드시 거쳐야 하는 것이다. 일단 처음 문제를 보면 해당 정점까지의 최단 거리를 구하는 다익스트라를 떠올릴 수 있겠다. 그리고 정적으로 2정점을 지난다는 것이 조건이니 두 개의 정점을 지난다는 걸 구현하면 된다. 그렇다면 일단 1을 시작 정점으로 해서 모든 정점으로 향하는 최단 거리를 구하고, 또 U 정점을 시작정점으로 구하고, V 정점을 시작정점으로 구한 뒤, 1부터 U까지, U에서 V까지, V에서 N까지 최단 거리와 1부터 V까지, V에서 U까지, U에서 N까지 최단 거리를 비교한 후 최단 거리를 출력하면 되지 않을까? 생각했다. 여기서 중요한 것은 만약 1에서 부터 두 정점을 지나 N까지 가는 경우가 없다면 -1.. 2023. 4. 3.
1005번 ACM Craft G3 문제가 꽤나 길다. 간단하게 말하자면 해당 건물을 올리기 위해 먼저 다른 건물을 올려야 한다는 것이다. 하지만 여기서 특기할 점이 있다면 1번 건물을 짓고 동시에 2번과 3번 건물을 짓기 시작할 수 있다는 것이다. 따라서 4번 건물을 짓기 위해 필요한 시간은 1번 건물 10초 + 2번 건물 1초 + 3번 건물 100초 + 4번 건물 10초로 121초 가 아니라 1번 건물 10초 + (동시에 짓는 건물 중 오래걸리는 시간(2번, 3번))100초 + 4번 건물 10초로 120초이다. 이런 개념을 가지고 가면 간단하게 위상 정렬로 풀린다. 다른 건 다 위상정렬과 비슷하나 추가적으로 필요한 것은 최소의 시간을 기록할 DP 배열과 건물짓는데 걸리는 시간을 비교할 방법이다. DP[1] (1번째 값) 은 건물1의 건.. 2023. 4. 3.
2252번 줄 세우기 G3 문제의 내용은 위와 같다. 중요한 것은 N과 M을 입력 받은 후, M번 입력을 받는데, 그때 입력받는 두 번호가 비교하는 학생의 번호이고, 앞에 입력받는 번호의 학생이 뒤에 입력받는 학생보다 앞에 선다는 것이다. 즉 3 2 1 3 2 3 이면 1번 학생은 3번 학생의 앞에, 2번 학생은 3번 학생의 앞에 줄을 선다는 것이다. 1번과 2번 학생의 순서는 상관없으므로 답은 1 2 3 또는 2 1 3이 될 수 있다. 이를 위해 우선 Linked List배열을 생성한다. 이 때 받을 인자는 Integer이다. 그 후 N의 크기만큼의 배열을 생성하고, 각각 초기화를 시켜준다. 이후 순서 비교를 위해 입력받은 인자를 리스트에 입력한다. 순서를 정해준 것이기 때문에 유향 그래프라고 할 수 있다. 이런 느낌. 또한 학.. 2023. 4. 3.
위상정렬 위상 정렬이란 순서가 있는, 즉 방향이 있는 작업을 차례로 진행해야 할 때 순서를 결정해주기 위해 사용하는 알고리즘이다. 사이클이 없는 방향 그래프(DAG)의 모든 노드를 주어진 방향성에 어긋나지 않게 순서를 나열하는 것이 바로 위상정렬이다. 위상 정렬을 배우기 위해서는 우선 DAG(Directed Acyclic Graph)의 개념과 특정 노드로 들어오고 나가는 차수에 대한 개념을 알고 있어야 한다. DAG는 말 그대로 방향을 가지지만 사이클을 가지지 않는 그래프를 의미하고, 진입, 진출 차수는 해당 노드로 향하는 간선과, 해당 노드에서 나아가는 간선의 개수라고 생각하면 된다. 여기서 중요한 것은 진입 차수이다. 진입 차수가 존재한다는 것은, 해당 노드로 이동하기 위해서는 사전에 거쳐야 할 노드가 있다는.. 2023. 4. 3.

티스토리툴바