Knowledge/자료구조12

• 

  순열과 순열의 코드 구현 [Java] 순열 - 순열 : n개의 값 중에서 r 개의 숫자를 모든 순서대로 뽑는 것을 말한다. ex) [1, 2, 3] 이라는 3개의 배열에서 2개의 숫자를 뽑는 경우 -> 총 6개이다. [1, 2] [1, 3] [2, 1] [2, 3] [3, 1] [3, 2] swap을 이용한 순열 - swap 함수를 활용하여 배열들의 값을 직접 바꾸는 방법이다. - 배열의 첫 값부터 순서대로 하나씩 바꾸며 모든 값을 swap 한다. - depth 를 기준으로 depth 보다 인덱스가 작은 값들은 그대로 고정하고, 큰 값들만 들고 다시 swap을 진행한다. swap을 이용한 순열[코드 구현] //순서 상관 없이 n 개중에 r개를 뽑는 경우 //ex. permutation(arr, 0, 4, 2);//4개 중 2개를 뽑는 경우 .. Knowledge/자료구조 2023. 9. 14.

• 

  [자료구조] 이진 트리의 종류와 특징 🎁 트리(Tree)란 무엇인가요? (더보기) 🎁 이진 트리(Binary Tree) 각 노드는 최대 2개의 자식을 갖는 트리를 뜻한다. 각 노드는 자식이 없거나 1 or 2개만을 가지는데, 자식 노드는 좌우를 구분한다. (1). 왼쪽 자식 : 부모 노드의 왼쪽 아래 (2). 오른쪽 자식 : 부모 노드의 오른쪽 아래 🎁 이진 트리 종류 1. 포화 이진트리(Perfect binary Tree) - 모든 레벨에서 노드들이 꽉 채워져 있는 트리 - 노드가 2개이며, 차수(Degree)가 2이다. - 모든 노드가 가득 차 있기 때문에, 단말 노드부터 루트 노드까지의 높이(Height)가 같다. - 노드의 갯수는 n = 2^h - 1, h = 높이 - 포화 이진 트리의 높이가 h일 때, 노드의 수는 2의 h(+1) .. Knowledge/자료구조 2023. 8. 21.

• 

  [자료구조] 트리(Tree)의 구조와 순회 🎁 트리(Tree)는 무엇인가요? 노드와 링크로 구성된 자료구조(그래프의 한 종류)이다. 계층적 구조를 나타낼 때 사용한다.(ex. 폴더(디렉터리) 구조 , 조직도) 🎁 트리의 구조 1. 노드(Node) : 트리 구조의 자료 값을 담고 있는 단위 2. 에지(Edge) : 노드 간의 연결선 (= Link, branch) 3. 루트 노드(Root Node) : 부모가 없는 노드(가장 상단의 노드) 4. 잎새 노드(Leaf Node) : 자식이 없는 노드(단말노드) 5. 부모 노드(Parent) : 연결된 2개의 노드 중 상위의 노드 6. 자식 노드(Child) : 연결된 2개의 노드 중 하위의 노드 7. 형제 노드(Sibling) : 같은 부모를 가지는 노드 8. 레벨(Level) : 트리의 특정 깊이를 가.. Knowledge/자료구조 2023. 8. 19.

• 

  [Java/자료구조] 우선순위 큐(PriorityQueue) 📢 우선순위 큐 우선 순위가 높은 데이터가 먼저 나옴(!= FIFO) (1). 모든 테이터에 우선순위가 있다. (2). Dequeue 시, 우선순위가 높은 순으로 나감. (3). 우선 순위가 같은 경우는 FIFO(선입선출)한다. 📢 우선 순위 큐의 삽입/삭제 최소 힙 및 최대 힙의 삽입과 삭제와 같음 📢 구현 하는 방법 배열 연결 리스트 힙 -> 우선순위 큐 자료형 클래스는 힙으로 구성되어있다. enqueue() dequeue() 정렬된 배열 O(n) O(1) 정렬된 연결 리스트 O(n) O(1) 힙 O(logN) O(logN) 📢 PriorityQueue 사용 방법 // 우선순위: 낮은 숫자 순 PriorityQueue pq = new PriorityQueue(); pq.add(5); pq.add(7).. Knowledge/자료구조 2023. 8. 13.

