안녕 세상아,

https://www.acmicpc.net/problem/11279 11279번: 최대 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net priority_queue의 정말 기본 문제이다. 시간 초과되지 않기 위해 몇개 신경쓰고 추가해주거나 바꿔주면 된다. https://hello-world-cpp.tistory.com/49 [c++/백준]1927 최소 힙 https://www.acmicpc.net/problem/1927 1927번: 최소 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다...

https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 팀 나누고 최솟값 구하는게 중요한 것 같다. #include #include using namespace std; int n; int arr[21][21]; bool isVisited[22]; int minNum = 10000000;//최솟값 찾기 위함 void dfs(int x, int idx) { if (x == n / 2) { int start, link; start = 0; link = 0; //start와 l..

https://www.acmicpc.net/problem/1927 1927번: 최소 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 힙 구현의 가장 기초인것 같다. 구현을 해도 되지만 STL 사용하면 더 쉽게 풀 수 있다. 우선순위 큐는 삽입 순서에 상관 없이 우선순위가 가장 높은 원소가 먼저 출력되는 특징을 갖고있다. 일반적으로는 값이 가장 큰 원소가 먼저 출력이 되지만 아래와 같이 조건을 붙여주면 값이 가장 작은 원소가 먼저 출력될 수 있다. 우선순위 큐의 기본 템플릿은 priority_queue < 자..

https://www.acmicpc.net/problem/9020 9020번: 골드바흐의 추측 1보다 큰 자연수 중에서 1과 자기 자신을 제외한 약수가 없는 자연수를 소수라고 한다. 예를 들어, 5는 1과 5를 제외한 약수가 없기 때문에 소수이다. 하지만, 6은 6 = 2 × 3 이기 때문에 소수가 아 www.acmicpc.net 두 소수의 차가 가장 작은 것을 골라서 출력해야돼서 까다로웠던 문제였다. while문 전까지는 에라토스테네스의 체를 이용하여 전체 범위의 수 중 소수를 구했다. 두 소수의 차가 가장 작은 것을 구하기 위해 함수도 만들어보고 이것저것 해봤지만 안됐고 어떤 블로그의 천재님이 해놓으신 방법을 참고하여 풀었다. 소수의 차가 가장 작으려면 최대한 중앙값을 구해야한다. #include u..

https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 이분탐색 처음엔 쉽게 생각했는데 정답률 21프로인건 이유가 있는거였다. 답은 제대로 다 나오는데 제출만 하면 틀려서 멘붕 .. 틀린 이유 중 가장 큰 이유는 자료형 제대로 다 안맞춰서인 것 같다. 어떤건 long long int, 어떤건 int로 해서 다른 자료형이 합쳐지면서 틀렸다. 그리고 left값을 0으로 두고 풀어서 컴파일 에러가 떴다. 런타임에러, 컴파일 에러..

https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 생각해내기 꽤 어려웠던 문제였다. 마이너스가 한번 나오면 그 이후는 모두 마이너스로 계산하는 것이 포인트인 것 같다. 그리고 i가 str.size()와 같을 때도 계산해주는걸 잊으면 안된다. ans에 남아있는 숫자를 털어서 계산해줘야 정답이 나온다. #include #include using namespace std; int main() { ios::sync_with_stdio(false);..

https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 이분탐색을 이용해서 간단하게 풀 수 있는 문제이다. #include #include #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int n, m; int ans = 0; cin >> n >> m; vector v;//나무..

https://www.acmicpc.net/problem/4948 4948번: 베르트랑 공준 베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼 www.acmicpc.net 에라토스테네스의 체를 사용해서 구하는 문제이다. 개인적으로 실2까진 아닌 것 같다. #include using namespace std; int arr[1000000]; int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int n; while (1) { cin >> n; int cnt = 0;//cnt 초기화 ..

https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net 연결 요소가 뭔지 몰라서 문제에서 나온 예제를 직접 그려보며 이해했다. 연결 요소의 개수는 간단하게 말해서 각각 서로 연결되지 않은 그래프의 개수이다. dfs를 이용하여 탐색을 하였고, main문에서 일정한 조건으로 반복문을 돌리면서 cnt를 ++해주었다. #include #include using namespace std; int n..

https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net dp의 순서를 찾아준 후 최댓값을 따로 만들어서 풀어주었다. 생각보다 쉽게 풀었다. 순서는 첫번째 빼고 (dp의 직전 값과 arr의 현재 값을 더해준 것, arr의 현재값)을 비교해서 더 큰 값을 dp에 넣어주면 된다. 고려해야될 것은 계속하다보면 가장 큰 합이 구해졌는데 음수를 계속 더해서 작아지는 경우가 있다. 이런 경우를 대비하여 큰 수를 갱신할 maxCount값을 만들었다. #include #incl..