본문 바로가기

개발 지식/알고리즘

 (11)
쉘 정렬 JAVA로 작성되었습니다. 쉘 정렬 삽입 정렬을 개산한 알고리즘, 바탕은 삽입정렬을 기본으로 진행한다. 가까운 위치에 삽입되는 (어느정도 정렬이 되어있는) 삽입정렬이 빠른 것을 이용하여 삽입정렬을 하기 전 배열을 어느정도 정렬한 상태에서 삽입정렬을 진행하는정렬 방식이다. 이때 gap이라는 것이 존재하는데 gap만큼 배열을 띄엄띄엄 정렬하는데 사용한다. 갭을 설정한다. 갭의 값은 이전 갭의 절반으로 설정한다. (초기 값은 배열의 크기 / 2 로 설정한다) (홀수를 권장하므로 2로 나누었을 때 짝수가 나온다면 +1을 하여 홀수로 정한다.) 원본 배열에서 다음 요소와 인덱스의 차이가 gap만큼 있는 부분 배열들을 생성한다. (리스트의 길이가 11(0~10)이고 갭이 5라면 (0, 5, 10), (1, 6), ..
합병 정렬 JAVA로 작성되었습니다. 합병 정렬 분할정복을 이용한 정렬방법 배열을 한개의 조각이 될 때까지 쪼개고 두개 (1, 1)를 서로 비교, 4개(2, 2)를 서로 비교, 8개(4, 4)를 서로 비교 하는 방법 비교한 결과를 저장하기 위해 임시의 배열이 추가로 필요하다. 인자로 들어온 left가 right보다 작은지 검증한다 (같다면 숫자가 하나이기에) 중간값을 결정한다. ((오른쪽 값 - 왼쪽 값) / 2 + left) 중간값과 왼쪽 배열, 중간값 오른쪽 배열을 다시 분할하는 재귀함수를 호출한다. left + 1 = right 가 될때까지 분할을 수행한다. (분할해야 하는 배열의 요소가 2개) (3개인 경우 2개와 1개로 쪼개지고 왼쪽의 2개만 쪼개져 서로 비교를 진행하고 다시 돌아와 2개와 1개의 비교를 ..
탐색 (선형 탐색, 트리 탐색, AVL, 회전 연산) 탐색: 임의의 키 값을 대상 파일에서 찾는 것 선형탐색 O(n) - 정렬되어 있지 않은 파일 O(n) - none-sorted - 정렬되어 있는 파일 O(n) - sorted none-sorted에 비해서 없는 키값을 찾을 때 유리하다. 트리탐색 tree -> binary tree 정의: 임의의 키 값은 왼쪽보다 크고 오른쪽보다 작다 구성: 맨 처음 들어오는 키 값은 루트, 나머지는 정의대로 삽입한다. - ex) 5 4 3 6 8 2 1 7 - ex) 5 3 6 8 4 7 1 2 - ex) 1 2 3 4 5 6 AVL Tree : Hight Balanced -k tree 일 때 k는 1이하 k : 왼쪽 자식과 오른쪽 자식의 Depth 차이 L : 왼쪽 자식 Depth R : 오른쪽 자식 Depth Eve..
트리 (완전 이진, 포화 이진, Max-heap, Min-heap) 완전 이진 트리 (Complete binary tree) root에서 레벨 순으로 (좌에서 우로 M) leaf 노드를 제외한 모든 노드의 자식 수가 2개 포화 이진 트리 (Perfect binary tree) 레벨 I의 노드 수 : 2^(i - 1) 레벨 3의 노드 수 : 2^(3-1) = 4개 트리의 노드 수 : 2^3 - 1 = 7개 leaf 노드를 제외한 모든 노드의 자식 수가 2개 완전 이진 트리를 만족함 이진트리의 부모를 구하는 방법 ⌊자식 노드/2⌋ ex) 5번째 노드의 부모는 몇 번째 노드인가? ⌊5/2⌋ ( 5/2 = 2.5 의 바닥함수는 2 ) : 2 번째 노드가 부모 노드 이진트리의 자식를 구하는 방법 부모 * 2, 부모 * 2 + 1 ex) 3번째 노드의 자식은 몇 번째 노드인가? 3..
스택, 큐 스택 (Last In First Out) (배열로 구현) peapable stack : 중간에 넣고 뺄 수 있는 스택 (LL로 구현) 하나의 공간에 두개의 스택 S1 □□□□□□□ S2 -> bottom point가 두개 다중 스택: 하나의 스택 안에 여러개의 스택이 들어가는 형태 초기 공간 분배 방법 영분배: n개의 스택을 모두 합친 뒤 모든 스택의 크기 0 균등분배: 스택을 합쳐서 저장공간 균등하게 재분배 차등분배: 스택의 이용도 추정하여 그 비융ㄹ에 따라 공간 분할 knuth's 0분배: 처음에는 모두 0, overflow가 발생할 때 마다 할당 공간 1 증가 ------------------------------------------------------------------------------..
메모리 관리 Dangling Reference int *p = &a 에서 a 변수가 사라졌을 때 : int *p = (int *)malloc(sizeof(int)); int *q = p; free(p); q : ?? Garbage int *p, *q p = (int *)malloc(sizeof(int)); q = (int *)malloc(sizeof(int)); p = 0; -> 동적할당된 메모리 공간 : ?? 최초 적합 주소순으로 적합하는 방식 들어갈 수 있는 크기의 빈 영역중 첫 번째 분할 영역에 배치 최적 적합 크기순으로 적합하는 방식 들어갈 수 있는 크기의 빈 영역중 단편화를 가장 작게 남기는 분할 영역에 배치 최악 적합 최적 적합의 반대 들어갈 수 있는 크기의 빈 영역중 단편화를 가장 많이 남기는 분할 영역..
Linked List Ruby로 작성되었습니다. - Node 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 # frozen_string_literal: true class Node attr_accessor :prev, :value, :next def initialize(left, value, right) @prev = left @value = value @next = right end end node1 = Node.new(nil, 1, nil) node2 = Node.new(node1, 2, nil) node2.prev.next = node2 node3 = Node.new(node2, 3, nil) node3.prev.next = node3 puts node1.va..
포인터, 매개변수, CBV, CBR 포인터 int a int *p int **p p = &a pp = &p 형식 매개변수 swap(int *px, int *py) {} 실 매개변수 swap(&a, &b); CBV (call-by-value) func(a, b); CBR (call-by-reference) func(&a, &b);
배열 접근 1차원 배열 접근 공식 int a[10] &a[7] = &a[0] + (7 * 4) (int 형이 4바이트 일 때) 2차원 배열 접근 공식 int a[3][4] (1,1) 행 우선 : α + (행 * 열의 갯수 + 열) + D 열 우선 : α + (열 * 행의 갯수 + 행) + D Q1. [1][1]은 몇 번째? 행 우선 : 5번째 열 우선 : 6번째 Q2. [2][1]은 몇 번째? 행 우선 : α + (2 * 4 + 1) + D = 10 열 우선 : α + (1 * 3 + 2) + D = 6 3차원 배열 접근 공식 int a[3][4][3] Q1. [2][3][2]은 몇 번째? 행 우선: ((3 * 4) * 1) + (α + (2 * 4 + 1) + D) 열 우선: ((3 * 4) * 1) + (α +..
infix, postfix infix : a + b postfix : ab+ infix -> postfix = (5 + (3 x 2)) -> 532x+

티스토리툴바