지우너

백준 1517번 | 버블 소트 (C++)(c++)백준 1517번: 버블 소트 - Study hard 코드는 위의 두 블로그를 보고 이해하는 데에 중점을 두었기 때문에 두 번째 블로그의 코드가 어떻게 작동하는지 노트에 쓰면서 이해한 것만 올리려고 한다. 노트에 정리한 것이라 조금 더러울 수는 있지만, 좀 더 깔끔하게 정리할 수 있으면 그렇게 하고 싶다.재귀는 역시 좀 복잡하다는 생각이 들었다.mergeSort는 범위를 1/2씩 쪼개는 함수인 것 같고, merge함수에서 정렬+떨어진 두 수의 거리를 구하는 역할을 한다.

더보기#include #include #define MAX 1000001using namespace std;int N; // (1 ≤ N ≤ 1,000,000)long long M; // (1 ≤ M ≤ 2,000,000,000)long long treeHeight[MAX];int main(){ // 나무의 수 N과 가져가려고 하는 나무의 길이 M cin >> N >> M; long long maxi=0; // 둘째 줄에는 나무의 높이가 주어진다. for (int i=0; i> treeHeight[i]; maxi=max(maxi, treeHeight[i]); } // 나무의 높이의 합은 항상 M보다 크거나 같기 때문에, 상근이는 집에 필요한 나무를 항상 ..

백준 11725번 트리의 부모 찾기 - 꾸준함위의 링크를 보면서 parent를 2부터 N까지 출력하는 부분이 이해가 되지 않았다.for (int i=2; i결론부터 말하자면 DFS(1)부터 시작하니까 parent[1]은 채워질 수 없다.이미 방문한 노드 1을 다시 방문할 수 없기 때문에 next=1이 저장되었을 때, parent[next]=node가 실행되지 않는다.따라서 parent[1]에 어떤 수가 저장 될 수 없는 것이다.그래서 parent[0], parent[1]은 수가 채워지지 않을 수밖에 없고, 2부터 N까지 parent[i]를 출력하는 것이 답이 된다. DFS(1)을 했을 때, tree[1][i]에 저장된 수들은 next에 저장되어 parent[i]=1이 된다.그리고 다시 DFS(i). 이때..

1158 문제에서 범위가 (1 ≤ K ≤ N ≤ 100,000) 이렇게 늘어났고, 시간제한이 2초 → 0.15초가 되었다.이 문제는 Segment Tree를 이용해서 푸는 문제.Segment Tree는 구간합, 구간최솟값 등 특정 구간의 정보를 관리할 때 유용하게 쓰이는 자료구조이다.본 문제에서는 Segment Tree를 다음과 같이 구간에서 살아있는 원소의 갯수를 관리하기 위해 사용한다. 세그먼트 트리(Segment Tree)개인적으로 기초설명이 가장 잘 되어 있는 블로그! 꼼꼼히 여러 번 읽으면서 이해하기 [C/C++] 백준 1168번 - 요세푸스 문제 2 (세그먼트 트리)백준 - 요세푸스 문제 2 (1168 번)내 기준에서 처음 봤을 때, 위의 블로그보다 이해하기가 쉬웠다.아마 배열 크기를 1두 블..

반복수열 문제 바로가기A=57, P=2일 때, 수열 D는 [57, 74$(=5^2+7^2=25+49)$, 65$(=7^2+4^2=49+16)$, 61$(=6^2+5^2=36+25)$, 37, 58, 89, 145, 42, 20, 4, 16, 37, …]이 된다. 그 뒤에는 앞서 나온 수들(57부터가 아니라 58부터)이 반복된다.빨간색으로 표시한 부분이 반복된다는 의미 같다.A는 시작하는 수고, A부터 A의 각 자리를 P제곱하여 더한 수가 그 다음 수가 되는 문제. 참고사이트: 백준 2331번 반복수열 - 꾸준함코드는 위의 사이트를 보면서 짰기 때문에 풀이만 작성 처음 방문하면 visited[num]이 1이 된다.위의 예시를 보면 [57, 74, 65, 61, 37, 58, 89, 145, 42, 20, ..

https://www.acmicpc.net/problem/1676 1676번: 팩토리얼 0의 개수N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오.www.acmicpc.net 아래와 같이 풀었는데, 시간 초과가 떴다.#include using namespace std;int main(){ // 첫째 줄에 N(0 ≤ N ≤ 500)이 주어진다. int N; cin >> N; // 팩토리얼 저장 long long factorial[N+1]; factorial[0]=1; factorial[1]=1; for (int i=2;i[백준][C++] 1676: 팩토리얼 0의 개수 - 토르비욘[백준] 알고리즘 C++ 1676번 - ..