자료구조, 알고리즘/자료구조

[비선형 자료구조] 힙과 우선순위 큐

| 들어가기 전에 - 왜 우선순위 큐는 비선형 구조일까? : 큐는 선형구조로 1 : 1의 대응방식을 가진다. 앞에서 부터 데이터를 꺼내고, 뒤에서부터 데이터를 축척한다. : 우선순위 큐는 이러한 큐에 우선순위 개념을 추가한 형태로, 우선순위를 따져 우선순위가 높은 데이터를 먼저 뽑는다. : 우선순위 큐는 배열, 연결리스트, 힙으로 구현이 가능한데 이중에서 힙으로 구현을 하는 것이 가장 효율적이다. : 따라서, 자바에서도 우선순위 큐는 힙으로 구현되었다. 힙은 완전 이진 트리 형태이며, 이는 1 : N 관계를 갖는 비선형구조이다. - 자바에서는 우선순위 큐를 힙으로 구현한다. 왜? : 위에서도 잠시 언급했던 것처럼, 힙으로 큐를 구현하는 것이 가장 효율적이기 때문에, 자바도 구현방식으로 힙을 쓴다. - 배..

[비선형 자료구조] 트리와 그래프

| 요약 핵심 단어 핵심 특성 언제 쓰면 좋을까 트리 계층, Acyclic, 4가지의 순회 포화 이진 트리의 경우, 하위로 갈수록 노드의 갯수가 2^0, 2^1, 2^2..로 증가 계층 관계의 데이터를 다룰 때 그래프 네트워크, cyclic, DFS/BFS 루트가 없고, 각 정점들간 단방향 또는 양방향의 관계를 가질 수 있음 연관 관계를 가진 데이터들에서 최적의 결과를 찾아야할 때 | 트리와 그래프의 차이 트리 그래프 개요 그래프의 한 종류 정점(vertex, 노드)과 간선(edge)으로 이루어진 자료구조 그림 출처 : 위키백과 출처 : 위키백과 방향 (단)방향 그래프 무(양)방향, (단)방향 그래프 사이클 Acyclic Cyclic 모델 계층 모델 네트워크 모델 루트 최상위 노드 없음 상-하위 관계 인..

비선형 자료구조 총정리

보호되어 있는 글입니다.

[선형자료구조] 해시테이블

| 요약 종류 구분 내용 언제 쓰는 게 좋을까 HashTable 특징 - 해싱 함수를 통해 키 -> 해시로 변환한다 - key + value - 특정 키와 값을 연결할 때(알파벳-단어, 사전, 전화번호부) - 중복을 제거해야할 때(전체 명단 중 투표 여부 확인) 장점 - 해시 충돌이 없을 때 검색, 삽입, 삭제가 빠르다 (시간복잡도 : 평균 O(1), 최악 O(n)) - 보안성이 높다 (Key와 Hash간의 연관성X) - 데이터 캐싱에 자주 사용된다. - 중복 제거에 유리하다. 단점 - 해시 충돌 : key1과 key2가 해시함수를 거쳐 동일한 해시값(공간)을 가지는 상태 - 공간 복잡도가 커진다 - 순서가 있는 경우에는 맞지 않는다 - 해시 함수 의존도가 높다 - 해시 테이블은 키와 값을 대응시켜 저장..

[선형자료구조] 스택, 큐, 데크

| 스택 종류 구분 내용 언제 쓰는 게 좋을까 Stack 특징 - 후입선출(LIFO) - top / bottom - push, pop, peek - 데이터가 입력된 순서의 역순으로 처리되어야 할 때 Ex. - 함수 콜스택,역추적,인터럽트 처리 - 재귀, DFS - 괄호 검사, 후위 연산, 문자열 역순출력, 실행취소 장점 - top을 통한 접근, 삽입, 삭제가 빠르다. (시간복잡도 O(1)) 단점 - top 이외의 데이터에 접근 불가(탐색x) - 스택은 마치 옷을 겹겹히 쌓듯 데이터를 쌓아 올렸다가 맨 위에서부터 꺼내는 구조이다. - 스택에 대한 알고리즘 문제를 보면, "괄호 검사", "후위 연산", "문자열의 역순 출력", "실행 취소"와 같이 [ 넣었다가 위에서부터 빼는 행위 ]를 통해 문자열의 특정 ..

[선형자료구조] 연결리스트

