본문 바로가기

백준 문제 풀이

 (152)
백준 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 말고도 현재 열쇠의..
백준 12893번 - 적의 적(C++) https://www.acmicpc.net/problem/12893 12893번: 적의 적 첫 줄에 용재 주위 사람의 수 N(1 ≤ N ≤ 2,000)과 적대관계의 수 M(0 ≤ M ≤ 1,000,000)이 주어진다. 두 번째 줄부터 M개의 줄에 거쳐 서로 적대관계에 있는 사람의 번호 A, B(1 ≤ A, B ≤ N)가 주어진다. www.acmicpc.net 문제를 처음 접했을 때 그래프 문제라는 것은 바로 파악할 수 있었다. 그러나 이 문제는 이분 그래프의 정석이라고 난이도 기여에서 말하던데 이분 그래프를 자세히 공부해본적이 없어서 조금 어려웠던 듯 하다. 우선 먼저 적대관계 그래프를 그려서 문제의 의미를 파악해보자. 1 2 2 3 3 4 4 5 입력이 들어온다면 위와 같은 적대 그래프가 만들어질 것이..
백준 1786번 - 찾기(C++) https://www.acmicpc.net/problem/1786 1786번: 찾기 첫째 줄에, T 중간에 P가 몇 번 나타나는지를 나타내는 음이 아닌 정수를 출력한다. 둘째 줄에는 P가 나타나는 위치를 차례대로 공백으로 구분해 출력한다. 예컨대, T의 i～i+m-1번 문자와 P의 1～m www.acmicpc.net KMP 알고리즘의 기본 문제이다. 문제에서도 친절하게 KMP알고리즘에 대해 설명하고 있다. https://tigerfrom2.tistory.com/400 문자열 찾기 - KMP 알고리즘 KMP 알고리즘이란? KMP 알고리즘이란 문자열에서 단어를 빠르게 골라낼 수 있는 알고리즘이다. 러프하게 생각하면 쉽게 문자를 찾아낼 수 있지만 이것은 아주 느리다. KMP의 아이디어 KMP의 중요한 tige..

티스토리툴바