Doby's Lab

https://www.acmicpc.net/problem/12837 12837번: 가계부 (Hard) 살아있는 화석이라고 불리는 월곡이는 돈에 찌들려 살아가고 있다. 그에게 있어 수입과 지출을 관리하는 것은 굉장히 중요한 문제이다. 스마트폰에 가계부 어플리케이션을 설치해서 사용하려 www.acmicpc.net 처음에 문제의 뜻을 몰라서 TC보고 구간합 세그먼트 트리인 걸 알았다. 그리고 1번 쿼리에서는 b번 인덱스에 C를 더하라는 뜻이다. 이번 문제는 배열 선언이 필요 없다. 애초에 초기 값이 모두 0이기 때문에 따로 선언하지 않고, 바로 트리에다가 코드를 짰다. 초기 값이 0이다 보니 세그먼트 트리 전처리 함수도 필요가 없었다. [AC 코드] #include #define ll long long #de..

https://www.acmicpc.net/problem/5971 5971번: Meeting Place Bessie and Jonell are great friends. Since Farmer John scrambles where the cows graze every day, they are sometimes quite far from each other and can't talk. The pastures and paths on FJ's farm form a 'tree' structure. Each pasture has exactly one distinct www.acmicpc.net 영어문제였지만 어느 정도 해석이 가능했기에 풀 수 있었다. 1) 노드의 개수와 쿼리의 개수가 주어진다. 2) 2 ~ n까..

https://www.acmicpc.net/problem/3584 3584번: 가장 가까운 공통 조상 루트가 있는 트리(rooted tree)가 주어지고, 그 트리 상의 두 정점이 주어질 때 그들의 가장 가까운 공통 조상(Nearest Common Anscestor)은 다음과 같이 정의됩니다. 두 노드의 가장 가까운 공통 조상은, 두 www.acmicpc.net 테스트 케이스마다 매번 루트 노드가 달라지기 때문에 트리가 만들어지기 전에 루트 노드를 먼저 찾아야 했다. 그래도 이번 문제에서는 a와 b가 주어졌을 때 부모-자식 관계가 명확했기 때문에 루트 노드를 찾는 함수를 만들 수 있었다. for (int i = 1, a, b; i > a >> b; adj[a].push_ba..

https://www.acmicpc.net/problem/11437 11437번: LCA 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정 www.acmicpc.net 이번에 공부했던 알고리즘은 LCA (Lowest Common Ancestor, 최소 공통 조상)이다. 우선 공부했던 블로그들 (https://zoomkoding.github.io/algorithm/2019/07/27/LCA.html) (https://4legs-study.tistory.com/121) [개요] 트리에서 두 정점이 주어졌을 때, 두 정점의 조상(부모) 노드 중 공통되며 가장 가..

https://www.acmicpc.net/problem/16975 16975번: 수열과 쿼리 21 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 i j k: Ai, Ai+1, ..., Aj에 k를 더한다. 2 x: Ax 를 출력한다. www.acmicpc.net 구간합 lazy propagation으로 구현해주었다. >> 1번 쿼리 (구간 합 업데이트) 때문에 세그먼트 트리를 써야 했다. 그런데 구간 업데이트라서 lazy propagation이 필요했다. lazy propagation 개념 공부할 때와 똑같은 구성이라 그런지 어렵게 느껴지진 않았었다. #include #define MAX (100000 + 1) #define ll lo..

https://www.acmicpc.net/problem/15723 15723번: n단 논법 m개의 줄에 걸쳐 각 줄에 결론이 참인지 거짓인지 출력하라. 참일 경우 T, 거짓일 경우 F를 출력하라. 알 수 없는 경우도 거짓이다. 답은 필히 대문자로 출력해야 한다. www.acmicpc.net 이번 문제의 포인트는 플로이드 와샬과 문자열을 변환시키는 일이었다. n단 논법에 따라 a가 b라고 해서 b는 a가 되는 것은 아님을 알고 단방향 그래프로 표현해준다. 문자열은 getline을 썼고, n이나 m을 입력받고서는 버퍼에 '\n'가 남아있기 때문에 cin.ignore()을 해준다. #include #include #define MAX (26 + 1) #define INF 987654321 using name..

https://www.acmicpc.net/problem/10610 10610번: 30 어느 날, 미르코는 우연히 길거리에서 양수 N을 보았다. 미르코는 30이란 수를 존경하기 때문에, 그는 길거리에서 찾은 수에 포함된 숫자들을 섞어 30의 배수가 되는 가장 큰 수를 만들고 싶어한 www.acmicpc.net 30의 배수가 되는 경우를 백트래킹을 돌려야 하나 생각했는데 수의 길이가 10^5만큼 주어져서 시간 초과가 날 거 같았다. 이 문제는 수학적인 접근이 필요하다. 우선 30의 배수가 될 수 있는 조건은 0이 포함되어야 한다. (끝자리에) 모든 수를 더했을 때, 3의 배수여야 한다. 3의 배수 조건 == (각 자리의 수를 더했을 때, 3의 배수여야 한다.) 다음 수학 지식을 가지고 있다면 풀 수 있었다..

https://www.acmicpc.net/problem/14438 14438번: 수열과 쿼리 17 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 i v : Ai를 v로 바꾼다. (1 ≤ i ≤ N, 1 ≤ v ≤ 109) 2 i j : Ai, Ai+1, ..., Aj에서 크기가 가장 작은 값을 www.acmicpc.net 업데이트를 하는 부분에서 문제가 있었는데 leaf 노드에서 value값을 새롭게 할당하고, (start 즉, leaf노드만 새로운 값으로 할당 시키고 나머지는 update를 시켜주면 된다. int update(int start, int end, int node, int index, int value) { if (ind..