https://www.acmicpc.net/problem/1927 1927번: 최소 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 생각 사실 이 문제의 목적은 직접 최소 힙을 구현하라는 것이지만, C++에서는 STL priority_queue가 있어서 최소 힙을 직접 구현하지 않고도 문제를 풀 수 있다. C++에서 최소 힙을 사용하려면 아래와 같은 방식으로 선언해야한다. priority_queue pq; 코드 #include using namespace std; priority_queue pq; // 최소..
https://www.acmicpc.net/problem/7662 7662번: 이중 우선순위 큐 입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 Q에 적 www.acmicpc.net 생각 동일한 정수가 삽입될 수 있다. -> 중복이 허용된다. 최댓값과 최솟값을 삭제해야 한다. -> 정렬이 되있어야 한다. 그렇다면 STL multiset를 사용하면 편리하다. multiset을 사용하면 수를 중복해서 삽입할 수 있고, 자동으로 오름차순 정렬을 해준다. 그러므로 최솟값을 꺼내려면 iterator를 사용하여 set의 맨 왼쪽 부분(ms.begin() )을, 최댓값을 꺼내려면 se..
https://www.acmicpc.net/problem/13414 13414번: 수강신청 입력 데이터는 표준 입력을 사용한다. 입력은 1개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 과목의 수강 가능 인원 K(1 ≤ K ≤ 100,000)와 학생들이 버튼을 클릭한 순서를 기록한 대기목 www.acmicpc.net 생각 '처음에는 단순히 벡터에 값들 집어넣고, 중복한 값 넣으면 제거하고, 차례대로 출력하면 되는 거 아닌가?'라는 생각을 했었는데, 바로 시간초과가 떴다. 그래서 해시를 사용하는 unordered_set을 사용할까 고민했지만 unordered_set은 입력 순서를 보장해주지 않고 랜덤으로 출력된다는 문제를 가지고 있었다. 어떻게 하면 입력 순서를 보장할까 생각하던 중에, 해시를 사용..
https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 생각 일단 숫자를 입력받으면 숫자보다 작은 수들 중에 소수인 것들을 모아서 배열에 집어넣어야 한다. 그리고 투 포인터를 활용하여 그 배열 안에서 n과 같은 연속합이 있는지 찾아보면 된다. 소수를 찾는 방법은 에라토스테네스의 체를 활용하면 된다. https://danidani-de.tistory.com/50 에라토스테네스의 체(소수 찾기) C++ / 과정 / 시간복잡도 :: DANIDANI 알고리즘 개념 고대 그리스 수학자 에라토스테네스가 만들어 낸 방법으로, 마치 체로 치듯이 수를 걸러낸다고 하여 '에라토스테네스의 ..
생각 투 포인터를 사용해서 풀 수 있다. st, en 두 포인터를 둔다. 1. 수들을 입력받아 배열에 저장한다. 2. 수의 합을 저장하는 변수 total은 arr[0]을 더 해주고, 줄의 길이를 저장하는 변수 len은 최대한 큰 수로 둔다(0x7fffffff). 3. en을 0으로 둔다. 4. en이 n보다 작고 total이 s보다 작다면 en을 한 칸 오른쪽으로 옮긴다. 5. 그러고도 en이 n보다 작다면 total에 arr[en]을 더 해준다. 6. 계속 더하다보면 total이 s보다 커진다. 7. 그러면 그 때 en-st+1이 len보다 작다면 len에 en-st+1을 저장한다. 8. st가 다음 칸으로 넘어가기 전에 total에서 arr[st]를 빼준다. 9. 만약 s보다 큰 부분합을 찾지 못했다..
https://www.acmicpc.net/problem/2230 2230번: 수 고르기 N개의 정수로 이루어진 수열 A[1], A[2], …, A[N]이 있다. 이 수열에서 두 수를 골랐을 때(같은 수일 수도 있다), 그 차이가 M 이상이면서 제일 작은 경우를 구하는 프로그램을 작성하시오. 예를 들어 www.acmicpc.net 생각 투 포인터를 사용하여 문제를 해결 할 수 있다. (투 포인터에 대해서 궁금하다면 밑의 링크를 클릭해서 바킹독님의 강의를 보면 된다. 이 문제에 대한 풀이도 해주신다!) https://www.youtube.com/watch?v=I_0aAKzu0m8&list=PLtqbFd2VIQv4O6D6l9HcD732hdrnYb6CY&index=21 포인터 두 개 st, en을 둔다. 1...
https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 생각 이분탐색을 이용해보자. 1. 나무의 높이들을 입력받아 벡터에 넣고 그 벡터를 오름차순으로 정렬한다. 2. 잘라진 나무의 높이의 합을 입력받는 변수(cnt)를 하나 생성한다. 3. 벡터의 루프를 돌면서 잘라진 나무의 합을 구한다. 4. 처음(st)을 1, 끝(en)을 벡터의 back()으로 놓는다. 5. mid = (st + en + 1) / 2로 놓는다..
https://www.acmicpc.net/problem/1019 1019번: 책 페이지 첫째 줄에 0이 총 몇 번 나오는지, 1이 총 몇 번 나오는지, ..., 9가 총 몇 번 나오는지를 공백으로 구분해 출력한다. www.acmicpc.net 생각 페이지를 단순히 읽어나가면서 계산하면 당연히 시간초과가 발생한다. 하지만 아무리 생각해도 내 실력으로는 해결할 수가 없었다. 따라서 밑의 블로그 내용을 참고했다. (그림도 그려가면서 상세히 설명해주셔서 더욱 이해하기에 편리했다.) https://restudycafe.tistory.com/489 [백준/BOJ] 1019번 : 책 페이지 (수학, Counting) (+ Class 6 획득) 이 포스트에서는 프로그래밍 문제 사이트 백준 Online Judge(BO..
https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 생각 그리디 알고리즘을 이용해서 풀어야되는 문제이다. 그리디 알고리즘(욕심쟁이 알고리즘, Greedy Algorithm)이란 "매 선택에서 지금 이 순간 당장 최적인 답을 선택하여 적합한 결과를 도출하자"라는 모토를 가지는 알고리즘 설계 기법이다. (출처: 나무위키) 현재 선택한 회의가 있다고 가정하자. 그러면 다음에 있는 회의 중에서 가장 종료 시간이 빠른 회의를 선택해야 최대한 많은 회의를 진행할 수 있다. 1. 회의를 종료 시간이 가장 빠른 순서로 정렬한다. (만약 종료 시간이 같다면 시작 시간이 더 빠른 ..
생각 처음에는 BFS나 DFS를 사용하면 될 것 같다고 생각했는데, 이것만 이용하면 시간 초과가 뜬다. 다이나믹 프로그래밍(DP)를 사용해야 되는데, 다이나믹 프로그래밍은 여러 개의 하위 문제를 먼저 푼 후 그 결과를 쌓아올려 주어진 문제를 해결하는 알고리즘이다. 다이나믹 프로그래밍을 사용하려면 세 가지 과정을 거쳐야 하는데, 바로 테이블 정의하기 점화식 찾기 초기값 정하기 이다. 출처: https://blog.encrypted.gg/974 [실전 알고리즘] 0x10강 - 다이나믹 프로그래밍 안녕하세요, 이번 시간에는 다이나믹 프로그래밍을 다룹니다. 직전까지 막 재귀, 백트래킹, 정렬 이런 것들로 되게 고통받으셨을텐데 오늘껀 개념도 그렇게 어렵지 않고 구현 난이도도 낮아서 blog.encrypted.gg..
