분류 전체보기 (61) 썸네일형 리스트형 [Algorithm] AVL 트리 한쪽으로 치우친 편향 이진트리가 되면 트리의 높이가 높아지기 때문에이를 방지하고자 높이 균형을 유지하는 AVL 트리를 사용한다.AVL 트리 = 자가 균형 이진 탐색 트리 특징이진 트리의 속성을 가진다왼쪽, 오른쪽 서브 트리의 높이 차이가 최대 1이다어떤 시점에서 높이 차이가 1보다 커지면 회전(rotation)을 통해 균형을 잡아 차이를 줄인다AVL 트리는 높이를 logN으로 유지하기 때문에 삽입, 검색, 삭제의 시간복잡도는 O(logN)이다균형(밸런스) 잡는 방법Balance Factor를 사용한다. 이는 왼쪽과 오른쪽의 자식(노드)의 높이 차이를 뜻하는 말이다. 균형인수라고도 한다.균형 인수의 절대 값이 클수록 트리의 균형이 무너진 것이다. 트리를 균형있게 만들어야 하는 이유트리의 높이가 h라면 이진.. [Algorithm] 삽입 정렬 삽입정렬 개념구현 코드시간 복잡도삽입 정렬 Insertion Sort 란?자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입하는 알고리즘손안의 카드를 정렬하는 방법과 유사처음 Key 값은 두 번째 자료부터 시작 구현 코드def insertion_sort(arr): for i in range(1, len(arr)): key = arr[i] j = i-1 # key가 정렬된 부분에서 적절한 위치를 찾을 때까지 비교하고 이동 while j >= 0 and key 시간 복잡도 : O(N^2) 최선의 경우이동 없이 1번의 비교만 이루어짐외부 루프 : (n-1)번Best T(n) =.. [Algorithm] 버블 정렬 버블정렬 개념구현 코드시간복잡도개념인접한 두 원소를 검사하여 정렬하는 알고리즘뒤에서부터 앞으로 정렬해나가는 구조 구현 코드def bubble_sort(arr): for i in range(len(arr)-1, 0, -1): for j in range(i): if arr[j] > arr[j+1]: arr[j], arr[j+1] = arr[j+1], arr[j] 시간 복잡도 : O(N*2)루프문으로 맨 뒤부터 맨 앞까지 모든 인덱스에 접근 -> O(N)하나의 루프에서는 인접한 값들의 대소 비교 및 자리 교대 -> O(N)=> O(N^2) 최적화이전 패스에서 앞뒤 자리비교(swap)이 한 번도 일어나지 않았다면 정렬되.. [시스템 엔지니어링] I/O Bound 문제 I/O Bound 란?시스템의 전체 성능이 CPU 연산 속도가 아니라 I/O(입출력) 작업 속도에 의해 결정되는 상태를 말한다.여기서 I/O는 디스크 접근, 네트워크 통신, 데이터베이스 쿼리, 파일 읽기/쓰기, 시스템 콜 대기 등 CPU 외부장치와 데이터를 주고받는 모든 작업을 포함한다. 즉, CPU가 데이터를 더 처리할 여유가 있음에도 불구하고, I/O 완료를 기다리느라 놀고 있는 시간(iowait)이 많아지는 상황이 I/O Bound 상태이다. 대표 증상평균 CPU 사용률은 낮은데(또는 코어가 남는데), iowait 시간이 높다RPS/Throughput이 낮고 레이턴시가 길며, burst에서 급격히 악화(큐가 쌓임)동시성(concurrency)을 늘리면 어느 정도까지는 개선되지만, 임계점을 넘으면 .. [Algorithm] 해시충돌 해결방법과 각각의 특징 해시 충돌이란?해시 테이블에서 서로 다른 키 값이 동일한 해시 값을 갖는 현상 주요 해결 방법체이닝 : 같은 해시 값 → 리스트에 이어 붙이기 개방 주소법 : 같은 해시 값 → 테이블 내 다른 빈칸 찾아 저장하기 체이닝 (Separate Chaining)같은 해시 주소에 여러 개의 키가 할당되면, 해당 주소에 연결리스트(Linked List)나 다른 자료구조를 두어 충돌된 키들을 저장하는 방식이다 원리해시 테이블의 각 버킷(bucket)이 연결 리스트, 동적 배열, 혹은 트리 구조를 가진다같은 해시값이 나면 그 버킷의 리스트에 추가특징삭제가 간단: 버킷 내부 자료구조에서만 제거하면 됨부하율(α = n / 버킷 수) > 1도 가능최악의 경우(모두 같은 해시값) 한 버킷에 n개가 몰려 O(n)장점구현 단순,.. [Algorithm] B Tree, B+ Tree 개념차이점삽입과 삭제 과정시간복잡도B Tree 개념B-트리(B-tree)는 데이터베이스와 파일 시스템에서 널리 사용되는 트리 자료구조의 일종으로, 이진 트리를 확장해 하나의 노드가 가질 수 있는 자식 노드의 최대 숫자가 2보다 큰 트리 구조이다. 모든 키는 정렬돼 있고, 탐색·순차접근·삽입·삭제가 모두 O(log n)에 가능하도록 높이(h)를 매우 낮게 유지한다.이 구조는 디스크/페이지 I/O를 최소화하려고 고안됐고, DB와 파일시스템 인덱스의 표준이다. 최대 M개 자식을 가질 수 있는 B-Tree를 M차 B-Tree라고 부른다. [ DB 인덱스로 B(+)-트리를 채택하는 이유 ]메모리는 랜덤 접근이 빠르지만, 디스크/SSD는 페이지 단위 접근 비용이 크다.B-트리는 한 노드(=한 페이지)에 많은 키를 .. [Algorithm] 이진 최소 힙 (heapq) 1. 이진최소힙 개념2. 삽입과 삭제 과정3. 각 경우의 시간복잡도 정리개념완전이진트리 형태의 힙이며, 각 노드가 부모 보통 배열로 구현 (인덱스 i의 왼/오 자식 : 2i, 2i+1)* python의 heapq 모듈은 이진 최소 힙을 기반으로 동작함 삽입 과정def insert_min_heap(heap, value): heap.append(value) idx = len(heap) - 1 while idx > 0 and heap[(idx-1)//2] > heap[idx]: heap[idx], heap[(idx-1)//2] = heap[(idx-1)//2], heap[idx] idx = (idx-1)//2 heap =.. [Java] 코딩테스트 준비 StringTokenizer countTokens()배열lengthArrays.copyOf(int[] arr, int newLength) : 길이만큼 복사Arrays.copyOfRange(int[] arr, 시작index, 끝index) : 범위만큼 복사Arrays.sort(int[] arr) : 오름차순 정렬Arrays.sort(int[] arr, Collections.reverseOrder()) : 내림차순 정렬리스트size()문자열repeat(int count)parseInt(str) : 문자형->정수형slice (시작index, 끝index) = substringsubstr(시작index, 길이)HashMap1) 데이터 추가put(key, value) : key와 value 저장putAll(m) .. 이전 1 2 3 4 ··· 8 다음
