목록백준 (142)
mojo's Blog
[백준 11400] 단절선
문제 링크 => 11400번: 단절선 (acmicpc.net) 11400번: 단절선 첫째 줄에 두 정수 V(1≤V≤100,000), E(1≤E≤1,000,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다. 다음 E개의 줄에는 간선에 대한 정보를 나타내는 두 정수 A www.acmicpc.net DFS 트리를 이용하여 단절선을 찾아내는 문제이다. [백준 11266] 단절점 :: M - J - C (tistory.com) 에서 단절점을 구하는 과정에서 Case 2 를 고려하지 않고 Case 1 에서 dfn[cur] < low[child] 을 만족하는 경우에 cur ~ child 로 이어진 간선은 단절선이다. 그리고 단절선을 구하고 주의해야 할점은 문제에서 단절선을 사..
[백준 11266] 단절점
문제 링크 => 11266번: 단절점 (acmicpc.net) 11266번: 단절점 첫째 줄에 두 정수 V(1≤V≤10,000), E(1≤E≤100,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다. 다음 E개의 줄에는 간선에 대한 정보를 나타내는 두 정수 A, B www.acmicpc.net DFS 트리를 이용하여 단절점을 찾아내는 문제이다. Tarjan's Algorithm 을 이용하여 노드별로 dfs로 방문하면서 매겨지는 dfn값과 해당 노드에서 최소 dfn 값 (low)을 찾는 과정 속에서 단절점을 찾아내는 방법은 다음과 같다. case 1. 자식노드가 dfn 값이 매겨지지 않은 경우 : dfn[cur] 2 : low[2] = dfn[2] = 2 (2) 2..
[백준 1519] 부분 문자열 뽑기 게임
문제 링크 => 1519번: 부분 문자열 뽑기 게임 (acmicpc.net) 1519번: 부분 문자열 뽑기 게임 첫째 줄에 N이 주어진다. N은 1,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 다이나믹 프로그래밍 + 게임 이론 문제이다. 게임 이론이라는걸 이번에 처음 알게 되었다. 플레이어 1이 무조건 지게되는(필패) 경우를 찾고 dp 값을 업데이트 하는것을 기반으로 이 문제를 접근해 보려고 한다. 처음으로 N 값이 10 미만인 경우에 대해 살펴보면 이 경우는 필패이다. => 문제의 조건에서 "진 부분 문자열이란 자기 자신을 제외한 모든 연속된 부분 문자열을 말한다." 라고 명시되어 있으므로 10 미만의 숫자는 부분 문자열이 존재하지 않으므로 고를 수 없다. 따라서 dp[ 1~..
[백준 13283] Daruma Otoshi
문제 링크 => 13283번: Daruma Otoshi (acmicpc.net) 13283번: Daruma Otoshi For each dataset, output in a line the maximum number of blocks you can remove. www.acmicpc.net 다이나믹 프로그래밍 문제이다. 약간 이 문제 => 11049번: 행렬 곱셈 순서 (acmicpc.net) 랑 비슷한 느낌인데 재귀로 풀니 계속해서 시간초과를 받았습니다. (왜 그런지는 의문...? ㅠㅠ) 그래서 3중 for문으로 해결하였습니다. 일단, dp[x][y] 를 [x, y] 범위 내에서 제거할 수 있는 블럭의 수라고 하겠습니다. 풀이는 다음과 같습니다. 1. [0, 1], [1, 2], ... , [N-2, ..
[백준 22358] 스키장
문제 링크 => 22358번: 스키장 (acmicpc.net) 22358번: 스키장 첫 번째 줄에 다섯 개의 정수 $N, M, K, S, T$ ($1 \le N, M \le 10^5$, $0 \le K \le 10$, $1 \le S, T \le N$) 가 주어진다. 이후 $M$ 개의 줄에 각 코스의 정보가 세 개의 정수 $a_i, b_i, t_i$ ($1 \le a_i DAG 이다. 리프트를 타지 않는 경우(K = 0) 와 리프트를 한번 이상 타는 경우(K >= 1) 로 나눠서 해결할 수 있다. 2차원 배열 dp[x][y] 를..
[백준 1655] 가운데를 말해요
문제 링크 => 1655번: 가운데를 말해요 (acmicpc.net) 1655번: 가운데를 말해요 첫째 줄에는 수빈이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 수빈이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 최소힙, 최대힙을 이용하는 문제이다. 우선순위 큐를 이용하여 maxHeap, minHeap를 만들고 최소힙, 최대힙의 합한 갯수, 즉, 받아온 데이터의 갯수가 홀수일때와 짝수일때를 고려해줘야 한다. 데이터의 갯수(2n+1)가 홀수일 때 => 최대힙의 갯수 n+1 개, 최소힙의 갯수 n 개에 대하여 최대힙의 최댓값, 최소힙의 최솟값을 비교하여 더 작은 결과가 중간값이다. 데이터의..