[D-5] 1722 : 순열의 순서(Java)
📍 백준 1722번시간제한메모리제한제출정답 정답맞힌 사람정답 비율2 초128 MB163204923380834.168%✅ 문제1부터 N까지의 수를 임의로 배열한 순열은 총 N! = N×(N-1)×…×2×1 가지가 있다.임의의 순열은 정렬을 할 수 있다. 예를 들어 N=3인 경우 {1, 2, 3}, {1, 3, 2}, {2, 1, 3}, {2, 3, 1}, {3, 1, 2}, {3, 2, 1}의 순서로 생각할 수 있다. 첫 번째 수가 작은 것이 순서상에서 앞서며, 첫 번째 수가 같으면 두 번째 수가 작은 것이, 두 번째 수도 같으면 세 번째 수가 작은 것이….N이 주어지면, 아래의 두 소문제 중에 하나를 풀어야 한다.k가 주어지면 k번째 순열을 구하고, 임의의 순열이 주어지면 이 순열이 몇 번째 순열인지..
더보기
[D-8] 🤔세그먼트 트리
📍 세그먼트 트리✅ 정의주어진 데이터들의 구간 합과 데이터 업데이트를 빠르게 수행하기 위해 고안해낸 자료구조의 형태를 말한다.더 큰 범위는 인덱스 트리라고 부른다. ✅ 핵심 이론세그먼트 트리의 종류 : 구간 합, 최대 및 최소 구하기구현 단계 : 트리 초기화 하기, 질의값 구하기(구간 합 또는 최대 및 최소 구하기), 데이터 업데이트하기 ✅ 수행 과정1. 트리 초기화하기리프 노드의 개수가 데이터의 개수(N) 이상이 되도록 트리 배열을 만든다.트리 배열의 크기를 구하는 방법은 2^k >= N을 만족하는 k의 최솟값을 구한 후 2^k * 2를 트리 배열의 크기로 정의한다.리프 노드를 제외한 나머지 노드의 값을 채운다(2^k -1부터 1번쪽으로 채운다.). 샘플 데이터{5, 8, 4, 3, 7, 2, 1, ..
더보기
