자료구조

정렬 out-of-place 정렬과 in-place 정렬 out-of-place 정렬 모든 데이터를 자료 구조의 복사본에 옮긴 후 순서대로 배열하여 정렬하는 방법 in-place 정렬 자료 구조를 그대로 두고그 안에서 요소들의 위치를 바꾸어 정렬하는 방법 안정 정렬과 불안정 정렬 안정 정렬 중복된 숫자가 원래 순서를 유지한 상태로 정렬하는 방법 불안정 정렬 중복된 숫자의 순서를 보장할 수 없다 선택정렬 순서대로 리스트의 가장 작은 수를 찾고 그 수를 확정되지 않은 부분의 가장 앞 자리에 놓는 방법 리스트 안에서 순서만 바꿔주기 때문에 in-place 정렬 복잡도는 O( n^2​​ ), 최선, 최악, 평균의 경우 모두 O( n^2) 삽입정렬 요소를 하나씩 꺼내서 그 요소 앞에 있는 다른 요소들과 모두 비교..

레드블랙 트리 자가 균형 이진 탐색 트리 AVL 트리처럼 스스로 균형을 잡는 트리 규칙 모든 노드는 빨간색이나 검은색 루트는 항상 검은색 새로 추가되는 노드는 항상 빨간색 루트에서 잎 노드로 가는 모든 경로에는 같은 수의 검은색 노드가 있어야 한다. 어떤 경로에서도 빨간색 노드 2개가 연속으로 있어서는 안된다. 모든 빈 노드는 검은색이라고 가정 균형을 맞추는 방법 이모 노드가 검은색일 경우 회전을 한다. 회전을 하고 나면 부모 노드는 검은색, 두 자식 노드는 빨간색이 되어야 한다. 이모 노드가 빨간색일 경우 색상 전환을 한다 색상 전환을 하고 나면 부모 노드는 빨간색, 두 자식 노드는 검은색이 되어야 한다 레드블랙 트리 클래스 public class RedBlackTree implements RedBla..

