CS 공부/CS Study 원본 검색 결과

해당 글 19건

CS 11일차

이진 힙 자료구조 - 전에 함. DFS & BFS 그래프 알고리즘으로, 문제를 풀 때 상당히 많이 사용한다. 경로를 찾는 문제 시, 상황에 맞게 DFS와 BFS를 활용하게 된다. DFS 루트 노드 혹은 임의 노드에서 다음 브랜치로 넘어가기 전에, 해당 브랜치를 모두 탐색하는 방법 스택 or 재귀함수를 통해 구현한다. 모든 경로를 방문해야 할 경우 사용에 적합 시간 복잡도 인접 행렬 : O(V^2) 인접 리스트 : O(V+E) V는 접점, E는 간선을 뜻한다 BFS 루트 노드 또는 임의 노드에서 인접한 노드부터 먼저 탐색하는 방법 큐를 통해 구현한다. (해당 노드의 주변부터 탐색해야하기 때문) 최소 비용(즉, 모든 곳을 탐색하는 것보다 최소 비용이 우선일 때)에 적합 시간 복잡도 인접 행렬 : O(V^2)..
CS 공부/CS Study 원본 2021. 1. 25. 20:34

CS 10일차

TreeMap이란? TreeMap은 이진트리를 기반으로 한 Map 컬렉션입니다. 같은 Tree구조로 이루어진 TreeSet과의 차이점은 TreeSet은 그냥 값만 저장한다면 TreeMap은 키와 값이 저장된 Map, Etnry를 저장한다는 점입니다. TreeMap에 객체를 저장하면 자동으로 정렬되는데, 키는 저장과 동시에 자동 오름차순으로 정렬되고 숫자 타입일 경우에는 값으로, 문자열 타입일 경우에는 유니코드로 정렬합니다. 정렬 순서는 기본적으로 부모 키값과 비교해서 키 값이 낮은 것은 왼쪽 자식 노드에 키값이 높은 것은 오른쪽 자식 노드에 Map.Etnry 객체를 저장합니다. TreeMap은 일반적으로 Map으로써의 성능이 HashMap보다 떨어집니다. TreeMap은 데이터를 저장할 때 즉시 정렬하기..
CS 공부/CS Study 원본 2021. 1. 22. 22:09

CS 9일차

Trie 자료구조 이분 탐색 알고리즘 3-way handshake & 4-way handshake IPC (inter procsess communication) statement vs prepared statement JAVA 컴파일 과정 Trie(트라이) Trie 자료구조란? 일반 트리 자료구조 중 하나로, Digital Tree, Radix Tree, Prefix Tree라고도 불린다. 텍스트 자동 완성 기능과 같이 문자열을 저장하고 탐색하는데 유용한 자료구조이다. Trie 자료구조의 형태는? 각 노드는 맵을 가지고 있다. Key는 하나의 알파벳이 되고, Value는 그 Key에 해당하는 자식 노드가 된다. 다음은 DEV, DEAR, PIE, POP, POW라는 단어가 들어있는 Trie 자료구조를 도..
CS 공부/CS Study 원본 2021. 1. 18. 20:56

CS 8일차

Count Sort PCB와 Constext Switching 트랜잭션 상태, 주의점 JAVA - Collection API 이진 탐색 트리, TCP => 저번 study에 진행. Count Sort 계수 정렬은 일반적인 상황이 아닌, 배열의 구성 요소들이 적은 범위로 자주 등장할 때 쓸 수 있는 정렬 기법으로 O(n)의 시간 복잡도를 지닌다. 아이디어는, 여러번 반복되는 요소들을 한 번 쭉 훑으면서 등장하는 횟수를 센다. 그 횟수 배열을 작은 인덱스부터 누적합 배열로 갱신한다. 이 값이 새 위치 인덱스가 된다. 배열을 처음부터 훑으면서 등장하는 수의 누적합 값을 인덱스로 새 배열에 위치한다. 자기 자리를 찾았으면 자신에 해당하는 인덱스의 누적합을 -1 해준다. 즉 자기가 위치할 구간 정보가 누적합이고,..
CS 공부/CS Study 원본 2021. 1. 15. 22:21

