영운's 블로그

포인터와 참조 자료형 모두 주소값을 저장한다. C, C++ 같은 언어는 포인터를 사용하며 Java는 참조 자료형을 사용한다. 그렇다면 포인터와 참조 자료형의 차이는 무엇이고 Java는 왜 참조 자료형을 사용하는지 그 이유를 알아보자 포인터와 참조(Reference) 자료형의 차이 포인터는 임의의 메모리 주소를 저장 가능하고 참조 자료형은 임의의 메모리 주소를 저장할 수 없다. 개발자는 포인터에 임의로 0x100000e64 같은 주소를 저장할 수 있다. 이 과정에서 포인터에 잘못된 주소를 저장할 수도 있으며 그에 따라 'segment fault' 같은 오류가 발생하는 것은 모두 개발자의 책임이다. 자바의 참조 자료형은 개발자가 임의로 메모리 주소를 지정하여 저장하는 것이 불가능하다. 개발자가 참조 자료형에..

Heap이란? 힙은 '우선순위 큐'를 구현하거나 '힙 정렬'을 하기 위해 사용하는 자료구조이다. 힙은 이진 힙(Binary Heap)이라고 부르기도 한며 둘은 동일한 개념이다. '우선순위 큐'란 특정 우선순위 기준을 가지고 만든 큐를 의미한다. 사실 기존의 큐 또한 우선순위 큐에 속한다. 기존의 큐는 삽입된 순서 기준으로 먼저 삽입된 것에 우선순위를 부여한 우선순위 큐이라고 할 수 있다. 힙은 최대 힙(Max Heap)과 최소 힙(Min Heap)으로 나눌 수 있다. 최대 힙은 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 힙이다. 최소 힙은 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 힙이다. 아래부터는 최대 힙을 가정하고 힙에 대해 서술하고자 한다. 힙의 규칙은 다른 트리 자료..

Queue(큐)는 Stack(스택)과 반대로 선입선출(First In First Out, FIFO)의 특징을 가지고 있다. 먼저 들어온 것이 먼저 나간다는 FIFO는 일상생활에서의 줄서기, 마트 재고관리부터 운영체제의 프로세스 관리, 너비 우선 탐색(BFS) 알고리즘까지 다양한 곳에서 이용되고 있다. 이번 글에서는 큐에 대해 간단히 알아보고 이를 직접 자바로 구현해 본다. Queue는 Stack과 마찬가지로 배열과 리스트 두 가지 방법으로 구현할 수 있다. 배열로 구현한 Queue 전체 구조 배열을 이용하여 큐를 만드는 경우 다음과 같은 원형 큐 형태로 구현해야 한다. 원형 큐 형태를 구현함으로서 배열의 첫 데이터의 index가 0이 아닐 수도 있게 된다. 이를 통해 배열의 마지막 index에 데이터가 ..

이중 연결리스트(Doubly Linked List)의 개념을 정리하고 이를 자바(Java)로 구현하고자 한다. 마지막에는 자바의 Collction Framework에 있는 LinkedList 사용시 반복문 관련 주의할 점을 알아본다. 이중 연결리스트란? 이중 연결리스트는 '단일_연결리스트'와 비교하였을 때 노드가 양방향으로 연결되었다는 차이점을 갖는다. 단일 연결리스트에 있던 head변수와 추가적으로 마지막 노드를 가리키는 tail 변수를 갖는다. tail 변수가 추가됨에 따라 마지막 노드에서 역행적으로 선행 노드로의 접근이 가능해져 접근 연산이 훨씬 빨라진다. 단일 연결 리스트도 Tail 변수를 추가할 수 있지만 리스트의 마지막을 의미할 뿐 단일 연결이기에 리스트의 뒤에서부터 앞으로의 접근은 불가능하기..