트리 트리는 트리 모양으로 만든 자료구조이다. 즉, 모양은 트리구조지만, 내부적으로는 리스트이다. 자세히 다루자면 아래와 같다. 트리는 Node와 Branch를 이용해서, 사이클을 이루지 않도록 구성한 데이터 구조이다. 그렇다면 트리는 어디서 많이 사용되는가? 트리 중 이진 트리 (Binary Tree) 형태의 구조로, 탐색(검색) 알고리즘 구현을 위해 많이 사용됨 용어 트리를 공부하다보면 용어가 많이 나와 이를 정리해 보았다. Node: 트리에서 데이터를 저장하는 기본 요소 (데이터와 다른 연결된 노드에 대한 Branch 정보 포함) Root Node: 트리 맨 위에 있는 노드 Level: 최상위 노드를 Level 0으로 하였을 때, 하위 Branch로 연결된 노드의 깊이를 나타냄 Parent Node..

해시 해시는 Key-Value 쌍으로 저장되는 자료구조를 말한다. 자바에서는 hashMap이 Collections에 구현되어 있다. 이때 주의해야 할 점이 있는데, key는 반드시 중복되지 말아야 한다는 것이다. 해시 메커니즘 기본적인 해시는 위 그림과 같이 Hash function을 통해 만ㄷ르어 진다. Key-Value가 function을 거쳐 어떤 주소를 참조하게 된다. 기본적으로 인덱스 주소를 가지고, 그 주소에 value값이 링크되어 있다. 중복 key는? 해시 Key가 중복되면 어떤값이 나올까? 정답은 나중에 지정된 해시값이 나온다. 즉, 덮어쓰게 된다. 이를 충돌이라고 말한다. 기본적으로 인덱스는 value를 링크드 리스트로 포인트하고 있다. 같은 key를 가진 value가 들어오게 되면 v..

