지우너

백준 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번 - ..