백준 2881 : 산책길 등급 : Gold III 2881번: 산책길 (acmicpc.net) 2881번: 산책길 정부는 오크 나무 숲을 통과하는 산책길를 만들려고 한다. 숲을 평면으로 나타낼 수 있고, 나무 N개는 평면위의 격자점으로 나타낼 수 있다. 산책길은 축에 평행한 직사각형으로 나타낸다. 산책 www.acmicpc.net 사용 알고리즘 : Binary Search 사용 자료구조 : Vector, Set, Map 이분 탐색의 upper_bound와 lower_bound를 이용하여 푸는 문제. 위의 그림에서 표시한 (2, 2) ~ (4, 4)의 경우, 경계에 존재하는 나무 3그루를 제거해야 한다. 이를 수행하려면 아래와 같은 과정이 필요하다. 1) x가 2이면서 y가 2~4인 나무의 갯수 합 2) ..
백준 4792 : 레드 블루 스패닝 트리 등급 : Platinum III 4792번: 레드 블루 스패닝 트리 (acmicpc.net) 4792번: 레드 블루 스패닝 트리 무방향, 무가중치, 연결 그래프가 주어진다. 그래프의 각 간선은 빨간색 또는 파란색으로 색칠되어져 있다. 이 그래프의 스패닝 트리 중 파란색 간선이 정확히 k개인 것이 있는지 없는지 알아내 www.acmicpc.net 사용 알고리즘 : Kruskal Algorithm 사용 자료구조 : Vector, Union-Find 크루스칼 알고리즘을 두 번 이용하여 스패닝 트리의 수정 가능성을 확인하는 문제였습니다. 위의 그래프를 예로 들어보자. 먼저 파란색 간선을 최소로 사용해주기 위해 빨간색으로 이뤄진 간선을 모두 이어준다. 이후 각 정점을 확인..
백준 2104 : 부분배열 고르기 등급 : Platinum V 2104번: 부분배열 고르기 (acmicpc.net) 2104번: 부분배열 고르기 크기가 N(1 ≤ N ≤ 100,000)인 1차원 배열 A[1], …, A[N]이 있다. 어떤 i, j(1 ≤ i ≤ j ≤ N)에 대한 점수는, (A[i] + … + A[j]) × min{A[i], …, A[j]}가 된다. 즉, i부터 j까지의 합에 i부터 j까지의 최솟값을 곱 www.acmicpc.net 사용 알고리즘 : Divide and Conquer 사용 자료구조 : Vector 세그먼트 트리로도 구현할 수 있는 문제이지만, 분할 정복으로 더 간단하게 구현할 수 있다. 크기가 9(인덱스 0~8)인 위의 배열을 예로 들어보자. 마지막 인덱스가 8이므로, ..
백준 11003 : 최솟값 찾기 등급 : Platinum V 11003번: 최솟값 찾기 (acmicpc.net) 11003번: 최솟값 찾기 N개의 수 A1, A2, ..., AN과 L이 주어진다. Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다. www.acmicpc.net 사용 알고리즘 : Sliding Window 사용 자료구조 : Priority_Queue, Deque 이 문제는 두 가지 방법으로 풀 수 있다. 1. 우선순위 큐를 이용한 방법 (C++ 통과, JAVA 시간초과) 우선순위 큐에 값과 인덱스를 같이 넣고, 최솟값이 유효한 인덱스에 있는지를 확인하여 출력. 다음과 같이 값이 ..
백준 1562 : 계단 수 등급 : Gold I 1562번: 계단 수 (acmicpc.net) 1562번: 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 사용 알고리즘 : Bitmasking, Dynamic Programming 사용 자료구조 : - 다이나믹 프로그래밍에 비트필드 배열을 추가한 형식의 문제이다. 길이가 5인 수의 경우를 예로 들어보자. 행 부분은 길이, 열 부분은 그 위치에 올 수 있는 숫자이다. 계단 수는 0으로 시작할 수 없으므로 위와 같은 상태가 된다. 두 자리 수의 경우, 0은 1에서만 올 수 있으므로 1. → 두 자리 수이며, 두 번째 자리가 0인 계단 수는 10 하나 뿐이다. → 마찬가지로 9의 경우도 8에서만 올 ..