본문 바로가기

코딩테스트 준비/PS

 (21)
C++ 백준 20171 (Dessert Cafe) 백준 20171 (Dessert Cafe) https://www.acmicpc.net/problem/20171 20171번: Dessert Café Your program is to read from standard input. The input starts with a line containing two integers, n and k (3 ≤ n ≤ 100,000 , 1 ≤ k ≤ n), where n is the number of candidate sites and k is the number of apartment complexes. The candidate sites are n www.acmicpc.net 일단 N개의 노드에서 항상 N-1개의 간선이 주어지므로 스패닝트리로 볼 수 있다. 이 문제..
C++ 백준 2270 (하노이 탑) 백준 2270 (하노이 탑) https://www.acmicpc.net/problem/2270 2270번: 하노이 탑 첫째 줄에 정수 n(1≤n≤100,000)이 주어진다. 둘째 줄에는 세 정수 a, b, c가 주어진다. 이는 차례로 1, 2, 3번 막대기에 꽂혀 있는 디스크의 개수이다. 이는 0이상 n이하이며, a+b+c=n이다. 다음 3개의 줄 www.acmicpc.net 기본 하노이탑 문제 응용버전이다. 하노이탑 기본문제 (1~N까지 차례로 쌓인 탑을 다른 rod로 옮기는 문제)는 여기(링크)에 있다. 꼭 이해하고 오자. 1~N까지의 차례로 쌓인 탑을 옮길때는 2^N-1만큼의 횟수가 소요된다고 했다. 그렇다면 탑이 차례로 쌓여있지 않고 뒤죽박죽 섞여있을 때는 어떻게 될까? 이 문제가 바로 그것이다...
C++ 백준 11729 (하노이 탑 이동순서) 백준 11729 (하노이 탑 이동순서) https://www.acmicpc.net/problem/11729 11729번: 하노이 탑 이동 순서 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 www.acmicpc.net 하노이 탑은 유명한 문제지만 막상 구현 과정은 꽤 어렵다. 문제에서는 1~N까지 쌓여있는 하노이탑을 특정 rod로 옮기는 것이기 때문에 가장 기본적이 하노이 탑 문제라고 할 수 있다. 설명 1~N까지 차곡차곡 쌓여있는 탑을 어떻게 다른 탑으로 옮길까? 하노이 탑의 특성상 위에 놓일 탑은 아래에 있는 탑보다 항상 크기가 작아야 하기 때문에 꽤 복잡..
C++ 백준 1707 (이분 그래프) 백준 1707 (이분 그래프) https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net 이분 그래프(Bipartite Graph)에 대해 모른다면 구글링을 통해 알고오자! 그러나 문제에 자세한 설명이 쓰여져 있다. 설명 이분 그래프를 쉽게 설명하자면 인접한 노드끼리는 서로 다른 집합에 속해있어야 한다. 집합에 속해있다.. 유니온 파인드? 아니다. 집합의 개수가 두개밖에 없기때문에 유니온파인드를 쓸 필요는 없다. 그냥 DFS나 BFS를 돌면서 인접한 노드..
C++ 백준 5430 (AC) 백준 5430 (AC) https://www.acmicpc.net/problem/5430 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net deque를 이용해 풀 수 있는 문제였다. deque에 대한 이해가 없다면 구글링을 해서 알아오도록 하자. 또한 입력이 [1,2,3]과 같이 숫자만 주어지는게 아니기 때문에 이를 처리하는 과정이 살짝 귀찮았다. 설명 수열을 저장 후 뒤집기와 pop을 반복하는 문제였다. 그러나 뒤집기를 할 때 algorithm헤더파일에 존재하는 reverse함수를 쓰게 될 경우 이 함수는 O(N)의 시간복잡도를 갖기 때문에 시간초과가 날것이라는 생..
C++ 백준 14003 (가장 긴 증가하는 부분수열5) 백준 14003 (가장 긴 증가하는 부분수열5) https://www.acmicpc.net/problem/14003 14003번: 가장 긴 증가하는 부분 수열 5 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000) www.acmicpc.net LIS의 길이와 수열을 O(N*logN)안에 해결해야 하는 문제이다. LIS에 대한 기본이해와 O(N^2)의 시간으로 길이와 수열을 찾는 법, 그리고 O(N*logN)의 시간으로 LIS의 길이만을 찾는 방법은 아래에 있으니 반드시 모두 이해하고 이 글을 읽도록 한다. 1. LIS의 길이를 O(N^2)으로 구하는 방법 :..
C++ 백준 14002 (가장 긴 증가하는 부분수열4) 백준 14002 (가장 긴 증가하는 부분수열4) https://www.acmicpc.net/problem/14002 14002번: 가장 긴 증가하는 부분 수열 4 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 이 문제는 LIS의 길이 뿐만 아니라 LIS수열 중 하나를 출력하는 문제이다. 이 문제를 풀기에 앞서 LIS의 기본특성과 그 길이를 구하는 방법을 알아야 한다. 1. LIS의 길이를 O(N^2)으로 구하는 방법 : 여기(링크) 2. LIS의 길이를 O(N*log(N))..
C++ 백준 1562 (계단 수) 백준 1562 (계단 수) https://www.acmicpc.net/problem/1562 1562번: 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net DP와 재귀에 비트마스크 연산을 사용하여 풀 수 있는 문제이다. 때문에 이 문제를 해결하기 위해선 DP, 재귀호출, 비트마스크 연산에 대한 이해가 필요하다. 설명 계단 수의 기본적인 아이디어는 다음과 같다. 시작숫자를 특정 숫자로 고정한 뒤, 재귀호출을 통해 이어나아갈 수 있는 숫자를 붙여 입력 N의 길이가 되면 멈추는 방식이다. 그러나 이 문제는 한 가지 조건이 더 있다. 0~9까지 모든 숫자가 포함되어야 한다는 것이다. 0~9까지 모든 숫자가 있는지 없는지를 판단한다.. 있는지 없는지.. ..

티스토리툴바