https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 문제 상근이는 나무 M미터가 필요하다. 근처에 나무를 구입할 곳이 모두 망해버렸기 때문에, 정부에 벌목 허가를 요청했다. 정부는 상근이네 집 근처의 나무 한 줄에 대한 벌목 허가를 내주었고, 상근이는 새로 구입한 목재절단기을 이용해서 나무를 구할것이다. 목재절단기는 다음과 같이 동작한다. 먼저, 상근이는 절단기에 높이 H를 지정해야 한다. 높이를 지정하면 톱날이 땅으로부터 H미터 위로 올라간다. 그 다음, 한 줄에 연속해있는 나무를 모두 절단해버린다. 따 www.acmicpc.net 파라매트릭 서치 문제 랜선 자르기와 비슷한 문제 12345678910111213141516171819202122232425262728..

https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 후 K줄에 걸쳐 이미 가지고 있는 각 랜선의 길이가 센티미터 단위의 정수로 입력된다. 랜선의 길이는 231-1보다 작거나 같은 자연수이다. www.acmicpc.net parametric 탐색의 대표적인 문제 중 하나 이분 탐색의 방법을 이용한다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464..

힙(Heap) 힙은 완전 이진트리에서 기반한 자료구조 부모노드와 자식노드 간의 관계에 따라 최대힙과 최소힙으로 나뉜다. 데이터에서 최대값, 최소값을 빠르게 찾아내기 위한 자료구조이다. 최대힙(maxheap) - 자식 노드는 무조건 부모보다 작다. 최소힙(minheap) - 자식 노드는 무조건 부모보다 크다. 힙 정렬 (Heap sort) 위에서 말한 최대힙과 최소힙을 구성하며 정렬하는 방법이다. 최대힙 구성 힙 검증 부모와 자식간의 관계를 검사하여 위치를 바꿔준다. 이 과정을 레벨의 끝까지 이어서 검증 정렬 우선 순위 큐 말 그대로 우선 순위를 매겨 정렬하는 것으로 뽑아 낼때 마다 재정렬을 해야하는 배열보다 강한 장점을 가진 트리 구조를 이용한다. 구현에는 두가지 방법이 있다. stl의 priority_..

https://www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 안전한 영역이 최대로 몇 개가 만들어 지는 지를 조사하려고 한다. 이때, 문제를 간단하게 하기 위하여, 장마철에 내리는 비의 양에 따라 일정한 높이 이하의 모든 지점은 물에 잠긴다고 가정한다. 어떤 지역의 높이 정보는 행과 열의 크기가 각각 N인 2차원 배열 형태로 주어 www.acmicpc.net 이 문제는 다 풀어놓고 한가지 기준을 생각을 못해 꽤 시간이 걸렸던 문제 bfs dfs 둘다 풀이가 가능하다. 하지만 나는 bfs로 풀..

https://www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 그리디 알고리즘을 이용한 기본적인 문제 #include #include #include using namespace std; int main() { int num , k; cin >> num >> k; vector data; int temp_num; int count_num = num; for (int i = 0; i < num; i..

https://www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net 이 문제는 그리디 알고리즘으로 푸는 문제 최적해는 가장 처음에 짧은 시간을 먼저 선택하는 것 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849#include #include#include using namespace std; struct data_{ int value; int index;};bool compare(da..

https://www.acmicpc.net/problem/1149 1149번: RGB거리 RGB거리에 사는 사람들은 집을 빨강, 초록, 파랑중에 하나로 칠하려고 한다. 또한, 그들은 모든 이웃은 같은 색으로 칠할 수 없다는 규칙도 정했다. 집 i의 이웃은 집 i-1과 집 i+1이고, 첫 집과 마지막 집은 이웃이 아니다. 각 집을 빨강으로 칠할 때 드는 비용, 초록으로 칠할 때 드는 비용, 파랑으로 드는 비용이 주어질 때, 모든 집을 칠하는 비용의 최솟값을 구하는 프로그램을 작성하시오. www.acmicpc.net 2차원 배열로 푸는 다이나믹 프로그래밍 문제이다. 각 지점에 대해 앞배열의 정보를 이용해 푼다. -> 이미 계산된 결과를 이용 #include #include #include using name..

https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 다이나믹 프로그래밍으로 대표적인 문제 #include #include using namespace std; int main(){ int n; cin>>n; vector tiles; tiles.push_back(1); tiles.push_back(2); for(int i=2;i

백준 1003번 피보나치 함수 https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net f(0) 과 f(1)의 호출 횟수를 출력하면 된다. 목표 수까지 저장된 값들을 다 더해주면된다. #include #include using namespace std; vector zero; vector one; void fibonacci(int n) { for(int i=3;i>num; vector list; int temp; int max_= 0; for(int i=0;i>temp; list.push_back(temp); if(max_