야놀자 테크스쿨/JAVA 자료구조13 [면접을 위한 CS 전공지식 노트][자료구조] Hash Table 1. 해시 테이블이란? 해시 테이블은 데이터를 효율적으로 저장하고, 검색하기 위한 자료구조로 키(key)와 값(value)을 쌍으로 하여 데이터를 관리한다. 해시테이블은 해시 함수를 사용하여 키를 해시값으로 변환하고 이를 기반으로 저장할 배열의 인덱스를 결정하여 데이터를 저장하거나 검색한다. - 해시 테이블의 주요 특징 1) 해시 함수: 해시테이블은 해시 함수를 이용하여 키를 해시 값으로 변환한다. 해시 함수는 임의의 길이를 가진 데이터를 고정된 길이의 값으로 매핑하는 함수이다. 이 때 동일한 키는 항상 동일한 해시값으로 매핑되어야 한다. 해시 값은 배열의 인덱스와 연결되며, 이를 통해 데이터가 저장되거나 검색된다. 2) 해시 충돌: 해시 함수의 특성상 서로 다른 데이터가 같은 해시 값으로 매핑 될 수 .. 2023. 8. 11. [면접을 위한 CS 전공지식 노트][자료구조] Set 1. Set이란? 자료구조인 SET은 수학에서의 집합을 구현해놓은 것이다. 집합은 중복되지 않는 원소들의 모임으로 수학적인 집합 개념을 컴퓨터 과학의 문제에 적용하기 위해서 만들어진 자료구조 이다. Set은 다음과 같은 특징을 가지고 있다. SET의 주요 특징 1) 고유한 원소: Set은 각 원소가 중복되지 않는다. Unique한 원소. 2) 순서 없음: Set에서는 원소의 순서를 보장하지 않는다. 순서가 없다. 3) 집합 연산: Set은 원소들 간의 합집합, 교집합, 차집합 등과 같은 집합연산을 지원한다. 2. JAVA에서의 Set 1) HashSet 가장 일반적으로 사용되는 Set 구현체 이며, 해시테이블을 기반으로 구현되어 있다. HashSet의 주요 특징 - 순서를 보장하지 않는다. - 추가, 삭.. 2023. 8. 11. [면접을 위한 CS 전공지식 노트][자료구조] Map 0. 개요 이번 글에서는 키를 통해 검색할 경우에 자주쓰는 Map에 대해서 공부한 내용을 정리하고자 한다. 나 같은 경우에는 JAVA 코딩을 할 때에 map을 사용한다고 하면 HashMap만을 그냥 사용해왔는데, 공부해보니 그 외에도 코딩할 때 사용하면 유용할만한 자바에서 제공해주는 유용한 Map들이 존재했다. 이 글에서는 그것들에 대해서 기록해놓고 계속해서 볼 수 있도록 하려고 한다. 1. Map이란? 프로그래밍을 한번이라도 접해 본 사람이라면 각각의 언어마다 부르는 이름은 조금 다를 수도 있지만, Map 형식의 데이터를 이미 다뤄봤을 것이다. Python에서는 Dictionary라는 데이터타입으로 불리우기도 하고, API를 이용해본 사람들이라면 JSON(JavaScript Object Notation.. 2023. 8. 11. [자료구조] 힙과 우선순위 큐 1. 힙 힙은 트리 글에서 정리한 완전 이진 트리에 속하는 자료구조이다. 그래서 완전 이진 트리의 특성을 모두 지니고 있다. (완전이진트리의 특성: 모든 노드는 왼쪽 노드부터 채워져야하고, 마지막 레벨을 제외한 모든 레벨이 완전히 채워져 있다.) 힙은 최대힙과, 최소힙이 존재한다. 최대힙(Max Heap) - 부모 노드의 값은 항상 자식보다 크거나 같다. (좌우 순서는 상관없다) - 루트 노드는 언제나 트리의 최댓값이다. - 값의 중복을 허용. 최소힙(Min Heap) - 부모노드의 값은 항상 자식보다 작거나 같다. (좌우 순서는 상관없다.) - 루트 노드는 언제나 트리의 최솟값이다. - 값이 중복을 허용. 이러한 힙은 일차원 배열로 구현이 가능하다. 인덱스 1부터 루트노드부터 값을 넣어주면 아래와 같은.. 2023. 8. 10. [면접을 위한 CS 전공지식 노트][자료구조] Graph (그래프) 1. Graph 그래프는 정점(Vertex)과 간선(Edge)으로 이루어진 자료구조이다. 네비게이션 길찾기, 네트워크 분석 등 다양하게 사용될 수 있다. 2. Vertex와 Edge A라는 곳에서 무언가를 통해 B로 간다고 했을 때 A,B는 Vertex가 되고 A에서 B로 갈 때의 무언가는 Edge가 된다. Edge 같은 경우 단방향, 양방향 둘다 가능하다. 이 때 Vertex에서 나가는 Edge을 Outdegree라고 하고, Vertex로 들어오는 Edge을 Indegree라고 한다. 이때의 Vertex와 Edge들을 통합하여 그래프라고 부른다. 뿐만아니라 Edge별로 가중치를 다르게해서 Vertex들을 연결할 수 있다. 3. 정리 그래프는 Vertex와 그들을 연결해주는 Edge로 구성된다. Vert.. 2023. 8. 4. [면접을 위한 CS 전공지식 노트][자료구조] Tree(트리) 1. 트리 트리는 그래프 중 하나로 그래프와 같이 노드와 엣지로 구성되어 있다. 한 노드가 여러노드를 가리킬 수 있으며, 비선형적인 자료구조이다. 데이터 구조의 계층적인 속성을 표현하는 것이 특징이다. 우리가 사용하는 파일탐색기의 구조도 트리 구조라고 볼 수 있다. Tree를 알아보기에 앞서 트리와 관련된 용어를 알아야 할 필요가 있다. 1. Root: 트리의 시작점이자, 트리에서 제일 위에 있는 최상위 노드이다. 이를 root라고 부른다. 2. Node와 Edge: 노드는 트리에서 데이터를 저장하는 기본적인 단위이다. 각 노드는 하나이상의 자식노드를 가지고 있을 수 있고, 또한 부모노드와 연결될 수도 있다. 그리고 노드들을 연결해주는 간선을 Edge라고 한다. 3. Parent와 Child: 그림에서는.. 2023. 8. 4. [면접을 위한 CS 전공지식 노트][자료구조] Queue(큐) 0. 개요 이번에는 Queue에 대해서 공부한것을 글로 정리할 예정이다. 1. Queue 큐는 FIFO(First In First Out)구조이다. 스택이 LIFO(Last In First Out) 였던 것과 대조적이다. CPU 작업을 기다리는 프로세스, 스레드 행렬 또는 네트워크 접속을 기다리는 행렬, 너비 우선 탐색, 캐시, 메시지큐 등에 사용된다. 큐 같은 경우 node를 이용해 만든 선형큐와 배열을 이용해 만든 원형큐가 있다. 원형큐는 새로운 데이터를 offer 할 때마다 Rear 인덱스를 +1, poll 할 때마다 front+1에 있는 데이터를 꺼내고 front+1. 배열을 이용해 구현한 원형 큐에서의 상태 조건 1) Rear와 Front가 같은 곳을 가리키고 있다. -> 큐가 비어 있다. 2).. 2023. 8. 3. [면접을 위한 CS 전공지식 노트][자료구조] Stack(스택) 0. 개요 배열과 리스트에 대한 정리가 끝났으니, 다음 자료구조는 스택과 큐이다. 그 중 스택을 먼저 정리하려고 한다. 1. Stack 스택의 구조는 간단하다. LIFO(Last In First Out)가 핵심이다. 이것을 알고 있다면 이미 스택에 대해서 99.9%는 이해했다고 생각해도 무방하다. 스택에서는 push를 할 경우 스택에 데이터가 쌓이고, pop을 할 경우에는 가장 최근에 push된 데이터를 꺼내는 구조이다. 그리고 peek을 하게 되면 스택에 최 상위 top에 있는 데이터의 정보를 읽어올 수 있다. 스택의 기능을 명세한 인터페이스 스택이 가지고 있는 기능의 핵심을 명세했다. push: data를 스택에 집어 넣는다. pop: 가장 최근에 넣은 데이터를 스택에서 꺼낸다. peek: 가장 최근.. 2023. 8. 3. [면접을 위한 CS 전공지식 노트][자료구조] 연결리스트 LinkedList 0. 개요 이전 글에서는 선형 자료구조인 배열의 구조와 Java에서의 ArrayList를 살펴보았다. 이번에는 연결리스트에 대해서 공부한 내용을 글로 정리하여 남기고자 한다. 일단 연결리스트에는 단방향 연결리스트와 양방향 연결리스트가 있다. 이번 글에서는 두 가지 모두에 대해서 구현해보고, 특징들에 대해서 알아볼 예정이다. 1. 단방향 연결리스트 단방향 연결리스트는 말 그대로 한 방향으로만 링크된 리스트들을 의미한다. 즉, 앞에서 뒤로는 탐색이 가능하지만, 역방향으로는 탐색이 불가능하다. 그림으로 살펴보자. 아래 그림과 같이 Head는 다음 노드를 가리키고 있고, 0번 노드는 1번 Tail을 가리키고 있다. 그러나 Tail에서 0번 노드의 주소는 알지 못하기 때문에 역방향의 탐색이 불가능하다. 2. 양방.. 2023. 8. 2. 이전 1 2 다음
