자료구조

[백준] 16235 - 나무 재테크 (자바 Java)

[Gold III] 나무 재테크 - 16235 문제 링크 성능 요약 메모리: 142464 KB, 시간: 1044 ms 분류 자료 구조(data_structures), 구현(implementation), 시뮬레이션(simulation) 문제 설명 부동산 투자로 억대의 돈을 번 상도는 최근 N×N 크기의 땅을 구매했다. 상도는 손쉬운 땅 관리를 위해 땅을 1×1 크기의 칸으로 나누어 놓았다. 각각의 칸은 (r, c)로 나타내며, r은 가장 위에서부터 떨어진 칸의 개수, c는 가장 왼쪽으로부터 떨어진 칸의 개수이다. r과 c는 1부터 시작한다. 상도는 전자통신공학과 출신답게 땅의 양분을 조사하는 로봇 S2D2를 만들었다. S2D2는 1×1 크기의 칸에 들어있는 양분을 조사해 상도에게 전송하고, 모든 칸에 대해..

[자료구조] 이진 트리의 구현, 순회 (자바/Java)

이진 트리를 각각 배열과 링크드 리스트로 구현하고 트리의 노드들을 전위순회, 중위순회, 후위순회하는 코드를 구현하였다. 1. 배열 1-1. 트리 구현 배열로 이진 트리를 구현할 때는 배열의 index를 통해 부모와 자식 노드를 확인할 수 있다. 루트 노드의 index를 1로 하고, 같은 층위의 노드들을 순서대로 배열에 삽입하면 부모 노드의 인덱스가 i일 때 자식 노드의 인덱스는 i*2, i*2+1이 된다. 전체 정점의 개수를 입력받고 그 다음 줄에 각 간선의 parent와 child 값을 입력받는다. 13 1 2 1 3 2 4 3 5 3 6 4 7 5 8 5 9 6 10 6 11 7 12 11 13 위 케이스에서 1 2는 부모가 1, 자식 노드가 2임을 의미한다. 이때 루트노드는 부모 노드가 없으니 첫 ..

[백준] 10866 - 덱 Deque (자바/Java)

문제 정수를 저장하는 덱(Deque)를 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오. 명령은 총 여덟 가지이다. push_front X: 정수 X를 덱의 앞에 넣는다. push_back X: 정수 X를 덱의 뒤에 넣는다. pop_front: 덱의 가장 앞에 있는 수를 빼고, 그 수를 출력한다. 만약, 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다. pop_back: 덱의 가장 뒤에 있는 수를 빼고, 그 수를 출력한다. 만약, 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다. size: 덱에 들어있는 정수의 개수를 출력한다. empty: 덱이 비어있으면 1을, 아니면 0을 출력한다. front: 덱의 가장 앞에 있는 정수를 출력한다. 만약 덱에 들어있는 정수가 없는 경우에..

[자료구조] 트리 & 이진 탐색 트리 Binary Search Tree (자바/Java)

목차 트리 (Tree) 비-선형 자료 구조 (Non-Linear) 선형 자료 구조: 구조에 저장될 데이터들이 순차적으로 저장되는 형태 ArrayList, LinkedList, Map, Stack, Queue 등 비-선형 자료 구조: 복수의 데이터들이 복수의 데이터들과 연결될 수 있는 구조 Tree 검색 트리 내장 vs 외장 검색 트리 내장 검색 트리: 메인 메모리 내에 존재 외장 검색 트리: 검색 트리가 외부(주로 디스크)에 존재-검색 트리 전체를 메인 메모리에 올려놓고 쓸 수 없는 경우 이진 검색 트리(Binary Search Tree) 특성 각 노드는 키값을 하나씩 갖는다. 이 키값은 모두 다르다. 최상위 레벨에 루트 노드가 있고, 각 노드는 최대 2개의 자식 노드를 갖는다. 임의 노드의 키값은 자기..

[자료구조] 스택 Stack & 큐 Queue

목차 Stack 스택 물건을 쌓아 올리듯 자료를 쌓아 올린 형태의 자료구조 Last in First out: 마지막에 삽입한 자료를 가장 먼저 꺼냄 선형구조(자료 간의 관계가 1대 1의 관계) 맨 위의 원소만 접근 가능(top) 응용: 문자열 뒤집기, postfix 계산 메소드 push: 스택에 값을 추가 pop: 스택의 마지막 값을 삭제하고 반환 peek: 스택의 마지막 값을 반환(삭제x) isEmpty: 스택이 비어있는지 확인 push, pop 배열 스택을 이용 public class MyArrayStack { private E[] stack; private int topIndex; public void push(E item) { stack[++topIndex] = item; } public E po..

[자료구조] 스택 Stack 활용: 후위 표기식 계산기 (자바/Java)

목차 스택을 활용하여 후위 표기식 계산기를 구현할 수 있다. 먼저 중위표기식을 후위 표기식으로 바꾸고, 이를 다시 계산해야 한다. 1. 중위 표기식 → 후위 표기식 이 과정이 상대적으로 까다롭다. 먼저 연산자 우선순위를 고려해야 한다. 연산자는 사칙 연산(+ - * /)과 괄호만 들어온다고 가정한다. 1. 입력이 연산자가 아닌 경우 바로 출력해준다. StringBuilder를 사용하여 sb에 append하였다. 2. 입력이 연산자인 경우 2-1. 괄호인 경우 괄호는 연산자 중에서도 특수한 경우이다. 먼저 좌괄호 '('인 경우 stack에 그냥 push한다. 그리고 우괄호 ')'가 나오면, 좌괄호가 나올 때까지 stack에 있는 연산자들을 모두 pop하여 출력한다. 그리고 좌괄호는 연산에 포함되지 않으니,..

[자료구조] B-Tree

목차 B-트리 내장 색인: 메모리에 올려서 사용 (이진 검색 트리) 외장 색인: 메인 메모리 외부에 놓고 사용하는 색인 (B-트리) 색인의 규모가 클 경우 or 메인 메모리가 충분하지 않을 때 디스크에 두고 사용 디스크 접근 시간으로 인한 비효율을 최대한 줄여야 함 B-트리: 디스크 환경에서 사용하기 적합한 외장 다진 검색 트리 최대 M개의 자식을 가질 수 있는 B트리=M차 B트리 $$key_i−1

[자료구조] Array, ArrayList, LinkedList

목차 Array & ArrayList 배열 같은 종류의 데이터를 저장하기 위한 자료구조 index로 배열의 요소 참조 가능 크기가 고정 → overflow 위험 직관적으로 간단함 추가/제거 시 shift 필요 삽입 public void add(int index, E x) { if (this.numItems >= item.length || index this.numItems) { // 에러 처리 } else { for (int i = this.numItems - 1; i >= index; i--) { item[i + 1] = item[i]; // index에 값을 삽입하기 위해 오른쪽으로 한 칸씩 shift } item[index] = x; this.numItems++; } } ..