목록백준 (142)
mojo's Blog
[백준 13911] 집 구하기
문제 링크 => https://www.acmicpc.net/problem/13911 13911번: 집 구하기 첫줄에는 정점의 개수 V(3 ≤ V ≤ 10,000)와 도로의 개수 E(0 ≤ E ≤ 300,000)가 주어진다. 그 다음 E줄에 걸쳐 각 도로를 나타내는 세 개의 정수 (u,v,w)가 순서대로 주어진다. 이는 u와 v(1 ≤ u,v ≤ V)사 www.acmicpc.net 다익스트라 문제이다. 이문제를 처음에 접근 했을때의 코드를 먼저 살펴보도록 한다. 시간 초과한 코드 #include #include #include #include using namespace std; using ll = long long; #define endl '\n' #define INF 200000001 vector ve..
[백준 2240] 자두나무
문제 링크 => 2240번: 자두나무 (acmicpc.net) 2240번: 자두나무 자두는 자두를 좋아한다. 그래서 집에 자두나무를 심어두고, 여기서 열리는 자두를 먹고는 한다. 하지만 자두는 키가 작아서 자두를 따먹지는 못하고, 자두가 떨어질 때까지 기다린 다음에 떨어 www.acmicpc.net 다이나믹 프로그래밍 문제이다. 3차원 배열 dp[x][y][z] 를 설정하였다. (x : 자두의 위치, y : 자두가 떨어지는 초 단위, z : 자두의 움직일 수 있는 횟수) 이때 주의깊게 볼 점은 z = 1 일때 움직이는 횟수를 0으로 보는것이 핵심이다. (0으로 볼 경우 배열의 index가 -1을 침범하는 경우가 발생하기 때문) 처음의 자두의 위치가 1이라고 주어질 때, 자두가 떨어질 위치가 1, 2일때의..
[백준 2293] 동전 1
문제 링크 => 2293번: 동전 1 (acmicpc.net) 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 다이나믹 프로그래밍 문제이다. 오름차순으로 정렬된 동전을 통해 k원을 만족하게 되도록 하는 동전들의 개수를 구하는 문제이다. 예를들어서 동전 1원 하나만 들어왔다고 가정하자. 1 2 3 4 5 6 7 8 9 10(k) 1 1 1 1 1 1 1 1 1 1 1 이때 1원 이후로 값이 전부 채워진것을 확인할 수 있다. dp[1] = dp[1] + dp[0] (이때 dp[0] = 1 이라고 설정) = 0 + ..
[백준 14002] 가장 긴 증가하는 부분 수열 4
문제 링크 => 14002번: 가장 긴 증가하는 부분 수열 4 (acmicpc.net) 14002번: 가장 긴 증가하는 부분 수열 4 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 다이나믹 프로그래밍 문제 + 약간의 생각을 더 해서 풀어야하는 문제이다. 참고로 이문제는 N=1000 밖에 안되기 때문에, 이분탐색을 사용하지 않고 다이나믹 프로그래밍으로 해결이 가능하다. 그러나 문제는 가장 긴 증가하는 부분 수열을 특정지어서 값을 표현하는게 생각보다 쉽지는 않았던거 같다. 이 ..
[백준 12015] 가장 긴 증가하는 부분 수열 3
문제 링크 => 12738번: 가장 긴 증가하는 부분 수열 3 (acmicpc.net) 12738번: 가장 긴 증가하는 부분 수열 3 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000) www.acmicpc.net 가장 긴 증가하는 부분 수열 2 문제에서 수열의 값이 커진것을 제외하고 동일한 문제이다. [백준 12015] 가장 긴 증가하는 부분 수열 2 :: M - J - C (tistory.com) [백준 12015] 가장 긴 증가하는 부분 수열 2 문제 링크 => 12015번: 가장 긴 증가하는 부분 수열 2 (acmicpc.net) 12015번: 가장 ..
[백준 12015] 가장 긴 증가하는 부분 수열 2
문제 링크 => 12015번: 가장 긴 증가하는 부분 수열 2 (acmicpc.net) 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net 이 문제는 이분 탐색을 이용하는 문제이다. 이전에 해결하였던 문제를 동일하게 적용한다면 시간 초과가 난다. (n값이 1,000,000 으로 주어짐) vector v 를 활용하여 다음과 같은 방법으로 배열에 있는 값들을 push하도록 한다. 현재 벡터 v의 원소들에 대하여 arr[i] 값이 있는지를 lower_bound를 이용하여 구한다. lower_bound를 이용하여 얻어낸 ..