AVL 트리 스스로 균형을 잡는 이진 탐색 트리 왼쪽과 오른쪽의 높이 차이가 항상 1보다 작거나 같아야 한다. 노드 class Node{ T data; Node left; // 왼쪽 자식을 가리키는 포인터 Node right; // 오른쪽 자식을 가리키는 포인터 Node parent; // 부모 노드를 가리키는 포인터 // 생성자 public Node(T obj){ data = obj; parent = left = right = null; } add 메소드 클래스를 생성 후, 트리가 비어있으면 노드를 추가하고 비어있지 않다면 add 메소드를 재귀로 호출 // AVL 클래스의 생성자 public AVLTree(){ root = null; currentSize = 0; } // add 메소드 public v..

힙과 트리 트리 노드를 나무 형태로 연결한 구조를 트리라고 한다 트리에 있는 각각의 요소는 노드라고 한다. 노드는 부모와 자식형태로 이어진다. root(뿌리) - 트리의 시작 부분, 뿌리를 통해서 트리를 탐색한다 leaf(앞) - 자식이 딸려있지 않은 부분 edge(간선) - 두 노드를 연결하는 선, 뿌리로부터 간선의 수에 따라 Level을 나눔 힙 - Tree levels 힙 최대값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리를 기반으로 한 구조 max heap(최대 힙)과 min heap(최소힙)이 있다. 최대 힙 : 부모 노드 > 자식노드, 가장 큰 숫자가 뿌리에 있다 최소 힙 : 부모 노드 < 자식노드, 가장 작은 숫자가 뿌리에 있다 log​2​​(n+1)−1 은 height..

해시 데이터를 빠르게 추가하거나 제거하도록 한 데이터 구조 해시는 키, 그리고 그와 연관된 값으로 이루어져있다 해시 함수 해시 함수를 작성할 때 고려해야할 점 데이터의 속성 연산이 빨라야한다 두 요소가 "같다면" 같은 값을 반환 같은 실행 환경일 경우 같은 객체라면 같은 값 반환 코드를 새로 실행하면 객체가 같더라도 다른 값이 반환돌 수 있다 코드에서 최대한 충돌이 일어나지 않도록한다 해시 충돌 서로 다른 값을 가진 키가 일치하는 경우를 해시 충돌이라고 한다 위 사진에서는 전화번호 3분할한 것의 합을 키로 지정 -> 키의 값이 2386으로 같아 해시 충돌이 발생 해시 함수에서 문자열 public int hashCode(String s) { int g=31; int hash=0; // 문자열을 숫자로 나타..

연결 리스트 포인터를 사용하여 여러 개의 노드를 연결하는 자료 구조 연결 리스트의 기본 구성 요소는 노드 노드에는 2가지의 정보가 저장된다 인접한 노드를 가리키는 next라는 이름의 포인터 노드에 넣는 데이터 Head라는 이름의 포인터로 시작, Head는 리스트의 첫번째 노드를 가리킨다 노드와 크기 - 연결 리스트의 내부 클래스에서 노드를 정의한 코드 public class LinkedList implements ListI{ // 노드 정의 class Node{ E data; Node next; public Node(E obj){ data=obj; next=null; } } private Node head; // 노드 개수를 세는 변수 private int currentSize; // 기본 연결리스트 p..

경계조건 Boundary Conditions - Empty data structure - Single element in the data structure - Adding / removing beginning of data structure - Adding / removing end of the data structure - Working in the middle 어떤 자료 구조든 아래의 경계 조건에서 문제가 생기진 않을지 생각해봐야 한다 1. 자료 구조가 비어있는 경우 2. 자료 구조에 단 하나의 요소가 들어있을 때 3. 자료 구조의 첫 번째 요소를 제거하거나 추가할 때 4. 자료 구조의 마지막 요소를 제거하거나 추가할 때 5. 자료 구조의 중간 부분을 처리할 때 출처 : https://www.boos..

빅 오 표기법 - 알고리즘의 효율성을 표시하는 표시법 - O (빅 오 복잡도) : 비교 대상인 그래프가 일치 혹은 아래에 있을 때. 비교 대상인 다른 알고리즘과 같거나 더 빠르다. ( N >= ) - o (리틀 오 복잡도) : 비교 대상인 그래프가 아래에 있을 때. 비교 대상인 다른 알고리즘보다 더 빠르다. ( N > ) - θ (세타 복잡도) : 비교 대상인 그래프가 일치할 때. 비교 대상인 다른 알고리즘과 같다. ( N = ) - Ω (빅 오메가 복잡도) : 비교 대상인 그래프가 일치 혹은 위에 있을 때. 비교 대상인 다른 알고리즘과 같거나 느리다. ( N O(logn) > O(n) > O(nlogn) > O(n^c) > O(c^n) > O(n!) 참고 ) https://velog.io/@9wonsi..

시간 복잡도 - 서로 다른 알고리즘의 효율성을 비교할 때 사용 규칙 1. 입력 값(n)은 항상 0보다 크다. 규칙 2. 함수는 많은 입력값이 있을 때 더 많은 작업을 한다. 규칙 3. 시간 복잡도에서는 모든 상수를 삭제한다. 시간 복잡도가 3n이라면 복잡도가 n인 알고리즘 이다. 2n,5n,10n 모두 복잡도가 n인 알고리즘이다. 규칙 4. 낮은 차수의 항은 모두 무시한다. 시작 복잡도에서 n과 n² 를 비교할 때 n² 이 항상 더 오래걸리는 알고리즘으로 판단한다.. n³ + n² + n의 시간 복잡도는 n³인 알고리즘이다. 규칙 5. 시간 복잡도 함수가 log를 포함할 경우 밑은 무시한다. 규칙 6. 등호를 사용하여 표현한다 참고 https://www.boostcourse.org/