About Dev

https://www.acmicpc.net/problem/11505 11505번: 구간 곱 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 곱을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 알고리즘 : 세그먼트 트리 풀이 날짜 : 2023.07.20. 다음 문제와 연산 종류만 다를 뿐 동일한 문제이다. [백준/Tree] - 백준 2042: 구간 합 구하기 [골드 Ⅰ/ Java] 입력 값 크기가 크고, 그 값들을 곱하는 연산을 하기 때문에, 연산 중간중간 정해진 값 (mod = 1,000,000,007) ..

https://www.acmicpc.net/problem/10868 10868번: 최솟값 N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100,000)개 주어졌을 때는 www.acmicpc.net 알고리즘 : 세그먼트 트리 풀이 날짜 : 2023.07.20. 세그먼트 트리를 이용하는 문제이다. 시작 노드와 끝 노드의 부모를 타고 올라 오다가 만나는 노드 값이 답이다. 세그먼트 트리에 대한 설명은 다음 글에 기재되어있다. [백준/Tree] - 백준 2042: 구간 합 구하기 [골드 Ⅰ / JAVA] 하지만 위와 같이 자매 노드와 비교를 해..

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 Solution 세그먼트 트리, 펜윅 트리 배열의 부분 합을 구할 때 보통 합 배열을 이용한다. 하지만 크기가 7인 배열의 3번째 값이 바뀌면, 합 배열을 3번부터 끝까지 다 수정해야 한다. 대신에 세그먼트 트리로 배열을 이진 트리처럼 저장하면, 관련된 부분만 수정할 수 있다. 자료 구조만 바꾸었는데 탐색 횟수가 반으로 줄었음을 알 수 있..

https://www.acmicpc.net/problem/14426 14426번: 접두사 찾기 문자열 S의 접두사란 S의 가장 앞에서부터 부분 문자열을 의미한다. 예를 들어, S = "codeplus"의 접두사는 "code", "co", "codepl", "codeplus"가 있고, "plus", "s", "cude", "crud"는 접두사가 아니다. 총 N개의 문자 www.acmicpc.net 알고리즘 : 트라이 풀이 날짜 : 최대가 N = 10,000, M = 10,000 트라이 자료구조를 공부한 문제이다. 더보기

https://www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net Solution DFS, BFS 문제에서 노드의 개수 N이 최대 100,000 이고, 싸이클이 없는 트리의 엣지 개수는 N - 1 이다. 노드 간 거리를 다 계산하고 비교해서 트리의 지름을 구하면 총 연산 횟수는 O(N²) 가 되어 시간 초과가 발생한다. 대신 이 연산을 직접 완전 탐색해서 모든 거리를 계산하고 공통점을 관찰해 보면, 어떤 노드에서든지 트리의 지름의 노드까지 거리가..