사진과 음악을 좋아하는 개발자 지망생의 블로그

1. 비교 모델에서의 정렬1) 비교모델이란?데이터 항목 간의 비교 연산만을 이용해 정렬을 수행하는 방식병합, 퀵, 힙 등 전통적인 정렬 알고리즘이 비교모델에 속함  2) 비교모델의 탐색과 정렬의 하한탐색 하한탐색의 경우 최악의 경우 $\log n$번의 비교가 필요함이유탐색 알고리즘은 이진 결정 트리(Binary Decision Tree)로 표현할 수 있음결정 트리의 각 내부 노드는 항목 간의 비교를 나타내며, 루트에서 리프까지의 경로는 탐색 과정임탐색 가능한 n개의 항목을 모두 포함하려면 트리의 최소 깊이는 $\log n$이 됨 정렬 하한정렬 문제는 최소 $n \log n$번의 비교가 필요함증명정렬된 배열의 경우의 수(모든 가능한 결과)는 $n!$(순열의 개수)임n!개의 리프를 포함하는 결정 트리의 최소..

1. 선택 정렬(Selection Sort)정의각 단계에서 남은 부분 중 가장 작은 원소를 선택해, 해당 위치에 배치하는 정렬 알고리즘제자리 정렬(In-place Sort)로 추가 메모리 공간을 거의 사용하지 않고, 배열 내에서 정렬함안정 정렬이 아니기 때문에 동일한 값의 순서가 변경될 수 있음  시간 복잡도최악/최선/평균: $O(N²)$  정렬 단계가장 작은(또는 큰) 원소 선택배열에서 아직 정렬되지 않은 부분 중에서 가장 작은(또는 큰) 원소를 찾음가장 앞의 원소와 교환찾은 원소를 현재 정렬되지 않은 부분의 첫 번째 원소와 교환함다음 위치로 이동다음 위치로 이동하여 1~2단계를 반복전체 배열이 정렬될 때까지 반복배열이 모두 정렬될 때까지 위 과정을 반복  장점 및 단점장점알고리즘이 직관적이고 구현이 ..

1. 스택(Stack)시간 순서상 가장 최근에 추가한 데이터가 가장 먼저 출력되는 후입선출(LIFO, Last In First Out) 형식으로 데이터를 다루는 자료구조데이터를 추가하는 것을 push, 데이터를 꺼내는 것을 pop이라고 한다활용 예시: 후위 표기법 연산, 괄호 유효성 검사, 웹 브라우저 방문기록(뒤로 가기), 깊이우선탐색(DFS)  1) 리스트(list) 기반 구현python에서 stack을 가장 간단히 구현하는 방법은 list를 이용하는 것이다.append 메소드를 사용하면 맨 뒤에 데이터가 추가 되고, pop을 하게 되면, 맨 앞의 데이터가 나온다시간복잡도: $O(1)$# stack 선언s = []# push - O(1)s.append(1) # [1]s.append(2) # [1, 2..

1. 투 포인터 기법1) 개요두 개의 포인터(slow, fast)를 이용하여 연결 리스트의 사이클을 탐지하는 방법slow 포인터는 한 번에 1칸씩 이동하고, fast포인터는 한 번에 2칸씩 이동  2) 사이클이 없는 경우만약 연결 리스트에 사이클이 없는 경우, fast포인터는 리스트의 끝(None)에 도달함예를 들어, A -> B -> C -> D -> None의 리스트에서, fast 포인터는 한 번에 두 칸씩 이동하면서 끝에 도달함slow 포인터: A -> B -> C -> Dfast 포인터: A -> C -> None  3) 사이클이 있는 경우사이클이 있을 경우, fast 포인터가 slow포인터를 따라잡고 만나게 되는 지점이 생김마치 원이 있는 트랙에서 두 사람이 달릴 때, 빠르게 달리는 사람이 결국..

1. Array미리 할당된 공간에 연관된 데이터를 연속적이며 순차적으로 저장하는 자료구조1) 정적 배열(Static Array)미리 할당된 크기를 가지며 연속적으로 순차적으로 데이터를 저장하는 자료구조특징고정된 크기를 갖는다저장 공간을 미리 확보해야 한다메모리 상에 데이터가 서로 인접한(연속적인) 메모리 위치에 저장된다 → 논리적 저장 순서와 물리적 저장 순서가 같다시간 복잡도삽입과 삭제 → 삽입 및 삭제로 인해 데이터들이 한칸 씩 움직여야 하기 때문에 $O(N)$을 갖음탐색메모리 시작 주소에 + N 만 하면 되기 때문(랜덤 접근, Random Accesss)에 시간 복잡도 $O(1)$을 갖음Random Access(Direct Access)데이터 접근 시, 어떤 순서로든, 어느 위치에 있는 데이터라도 ..

힙(Heaps)의 사전적 용어 Heap 1. 무질서하게 서로의 위에 쌓아 올린 물건들의 무질서한 집합체. 2. 많은 양 또는 수. 자료 구조에서의 힙(Heaps) - 트리 데이터 구조에서의 "힙"은 최댓값 또는 최솟값을 효율적으로 검색하고 추출하기 위한 방법 중 하나 - 이때 "힙"은 일종의 이진 트리(binary tree)를 기반으로 구성되며, 다음과 같은 특성을 갖는다 1. 힙은 완전 이진 트리(Complete Binary Tree) 구조를 가진다 2. 최대 힙(Max Heap)은 부모 노드가 항상 자식 노드보다 크거나 같은 값을 갖는 구조입니다. → 즉, 가장 큰 값이 루트 노드에 위치함 3. 최소 힙(Min Heap)은 부모 노드가 항상 자식 노드보다 작거나 같은 값을 갖는 구조입니다. → 즉, ..

array - 인덱스가 존재하며 타입의 데이터가 연속적으로 존재하는 집합 - 따라서 조회가 빠르나 미리 배열의 크기를 지정해야하며, 데이터 삽입·삭제가 불편하다 list - 수정가능하며 순서가 있는 데이터 집합 - 각 원소의 길이가 달라도 되며 각 원소의 데이터 타입이 달라도 된다. - 인덱스가 존재하나 순서만 나타내는 정도이며 메모리 주소가 비연속적일 수 있다. - 포인터를 통해 다음 데이터를 가리키고 있어 삽입 및 삭제가 쉬우나 데이터 검색 성능이 좋지 않다 ○ list.insert(idx, elm) - list에서 idx번째 위치에 elm을 삽입함. - idx에 elm을 삽입하기 위해선 list의 길이가 1 증가해야하며 기존 idx에 있던 원소는 한칸씩 밀려나게 된다 ○ del(list[idx]) ..

1. 메모리 구조 메모리 구조에는 크게 code, data, stack, heap이 있다 code에는 실행할 프로그램의 코드가 data에는 전역변수와 정적 변수가 stack에는 함수의 매개변수와 지역변수가 heap에는 동적으로 할당하는 변수나 메소드가 저장된다 data를 조금 더 분해하면 초기화된 영역과 초기화되지 않은 영역(BSS)이 있다 2. Python Memory Management 파이썬은 python memory management 에 의해 관리되고 있다 파이썬에서 변수가 선언되면 변수에 값이 들어가는 것이 아니라 python memory management에 의해 heap영역에서 선언된 변수에 메모리 영역을 할당해 주고 변수에는 할당된 변수의 '주소'가 저장된다. 그리고 주소에 해당된 메모리..