CS 7일차

Hash Radix Sort OSI 7 계층 System Call DB - Transaction Hash 연관 배열 구조로 키와 값이 1:1로 매핑되어 저장한다. 충돌이 일어나지 않으면, 삽입, 검색, 삭제 모두 O(1) 시간 복잡도를 지닌다. 충돌을 다루기 위해, open addressing 과 separate chaining 방식이 있다. 조금 더 효율적인 것은 seperate chaining 방식을 삽입 시에 head에 삽입하는 방법으로 구현하는것이다. 해시 함수와 버켓 크기에 따라 성능이 크게 좌우된다. 단접으로는 순서가 있는 배열에 어울리지 않고, 공간 효율성이 떨어진다. Radix Sort 기수 정렬은 정수형 정렬에 특화된 정렬로 시간복잡도는 O(dn) 이다. d = 가장 큰 수의 자리 수 이..
CS 공부/CS Study 원본 2021. 1. 13. 22:30

CS 6일차

B Tree & B+ Tree Heap Sort 웹 통신의 큰 흐름 인터럽트 정규화에 대해서 | 정규화 탄생 배경 | 정규화란 무엇인가 자바 - 추상 클래스, 인터페이스, 차이 B Tree & B+ Tree B Tree 데이터베이스, 파일 시스템에서 널리 사용되는 트리 자료구조의 일종이다. 이진 트리를 확장해서, 더 많은 수의 자식을 가질 수 있게 일반화 시킨 것이 B-Tree 자식 수에 대한 일반화를 진행하면서, 하나의 레벨에 더 저장되는 것 뿐만 아니라 트리의 균형을 자동으로 맞춰주는 로직까지 갖추었다. 단순하고 효율적이며, 레벨로만 따지면 완전히 균형을 맞춘 트리다. 대량의 데이터를 처리해야 할 때, 검색 구조의 경우 하나의 노드에 많은 데이터를 가질 수 있다는 점은 상당히 큰 장점이다. 대량의 데..
CS 공부/CS Study 원본 2021. 1. 11. 22:31

CS 5일차

Heap Merge Sort DNS round robin 프로세스 주소 공간 DB - 인덱스 JVM Heap 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전 이진 트리 자료 구조이다. 완전 이진 트리이기 때문에 배열을 이용하여 손쉽게 구현할 수 있다. max - heap은 부모가 자식보다 항상 큰 자료구조이고, min - heap 은 부모가 항상 자식보다 작은 자료 구조이다. 이를 응용하여 우선 순위 큐를 구현할 수 있다. 새로운 원소가 삽입 될 때나 root 원소를 추출하고 나서 heap 규칙을 따르도록 원소의 위치를 바꾸는 과정을 heapify 라 불리며 log n 이 소요 된다. 새로운 원소는 항상 힙 구조의 제일 끝 원소로 추가되며 heapify 과정을 통해 자신의 자리를 찾아 ..
CS 공부/CS Study 원본 2021. 1. 8. 22:40

CS 4일차

Tree 퀵 정렬 HTTP의 문제점들 데이터베이스 | DB를 사용하는 이유 | DB의 성능 프로세스 vs 스레드 Tree 계층적 관계 표현 루트 노드를 제외하고 모든 노드는 단 하나의 부모 노드만을 갖는다. 이진 트리는 배열과 연결 리스트로 표현 가능. 이진 트리란? 루트를 기준으로 left, right subtree가 존재하고, 두 서브트리 모두 이진트리여야 한다. 따라서 공집합도 노드로 인정한다. 각 노드가 최대 2개 까지만 자식 노드를 갖을 수 있다. 이진 트리의 종류 정 이진 트리 ( FULL ) 리프 노드를 제외하고 2개의 자식 노드를 갖는다. ( 자식이 있다면 2개고 아니면 없다! ) 완전 이진 트리 ( COMPLETE ) 왼쪽에서 오른쪽으로 순서대로 차곡 차곡 쌓인다 포화 이진 트리 ( PE..
CS 공부/CS Study 원본 2021. 1. 6. 22:29