공부 기록용 블로그

Arrays.sort()로 풀면 시간초과가 나는 문제가 있는데, Arrays.sort()의 경우 dual-pivot Quicksort 알고리즘을 사용한다. 얘는 평균 시간 복잡도 O(nlogn), 최악 O(n²) 따라서 시간초과가 날 수 있다. 해결 방법 ①Collection.sort() Timsort → 합병 정렬(Merge sort), 삽입 정렬(Injection sort) 알고리즘을 사용하는데, 합병 정렬의 최악의 경우와, 삽입 정렬의 최선의 경우가 섞여있는 정렬 알고리즘을 hybrid sorting algorithm이라고 한다. 합병 정렬 : 최선, 최악 모두 O(n) 삽입 정렬 : 최선 O(nlogn), 최악 O(n²) 두 정렬 모두 안정 정렬(stable sort)이다. 시간 복잡도가 O(n)..

그래프(Graph) 연결되어 있는 객체 간의 관계를 표현할 수 있는 자료구조. 그래프는 간선 종류에 따라 무방향 그래프(undirected graph)와 방향 그래프(directed graph)로 구분됨. 간선에 비용이나 가중치가 할당된 그래프를 가중치 그래프(weighted graph) 또는 network라고 한다. 네트워크는 도시와 도시를 연결하는 도로의 길이, 회로 소자의 용량, 통신망의 사용료 등을 추가로 표현할 수 있으므로 응용 분야가 매우 광범위하다. 인접 정점(adjacent vertex) : 간선에 의해 직접 연결된 정점 차수(degree) : 하나의 정점에 인접한 정점의 수 (undirected graph는 간선X2) directed graph에서 (=) 진입 차수(in-degree) :..

접근 속도는 빠르지만 기억 공간이 많이 요구됨. 다른 방식에 비해 검색속도 빠름. 삽입 삭제 작업 빈도가 많을 때 유리. 대부분 탐색방법들은 탐색키를 저장된 키 값과 반복적으로 비교하여 탐색하고자하는 항목에 접근하지만, 해싱은 키 값에 산술적 연산을 적용해 해당 항목이 저장되어있는 테이블의 주소를 계산하여 접근한다. : 자료를 꺼내기 위해 전체 배열을 탐색하지 않음. *키 값의 연산에 의해 직접 접근이 가능한 구조 : 해시테이블 *해시테이블을 이용한 탐색 : 해싱 키들의 비교에 의한 탐색은 정렬이 안되어있으면 O(n), 정렬되어있으면 O(logn₂ N). 보통 사전과 같은 자료구조를 구현할 때 최상의 선택이 됨. 사전 구조(dictionary)는 맵이나 테이블로 불리기도 한다. 탐색 키/키와 관련된 값으..

우선순위 큐는 배열이나 연결리스트, 힙으로 구현이 가능하다. 그 중 가장 효율적인 구조가 Heap, 이유는 시간복잡도가 O(log n) 데이터가 우선순위를 가지는 것이 특징이다. 우선순위가 높은 것 부터 먼저 나가고 최대힙/최소힙이 있음. 우선순위큐를 위한 것이 Heap Heap은 완전 이진트리이다. 그니까 완전이진트리가 아니면 힙ㄴㄴ 최댓값과 최솟값을 빠르게 찾는 것이 목적이기 때문에 전체 정렬이 필요 없다. 반정렬상태(느슨한 정렬 상태)를 유지하는데, 부모가 자식키보다 항상 큰 이진트리인 정도만 정렬한다. 가장 중요한 것은 중복값을 허용한다는 것! BST에서는 허용하지 않았다. priority queue 사례 : 시뮬레이션 시스템, 네트워크 트래픽 제어, OS 작업 스케줄링, 수치해석적 계산, 이산이..

트리를 알아보자,, 우선 트리하면 대표적인게 컴퓨터의 File System. 이외에 HTML Tag구조, 도-시군구-읍면동 주소체계, DBMS, 라우터 통신 알고리즘, 검색엔진에 사용된다. 트리는 아래로만 흐르는 방향그래프(Directed Graph)이다. 만약 그런 제약이 없다면 그래프. Binary Tree 이진트리는 자식의 갯수가 무조건 두개로 고정되어있다. *모든 노드가 2개의 서브트리를 갖고 있음. *공집합도 이진트리임. 일반 트리와 이진 트리의 차이점 1) 이진트리의 모든 노드는 차수가 2 이하, 즉 자식 노드의 갯수가 2 이하. 일반 트리는 자식 노드의 갯수 제한 없음. 2) 일반 트리와 달리 이진트리는 노드를 하나도 갖지 않을 수도 있음. 3) 서브트리간 순서가 존재함. : 왼쪽 서브트리,..

Stack - 후입선출(LIFO) : 입출력은 맨 위에서만 일어남, 중간부분 데이터는 삭제 못함. 입출력이 이뤄지는 부분을 stack top, 바닥을 stack bottom, 스택에 저장되는 것을 elememt라고 함. element가 없을 때는 empty stack이라 함. push연산중에 stack이 가득차서 입력이 불가능하면 오류 발생. pop연산중에 stack data가 없어서 출력이 불가능하면 역시 오류 발생 stack.empty()연산으로 비었는지 확인 후 pop 자료가 역순으로 출력되어야 하거나, 괄호검사에 이용. 배열과 연결리스트로 구현 가능. Stack 구현 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 2..