본문 바로가기

분류 전체보기152

[LeetCode] Sort Colors 목차 문제 공간복잡도를 O(1)로 정렬하는 문제입니다. 0,1,2 으로 구성된 array가 있을 때 정렬하는 문제입니다. 대부분의 정렬 예시 Input: nums = [2,0,2,1,1,0] Output: [0,0,1,1,2,2] Input: nums = [2,0,1] Output: [0,1,2] 제약사항 n == nums.length 1 2024. 4. 16.
[자료구조] 선택 정렬(Selection Sort) 목차 정렬 종류 비교 기반 정렬(Comparison Based Sorts) - Selection Sort, Bubble Sort, Insertion Sort, Heap Sort, Merge Sort, Quick Sort 비비교 기반 정렬(Non-comparison Based Sorts) - Counting Sort, Radix Sort, Bucket Sort 선택 정렬(Selection Sort) 개념 선택 정렬은 제일 작은 값을 찾고 앞에 있는 값들과 하나씩 변경하는 과정입니다. 단순하게 그냥 정렬 방식을 생각했을 때 떠올릴 수 있는 가장 쉬운 방법입니다. 정렬되어 있지 않은 책장이 있을 때, 모든 책을 살핀 뒤 제일 크기가 작은 책과 제일 왼쪽에 있는 책과 바꾸어 책장에 넣습니다. 그 후에 이제 나머.. 2024. 4. 15.
[자료구조] 링크드 리스트(Linked List) 목차 링크드 리스트(Linked List) 개념 Linked List는 Node라는 구조체로 이루어져 있습니다. Node는 data와 인접한 Node의 주소(address)를 저장하고 있습니다. 하나의 Array는 data만 저장하기 때문에 각 공간의 크기는 4byte였습니다. 하지만 Linked List의 경우 주소까지 저장해 야하기 때문에 하나의 공간에는 8byte의 공간이 사용됩니다. 인접한 Node의 주소를 저장하기 때문에, Array처럼 기존 고정된 크기의 연속된 메모리 공간을 할당할 필요 없습니다. 데이터가 추가되는 시점에 메모리를 할당해 주면 됩니다. 불연속적(discontinuous) 링크드 리스트 종류 Singly Linked List Doubly Linked List Singly Lin.. 2024. 4. 15.
[자료구조] 배열(Array) 목차 배열(Array) 개념 Array는 미리 할당된 크기의 메모리에 연속적으로 data를 저장하는 자료구조입니다. C언어에서 배열의 각 크기는 4byte입니다. Array는 미리 할당된 크기에 data를 저장하는 한계점이 존재합니다. → 이는 Dynamic Array를 통해 보완가능합니다. 만약 미리 할당된 크기를 넘어설 경우, 더 큰 Array를 선언하고 그 Array에 기존 데이터를 옮겨 담습니다. 더 큰 Array의 size는 일반적으로 기존 Array size의 2배를 할당합니다. (doubling 방법) 데이터를 옮겨 담을 때는 O(n) 시간이 걸립니다. 즉, 기본적으로 제일 뒤에 데이터를 추가할 때는 O(1)이지만, 만약 기존 크기를 넘어서는 순간 제일 뒤에 데이터를 추가하게 되면 새로운 A.. 2024. 4. 15.

티스토리툴바