코린이의 소소한 공부노트

1. 개념 정리 1) 이진 인덱스 구조를 활용하여 구간 합 문제를 효과적으로 해결해 줄 수 있는 자료구조 2) 펜윅 트리(Fenwick Tree)라고도 불린다. 3) 세그먼트 트리보다 구현하기 편하고 속도가 빠르다. - 세그먼트 트리는 필요한 리프 노드만 채우기 때문에 불완전 트리지만, 인덱스 트리는 리프 노드를 모두 채워서 만들기 때문에 인덱스를 활용할 수 있다. - 데이터의 개수가 N개일 때, 세그먼트 트리를 만들기 위해 필요한 공간을 통상 4*N만큼 준비했었다면 인덱스 트리를 만들 때는 N만큼만 준비하면 된다. 4) 인덱스는 1부터 사용하고, 인덱스를 활용하면 해당 인덱스의 값이 몇 개의 데이터의 합인지 알 수 있다. - 8비트로만 간단히 예시를 들어보면, 3과 -3을 비트 and 연산을 해보면 다..

1. 개념 정리 1) 여러 개의 데이터가 연속적으로 존재할 때 특정 구간의 데이터의 합을 담은 이진 트리 2) 실제 구현은 트리가 아닌 배열로 하게 된다. - 배열은 인덱스가 있어 접근성이 좋기 때문이다. 3) 세그먼트 트리를 이용한 구간 합 처리의 시간 복잡도는 O(lgn)이다. 2. 예시 1) 구간 합의 데이터가 될 배열을 준비한다. int[] arr = {1,2,3,4,5,6,7,8}; 2) 구간 합 트리가 될 배열도 준비한다. int[] tree = new int[32]; // arr.length * 4 // 데이터의 개수가 N개일 때 필요한 부분 합 트리의 공간은 // N 이상의 2의 거듭제곱수 중 가장 작은 것 * 2이다. // 여기서 N=8이므로 8 이상의 2의 거듭제곱수 중 가장 작은 것은..

1. 개념정리 1) 트리: 값을 가진 노드(node)가 엣지(edge)로 연결되어 있는 구조 - 상위 노드를 부모, 하위 노드를 자식이라 부른다. - 최상위 노드는 루트(root)라고 부른다. - 부모 노드에 자식 노드가 0~n개 연결되어 있는 구조 2) 이진 트리(binary tree): 자식 노드가 최대 2개인 트리 3) 이진 탐색 트리(binary search tree): 부모의 왼쪽에는 부모의 값보다 작거나 같은 값을 가진 노드가, 오른쪽에는 크거나 같은 값은 가진 노드가 있는 트리 2. 구현 코드 class Node{ // 정수 값을 담는 노드 protected Node left; protected Node right; protected int value; Node(int value){ this..

1. 개념정리 1) 뒤쪽에서는 삽입이, 앞쪽에서는 삭제가 일어나는 구조 2) FIFO(First In First Out, 첫 삽입 데이터가 먼저 삭제됨) 3) java.util 패키지에 Queue 인터페이스가 있고, 이를 구현한 클래스 중 대표적인 것이 LinkedList가 있다. 2. 구현 코드 class ArrayQueue{ // int[]로 구현하는 큐 protected final int defCap = 100;// 큐의 용량 protected int[] queue;// 큐로 사용할 배열 protected int numElements = 0;// 큐에 들어간 요소의 개수 protected int front = 0;// 큐의 맨 앞 인덱스 protected int rear;// 큐의 맨 뒤 인덱스 p..

1. 개념정리 1) 한쪽에서만 데이터 삽입과 삭제가 가능한 구조 2) LIFO(Last In First Out, 마지막 삽입 데이터가 먼저 삭제됨) 3) java.util 패키지에 Stack 클래스가 있다. 2. 구현 코드 class ArrayStack{ // int[]로 구현하는 스택 protected final int defCap = 10; // 스택의 용량 protected int[] stack; // 스택의 요소를 담을 배열 protected int topIndex = -1; // 스택의 가장 마지막 인덱스 public ArrayStack() { // 기본 생성자 stack = new int[defCap]; } public ArrayStack(int maxSize) { // 스택의 크기를 지정한 ..

1. 개념정리 1) 같은 타입인 여러 개의 변수를 하나로 묶어놓은 것 - 타입은 기본형, 참조형 가리지 않는다. - 물리적으로(하드디스크) 연속되지 않은 공간에 있어도 상관없다.. - java.util 패키지에 LinkedList 클래스가 있다. 2) 리스트의 요소를 노드(node)라고 부르며, 각 노드에는 값(value)과 다음 노드의 주소가 저장된 링크(next)가 있다. - 특히, 맨 앞 노드를 head, 맨 뒤 노드를 tail이라고 부른다. - 마지막 노드라면 next == null - 데이터가 추가되면 연결만 해주면 되기 때문에, 연결 리스트의 최대 크기는 정해져 있지 않다. 3) 이중 연결 리스트는 단순 연결 리스트에서 이전 노드의 주소가 저장된 링크(previous)가 추가된 것이다. - 맨..

1. 개념정리 1) 같은 타입인 여러 개의 변수를 하나로 묶어놓은 것 - 타입은 기본형, 참조형 가리지 않는다. - 물리적으로(하드디스크) 연속된 공간에 저장되어있다. - 자바는 참조변수에 배열의 시작주소를 저장해서 이용하고 있다. 2) 배열의 크기는 배열을 이루고 있는 요소의 개수와 같다. - 한번 선언된 배열의 크기는 바꿀 수 없다. - 크기를 늘리고싶다면 새 배열을 만들어 반복문이나 System.arraycopy() 등을 이용해 요소를 복사해야 한다. - java.util 패키지에 있는 ArrayList 클래스를 이용해서 유연한 배열을 사용할 수 있다. 3) 배열이 다른 배열의 요소가 될 수 있다. - 1차원 배열의 요소가 1차원 배열이라면 그 배열은 2차원 배열이 된다. 4) 인덱스(위치)는 0번..

1. 단순구조(기본구조): 언어에서 기본으로 제공하는 타입 2. 선형구조: 데이터가 연속적으로 붙어있거나 순서가 정해져 있는 구조 1) 리스트(배열, array): 데이터가 연속적으로 붙어 있는 구조 2) 연결 리스트(linked list): 불연속적인 데이터가 링크를 통해 연결되어 있는 구조 - 단순 연결 리스트: 한 데이터가 다음 데이터(next)를 가리키고 있는 구조. 순서가 있다. - 이중 연결 리스트(doubly linked list): 연결 리스트에서 이전 데이터(previous)를 가리키는 링크를 추가한 구조 - 원형 연결 리스트(circular linked list): 이중 연결 리스트에서 맨 앞 데이터와 맨 뒤 데이터를 연결하는 링크를 추가한 구조 3) 스택(stack): 한쪽에서만 데이..