• 

  힙(Heap)의 구조 [삽입/삭제] [ 목차 ] 📢 Heap 🔊 완전 이진 트리 형태 중복 값 허용 반 정렬 상태 🔊 최소 값 또는 최대 값을 빠르게 찾아내는 데 유용한 자료구조 최소 힙 최대 힙 🔊 Heap은 배열 및 ArrayList로 대체로 구현한다. 📢 최소 힙과 최대 힙 🔊 최소 Heap (Min Heap) 부모 노드의 키가 자식 노드의 키보다 작거나 같은 형태이다. 🔊 최대 Heap (Max Heap) 부모 노드의 키가 자식 노드의 키보다 크거나 같은 형태이다. 📢 힙의 삽입과 삭제 🔊 최소 Heap 삽입 트리의 가장 끝 위치에 데이터 삽입 부모 노드와 키를 비교한 후 작을 경우 부모 자리를 교체를 반복해서 교체한다. 🔊 최소 Heap 삭제 최상위 노드 반환 및 삭제 가장 마지막 위치의 노드를 최상위 노드로 위치 시킨다. 자식 .. Knowledge/자료구조 2023. 8. 12.

• 

  [Java/자료구조] 연결리스트(Linked List)의 특징 [ 목차 ] 📢 연결 리스트(Linked List) 데이터를 링크로 연결해서 관리하는 자료구조 자료의 순서는 정해져 있지만, 메모리 상 연속성은 보장되지 않는다. 🔊 연결 리스트(Linked List)의 장점 데이터 공간을 미리 할당할 필요가 없음 즉, 리스트의 길이가 가변적이라 데이터 관리(추가 및 삭제) 가 용이하다. 🔊 연결 리스트(Linked List)의 단점 연결 구조를 위한 별도의 데이터 공간이 필요하다. 연결 정보를 찾는 시간이 필요하다(접근 속도가 상대적으로 느리다) 데이터를 추가 및 삭제 시 앞 뒤 데이터의 연결을 재구성하는 작업이 필요하다 🔊 연결 리스트의 기본 구조 노드(Node) : 데이터 저장 단위로, 값과 포인터로 구성되어 있다. 📢 연결 리스트의 기본 연산 🔊 데이터 추가 데이.. Knowledge/자료구조 2023. 8. 11.

• 

  [Java/자료구조] 해시테이블(HashTable)이란? [ 목차 ] 📢 해시 테이블 키(Key), 값(Value)을 대응시켜 저장하는 데이터 구조이다. 키(Key)를 통해 해당 데이터에 빠르게 접근이 가능하다. 📢 해시 테이블 구조 키(Key) : 해시 테이블 접근을 위한 입력 값이다. 해시 함수(Hash Function) : 키를 해시 값으로 매핑하는 연산 해시 값(Hash Value) : 해시 테이블의 인덱스 해시 테이블(Hash Table) : 키와 값을 연관시켜 저장하는 데이터 구조이다. 📢 해시 충돌 해시 테이블의 같은 공간에 서로 다른 값을 저장하려는 경우이다. 서로 다른 키의 해시 함수를 통한 해시 값이 동일한 경우이다. 📢 해시 충돌 해결 방법 🔥 개방 주소법(Open Address) 충돌 시, 테이블에서 비어 있는 공간의 hash를 찾아 데이.. Knowledge/자료구조 2023. 8. 11.

• 

  [Java/자료구조] HashMap 자료구조 파헤치기 [ 목차 ] 📢 해시맵(HashMap) Map 인터페이스에 속해 있는 컬랙션이다 Key : 해당 Map에 유일하게 있어야 하고, 중복을 허용하지 않지만, 값은 중복이 가능하다. 내부에 키와 값을 저장하는 자료구조를 가지고 있다. Key와 Value이 저장되는 위치를 결정하므로, 삽입한 순서에 따라 정렬되지 않는다. 📄 해싱(Hashing) 해시 함수에 문자열 입력값을 넣어서 특정한 값으로 추출하는 것을 의미 ⭐ 해싱의 목적 인덱싱 : 올바른 위치를 찾는다. 암호화/복호화 : 인증된 사용자만 볼 수 있다. 비교 : 짧은 해싱 결과로 비교한다. 📄 맵(Map) Map : Key와 Value를 두 쌍으로 데이터 보관하는 자료구조이다. 키는 맵에 오직 유일하게 있어야함 ,값은 중복 상관 X 📢 HashMap 주.. Knowledge/자료구조 2023. 8. 11.