시간복잡도 시간복잡도는 알고리즘, 자료구조를 공부하게되면 접하게되면 단어이다. 그렇다면 시간복잡도는 무엇인가? 쉽게 말해 지금 내 코드의 실행 시간을 Big O (빅-오) 표기법: O(N) 표기법으로 표현을 한 것이다. 시간 복잡도 계산은 반복문이 핵심 요소임을 인지하고, 계산 표기는 최상, 평균, 최악 중, 최악의 시간인 Big-O 표기법을 중심으로 공부하면 된다. 대문자 O 표기법 및 게산 방법 입력 n 에 따라 결정되는 시간 복잡도 함수 O(1), O($log n$), O(n), O(n $log n$), O($n^2$), O($2^n$), O(n!)등으로 표기함 입력 n 의 크기에 따라 기하급수적으로 시간 복잡도가 늘어날 수 있다. O(1) < O($log n$) < O(n) < O(n $log n..

스택 스텍은 많은 분야에서 사용되고 있다. (게임) 스텍이란 마지막에 넣은 데이터를 가장 먼저 추출하는 자료구조이다. 즉, LIFO를 말하며, 주로 컴퓨터 내부 프로세스 구조의 함수 동작 방식이 이걸로 구현되어 있다. 또한 우리가 자주 사용하는 컴퓨터 뒤로가기도 스텍구조 이다. 스텍 사용법 자바 내부라이브러리에 스텍이 구현되어 있다. import java.util.Stack; Stack stack = new Stack(); //int형 스택 선언 Stack stack = new Stack(); //String형 스택 선언 util에 있는 stack이 구현되어 있으며, import시 사용할 수있다. 이미 내부에 다양한 메서드가 구현되어 있다. 추가 push() push(value) 메서드를 활용하면 된다...

큐(Queue)란? 큐는 배열을 기반으로 만든 자료구조이다. 가장 먼저 넣은 요소를 가장 먼저 꺼낼 수 있다는 것이 특징이다. 예시로 터널에 들어간 차량, 음식점 줄서기 등이 있다. 개인적으로 자료구조에서 인간적으로 합당하다고 생각하는 구조이다... 들어가기에 앞서 큐에서 자주 사용하는 용어 2개를 소개한다. Enqueue : 큐에 요소 넣는 기능 Dequeue : 큐에 요소 꺼내는 기능 특징 몇가지 특징을 짧게 알아보자 FIFO : First input First out 의 약자로 선입선출 이라고 많이 말한다. 큐의 가장 큰 특징이자 중요한 개념이다. 큐는 꼬리 쪽으로만 요소가 들어가고 헤드 쪽으로만 요소가 나가게 된다. 컴퓨터 버퍼에서 주로 사용한다. Python Queue 파이썬에서는 큐는 내부구현..

배열이란? 배열을 왜 쓸까? 같은 종류의 데이터를 관리하기 하기 위해서 같은 종류의 데이터를 순차적으로 저장 대전제는 데이터를 쉽게 관리하는 목적이다. 그것을 한 묶음으로 관리하는게 효율적이다. 근데 이걸 또 순차적으로 있다면? 한눈에 봐도 데이터를 다루기가 쉬울 것이다. 장점 - Index 배열의 가장 큰 장점은 Index라고 할 수 있다. 배열는 공간에 각각의 element 마다 각각의 index가 생긴다. (각각각각) 각 요소에 번호가 생기면 데이터 안에 하나의 값만 가져올 때 굉장히 편해진다. 또한 값을 찾을 때 소모되는 비용은 index로 인해 시간복잡도 O(1)을 가진다. 단점 - 배열의 크기설정 & 추가/삭제 배열의 가장 큰 단점 데이터를 삭제와 추가 하는 부분에서 발생한다. 배열은 크기를 ..

자료구조 공부 목표 자료구조 개념 및 설명 stack, queue, tree, graph 개념 이해 기본 개념과 구조를 파악 및 목적을 이해 상황에 맞는 자료구조를 떠올릴 수 있다. tree 및 graph 탐색 기법 이해 BST 이해 BFS, DFS 개념 이해 자료구조란? 쉽게 말해 데이터들의 구조이다. 수많은 데이터들을 어떻게 저장하고, 어떻게 위치를 새우냐에 따라 사용하는 방법이 다를 것이다. 데이터 : 문자, 숫자, 그림, 영상 등 다양한 정보의 집합 자료구조 종류 자료구조 단순구조 정수 / 실수 문자 / 문자열 2진수 선형구조 (선 모양으로 생긴 자료 구조) 리스트(배열) 연결 리스트 단순 / 이중 / 원형 덱 / 스텍 / 큐 비선형구조 트리 일반 트리 / 이진 트리 그래프 방향 그래프 / 무방향..

비선형구조 1. 트리 (Tree) 사이클(순환)이 없는 연결된 그래프입니다. 트리를 구성하는 노드 간에는 단순 경로가 존재하는 특징이 있습니다. 여기서 단순 경로란 지나왔던 접점을 다시 지나지 않는 경로 입니다. 우리가 주로 쓰는 간단한 예시로는 폴더 구조가 있습니다. 트리는 일반트리와 이진트리가 있습니다. 차이로는 이진트리는 2개 이상의 노드가 존재하지 않는 구조라 생각하면 쉽습니다. ( 이진트리 - 각 노드가 최대 두개의 자식을 갖는 트리 ) 트리의 큰 특징으로는 1. 방향성 있음. 2. 각 노드는 어떤 자료형으로도 표현이 가능 3. 사이클이 존재 할 수 없다.(하나의 연결 그래프) 4. 트리는 이진 트리, 이진 탐색 트리, 균형트리 등이 있습니다. 2. 그래프 (Graph) 그래프란? 노드와 노드를..

- 자료구조의 분류 선형구조 1. 배열 (Array) (선형 리스트) 배열의 특징은 논리적 순서와 물리적 순서가 일치한다. 즉, index값을 통해 원소 접근이 용이하며, 구현이 쉽다. 하지만 단점으로 삽입, 삭제 등에 대한 연산에 필요한 Cost가 높다. 삭제를 하는 경우 순서를 맞추기 위해 뒤의 원소들을 앞으로 Shift 연산을 해줘야 한다. 삭제 1 2 3 4 5 1 2 삭제 4 5 1 2 4 5 1 2 4 5 2. 연결 리스트(LinkedList) 배열의 삽입/삭제의 단점을 극복하고자 만든 개념이 리스트이다. 배열은 논리적, 물리적 저장이 순서대로 되어 있다. 하지만 리스트는 논리적으로는 순서대로 되어 있으나 물리적으로는 순서대로 되어있지 않다. 대신 각 원소가 index위치에 ..

퀵 정렬 - 숫자를 오름차순으로 정렬하는 프로그램 - 기존 선택, 버블, 삽입은 N^2이라는 시간 복잡도를 가지고 있다. - 데이터가 무수히 많아 짐에 따라 좀 더 빠른 정렬을 생각 해볼 필요가 있다. - 이때 생각해낸 것이 퀵정렬이다. - 특정한 배열이 있을 때 "분할 정복" 알고리즘을 쓴다 & 재귀 알고리즘을 이용한 정렬이다. 기본원리 가운데 pivot값을 정한 후 작은값 + pivot값 + 큰값 같은 형식으로 정리하는 원리 이다. 코드는 직관성 있고 이해하기 쉽지만 효율적이지 않다. -메모리 사용 측면에서 좋지 못한 코드이다. 리스트의 정 가운데 있는 값을 pivot 값을 선택합니다. 시작 인덱스(low)는 계속 증가 시키고, 끝 인덱스(high)는 계속 감소 시키기위한 while 루프를 두 인덱스..

삽입 정렬 - 숫자를 오름차순으로 정렬하는 프로그램 arr = [3, 4, 5, 1, 2]이라는 리스트가 있을 때 이것을 어떻게 오름차순으로 정렬할까? 삽입정렬은 앞의 있는 원소들이 이미 정렬되어있다고 가정을 한다 라는 특성이 있다. 즉, 하나의 원소를 선택 후 삽일 할 위치에 보내는 방법을 삽입 정렬이라고 한다. #1 [1, 3, 4, 5, 2] #1 선택해 맨 처음 자리로 이동 [(1) _, 3, 4, 5, (1), 2] 빈 공간이 있다고 생각하고 이동 #2 [1, 2, 3, 4, 5] #2 선택해 공간의 위치에 이동 1과 3 사이 [_, 1, (2)_, 3, _, 4, 5, (2)] #3 [1, 2, 3, 4, 5] #3 선택해 자리 이동 //변화 없음... #4 [1, 2, 3, 4, 5] #4 ..

버블 정렬 숫자를 오름차순으로 정렬하는 프로그램 하지만 쉽게 해석하려면 가장 큰 숫자를 맨 뒤로 보내는 것과 같다고 생각하면 된다. arr = [3, 4, 5, 1, 2]이라는 리스트가 있을 때 이것을 어떻게 오름차순으로 정렬할까? 두 수를 선택해서 큰값을 뒤로 보내는 방법을 버블 정렬이라고 한다. #1 [3, 4, 5, 1, 2] #3과 4을 자리 바꾸기 // 변하지 않음 #2 [3, 4, 5, 1, 2] #4와 5 자리 바꾸기 // 변하지 않음 #3 [3, 4, 1, 5, 2] #1과 5 자리 바꾸기 #4 [3, 4, 1, 2, 5] #2와 5 자리 바꾸기 순서로 진행된다. 결국 5가 가장 마지막이고 1은 가장 처음으로 온다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 ''' 반..