| 요약 종류 구분 내용 언제 쓰는 게 좋을까 LinkedList 특징 - 각 노드가 연결된 상태 - 각 노드의 메모리 주소는 항상 연속적이지 않다. - head / tail (양방향 이상) - 자료의 삽입과 삭제가 많은 경우 장점 - 데이터의 삽입 및 삭제가 잦을 때 유리 * 삽입, 삭제 시 새로운 배열 생성 없이 링크만 연결한다. 단점 - 특정 인덱스를 조회하는 데 시간이 O(n)만큼 소요된다. * 처음~끝까지 인덱스를 돌기 때문에 Array보다 느리다. 양방향 - 각 노드가 prev / next 두 가지의 연결점을 가진다. 원형 - head -> tail -> head 식으로 원형으로 연결된 상태 - 연결리스트는 각 노드가 연결된 상태로, 삽입과 삭제가 용이하다. - 다만, 연결리스트는 조회에는 취..

[선형자료구조] 배열과 ArrayList

| 요약 종류 구분 내용 언제 쓰는 게 좋을까 Array 특징 - 정해진 크기만큼 공간 할당 - 데이터가 연속적으로 하나씩 저장되어 있다. - 데이터와 인덱스가 1 : 1로 매칭 - 많은 양의 데이터를 다룰때 - 특정 위치 자료를 빠르게 선택할때 장점 - 인덱스를 통해 빠르게 데이터에 접근할 수 있다. 단점 - 길이를 미리 설정해야 한다. ArrayList 특징 - 가변 길이 배열 - 삽입 & 삭제 시, 배열을 새로 생성하고 복사한다. 장점 - 크기가 고정되어 있지 않다 (유동적) 단점 - 처음 또는 중간에 데이터를 삽입하거나 삭제할 때마다 배열을 새로 생성&복사하거나, 데이터를 모두 앞으로 미뤄야 한다. | ArrayList은 어떻게 가변적으로 데이터를 관리하나 - ArrayList는 java.util..

자릿수 - 자릿수와 경우의 수

| 자릿수와 경우의 수 (1) X진수의 K자릿수에 대한 모든 경우의 수 어떤 연속된 10진수 수 3개에 대한 배열이 있다고 가정할 때, 각 자리에 올 수 있는 수의 범위는 0 ~ 9이다. 0 0 0 0 0 1 0 0 2 0 0 3 0 0 4 0 0 5 0 0 6 0 0 7 0 0 8 0 0 9 ..... (생략) 10진수의 세 자릿수에 대한 모든 경우의 수는 아래와 같다 --> 10 x 10 x 10 = 1000 (곧, 000 ~ 999) 결국 x 진수의 k자릿수에 대한 모든 경우의 수는 --> x * x * x.... = x^k (자릿수 하나당 0 ~ x-1) (2) x진수의 각 자릿수 하나당 0 ~ x-1 범위를 가지며, x - 1를 넘어서면 올림이 이루어진다. - 10진수일 때 1 1 8 1 1 9..

소수판별법 - 에라토스테네스의 체

| 합성수와 소수 합성수 나누어떨어지는 수가 하나라도 존재하는 수 ex. 100 = 1 x 100, 2 x 50, 4 x 25, 5 x 20, 10 x 10... 소수 오직 1과 자기 자신만으로 나누어떨어지는 수 ex. 3 = 1 x 3 소수에 관한 알고리즘 문제는 보통 아래의 세가지가 있다고 하는데요. 1. 자연수 N이 소수인지 판별하거나, 2. 1~N까지 중 소수의 갯수를 구하거나 3. 1 ~ N 까지의 소수를 나열하는 이 중에서 먼저 1.자연수 N이 소수인지 판별하는 법을 이야기해 보려고 합니다. | N을 2부터 N - 1 까지 모두 나누기 [1] 소수는 1과 자기 자신을 제외한 다른 수로는 나누어떨어져서는 안됩니다. 그것을 판별하기 위한 코드는 아래와 같은데요. 2부터 N - 1가 N의 약수인지 ..

선형자료구조 총정리

| 자료구조란? - 자료를 목적에 따라 효율적으로 관리하기 위한 구조이다. - 데이터를 CRUD할 때 유용하다. - 적절히 사용하면 속도를 높히고, 메모리 사용도 줄일 수 있다. | 자료구조의 분류 분류 특징 종류 선형 자료구조 데이터가 1:1관계로 들어가있다. 배열, 연결리스트, 스택/큐/데크, 해시테이블 비선형 자료구조 데이터가 1:N, N:N 관계로 들어가 있다. 트리, 그래프, 힙/우선순위 큐, 트라이 * 선형 자료구조는 기차처럼 길쭉하게 하나의 몸으로 구성되어 있다. * 자료구조를 직접 구현하여(=추상 자료형) 사용할 수도 있다. | 선형 자료 구조 종류 구분 내용 언제 쓰는 게 좋을까 Array 특징 - 정해진 크기만큼 공간 할당 - 데이터가 연속적으로 하나씩 저장되어 있다. - 데이터와 인덱..