CS/Data Structure

빅오 표기법 (Big-O) 불필요한 연산을 제거하여 알고리즘 분석을 쉽게 할 목적으로 사용된다. Big-O로 즉정되는 복잡성에는 시간과 공간 복잡도가 있다. 시간 복잡도 알고리즘의 성능을 설명하는 것. 알고리즘을 수행하기 위해 프로세스가 수행해야하는 연산을 수치화한 것이다. 실행시간이 아닌 연산수치로 판별하는 이유 명령어의 실행시간은 컴퓨터의 하드웨어 또는 프로그래밍 언어에 따라 편차가 크게 달라지기 때문에 명령어의 실행 횟수만 고려하는 것이다. 시간 복잡도에서 중요하게 보는 것은 가장 큰 영향을 미치는 n의 단위이다. // O(1) – 상수 시간 : 문제를 해결하는데 오직 한 단계만 처리함. System.out.println("Hello, World!"); // O(n) – 직선적 시간 :문제를 해결하..

Heap 힙은 자료구조의 일종으로 우선 순위 큐를 위해 만들어졌다. 우선 순위 큐 : 우선순위의 개념에 큐를 도입한 자료구조 데이터들이 우선순위를 가지고 있으며, 우선순위가 높은 데이터가 큐에서 먼저 빠져 나간다. 시뮬레이션 시스템, 작업 스케줄링, 수치해석 계산 등에 사용된다. 우선 순위 큐는 배열, 연결 리스트, 힙으로 구현한다. 개념 Tree의 형식을 취하고 있으면 Tree 중에서도 배열을 기반으로 한 완전 이진 트리(Complete Binary Tree)이다 최대값 및 최소값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전 이진 트리이다. 중복된 값을 허용. (이진 탐색 트리는 중복 값을 허용하지 않음) 힙은 일종의 반정렬 상태(느슨한 정렬 상태) 를 유지한다. 큰 값이 상위 레벨에 있고 작은 값..

1.Stack 가장 마지막으로 들어간 데이터가 가장 첫 번 째로 나오는 성질을 가진 자료 구조 LIFO(Last in First Out) 구조 삽입 및 삭제에 O(1), 탐색에 O(n)의 시간 복잡도를 가진다. 한 쪽 방향에만 자료를 추가, 삭제 할 수 있으며 가장 마지막에 삽입된 자료의 위치를 `top`이라 한다. Stakc은 `top`에만 접근이 가능하기 때문에 그 외의 위치에 대한 데이터 추가 및 삭제가 불가능하다. 웹 브라우저 방문 기록, 실행 취소, 역순 문자열 만들기, 후위 표기법 계산 등에 쓰인다. Push : 데이터를 스택의 맨 위에 추가. Pop : 스택의 맨 위에 있는 데이터를 제거. + 장점 top 위치의 데이터에 바로 접근하므로 데이터 삽입, 삭제의 시간 복잡도가 O(1)로 빠르다...

연결리스트는 데이터 요소가 순서대로 연결된 데이터 구조이다. 각 요소는 자신의 데이터와 다음 요소를 가리키는 포인터(참조)로 이루어져 있다. 이러한 구조로 배열과 달리 연결리스트는 각 요소의 위치가 연속적이지 않을 수 있다. Singly Linked List (단일 연결 리스트) 각 요소가 데이터와 다음 요소를 가리키는 포인터로 이루어져 있다. 맨 끝 요소는 다음 요소를 가리키는 포인터가 null이다. Doubly Linked List (이중 연결 리스트) 각 요소가 데이터와 이전 요소를 가리키는 포인터, 다음 요소를 가리키는 포인터로 이루어져 있다. 양방향으로 순회가 가능하다. [단일 연결 리스트 Code] public class LinkedList { private Node head; public L..