줭 Blog

1. 힙(Heap)이란? - 최대값 및 최소값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리(complete binary tree)를 기본으로 한 자료구조 - A가 B의 부모노드(parent node)이면, A의 키(key)값과 B의 키값 사이에는 대소관계가 성립함 - 단, 형제 사이에는 대소관계가 성립하지 않음 - 일종의 반정렬 상태(느슨한 정렬 상태) 유지 - 대부분은 자식노드의 개수가 최대 2개인 이진 힙(binary heap)을 사용 - 중복 허용 힙(Heap) vs 이진 탐색 트리(Binary Search Tree) - 힙은 중복된 값을 허용함 - 이진 탐색 트리는 중복된 값을 허용하지 않음 - 가장 높은(혹은 가장 낮은) 우선순위를 가지는 노드가 항상 루트 노드에 위치 - 우선순위 큐..

1. 큐(Queue)란? - 스택과 마찬가지로 데이터를 일시적으로 쌓아 두기 위한 자료구조 - 선입선출 구조를 가짐 - 선입선출(FIFO, First In First Out) : 가장 먼저 넣은 데이터를 가장 먼저 꺼냄 - 인큐(enqueue) : 큐에 데이터를 넣는 작업 디큐(dequeue) : 큐에서 데이터를 꺼내는 작업 프런트(front) : 데이터를 꺼내는 쪽 리어(rear) : 데이터를 넣는 쪽 - 예) 은행 창구에서 차례를 기다리는 대기열, 마트에서 계산을 기다리는 대기열 2. 배열로 큐 구현 - 스택과 마찬가지로 배열로 큐를 구현할 수 있음 - 하지만 효율성이 떨어짐 (1) 인큐(enqueue) - 32를 인큐 - 데이터를 넣기만 하면 되기 때문에 복잡도는 O(1) - 적은 비용으로 구현 가..

1. 스택(Stack)이란? - 데이터를 일시적으로 저장하기 위해 사용하는 자료구조 - 후입선출 구조를 가짐 - 후입선출(LIFO, Last In First Out) : 가장 나중에 넣은 데이터를 가장 먼저 꺼냄 - 푸시(push) : 스택에 데이터를 넣는 작업 팝(pop) : 스택에서 데이터를 꺼내는 작업 꼭대기(top) : 푸시와 팝을 하는 위치 바닥(bottom) : 스택의 가장 아랫부분 ※ Java 프로그램에서 메서드를 호출하고 실행할 때 프로그램 내부에서는 스택을 사용함 void x() {...} void z() { x(); } int main() { z(); } main 실행 - z 실행 - x 실행(아래 그림) - x 종료 - z 종료 - main 종료 2. 스택 구현 1) 필드 - int형..

1. 배열(Array) - 가장 기본적이고 간단한 자료구조 - 같은 자료형의 변수로 이루어진 구성 요소(component)가 모인 것 배열 ju-zero.tistory.com/22?category=900872 [Java-05] 배열(Array) - 1차원 배열 1. 배열(array)이란? 같은 타입의 여러 변수를 하나의 묶음으로 다루는 것 ex) int[] score = new int[5]; -> 5개의 int값을 저장할 수 있는 배열을 생성함 2. 배열의 선언과 생성 1) 배열 선언 - 생성된 배열을. ju-zero.tistory.com - Java를 공부하면서 배열의 개념에 대해서 익혔기 때문에, 배열을 다루는 여러 방법을 공부해보려고 한다. 2. 배열의 복제(클론) 배열이름.clone() int[]..

1. 자료구조(data structure) - 컴퓨터 과학에서 효율적인 접근 및 수정을 가능케 하는 자료의 조직, 관리, 저장 - 데이터 값의 모임, 데이터 간의 관계, 데이터에 적용할 수 있는 함수나 명령 - 자료구조를 선택한 후 알고리즘을 사용 2. 시간복잡도(time complexity) (1) 시간복잡도란? - 알고리즘의 실행 시간 분석 +) 공간 복잡도(space complexity) : 알고리즘이 사용하는 기억 공간 분석 - 알고리즘의 절대적인 실행 시간 X - 알고리즘을 이루고 있는 연산들이 몇 번 실행되는지 숫자로 표시 O - 시간복잡도가 클수록 알고리즘의 실행이 오래 걸림 (2) 시간 복잡도 함수 - 연산의 개수를 입력의 개수 n의 함수로 나타낸 것 T(n) T : 함수 n : 입력의 개..