본문 바로가기

백준 문제 풀이

 (134)
백준 1823번 수확 (C++) https://www.acmicpc.net/problem/1823 1823번: 수확 첫째 줄에 벼의 개수 N(1 ≤ N ≤ 2,000)이 주어지고 두 번째 줄부터 N+1번쨰 줄까지 벼의 가치 v(i) (1 ≤ v(i) ≤ 1,000) 가 주어진다. www.acmicpc.net 비슷한 문제를 몇 개 풀어본적이 있어서 비교적 쉽게 풀 수 있었다. 최댓값을 보고 생각해야하는 것은 bfs이다. 그러나 N의 개수를 보고 빠르게 접는다. 양방향을 보고 생각해야하는 것은 투포인터, 이분탐색, dp이다. 그리고 모든 방법을 고려해야하기 때문에 이분탐색과 투포인터는 제외시켜야한다. 그래서 남는 선택지는 dp이다. 두가지 선택지가 존재한다. 앞을 먼저 수확하거나 뒤를 먼저 수확하거나. 이것을 코드로 바꿔보면 dp[left..
백준 9024번 두 수의 합(C++) https://www.acmicpc.net/problem/9024 9024번: 두 수의 합 프로그램은 표준입력으로 입력을 받는다. 프로그램 입력은 t 개의 테스트 케이스로 구성된다. 입력의 첫 번째 줄에 테스트 케이스의 개수를 나타내는 정수 t 가 주어진다. 두 번째 줄부터 두 줄 www.acmicpc.net 문제를 보자마자 이분탐색 투포인터가 떠올라야한다. 난 누적합도 떠올랐는데 이 문제는 모든 조합을 확인하면 TLE임을 알았고 간격의 차이에 따라 계산을 걸러낼 수 있는 양 끝 시작 투포인터를 사용해야한다고 생각했다. 2 3 10 14 29 가 있다고 하자. 그렇다면 두 수의 합은 lo++를 할 수록 커지고 hi-- 할수록 작아진다. 그러므로 두 수의 합이 k보다 작다면 더 크게 만들어 줘야하니까 lo..
백준 25401번 카드 바꾸기 (C++) https://www.acmicpc.net/problem/25401 25401번: 카드 바꾸기 $N$개의 카드가 놓여있다. 편의상 가장 왼쪽에 있는 카드를 $1$번 카드, 그 다음에 있는 카드를 $2$번 카드 $\dots$, 가장 오른쪽에 있는 카드가 $N$번 카드라고 하자. $N$개의 카드에는 각각 정수가 하 www.acmicpc.net 수학적인 테크닉이 조금 필요한 문제이다. 일정하게 증가,감소 수열을 만들어야하기 때문에 처음 떠오른 방식은 dp, 이분탐색이었다. 1. DP : 내가 DP를 잘 못하기도 하고 어떻게 점화식을 짜야할지 감이잡히지 않았다. 2. 이분탐색: 숫자의 범위가 -100만~ 100만이기 때문에 이분탐색을 떠올리고 가장 최적의 증가, 감소치를 찾으면 될 것이라 생각하였으나. 만약 4..
백준 2758번 - 로또(C++) https://www.acmicpc.net/problem/2758 2758번: 로또 선영이는 매주 엄청난 돈을 로또에 투자한다. 선영이가 하는 로또는 1부터 m까지 숫자 중에 n개의 수를 고르는 로또이다. 이렇게 열심히 로또를 하는데, 아직까지 한 번도 당첨되지 않은 이유는 www.acmicpc.net 별로 특별해 보이지 않은 문제였다. 조합을 구하되 조건이 있는 조합이기 때문에 백트래킹으로 가지를 잘 치면 통과할 수 있을 것이라 생각했다. 그러나 계속 시간초과가 났고 구글링 해보니 dp 문제였다. 역시 난 dp가 약하다.. 아무튼, 1 2 4 8 1 2 4 9 1 2 4 10 1 2 5 10 이 가능하다고 할 때, 위 조합을 잘 보면 10개 중 3개를 뽑는 개수를 포함하고 있다. 왜냐하면 10개 중 4..
백준 11062번 카드 게임 C++ https://www.acmicpc.net/problem/11062 11062번: 카드 게임 근우와 명우는 재미있는 카드 게임을 하고 있다. N개의 카드가 일렬로 놓여 있다. 각 카드에는 점수가 적혀있다. 근우부터 시작하여 번갈아가면서 턴이 진행되는데 한 턴에는 가장 왼쪽에 있는 www.acmicpc.net 누가봐도 나 DP에요! 소리치고 있는 문제이다. 다만 아이디어를 떠올리기는 쉽지 않았다. 1 2 3 4번 인덱스가 있을 때 난 dp[1] dp[4] 를 만들어서 왼쪽을 선택시, 오른쪽을 선택시를 고려해서 고르는 것을 택했다. 그러나 이것은 정답이 아니었고.. 2차원 배열을 사용하는 것이 정답이었다. dp[x][y] 라고 할 때 x번~y번이 인덱스에서 최댓값을 가지고 있으면 된다. 그리고 문제 조건에서..
백준 2357 최솟값과 최댓값 (c++) https://www.acmicpc.net/problem/2357 2357번: 최솟값과 최댓값 N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수, 또는 제일 큰 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100 www.acmicpc.net 세그먼트 트리는 원래 O(N)이상 걸리는 작업들을 log 시간으로 해결할 수 있는 자료구조이다. 코딩테스트에 출제된다면 아마 모르면 맞아야지 문제이기 때문에 정답률이 처참할 것으로 예상된다. 하지만 세그먼트 트리를 응용까지 해서 풀어야하는 테스트는 아마도 카카오 네이버를 제외하면 거의 없을 거라 생각한다. 세그먼트 트리는 1. 세그먼트 트리 빌드 2. 업데이트..
백준 5639번 - 이진 검색 트리 (c++) https://www.acmicpc.net/problem/5639 5639번: 이진 검색 트리 트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다 www.acmicpc.net 이진검색트리는 세가지 검색법이 있다. 1. 전위순회 - root -> left -> right 2. 중위순회 - left -> root -> right 3. 후위순회 - left -> right -> root 문제에서는 전위순회로 들어온 값들을 후위순회한 값으로 나타내라고 한다. 처음 생각은 다시 트리를 구성해서 전위순회해야하는건가 싶었는데 불가능하지는 않겠지만 비용이 많이들고 굳이 ..
백준 1194번 - 달이 차오른다, 가자. (C++) https://www.acmicpc.net/problem/1194 1194번: 달이 차오른다, 가자. 첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고, www.acmicpc.net bfs 최단거리 문제임은 자명한데, 주어진 다른 조건이 있어 쉽지 않은 문제이다. 문제를 보며 깨달아야하는 것은 들고있는 열쇠마다 타일에 접근하는 것의 의미가 다름을 깨달아야한다. 즉 2,2 가 a라고 할 때 열쇠 a,b,c를 가지고 있는 것과 열쇠 a만을 가진 것은 의미가 전혀 다르다는 의미이다. 그래서 bfs를 돌 때 각 bfs 노드들은 x,y 말고도 현재 열쇠의..

티스토리툴바