자료구조

[자료구조] Queue, Stack, Deque

1. Stack 책을 쌓는 것처럼 차곡차곡 쌓아 올린 형태의 자료구조이다. 나중에 들어온게 먼저 나가는 후입선출(LIFO, Last In First Out) 방식이다. 2. Queue "줄을 서서 기다린다." 라는 사전적 의미를 가지고 있다. 먼저 들어온게 먼저 나가는 선입선출(FIFO, First In First Out) 방식이다. 3. Deque Double-ended Queue(양단 큐)라는 뜻으로, Stack와 Queue의 장점을 합쳐놓은 자료구조이다. 양쪽 끝에서 삽입과 삭제가 모두 가능하다는 특징이 있다. Deque Interface는 다음과 같이 크게 3가지 기능(추가, 삭제, 조회)을 제공한다. 1. 추가 Type Method Description boolean add(E e) 이 dequ..

[자료구조] ArrayList vs LinkedList

Java에서 List 인터페이스를 사용할 때 대표적으로 쓰이는 클래스가 ArrayList와 LinkedList 입니다. 두 클래스의 특성과 어떠한 차이가 있는지 알아보겠습니다. ArrayList 1. 내부 구조 배열을 사용하여 구현합니다. 2. 추가, 삭제, 조회 인덱스 기반으로 데이터에 접근 가능합니다. 요소가 추가될 때마다 배열의 크기를 동적으로 조절한 후 새로운 요소를 추가합니다. 3. 메모리 사용 내부 배열의 크기를 늘리거나 줄일 때마다 새로운 배열을 할당한 후 기존 배열을 복사해야 합니다. 따라서 메모리 사용이 불규칙해질 수 있습니다. LinkedList 1. 내부 구조 노드들의 연결 리스트로 구현되어 있습니다. 각 요소는 링크로 연결되어 있으며, 새로운 요소를 추가할 때마다 새로운 노드를 만듭..

[자료구조] 5.3. 비선형 자료 구조

본 포스팅은 [면접을 위한 CS 전공지식 노트]의 내용을 참고하여 작성하였습니다. 5.3. 비선형 자료 구조 비선형 자료 구조란 일렬로 나열하지 않고, 자료 순서나 관계가 복잡한 구조를 말한다. 1) 그래프 그래프는 정점과 간선으로 이루어진 자료 구조를 말한다. 정점과 간선 ' 어떠한 곳에서 어떠한 곳으로 무언가를 통해 간다. ' 위에서 '어떠한 곳'은 정점(vertex)이고, '무언가'는 간선(edge)이 된다. 이와 같이 정점과 간선으로 이루어진 집합을 '그래프(graph)'라고 한다. 정점으로 나가는 간선을 해당 정점의 outdegree라고 하며, 들어오는 간선을 해당 정점의 indegree라고 한다. 또한, 간선과 정점 사이에 드는 비용을 '가중치'라고 한다. 2) 트리 트리는 그래프 중 하나로 ..

[자료구조] 5.2. 선형 자료 구조

본 포스팅은 [면접을 위한 CS 전공지식 노트]의 내용을 참고하여 작성하였습니다. 5.2. 선형 자료 구조 선형 자료 구조란 요소가 일렬로 나열되어 있는 자료 구조를 말한다. 1) 연결 리스트 연결 리스트는 데이터를 감싼 노드를 포인터로 연결해서 공간적인 효율성을 극대화시킨 자료구조이다. 삽입과 삭제에 O(1), 탐색에 O(n)이 걸린다. 위와 같이 prev 포인터와 next 포인터로 앞과 뒤를 연결한 것이 연결 리스트이다. 연결 리스트는 다음과 같이 3가지 연결 리스트가 존재한다. 싱글 연결 리스트: next 포인터만 가진다. 이중 연결 리스트: next 포인터와 prev 포인터를 가진다. 원형 이중 연결 리스트: 마지막 노드의 next 포인터가 헤드 노드를 가리키는 이중 연결 리스트. 2) 배열 배열..

[자료구조] 5.1. 복잡도

본 포스팅은 [면접을 위한 CS 전공지식 노트]의 내용을 참고하여 작성하였습니다. 5.1. 복잡도 복잡도는 시간 복잡도와 공간 복잡도로 나뉜다. 1) 시간 복잡도 문제를 해결하는 데 걸리는 시간과 입력의 함수 관계. 알고리즘의 로직이 얼마나 오랜 시간 걸리는지. 빅오 표기법*으로 나타냄. (빅오 표기법*: 가장 영향을 많이 끼치는 항의 상수 인자와 나머지 항을 없앤 것. 예를 들어 10n^2+n의 시간이면 O(n^2)로 표기한다.) 필요한 이유: 효율적인 코드로 개선하는 데 쓰이는 척도. 2) 공간 복잡도 프로그램을 실행시켰을 때 필요로 하는 자원 공간의 양. 정적 변수는 물론이고 재귀함수로 인해 동적인 공간을 계속해서 필요할 경우도 포함. int a[1005]; 위와 같은 코드를 예시로 들면, a 배열..