개발 노트

백준 2912번 백설공주와 난쟁이https://www.acmicpc.net/problem/2912 세그먼트 트리, 이진탐색 알고리즘 문제 세그먼트 트리 모아보기: https://noteofdeveloper.tistory.com/tag/%EC%84%B8%EA%B7%B8%EB%A8%BC%ED%8A%B8%ED%8A%B8%EB%A6%AC 이진탐색 모아보기: https://noteofdeveloper.tistory.com/tag/%EC%9D%B4%EC%A7%84%ED%83%90%EC%83%89 너무 어려워서 잡히는 줄 알았다....ㅠㅠㅠ 인덱스를 이용해 자식노드에 접근할 일이 없으므로 세그먼트로 풀기에 좋은 문제 세그먼트 트리는 루트부터 값이 들어가게 되므로 이런 형태로 그려진다. (색상명,난쟁이수)쌍으로 구성 ..

문제 https://github.com/Hline/algorithm/blob/master/SW210813_%ED%86%A8%EB%B9%84/%ED%86%A8%EB%B9%84.txt 샘플케이스 https://github.com/Hline/algorithm/blob/master/SW210813_%ED%86%A8%EB%B9%84/in

백준 2357번 최솟값과 최댓값 https://www.acmicpc.net/problem/2357 계속 구간을 찾아야하므로 세그먼트 트리로 풀어낼 수 있다. 세그먼트 트리 자료 https://noteofdeveloper.tistory.com/63 최댓값, 최소값쌍 트리.

백준 2042번 구간합구하기 https://www.acmicpc.net/problem/2042 계속 구간을 찾아야하므로 세그먼트 트리로 풀어낼 수 있다. 세그먼트 트리 자료 https://noteofdeveloper.tistory.com/63

백준 10868번 최솟값 https://www.acmicpc.net/problem/10868 계속 구간 최소를 찾아야하므로 세그먼트 트리로 풀어낼 수 있다. 세그먼트 트리 자료 https://noteofdeveloper.tistory.com/63

인덱스 트리 개념설명 https://beenii.tistory.com/156 세그먼트 트리 개념설명 https://minusi.tistory.com/entry/%EC%84%B8%EA%B7%B8%EB%A8%BC%ED%8A%B8-%ED%8A%B8%EB%A6%ACSegment-Tree-Index-Tree 인덱스 트리 vs 세그먼트 트리 인덱스 트리: 리프노드를 모두 채워서 만듦. 특정 인덱스(node)로 지정 탐색이 가능. 업데이트도 지정 업데이트 가능(리프노드부터 업데이트 가능) 세그먼트 트리: 필요한 리프노드만 채움. 불완전 트리라서 특정 인덱스(node)로 지정 탐색이 어려움. 업데이트도 지정 업데이트가 불가능(루트노드부터 업데이트 필요) => 문제에서 인덱스가 주어지는 경우 인덱스 트리를 사용하는 것이..

풀이: 이 문제의 특이점 1. 나중에 지나가는 공은 그 지점의 점수를 얻을 수 없다 = 나와 상대의 단계가 다르다 2. 공이 이동하다가 한 지점에 동시 도착하면 공이 부딪혀 게임판 밖으로 나가기 = 나와 상대의 단계가 같다 을 고려하기 위해서는 나와 리아의 단계를 확인해야한다. 동시 도착한 지점이 공통 조상이므로 공통조상을 구해야한다. LCA와 동일한 유형이므로 LCA에서 고려해야할 항목들이 동일하게 적용된다. LCA 바로가기 (2. 반복문(for/while) 하나에서 두 정점을 동시에 탐색해야 한다. 3. 각 정점별 단계를 미리 단계를 알아놔야한다.) 이 때, 특점 지점에서 이동하는 경로가 고정되어 있으므로 1부터 각지점까지의 누적합을 구해두면 이 문제의 특이점을 쉽게 해결할 수 있다. 공통조상까지의 ..

BOJ 11437번 LCA https://www.acmicpc.net/problem/11437 풀이: 다른 사람들이 왜 이렇게 풀어야만 했는지 이해를 못해서.... 한참 헤맸다 문제에 주어지지 않는 게 있는데 *부모-자식 관계의 정의*가 주어지지 않는다. 1. 주어진 정점들을 다 연결했을 때 1과 가까운 노드가 부모가 된다. 최상위가 1번이라서 작은수가 부모가 된다고 착각하면 방황하게 된다ㅠㅠ 정점을 하나씩 탐색 돌리면 시간 초과가 뜨고, 문제는 항상 한 쌍으로 주어지기 때문에 2. 반복문(for/while) 하나에서 두 정점을 동시에 탐색해야 한다. 두 정점을 동시에 탐색하려면 각 정점의 단계(Level)을 알아야한다. 정점별로 탐색을 돌리면 시간초과가 뜨기 때문에 3. 각 정점별 단계를 미리 단계를 ..