본문 바로가기

알고리즘/Baekjoon

 (196)
완전 탐색. [2798] [1. 문제 설명] https://www.acmicpc.net/problem/2798 [2. 풀이 접근] 시간 복잡도 분석 전체 100 개 중 3 가지를 선택해야 함. => 100C3 그러나 특정 조건을 만족해야 함. => 반드시 3개를 선택 하고 그 합이 M 을 넘지 않아야 함. 이 조건을 통해 가지치기가 가능 함 기저 사례 혹은 가지 치기 할 수 있는 경우 3가지 카드를 선택 한 경우. (가지 치기) => 현재까지 합이 M 이하인 경우, 누적 합을 반환. => 현재까지 합이 M 초과한 경우, 0을 반환. 이번에 선택 할 아이템이 배열의 범위를 벗어난 경우 (기저 사례) => 0을 반환. 현재까지 합이 M 을 초과한 경우. (가지 치기) => 0을 반환. 문제 조건 상 반드시 3가지 카드는 선택되어야 ..
완전 탐색. [14501] [1. 문제 설명] https://www.acmicpc.net/problem/14501 [2. 풀이 접근] 시간 복잡도 계산 금일 상담을 선택 => 금일 상담을 퇴사 전까지 할 수 있는 경우에만 선택하도록 한다. 금일 상담을 하지 않고, 다음 날로 이동 매일 2가지 선택이 존재하므로, O(N2) N 의 최대 값은 15 이므로, 총 경우의 수는 대략 32000개 이므로, 시간 내 풀이 가능 [3. 코드]
DP/최단거리 역추적. [11780] [1. 문제 설명] n 개의 도시가 있고, a 도시에서 b 도시에 도착하는 m 개의 버스가 있으며, 각 버스는 한번 사용할 때 필요한 비용이 잇다. 모든 도시 쌍에 대해서 A -> B 로 가는데 필요한 비용의 최소값과 경로를 출력하도록 한다. [2. 풀이 접근] n 은 최대 100 이고, 모든 도시 쌍의 최단 경로를 구해야 하므로, 플로이드 워셜 알고리즘을 이용하도록 한다. => 플로이드 워셜 알고리즘의 시간복잡도: O(N3) 플로이드 워셜 알고리즘 사용 후, 경로를 구해야 할 때는 아래와 같이 접근한다. u -> v 로 가는 경로보다 u -> k -> v 로 가는 경로가 최단이면, u 와 v 의 경유지 k 를 설정하도록 한다. u 와 k 사이의 경로와 k 와 v 사이의 경로를 합치면, 전체 u -> v..
SCC. [3648] [1. 문제 설명] [2. 풀이 접근] 오답이었던 방식 1 을 포함하는 경우는 x1 이 반드시 true 이어야 하므로 무시한다. (true / false 중 아무거나 와도 된다.) -1 을 포함하는 경우는, 해당 절을 true 로 만들어야 하므로, xi 에 오는 값을 정할 수 있다. => (true 또는 false 중 하나가 되야 한다.) 이때, xi 에 이미 값이 할당되어있고, 이번에 할당 할 값 과 다르면 전체 식을 true 로 만들 수 없다. => 앞에 절을 참으로 한 값을 변경하면, 이번 절이 참이 되나, => 그 전의 절은 false 가 되므로 전체 식을 true 로 할 수 없다. => "no" 를 출력한다. 논리식에 대한 그래프를 만들고 난 뒤, scc 로 묶는다. n 과 -n 이 같은 scc..
SCC. [11281] [1. 문제 설명] 2-SAT 해가 존재하는지 확인하고, 존재할 경우 각 해를 출력하도록 한다. [2. 풀이 접근] [3. 코드]
SCC. [11280] [1. 문제 설명] 2-SAT 는 N 개의 boolean 변수가 있을 때, 2-CNF 식을 true 로 만들기 위해 xi 를 어떤 값으로 정해야하는지를 구하는 문제이다. 2-CNF 식은 아래와 같은 형태이다. f = (x ∨ y) ∧ (￢y ∨ z) ∧ (x ∨ ￢z) ∧ (z ∨ y) N 개의 변수가 있고, M 개의 절이 주어질 때, 식 f 를 true 로 만들 수 있다면 1, 없다면 0을 출력한다. [2. 풀이 접근] 각 절(clause) 들이 모두 true 가 되어야, 전체 식 f 가 true 가 된다. p ∨ q 를 참으로 하는 명제는 아래와 같다. !p -> q !q -> p 정리하면, p 와 q 둘 중 적어도 하나는 true 이어야 한다. p 가 true 이면, q 는 어느 값이어도 상관이 없..
SCC. [4013] [1. 문제 설명] 위와 같이 교차로 에 ATM 및 레스토랑이 있을 때, 시작 점이 주어지고, 어떤 레스토랑까지 이동하면서 인출 할 수 있는 현금의 최대 액수를 구하도록 한다. 한번 출금하면 해당 ATM 에서는 더 이상 출금 할 수 없으며. 한번 지나간 edge 를 다시 지나갈 수 있다. (원: ATM, 이중원: ATM + 레스토랑) [2. 풀이 접근] 한번 지나간 edge 를 다시 지나갈 수 있으므로, 현금을 최대한 인출 하기 위해 cycle 을 형성 할 수 있다. 풀이 개요 전체 그래프를 SCC 단위로 나눈다. 시작 위치를 포함하는 SCC 에서 출발한다. 레스토랑이 있는 SCC 를 방문 하는 모든 경우를 체크하여 최대 값을 구한다. 최대한 많은 현금을 인출하기 위해 같은 SCC 에 속한 모든 노드를 ..
SCC. [3977] [1. 문제 설명] 다른 모든 구역에 도달할 수 있는 시작 구역을 찾는다. 없으면, Confused 를 출력하고, 있다면, 시작 구역을 오름차순으로 출력한다. [2. 풀이 접근] A. 단순한 풀이 dfs 를 수행하여 모든 정점에 도달 할 수 있는 경우가 시작 구역이 된다. 모든 정점을 대상으로 dfs 를 수행한다. 단, 시간 초과가 발생하므로, 이 풀이는 폐기해야 한다. B. SCC 를 이용한 풀이 같은 SCC 에 속한 노드들은 항상 그 경로가 존재한다. 이러한 특성을 이용하여 SCC 에서 SCC 로 이동 하는 경우를 생각한다. 어떤 SCC 에서 다른 SCC 를 모두 방문할 수 있다면, 이 SCC 에 속한 노드만 출력하면 되기 때문이다. 방향 그래프에서 각 SCC 사이를 연결하는 간선들을 모으면, SCC..
SCC. [4196] [1. 문제 설명] 도미노 블록의 배치가 그래프 형태로 주어졌을 때, 모든 블록을 넘어뜨리기 위해 손으로 넘어뜨려야 하는 블록 개수의 최소값을 출력한다. [2. 풀이 접근] A. 잘못된 접근 dfs 를 수행하면 현재 블록을 기준으로 넘어 질 수 있는 블록들이 모두 방문된다. 이러한 점을 이용하여, dfsAll() 을 실행하여 호출 될 수 있는 dfs() 횟수를 출력한다. 이 풀이가 틀린 이유는 아래와 같은 경우처럼, 최초 dfs 호출 대상에 따라 답이 바뀌기 때문이다. B. 올바른 접근 모든 정점을 SCC 로 묶는다. 이 SCC 속한 블록들은 어떤 블록을 선택하더라도 모두 넘어지게 된다. 이 SCC 에서 다른 SCC 로 연결된 경우를 고려한다. 이 SCC 를 수동으로 넘어뜨린 경우, 연결된 SCC 에 속..
SCC. [2150] [1. 문제 설명] 방향 그래프가 주어졌을 때, 그래프 내 SCC(=강결합 컴포넌트) 개수와 각 컴포넌트에 속한 정점 번호를 출력한다. [2. 풀이 접근] 강결합 컴포넌트 (이하 SCC) 란 방향 그래프에서 서로 다른 임의의 두 정점 u ~> v 와 v ~> u 로 가는 경로가 존재하는 컴포넌트를 말한다. 위 그림에서 (a, b) (b, e) (e, a) 는 모두 경로가 존재하므로, 같은 SCC 에 속하게 된다. 이러한 SCC 를 구하는 알고리즘 중 타잔 알고리즘을 적용하여 문제를 해결하도록 한다. 타잔 알고리즘 동작 원리는 아래 링크를 참조하도록 한다. [3. 코드]

티스토리툴바