티스토리

영운's 블로그

검색하기

블로그 홈

영운's 블로그

you88.tistory.com/m

오영운(you88) 님의 블로그입니다.

구독자: 7

방명록 방문하기

주요 글 목록

[자료구조 Java] 해시 테이블 (3) - 시간 복잡도, 장점과 단점 [자료구조 Java] 해시 테이블 (1) - 해시 테이블 및 해시 충돌(Hash Collision) [자료구조 Java] 해시 테이블 (2) - 체이닝(Chaining), 선형 조사법(Linear Probing), 이차 조사법(Quadratic Probing), 이중 해싱법(Double Hasing) [자료구조 Java] 해시 테이블 (3) - 시간 복잡도, 장점과 단점 [Java] 자바 Collection Framework의 HashMap은 어떤 해시 충돌 알고리즘을 사용할까? 해시 테이블의 평균, 최악의 case에서 갖는 시간 복잡도를 알아보고 이를 바탕으로 해시 테이블이 갖는 장점과 단점에 대해 알아보자 시간 복잡도 빅오 표기법 평균 최악 탐색 O(1) O(N) 삽입 O(1) O(N) 삭제 O(1).. 공감수 1 댓글수 0 2022. 7. 17.
[자료구조 Java] 해시 테이블 (2) - 체이닝(Chaining), 선형 조사법(Linear Probing), 이차 조사법(Quadratic Probing), 이중 해싱법(Double Hasing) [자료구조 Java] 해시 테이블 (1) - 해시 테이블 및 해시 충돌(Hash Collision) [자료구조 Java] 해시 테이블 (2) - 체이닝(Chaining), 선형 조사법(Linear Probing), 이차 조사법(Quadratic Probing),이중 해싱법(Double Hasing) [자료구조 Java] 해시 테이블 (3) - 시간 복잡도, 장점과 단점 [Java] 자바 Collection Framework의 HashMap은 어떤 해시 충돌 알고리즘을 사용할까? 해시 충돌(Hash Collision) 해결 알고리즘 4가지 해시 테이블에서 해시 충돌에 대한 해결방법은 아주 중요하다. 체이닝(Chaining), 선형 조사법(Linear Probing), 이차 조사법(Quadratic Prob.. 공감수 1 댓글수 0 2022. 7. 16.
[자료구조 Java] 해시 테이블 (1) - 해시 테이블 및 해시 충돌(Hash Collision) [자료구조 Java] 해시 테이블 (1) - 해시 테이블 및 해시 충돌(Hash Collision) [자료구조 Java] 해시 테이블 (2) - 체이닝(Chaining), 선형 조사법(Linear Probing), 이차 조사법(Quadratic Probing), 이중 해싱법(Double Hasing) [자료구조 Java] 해시 테이블 (3) - 시간 복잡도, 장점과 단점 [Java] 자바 Collection Framework의 HashMap은 어떤 해시 충돌 알고리즘을 사용할까? key, 해시 함수, 해시 값 등 해시의 기본 개념을 살펴보고 이를 바탕으로 해시 테이블(Hash Table) 자료구조를 알아본다. 또한 해시 테이블에서 필연적으로 발생하는 해시 충돌(Hash Collision)에 대해서도 살펴.. 공감수 1 댓글수 0 2022. 7. 16.
[자료구조 Java] 힙(Heap), 이진 힙(Binary Heap) 개념 정리 + 자바로 구현하기 Heap이란? 힙은 '우선순위 큐'를 구현하거나 '힙 정렬'을 하기 위해 사용하는 자료구조이다. 힙은 이진 힙(Binary Heap)이라고 부르기도 한며 둘은 동일한 개념이다. '우선순위 큐'란 특정 우선순위 기준을 가지고 만든 큐를 의미한다. 사실 기존의 큐 또한 우선순위 큐에 속한다. 기존의 큐는 삽입된 순서 기준으로 먼저 삽입된 것에 우선순위를 부여한 우선순위 큐이라고 할 수 있다. 힙은 최대 힙(Max Heap)과 최소 힙(Min Heap)으로 나눌 수 있다. 최대 힙은 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 힙이다. 최소 힙은 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 힙이다. 아래부터는 최대 힙을 가정하고 힙에 대해 서술하고자 한다. 힙의 규칙은 다른 트리 자료.. 공감수 1 댓글수 1 2022. 7. 11.
[자료구조] 트리(Tree) 관련 용어 간단 정리 트리는 스택, 큐, 배열, 리스트와는 다르게 계층적 구조를 가져 굉장히 중요한 자료구조이다. 트리를 공부하며 느낀 것은 트리라는 개념도 어렵지만 트리를 설명하는데 나오는 여러 새로운 용어들이 발목을 많이 잡는 것 같다. 여기서는 트리 관련하여 나오는 주요 용어를 정리하고자 한다. 노드(Node) , 키(Key) 트리를 구성하는 하나의 요소를 노드라고 부르며 하나의 노드가 저장하는 값을 키라고 한다. 하나의 노드는 키와 자손을 가리키는 참조 변수(left, right)를 갖는다. 루트 노드(Root Node), 서브 트리(Subtree) 가장 낮은 높이에 존재하는 노드를 루트 노드(Root Node)라고 부른다. 트리의 접근은 언제라 루트 노드를 시작으로 접근할 수 있다. 해당 노드의 왼쪽 혹은 오른쪽에 .. 공감수 0 댓글수 0 2022. 7. 9.
[자료구조 Java] 이진 탐색 트리(Binary Search Tree) 개념 정리 + 자바로 구현하기 이진 탐색 트리(Binary Search Tree) 필요성 탐색은 프로그램에서 가장 시간이 많이 걸리는 연산 중 하나이기에 효율적인 탐색을 구현하는 것은 굉장히 중요하다. 앞서 살펴본 스택, 큐, 배열, 리스트 구조는 모두 선형적인 구조를 갖고 있다. 선형적인 구조는 탐색 연산시 일일이 순차적으로 접근하여 데이터를 찾는 방식으로 탐색을 진행해야 하기에 탐색에 비효율적이다. 다음과 같이 배열과 연결리스트 모두 앞에서부터 순차적으로 탐색해야 값을 찾을 수 있고 최악의 경우 해당 값이 맨 마지막에 있다면 O(n)의 시간복잡도를 갖는다. 이러한 선형적인 구조의 탐색 비효율성은 데이터의 크기가 증가할수록 선형적으로 증가한다. 이러한 선형구조가 갖는 탐색의 비효율성을 개선한 것이 바로 이진 탐색 트리(Binary .. 공감수 2 댓글수 0 2022. 7. 9.
[자료구조 Java] 큐(Queue) 개념 정리 + 자바로 구현하기 Queue(큐)는 Stack(스택)과 반대로 선입선출(First In First Out, FIFO)의 특징을 가지고 있다. 먼저 들어온 것이 먼저 나간다는 FIFO는 일상생활에서의 줄서기, 마트 재고관리부터 운영체제의 프로세스 관리, 너비 우선 탐색(BFS) 알고리즘까지 다양한 곳에서 이용되고 있다. 이번 글에서는 큐에 대해 간단히 알아보고 이를 직접 자바로 구현해 본다. Queue는 Stack과 마찬가지로 배열과 리스트 두 가지 방법으로 구현할 수 있다. 배열로 구현한 Queue 전체 구조 배열을 이용하여 큐를 만드는 경우 다음과 같은 원형 큐 형태로 구현해야 한다. 원형 큐 형태를 구현함으로서 배열의 첫 데이터의 index가 0이 아닐 수도 있게 된다. 이를 통해 배열의 마지막 index에 데이터가 .. 공감수 0 댓글수 0 2022. 7. 7.
[자료구조 Java] 스택(Stack) 개념 정리 + 자바로 구현하기 스택(Stack)이란? 가장 늦게 들어간 요소가 가장 먼저 나오고 가장 먼저 들어간 요소가 가장 늦게 나오는 후입선출(LIFO: Last in First Out) 입출력 형태를 갖는 자료구조. 주요 연산으로 pop(), push()이 있다. pop은 가장 늦게 들어온 요소를 삭제하는 연산이고, push는 요소를 맨 앞에 삽입하는 연산이다. 구현 방법은 두 가지가 있다. 1. 배열을 이용한 구현 2. 리스트를 이용한 구현 두 가지 구현의 장단점은 결국 배열과 리스트의 장단점과 동일하다. 배열을 이용한 구현 장점: 구현이 간단하며 별도로 메모리를 동적으로 할당하지 않기에 속도가 빠르다. 단점: 크기가 고정 리스트를 이용한 구현 장점: 크기가 가변적 단점: 삽입, 삭제시 메모리를 동적으로 할당/해제하기에 속도.. 공감수 0 댓글수 0 2022. 7. 2.
[자료구조 Java] 이중 연결리스트(Doubly Linked List) 핵심 정리 이중 연결리스트(Doubly Linked List)의 개념을 정리하고 이를 자바(Java)로 구현하고자 한다. 마지막에는 자바의 Collction Framework에 있는 LinkedList 사용시 반복문 관련 주의할 점을 알아본다. 이중 연결리스트란? 이중 연결리스트는 '단일_연결리스트'와 비교하였을 때 노드가 양방향으로 연결되었다는 차이점을 갖는다. 단일 연결리스트에 있던 head변수와 추가적으로 마지막 노드를 가리키는 tail 변수를 갖는다. tail 변수가 추가됨에 따라 마지막 노드에서 역행적으로 선행 노드로의 접근이 가능해져 접근 연산이 훨씬 빨라진다. 단일 연결 리스트도 Tail 변수를 추가할 수 있지만 리스트의 마지막을 의미할 뿐 단일 연결이기에 리스트의 뒤에서부터 앞으로의 접근은 불가능하기.. 공감수 0 댓글수 0 2022. 7. 1.
[자료구조 Java] 단일 연결리스트(Singly Linked List) 개념 정리 + 자바로 구현하기 연결리스트란? 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식의 데이터 구조 노드는 데이터 구조를 구성하는 하나의 객체를 의미한다. 포인터는 주소값을 저장하는 것으로 이 포인터가 다른 노드의 주소값을 저장하는 방식으로 노드들이 연결되어 있다. 연결리스트 종류: 단일 연결리스트, 이중 연결리스트, 원형 연결리스트 단일 연결리스트란? 각 노드가 앞에서 뒤로의 연결만을 가진 연결리스트 단일 연결이기에 각 노드의 포인터에는 후행 노드의 주소값이 저장되어 있다. 따라서 앞에서 뒤로의 접근은 가능하지만 뒤에서 앞으로의 접근은 불가하다. 단일 연결 리스트의 구성 하나의 노드는 데이터와 포인터로 이루어져 있다. 단일 연결이기에 포인터는 다음 노드의 주소값만 저장하고 있으며 다시 앞으로 돌아가는 등의 연.. 공감수 0 댓글수 0 2022. 6. 30.
자료구조는 왜 알아야 하나? 자료구조란? 한정된 메모리 공간 안에서 데이터를 관리(저장, 사용)하기 위한 논리적 구조 자료구조를 왜 알아야 할까? 데이터의 개수가 늘어날 수록 어떠한 자료구조를 사용하는지에 따라 프로그램의 효율성이 크게 달라짐. 따라서 각 자료구조의 장단점을 정확히 파악하여 상황별로 적절한 자료구조를 사용하는 능력을 키워야 한다. 예를 들어 잦은 검색이 필요한 프로그램에서 배열을 사용하는 경우 배열의 맨 앞에서부터 배열의 맨 마지막까지 존재할 수 있기에 평균 시간복잡도는 O(n) 해시 테이블을 사용하는 경우 평균 시간복잡도는 O(1) 하지만 해시테이블은 hash값을 저장할 별도의 공간이 필요하며, 해시 충돌(key에 대응되는 hash가 동일한 경우)을 방지하기 위해 별도의 조치가 필요하고, hash 함수를 사용하는 .. 공감수 0 댓글수 0 2022. 6. 30.

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.