자료구조 (Data Structure)자료구조란 효율적으로 접근하고 수정할 수 있도록 데이터를 구성하고 저장하는 방법.저장되는 데이터의 형태에 따라 선형 자료구조와 비선형 자료구조로 구분된다.선형 자료구조 : 데이터가 일렬로 나열되어 있음배열, 연결 리스트, 스택, 큐비선형 자료구조 : 데이터가 특정한 형태를 띄고 있음트리, 그래프 1. 배열 (Array)가장 기본적인 자료구조로 동일한 자료형의 데이터를 일렬로 나열한 자료구조배열의 특징데이터 접근이 용이하다. (O(1)의 시간복잡도를 가짐)데이터 삽입/삭제가 어렵다. (O(N)의 시간복잡도를 가짐)중간에 데이터를 삽입하거나 삭제할 경우, 해당 위치 이후의 모든 요소를 이동해야 한다.구조가 간단하여 프로그램 작성이 쉽다.1) 배열 []int[] arr =..
https://www.acmicpc.net/problem/2243알고리즘 분류 : 자료 구조, 세그먼트 트리, 이분 탐색 ❓문제🔅해석 세그먼트 트리에서 구간의 정보를 조회하는 query는 총 다섯가지 정보를 넘긴다.query(int left, int right, int node, int queryLeft, int queryRight) 현재 문제에서는 해당 순위의 정보만 필요하므로 query(int left, int right, int node, int query) 으로 넘긴다. 문제의 입력을 보자면, 레벨 1 사탕 2개, 레벨 3 사탕 3개가 존재하고 여기서 2번째로 맛있는 사탕을 꺼내준다고 할 때, 답은 레벨 1이다. 위 그림을 볼 때, 노드를 탐색하면서 해당 노드의 값이 B보다 크거나 같을 때 왼쪽..
https://www.acmicpc.net/problem/2042알고리즘 분류 : 자료 구조, 세그먼트 트리 ❓문제🔅해석세그먼트 트리를 이용하는 가장 기본적인 문제이다.인덱스 트리 생성 - init인덱스 트리의 리프 노드에 배열을 담아야 하므로 리프 노드가 시작하는 인덱스 번호를 알아야한다.리프 노드의 개수를 S로 표현하고 S는 N 이상의 2^n으로 표현 가능한 수여야 한다.따라서 S 는 아래와 같이 구한다. (N은 주어진 배열의 크기)S = 1;while (S 리프 노드에 배열에 적혀있는 수를 넣기위해 S번째부터 넣는다.그 외 내부 노드는 S - 1번째부터 자식 노드(왼쪽, 오른쪽) 합을 대입한다.private static void init() { // leaf노드 채우기 for (in..