• 

  [Java/자료구조] 배열 [ 목차 ] 📢 배열 많은 수의 데이터를 다룰 때 사용하는 자료 구조이다. 각 데이터를 인덱스와 1:1 대응 하도록 구성되어 있다. 데이터가 메모리 상에 연속적으로 저장된다. 📌 배열의 장점 인덱스를 이용하여 데이터를 빠르게 접근할 수 있다. 인접한 메모리는 빠르게 엑세스가 가능하다. 📌 배열의 단점 데이터 추가 및 삭제가 번거로운 편이다. (1). 미리 최대 길이를 정해서 생성해야한다. (2). 가변 길이 배열은 배열의 크기를 변경할 때마다 새로운 배열을 생성해야한다. (3). 데이터 삭제 시에는, 인덱스를 유지하기 위해서 빈 공간을 유지해야한다. 📢 그림 풀이 Knowledge/자료구조 2023. 8. 9.

• 

  [자료구조][Java] 데크(Deque) [ 목차 ] 📢 데크 양쪽에서 삽입과 삭제가 모두 가능한 자료구조 Deque : Doubly-ended Queue Stack + Queue 한 상태 📢 데크의 기본 구조 데크의 기본 구조는 양방향에서 삽입과 삭제가 가능한 구조 일부 기능을 제한하여 용도에 맞게 변형이 가능하다. 💻 입력제한 데크(Scroll) 한 쪽의 입력을 제한한 데크 💻 출력제한 데크(shelf) 한 쪽의 출력을 제한한 데크 💻 그림 예시 📢 Deque 사용 예시 💻 Deque(기본) public class Main { public static void main(String[] args) { //기본 Deque를 이용한 예제 Deque deque = new ArrayDeque(); // Front 부분 입력 deque.addFirst.. Knowledge/자료구조 2023. 8. 9.

• 

  [자료구조][Java] 큐[Queue] [ 목차 ] 📢 큐(Queue) 선입선출(First In First Out; FIFO) 자료구조 -> 먼저 들어온 데이터가 먼저 나가는 구조이다. 입력 순서대로 데이터 처리가 필요할 때 사용한다.ex(프린터 출력 대기열, BFS(Breath-First Search)) 📈 큐(Queue)의 기본 구조 선입선출 구조를 따른다. 기본적으로 데이터 추가, 꺼내기, 큐 공간 확인 동작으로 이루어져있다. 데이터가 꺼내는 쪽이 Front이고, 데이터를 꺼내는 동작을 Dequeue 라고 한다. 데이터를 추가하는 쪽이 Rear이고, 데이터가 들어오는 동작을 Enqueue 라고 한다. 📈 큐(Queue)의 기본 연산 데이터 추가(Enqueue) - 큐에 데이터 추가 데이터 꺼내기(Dequeue) - 큐에 데이터 꺼내기 📈.. Knowledge/자료구조 2023. 8. 9.

• 

  [자료구조][Java] Stack이란? 📢 스택(Stack) 후입선출(後入先出)의 특성을 가지는 자료구조를 일컫는다. 맨 마지막의 데이터가 가장 먼저 출력이 된다. 🧨 예시 스택은 "쌓여 있는 팬케이크" 라고 생각하는 것이 좋다. ex) 팬케이크를 하나씩 쌓게 되면 먼저 내려놓은 것이 맨 아래에 있고 나중에 쌓은 것이 맨 위에 있을 것이다. 즉, Last In First Out(LIFO) -> 가장 나중에 올라온 것이 가장 먼저 나가게 되는 것이다. 🧨 스택의 종류 힙 영역 메모리에서 일반적인 데이터를 저장하는 스택 스택과 스택 영역 메모리에서 프로그램의 각 분기점에 변수와 같은 정보를 저장하기 위한 스택 📈 스택의 개념 스택은 해당 이미지처럼 출입구가 1개이다. 즉, 데이터의 삽입과 제거가 한 곳에서 이루어진다. 먼저 들어간 데이터가 늦게 .. Knowledge/자료구조 2023. 8. 7.