Computer Science/자료구조
-
이분 검색Computer Science/자료구조 2023. 12. 16. 00:03
이분 검색 = Binary Search 정렬 된 데이터 집합을 가지고 수행해야 한다. 자세한 정보 : https://prosto.tistory.com/165 요약 정렬(오름차순) 된 데이터 집합을 반으로 쪼개어 2분할 한 다음, 찾아야 하는 값이 m 이고, 반으로 쪼갠 기준이 된 값을 mid 라고 했을 때 mid > m 이면 왼쪽 구간을 탐색 mid < m 이면 오른쪽 구간을 탐색한다. 탐색 방법은 처음과 같이 데이터 집합을 반으로 쪼개어 mid 가 m 보다 큰지 작은지 판단 후 분할을 반복하거나, mid 가 m 과 같다면 반환한다. 코드 데이터 집합에서 이분 검색으로 m 찾기 public int 이분검색(int n, int m, int[] arr) { Arrays.sort(arr); int lt = 0..
-
버블 정렬 , 선택 정렬 , 삽입 정렬Computer Science/자료구조 2023. 12. 16. 00:03
참고 @minji0801 : 버블 정렬 vs 선택 정렬 vs 삽입 정렬 차이 shinsunyoung : 기본적인 정렬 방법들(선택, 삽입, 버블)에 대해 알아보자 요약 모두 O(n²) 버블 정렬 인접한 두 데이터만 비교하면서 정렬 오름차순 정렬 시 데이터 집합의 끝에 큰 수를 위치 시키면서 정렬 됨 선택 정렬 0번 인덱스부터 key로 두어 데이터 집합에서 최소값을 찾아 key와 교환하며 정렬 오름차순 정렬 시 데이터 집합의 앞에 작은 수를 위치 시키면서 정렬 됨 삽입 정렬 1번 인덱스부터 key로 두어 탐색을 시작하며, key 왼쪽 구간에 있는 데이터와 비교하여 왼쪽 구간의 데이터들 중 key보다 큰 값들의 앞에 삽입하여 정렬 코드 버블정렬 public int[] 버블정렬(int n, int[] arr)..
-
단방향 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..