| 자료구조 & 알고리즘
-
💡 [자료구조] Heap이란?| 자료구조 & 알고리즘/자료구조 2021. 10. 26. 09:21
💡 힙(Heap)이란? 정식명은 Heap tree, 여러 개의 값 중에서 가장 크거나 작은 값을 빠르게 찾기 위해 만든 이진 트리에요 삽입/삭제의 속도 때문에 완전 이진 트리로 나타내며, 대개 배열로 표현하는데 계산을 편하게 하기 위해 인덱스는 1부터 사용해요 두 종류, 최대 힙(부모 노드가 항상 자식들보다 큰 힙)과 최소 힙(부모가 항상 자식들보다 작은 힙)으로 나뉘어요 최댓값(최솟값)을 O(1)안에 찾을 수 있어요 데이터의 삽입/삭제는 O(logN)이 소요돼요 데이터의 삽입은 다음 프로세스로 이루어져요 가장 끝의 자리에 노드 삽입 그 노드와 부모 노드를 비교하여 규칙(최대/최소)에 맞으면 보존, 아니면 교환 규칙에 맞을 때까지 2번 과정 반복 데이터의 삭제는 루트 노드만 가능하며, 다음 프로세스로 이..
-
💡 [자료구조] Array vs. LinkedList| 자료구조 & 알고리즘/자료구조 2021. 10. 26. 09:16
Array(배열) 데이터 접근에 유리. 데이터 size가 정해져 있을 때 유리. 정적인 자료구조로, 컴파일 타임에 크기가 결정된다. 인덱스를 통해 데이터에 빠른 접근이 가능하다. O(1) 데이터의 삽입/제거 시 O(N) 사용할 자료의 사이즈가 명확할 때, 데이터의 삽입/제거가 아주 빈번한 게 아니라면 LinkedList보다 효율적이다. Linked List(연결리스트) 데이터 추가/삭제에 유리. 동적인 자료구조로, 런타임에 크기가 계속해서 변한다. 인덱스를 사용하지 않기 때문에 데이터의 조회가 느리다. O(N) 트리 구조의 근간이 되는 자료구조이다. 양측 끝에 데이터의 삽입/제거 시 O(1), 중간 삽입/제거 시 O(N). 이 경우에도 Array보다 빠르다. 논리 구조상 Linked List가 Array..
-
💡 [알고리즘] 거품정렬, 선택정렬, 삽입정렬| 자료구조 & 알고리즘/알고리즘 2021. 10. 26. 09:06
Bubble Sort (거품 정렬) 서로 인접한 두 원소의 대소를 비교하고, 조건에 맞지 않다면 자리를 교환하며 정렬하는 알고리즘 첫번째 라운드가 끝나면 가장 큰 데이터가 맨뒤 N번째에 있게 되어서 2회차는 N-1번째까지만 정렬하고 3회차는 N-2번째까지 정렬하는 식으로 정렬해요 총 라운드는 (배열 크기-1) 번 진행되고, 각 라운드별 비교 횟수는 (배열 크기-라운드 횟수)이에요 시간 복잡도 : 최선, 평균, 최악 모두 O(N^2) 공간 복잡도 : 주어진 배열 안에서 교환(swap)을 통해 정렬이 수행되므로 O(n) 장점 추가적인 메모리 소비가 적어요 구현이 매우 쉬워요 안정 정렬, 제자리 정렬이에요 단점 다른 정렬 알고리즘에 비해 교환 과정이 많은 비효율적 알고리즘이에요 Selection Sort (선..
-
[자료구조] 메모리 구조와 동적 할당 - 프로그래밍 언어별로 어떻게 다를까? - C/C++/Java/Python| 자료구조 & 알고리즘/자료구조 2021. 6. 16. 11:28
프로세스 메모리 구조 먼저 메모리 구조를 살펴볼 필요가 있겠습니다. 기본적인 메모리 구조는 컴퓨터 과학의 영역이기 때문에 프로그래밍 언어별로 다르지 않고 모두 이 구조를 따릅니다. 다만 가상머신을 경유하는 언어들의 경우 가상머신에서 이 구조를 다르게 구분하여 사용하는 경우는 있습니다. 이는 아래에서 다루겠습니다. 프로그램이 프로세스되면 크게 코드 영역(text)과 데이터 영역(data + bss)으로 나뉩니다. [1] 코드 영역 코드 영역은 말 그대로 수행될 명령어가 자리잡는 곳으로, 프로세스가 실행할 코드와 매크로 상수가 기계어의 형태로 저장된 공간입니다. 컴파일 타임(Compile Time)에 결정되고 중간에 코드를 바꿀 수 없게 READ-ONLY로 지정되어 있습니다. [2] 데이터 영역 데이터 영역..