본문 바로가기

분류 전체보기

 (689)
최단 경로(벨만-포드) 문제 솔루션 [1. 개요] 시간 복잡도 O(VE) 모든 Edge 의 relax 를 |V| 번 만큼 반복, 마지막 |V| 번째에서 relax 가 발생한다면, 음수 사이클이 있다는 것이다. 함정 벨만-포드 수행 후 어떤 노드 u 까지 가는 경로가 존재하는가? upper[u] != INF 가 아니라고 판단하면 안된다. 그래프가 아래와 같이, 완전히 연결되지 않았다면, 시작점과 연결되지 않은 상태에서, 음수 사이클이 있다면, 적당히 큰 값 M 에 대한 어떤 연산 결과가 참이라면 u 까지 가는 경로가 있다고 판단해야함. => 이 값은 문제 조건에 따라 다름... => weight 조건이 [0, K] 이고 (음수 weight 와 별개로.. 양수 weight 에 대해서만), => 전체 edge 개수가, L 개라면, => M=KL..
벨만-포드. [1865] [1. 문제 설명] https://www.acmicpc.net/problem/1865 [2. 풀이 접근] 문제 풀이 시 약간 애매할 수 있는 부분. 출발지가 어디인가? 되돌아오는 경로가 있는지 어떻게 확인하는가? 내가 최종적으로 제출한(혹은 타당하다고 생각하는) 코드는 플로이드-워셜을 이용한 풀이이다. 이 문제에서 음수 사이클은 중요하지 않다고 생각함. 사이클을 지나되, 무한 루프에 빠진 경로가 아니고, 이 음수 사이클을 적당히 지난 경로라고 생각하면 됨. 그림.. 추가하도록, 즉, 최종적으로 출발지로 되돌아 오는 것이 더 중요하다고 생각하며, 되돌아 왔을 때, 시간이 되돌아가 있는지(시간이 음수가 되는지) 를 판단하는 것이 옳다고 생각하기 때문이다. 또한 플로이드-워셜은 모든 출발지-도착지 간의 최단 ..
최단 경로(다익스트라) 문제 솔루션 [1. 개요] dfs, bfs 등과 달리 visit 여부가 필요 없다. 음수 사이클이 없다는 것이 보장된다면, 음수 weight 를 갖는 edge 에 대해서 최단 경로를 찾을 수 있다. [2. 예제] https://testkernelv2.tistory.com/486 b c d e
분할 정복. [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) 다익스트라 알고리즘의 아래와 같은 특성을 이용하는 문제이다. 출발지에서 모든 도착지 까지의 최단 경로를 구한다. 각 학생이 있는 마을에서 파티가 열리는 마을까지 최단 경로를 구하는 ..
그래프 탐색 솔루션 [1. DFS 개요] 재귀를 이용한 구현 재귀 호출 전 방문처리를 하도록 한다. [2. BFS 개요] 큐에 푸쉬하는 순간 바로 방문처리를 바로 하도록 한다. bfs 탐색 특성 최단 경로. a b c [3. 예제] https://testkernelv2.tistory.com/478 https://testkernelv2.tistory.com/483 https://testkernelv2.tistory.com/575 https://testkernelv2.tistory.com/577 === bfs === https://testkernelv2.tistory.com/579 https://testkernelv2.tistory.com/580 https://testkernelv2.tistory.com/581 https://..
유니온 파인드. [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 을 업데이트 하지 않고 풀이가 가능했던 문..
유니온 파인드 솔루션 [1. 개요] "상호 배타적 집합 == 유니온 파인드 == 분리집합" 전부 같은 표현이며, 보통 "유니온 파인드" 라는 명칭이 고유 명사 처럼 사용된다고 한다. 유니온 파인드 자료구조 구현을 위해서는 세가지 연산이 필요하다. 초기화를 제외한 연산의 시간복잡도는 거의 상수시간이 되도록 작성해야 한다. 초기화 => 각 원소가 각각의 집합에 포함되도록 한다. union => 두 원소를 하나의 집합을 합친다. find => 원소가 속한 집합을 반환한다. 위 자료구조 구현 패턴을 정의하도록 한다. 초기화 구현 패턴 int parents[] => 각 원소에 대해서 parents[i] = i 로 초기화 한다. => 자신의 부모가 자기 자신 => root int ranks[] => 각 원소가 속한 집합(트리)의 높이로..
구간 트리. [10868] [1. 문제 설명] https://www.acmicpc.net/problem/10868 [2. 풀이 접근] 구간의 최대 길이는 100,000 이며, 구간 트리를 구현하는데 필요한 공간복잡도 O(400,000) 으로 합격 구간 트리 구현 패턴을 지켜 작성하도록 한다. [3. 코드]

티스토리툴바