본문 바로가기

알고리즘/Baekjoon

 (196)
위상정렬. [1516] [1. 문제 설명] https://www.acmicpc.net/problem/1516 [2. 풀이 접근] 문제에서 다음과 같은 조건이 있다. 어떤 건물을 짓기 위해서 다른 건물을 먼저 지어야 할 수도 있다. 여러 개의 건물을 동시에 지을 수 있다. N개의 각 건물이 완성되기까지 걸리는 최소 시간을 출력한다. 1번 조건을 통해 일정한 순서를 지켜야 한다는 것을 알 수 있다. 여기에서 위상 정렬을 통해 접근 해볼 수 있음을 알 수 있다. 2번 조건은 조금 까다로울 수 있지만, 3번 조건을 통해 풀이의 힌트를 얻을 수 있다. 전체 건물대신, A 라는 어떤 하나의 건물에만 초점을 맞춰보자. A 라는 건물을 짓기 위해서는 A`, B`, C` 라는 건물을 먼저 지어야 하고, A`, B`, C` 의 건물을 짓기 위해..
최소신장트리. [1647] [1. 문제 설명] https://www.acmicpc.net/problem/1647 [2. 풀이 접근] 하나의 마을에서 집들을 연결하는 도로 => 그래프로 모델링 할 수 있다. 모든 집들이 연결 된 하나의 그래프를 두개의 그래프로 절단해야 한다. 단, 절단 된 두 마을의 유지비의 합을 최소로 해야한다. 여기서 다소 헷갈릴만한(?) 문구가 있는데, 임의의 두 집 사이에 경로가 항상 존재해야 한다. 이 문장은 하나의 마을을 두 개의 마을로 절단해야 할 때, 두 마을에는 적어도 두개의 집이 있어야 한다라고 생각이든다. 그러나, 예제의 정답을 보면 이런 형태가 아니어도 상관 없는 것 같다. 그래서 문제가 좀 단순화되어 아래와 같이 정답을 구할 수 있다. 크루스칼 알고리즘 등을 이용하여 MST 를 구성 => M..
최단경로. [2458] [1. 문제 설명] https://www.acmicpc.net/problem/2458 [2. 풀이 접근] 두 학생의 키를 비교한 결과들을 그래프로 모델링한다. 노드: 학생 번호 간선: 두 학생 간 비교 결과 => 작은 학생에서 큰 학생으로 연결 그래프로 모델링하고 나면, 문제에서 요구하는 부분 문제 (어떤 학생이 자신의 키가 몇 번째인지 알 수 있는가?) 를 아래 질문으로 답할 수 있다. 어떤 노드에서 다른 모든 노드로 가는 경로가 존재하는가? 어떤 노드에서 다른 모든 노드와 그 관계가 형성되는가? => 직접 연결 혹은 간접적으로 연결 여기서 좀 헷갈렸던 부분은 삭선한 부분이다. 왜 다른 모든 노드로 가는 경로로 체크하면 안되냐는 것이다. 위 그림에서 4번만이 자신의 키가 몇번째 인지 알 수 있다. 4번..
벨만-포드. [1865] [1. 문제 설명] https://www.acmicpc.net/problem/1865 [2. 풀이 접근] 문제 풀이 시 약간 애매할 수 있는 부분. 출발지가 어디인가? 되돌아오는 경로가 있는지 어떻게 확인하는가? 내가 최종적으로 제출한(혹은 타당하다고 생각하는) 코드는 플로이드-워셜을 이용한 풀이이다. 이 문제에서 음수 사이클은 중요하지 않다고 생각함. 사이클을 지나되, 무한 루프에 빠진 경로가 아니고, 이 음수 사이클을 적당히 지난 경로라고 생각하면 됨. 그림.. 추가하도록, 즉, 최종적으로 출발지로 되돌아 오는 것이 더 중요하다고 생각하며, 되돌아 왔을 때, 시간이 되돌아가 있는지(시간이 음수가 되는지) 를 판단하는 것이 옳다고 생각하기 때문이다. 또한 플로이드-워셜은 모든 출발지-도착지 간의 최단 ..
분할 정복. [24060] [1. 문제 설명] https://www.acmicpc.net/problem/24060 [2. 풀이 접근] 병합 정렬 구현 시 헷갈리는 부분 정리... 병합 정렬 구현 시 재귀를 사용하는데, 재귀의 탈출 조건 병합 정렬 시, 전체 구간을 어떻게 정의 할 것인가? => 배열의 길이가 N 일 때 => [0, N) 으로 범위를 잡지말고, => [0, N-1] 로 그 범위를 잡아야 함. => 동일한 표현이긴 한데, if, while 에서 등호 여부에 따라 답이 갈릴 수 있으므로, => 한가지 패턴으로 정의하는 것이 좋다. ==> ex) [0, N-1] 이면 분할 시 while (left N-1 까지 사용가능하므로, 등호 성립이 필요함. [3. 코드]
최단 경로. [1238] [1. 문제 설명] https://www.acmicpc.net/problem/1238 [2. 풀이 접근] 단순하게 생각하면, 각 학생별로 파티가 열리는 곳 까지 다익스트라를 진행한 뒤, 파티가 열린 곳에서 각 학생 집까지 다익스트라를 진행하면 될 것 같은 문제이다. 그러나 이 방법은 다익스트라 알고리즘을 N 번 수행해야 한다. (=> 대략 O(N*MLogN)) 여차하면 시간 초과가 발생 할 수 있으며, 플로이드-워셜 사용을 고려 할 경우 역시 시간 초과가 발생 할 수 있다. (=> O(N3), 이며, N 은 최대 1,000) 다익스트라 알고리즘의 아래와 같은 특성을 이용하는 문제이다. 출발지에서 모든 도착지 까지의 최단 경로를 구한다. 각 학생이 있는 마을에서 파티가 열리는 마을까지 최단 경로를 구하는 ..
유니온 파인드. [1043] [1. 문제 설명] https://www.acmicpc.net/problem/1043 [2. 풀이 접근] 최초에는 모든 파티에 참가할 수 있다고 할 수 있다. 이 후, 어떤 파티에 진실을 아는 사람이 있는 경우 이 파티를 참가하지 않도록 한다. 또, 어떤 파티에 진실을 아는 사람이 없는 경우 이 파티에는 무조건 참가가 가능하지는 않다. 이 파티에 참가한 사람이 진실을 모르더라도, 다른 파티에 참석하여 진실을 아는 사람과 만나는 경우에는 결국 진실을 알게 될 것이기 때문이다. 따라서 모든 파티에 참가자가 서로 만날 것인가에 대한 여부를 먼저 처리해야 한다. 전처리를 먼저하고 나서 파티 참석 여부를 따져야 한다는 것이다. 전처리는 아래와 같이 진행한다. 진실을 아는 사람들을 하나의 집합에 속하게 한다. 각 ..
이분탐색. [1939] [1. 문제 설명] https://www.acmicpc.net/problem/1939 [2. 풀이 접근] 시도 혹은 시도해보려 했던 오답인 풀이 유니온-파인드 => 공장이 있는 섬과 같은 집합에 속한 섬들이 존재 => 공장1에서 공장2로 갈때 이 섬들을 거쳐서만 갈 수 있다. => 즉, 이 집합에 속한 섬들을 연결 하는 edge 중 최소 weight 를 찾는다. ==> 틀린 이유 # 특정 경로를 선택 하였을 때, 위에서 선택 된 최소 weight 를 갖는 edge 를 거치지 않을 수 있다. BFS 에서 모든 경로 탐색 => BFS 에서 visit 을 업데이트 하지 않으면 모든 경로 탐색이 가능 할까라는 생각에서 출발 => 그래프 유형은 약간 다르지만, visit 을 업데이트 하지 않고 풀이가 가능했던 문..
구간 트리. [10868] [1. 문제 설명] https://www.acmicpc.net/problem/10868 [2. 풀이 접근] 구간의 최대 길이는 100,000 이며, 구간 트리를 구현하는데 필요한 공간복잡도 O(400,000) 으로 합격 구간 트리 구현 패턴을 지켜 작성하도록 한다. [3. 코드]
우선 순위 큐. [1715] [1. 문제 설명] https://www.acmicpc.net/problem/1715 [2. 풀이 접근] 값이 큰 숫자가 덧셈의 피연산자로 최대한 적게 사용 되어야 한다. 전체 숫자 들 중 가장 작은 값 2개만 계속 더해나가야 한다. 매번 숫자들을 정렬할 수 없으니, 최소 힙을 사용하도록 한다. 즉, 매번 최소 힙에서 두개의 숫자를 꺼내 더하고, 힙에 푸쉬하는 작업을 반복하면 된다. [3. 코드]

티스토리툴바