개발 노트

백준 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 너무 어려워서 잡히는 줄 알았다....ㅠㅠㅠ 인덱스를 이용해 자식노드에 접근할 일이 없으므로 세그먼트로 풀기에 좋은 문제 세그먼트 트리는 루트부터 값이 들어가게 되므로 이런 형태로 그려진다. (색상명,난쟁이수)쌍으로 구성 ..

백준 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)로 지정 탐색이 어려움. 업데이트도 지정 업데이트가 불가능(루트노드부터 업데이트 필요) => 문제에서 인덱스가 주어지는 경우 인덱스 트리를 사용하는 것이..

BOJ 2042 구간 합 구하기 java 백준 2042 구간 합 구하기 https://www.acmicpc.net/problem/2042 2042번: 구간 합 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 풀이: 값도 계속 변경되고 구간도 계속 변경되므로 세그먼트 트리 사용. 입력값의 범위가 크므로 반드시 long 타입 사용 long 타입으로 파싱하는 부분 주의! (Long.parseLong(st.nextToken())) 트리 초기화 첫번째 값 변경

백준 10868번 최솟값 https://www.acmicpc.net/problem/10868 10868번: 최솟값 N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100,000)개 주어졌을 때는 www.acmicpc.net 풀이: 최소값을 구해야하는 범위가 계속 바뀌는 문제 미리 구간별 최소값을 구해놓는 세그먼트 트리 활용

문제 백준 2357번 최솟값과 최댓값 https://www.acmicpc.net/problem/2357 풀이: 최소값과 최대값을 구해야하는 값의 범위가 계속 변함 세그먼트 트리를 이용하여 트리 구성 시 미리 최대값과 최소값을 구해두고 요구하는 범위에서 뽑아 쓰는 방식