자료구조
-
단방향 Linked List 구현Computer Science/자료구조 2023. 12. 5. 00:01
코드를 자주 읽어봐야 할 필요성을 크게 느껴서 포스팅 🐢 구현하는데 너무 어려웠다. 노드로 값을 확인하고 삭제하고 추가하는게 아직까지도 낯설다 😬 자주 읽어봐야 됨 코드 작성 Node class Node { T data; Node next; public Node(T data, Node next) { this.data = data; this.next = next; } } LinkedList class MyLinkedList { private Node head; private int size; public MyLinkedList() { this.head = null; this.size = 0; } // add =======================================================..
-
그래프Computer Science/자료구조 2023. 11. 22. 01:01
특징 정점과 간선으로 이루어진 자료구조. 연결된 정점간의 관계를 표현 할 수 있는 자료구조이다. 루트노드의 구분이 없다. 그래프는 Cyclic , 트리는 ACyclic 트리는 부모-자식 관계가 있지만, 그래프는 부모-자식관계가 없다. 그래프를 탐색 할 수 있는 알고리즘으로 DFS, BFS 순회 알고리즘이 있다. 구조 정점 Vertex : 각 노드 간선 Edge : 노드와 노드를 연결하는 선 ( link, branch ) 인접 정점 Adjacent Vertax : 간선 하나를 두고 바로 연결된 정점 정점의 차수 Degree - 무방향 그래프에서 하나의 정점에 인접한 정점의 수 - 무방향 그래프 모든 정점 차수의 합 = 그래프 간선의 수 2배 진입 차수 In degree : 방향 그래프에서 외부에서 오는 간..
-
힙 HeapComputer Science/자료구조 2023. 11. 21. 00:01
항상 완전 이진 트리 형태 -> 중복을 허용 -> 반 정렬 상태임 [= 부모 자식관계에선 정렬되어있지만, 형제끼리는 정렬되어있지않음] 최소값, 최대값을 빠르게 찾는데 유용 -> 최소힙 Min Heap , 최대힙 Max Heap -> 최소힙 : 부모 노드의 키 ≤ 자식 노드의 키 -> 최대힙 : 부모 노드의 키 ≥ 자식 노드의 키 Heap의 특성(같은 레벨에선 노드가 좌측부터 채워짐)으로 인해 보통 배열을 통해서 구현한다. Heap의 삽입 Min Heap을 예시로 함 트리의 가장 끝에 데이터 삽입 부모 노드와 키를 비교한 후 삽입된 키가 더 작을 경우 부모와 교체 (반복) Heap의 삭제 Min Heap을 예시로 함 항상 최상위 노드를 반환 & 삭제 가장 마지막 위치의 노드를 최상위로 옮김 자식 노드 중 ..
-
트리Computer Science/자료구조 2023. 11. 21. 00:01
노드와 링크로 구성된 자료 구조 그래프의 일종 -> 순환하면 그래프 , 순환하지 않으면 트리 계층적 구조를 나타낼 때 사용 -> 폴더구조, 조직도, 가계도 트리의 구조 노드 트리 구조의 자료값을 담는 단위 에지 = 엣지 = 간선 = edge = branch = link 노드간의 연결선 루트 노드 = Root 부모가 없는 노드. 최상위 노드 잎새 노드 = 단말 노드 = Leaf 자식이 없는 노드 내부 노드 잎새노드를 제외한 모든 노드 부모 노드 연결된 두 노드 중 상위인 노드 자식 노드 연결된 두 노드 중 하위인 노드 형제 노드 같은 부모를 가지는 노드 레벨 트리의 특정 깊이를 가지는 노드 집합 깊이 루트에서 어떤 노드까지의 간선 수 높이 트리에서 가장 큰 레벨 값 크기 자신을 포함한 자식 노드의 개수 차..
-
Linked List 연결리스트Computer Science/자료구조 2023. 11. 20. 00:01
데이터를 링크로 연결해서 관리 자료의 순서는 정해져 있지만, 메모리 상의 연속성은 보장하지 않는다. 장점 데이터의 공간을 미리 할당할 필요가 없다. 리스트의 길이가 가변적임 -> 데이터의 추가, 삭제가 용이하다. 단점 연결 구조 위한 별도의 공간 필요 연결 정보 찾는데 시간이 필요 -> 상대적으로 접근 속도가 느리다. 데이터의 추가, 삭제 시 앞뒤 데이터의 연결을 재구성 해줘야 한다. 단방향 연결리스트 기본 구조 사용되는 노드의 구조 class Node { T data; Node next; Node(){} Node(T data, Node next) { this.data = data; this.next = next; } } 일방통행적인 노드 연결 구조 한 방향으로만 탐색이 가능함 ex. 노드 D 찾기 노드..
-
해시맵 HashMapComputer Science/자료구조 2023. 11. 20. 00:01
Map Interface 순서가 없는 자료형 키 , 값 의 형태로 데이터 관리 대표 구현 클래스 -> HashMap , TreeMap Hash 임의의 길이를 갖는 임의의 데이터를 고정된 길이의 데이터로 매핑하는 단방향 함수 Hashtable , HashMap (+ HashSet) 키 , 값의 형태로 데이터를 관리하는 자료구조 -> 키를 통해 데이터에 빠르게 접근 가능하다. 해싱 : 키를 특정 계산식(해시 함수)에 넣어 나온 결과를 사용하여 값에 접근하는 과정 Hashtable과 HashMap 차이 ( 키 , 값 ) = ( null , null ) Thread - safe Hash table X O ( 멀티스레드에서 좋음 ) Hash Map O X ( 싱글스레드에서 성능 좋음) -> 멀티스레드 환경을 위한..
-
배열 arrayComputer Science/자료구조 2023. 11. 20. 00:01
배열 Array 많은 수의 데이터를 다룰 때 사용 장점 각 데이터와 인덱스의 관계가 1:1 -> 접근 속도가 굉장히 빠른 이유 1 데이터가 메모리상에 연속적으로 저장됨 -> 접근 속도가 굉장히 빠른 이유 2 단점 배열의 생성시 배열의 크기를 지정해야 한다. 데이터의 추가 삭제가 번거로움 -> 가변 길이 배열은 배열의 크기를 변경할 때마다 새로운 배열을 생성 -> 데이터 삭제 시 인덱스를 유지하기위해 빈 공간을 유지하기 때문에 비효율적이다. 자바에서 사용 //1. 기본 자료형 int[] arrIntegerA = new int[3]; int[] arrIntegerB = new int[]{0, 0, 0}; int[] arrIntegerC = {0, 0, 0}; arrIntegerC[2] = 0; arrInte..
-
Queue 큐Computer Science/자료구조 2023. 11. 20. 00:01
큐 Queue 선입선출 = FIFO = LIFO = 들어온 순서대로 나감 Java 큐는 자바에선 인터페이스로 존재하기 때문에 Queue 자체를 사용하려면 Queue 인터페이스를 상속 받아 구현해야 한다. 구현하는 대신에 Queue를 상속받아 활용한 LinkedList를 사용할수도 있다. Q.add( data ) = 큐에 data 입력 Q.poll() = 큐에서 값을 꺼냄 -> 맨 앞에 위치하는 값이 나온다. -> 값을 그냥 삭제하지 않고 들고 나오기 때문에 , 이 값을 사용하려면 적당한 변수에 담아주면 된다. -> int outNum = Q.poll() Q.peek() = 지금 사용 할 수 있는 값(맨앞에 있는 값)을 복사해오는 메서드 Q.contains( data ) = 큐에 data가 들어있는지 확인..
-
Stack 스택Computer Science/자료구조 2023. 11. 20. 00:01
자료구조 첫 번째 학습 주제 : 스택 Stack 후입 선출 형식으로 데이터를 관리하는 자료형이다. First In Last Out : 첫번째로 들어오면 마지막으로 나감 Last In First Out : 마지막에 들어오면 첫번째로 나감 마지막에 들어온 사람이 자리가 없어서 문 앞에 앉아있다가 제일 첫번째로 나감 🤣 Stack은 데이터가 입력된 순서의 역순으로 처리되어야 할 때 사용한다. ex : 함수 콜 스택, 수식 계산, 인터럽트 처리 등등 스택에서 사용하는 용어 void push( data ); : stack에 data 입력 Object peek() : 스택의 top 위치에 존재하는 값을 보여줌. -> top 위치의 값을 복사해온다고 생각하면 좋을것 같다. Object pop() : 스택의 top 위..