자료구조 & 알고리즘

자료구조 중 연결 리스트(Linked List)의 개념과 Java 예제 코드를 정리해보자. 연결 리스트(Linked List)란? LinkedList는 자료구조 중 하나로 데이터 요소를 연결된 노드로 표현하는 방식이다. 각 노드는 데이터와 다음 노드를 가리키는 포인터(또는 링크)로 구성된다. 이 포인터를 통해 다음 노드로 이동하면서 데이터를 순차적으로 접근할 수 있다. LinkedList는 동적으로 크기가 조절될 수 있으며, 데이터의 삽입과 삭제가 빠르게 이루어진다는 특징이 있다. LinkedList의 기본 개념을 정리해보면 다음과 같다. 노드(Node) : LinkedList의 기본 구성 요소로, 데이터와 다음 노드를 가리키는 링크(포인터)로 구성된다. 헤드(Head) : LinkedList의 첫 번째..

자료구조 중 배열(Array)에 대해 정리해보자. 배열(Array)이란? 배열(Array)은 자료구조 중 하나로, 동일한 데이터 타입의 요소들을 연속된 메모리 공간에 저장하는 방법이다. 배열은 인덱스(index)를 사용해 각 요소에 접근할 수 있다. 이러한 특징 때문에 배열은 데이터의 순서를 유지하고, 특정 위치의 요소에 빠르게 접근할 수 있는 장점이 있다. 배열(Array)의 장점 및 단점 장점 빠른 접근 : 배열은 인덱스를 사용하여 요소에 빠르게 접근할 수 있다. 인덱스를 알고 있다면 원하는 위치의 요소에 상수 시간(O(1))에 접근할 수 있다. 메모리 공간의 효율성 : 배열은 연속된 메모리 공간에 요소를 저장하므로, 메모리 공간을 효율적으로 사용할 수 있다. 또한, 요소들은 순서대로 저장되기 때문에..

우선순위 큐(Priority Queue)와 힙(Heap)에 대해 간단히 알아보자. 우선순위 큐(Priority Queue)란? 우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조이다. 어떤 데이터를 우선순위에 따라 처리하고 싶을 때 사용한다. ex) 상품 데이터를 자료구조에 넣었다가 비싼(가치가 높은) 상품부터 꺼내서 조회할 경우 : 이 때 상품의 가치를 상품과 함께 저장해 추출 시 가치가 높은 상품부터 꺼내도록 한다. 여기서 다시 한 번 스택(Stack), 큐(Queue), 우선순위 큐(Priority Queue) 자료구조를 비교/정리해보고 가자. 자료구조 가장 먼저 추출되는 데이터 스택(Stack) 가장 나중에 삽입된 데이터(후입선출) 큐(Queue) 가장 먼저 삽입된 데이터(선입선출) 우선순..

기초 자료구조인 Stack에 대해서 알고 있다면 어렵지는 않은 문제이다.. 하지만 시간 초과가 떴고.. 검색해보니 명령 N 이 최대 10,000이고 명령마다 println으로 출력 시 시간 초과가 발생할 수 있으므로 StringBufferr를 사용해주면 해결된다고 한다. 시간 초과 import java.io.*; import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); Stack stack = new Stack(); int num = sc.nextInt(); for(int i = 0; i < num; i++) { String order = sc.next..

Stack 기본 개념 LIFO(Last In First Out) 형식의 기초 자료구조 아래 그림처럼 한 쪽 끝에서만 데이터를 넣고 뺄 수 있다. 이러한 구조는 '뒤로 가기'나 '실행 취소(undo)', 컴퓨터 구조에서의 'stack memory'에서 사용된다. 구조 상 당연히 직전에 추가된 데이터를 빠르게 가지고 올 수 있다. 기본적으로 Java에서 Stack 클래스는 내부에서 최상위 타입 배열인 Object[] 배열을 사용해 데이터들을 관리하고 있다. Stack 기본 연산 push(item): item 하나를 스택의 가장 윗 부분에 추가한다. pop(): 스택에서 가장 위에 있는 항목을 제거한다. peek(): 스택의 가장 위에 있는 항목을 반환한다. isEmpty(): 스택이 비어 있을 때에 true..

자료구조(Data Structure). 구글링을 하면 '데이터 값의 모임, 또 데이터 간의 관계, 그리고 데이터에 적용할 수 있는 함수나 명령을 의미'한다는 위키백과의 글이 가장 먼저 검색된다. 그리고 자료구조를 검색하면 알고리즘 문제를 푸는 분들이 많다. 자료구조와 알고리즘은 뗄 수 없는 관계이기 때문이다. 어떤 알고리즘 문제를 해결하기 위해서는 문제를 파악한 다음 문제에 사용할 적합한 자료구조를 선택한다. 예를 들어 비슷해보이는 List일지라도 순서가 있는 데이터들의 삽입과 삭제가 빈번하다면 LinkedList를, 그렇지 않을 경우네는 ArrayList를 사용한다. 각 알고리즘의 문제에서, 그리고 실제 서비스 로직을 구현하는 상황에서도 각 자료구조 별 특징을 정확하게 이해하고 있어야 적합한 자료구조를..