| 자료구조 & 알고리즘/자료구조
-
💡파이썬 큐(Queue) 이론 및 예제| 자료구조 & 알고리즘/자료구조 2023. 11. 10. 15:32
알고리즘 코딩 테스트를 준비하다 보면 다양한 자료구조를 만나게 됩니다. 그 중에서도 큐(Queue)는 스택과 함께 가장 기본적인 자료구조 중 하나입니다. 이번 글에서는 큐의 개념과 파이썬으로 구현하는 방법에 대해 알아보겠습니다. 큐(Queue)란? 알고리즘 코딩테스트에서 가장 자주 활용되는, 데이터를 저장하는 자료구조 중 하나 (BFS문제에서 자주 활용) 먼저 들어온 데이터가 먼저 나가는 선입선출(FIFO, First In First Out) 방식 입력과 출력이 각각 다른 방향에서 한쪽으로만 일어남 큐의 크기가 제한되어 있음 - 데이터의 크기만큼 크기가 결정됨. 따라서 C에서는 enQueue, deQueue 할때마다 메모리 재할당(realloc)이 필요하지만 파이썬에서는 신경 안써도 됩니다. 파이썬 메모..
-
💡파이썬 스택(Stack) 이론 및 예제| 자료구조 & 알고리즘/자료구조 2023. 11. 9. 00:36
스택(Stack)이란? 스택은 흔히 두 가지 의미로 사용됩니다. 자료구조로써의 스택, 프로세스 메모리 구조로써의 스택 메모리입니다. 본 포스트에서는 자료구조로써의 스택에 대한 내용을 다루고 있으니, 스택 메모리에 대해 궁금하신 분은 저의 이전 포스팅을 참고해주세요. (무려 2년 3개월 전 포스팅... 시간 참 빨라요) 알고리즘 코딩테스트에서 가장 자주 활용되는 자료구조 중 하나 (DFS문제에서 자주 활용) 가장 나중에 들어온 데이터를 가장 먼저 처리하는 후입선출(LIFO, Last In First Out) 방식 입출력이 한쪽에서만 일어남 스택의 크기가 제한되어 있음 - 데이터의 크기만큼 크기가 결정됨. 따라서 C에서는 push, pop 할때마다 메모리 재할당(realloc)이 필요하지만 파이썬에서는 신경..
-
💡 [자료구조] Tree에 관하여| 자료구조 & 알고리즘/자료구조 2021. 10. 26. 09:37
Tree 스택이나 큐와 같은 선형 구조가 아닌 비선형 자료구조 계층적 관계 (Hierarchical Relationship)을 표현하는 자료구조 Tree 관련 용어 Node (노드) : 트리를 구성하고 있는 각각의 요소 Edge (간선) : 트리를 구성하기 위해 노드와 노드를 연결하는 선 Root Node (루트 노드) : 트리 구조에서 최상위에 있는 노드 Leaf Node (Terminal Node, 단말 노드) : 하위에 다른 노드가 연결되어 있지 않은 노드 Internal Node (내부 노드, 비단말 노드) : 단말 노드를 제외한 모든 노드로 루트 노드도 포함 Sibling Node (Brother Node, 형제 노드) : 동일한 부모를 가지는 노드 Path (경로) : 한 노드에서 다른 한 노..
-
💡 [자료구조] Stack and Queue| 자료구조 & 알고리즘/자료구조 2021. 10. 26. 09:28
Stack 후입선출(LIFO) 자료구조 함수가 호출되면 스택 영역 메모리에 함수가 올라가요 삽입과 삭제가 한 방향에서만 일어나요 DFS에서 많이 쓰여요 (재귀적 호출) Queue 선입선출(FIFO) 자료구조 작업을 순서대로 실행시키기 위해 대기열을 구현할때 많이 사용돼요 삽입과 삭제가 양 방향 각각에서 일어나요 BFS에서 많이 쓰여요 (재귀적 호출) 다양한 형태의 Queue가 존재하는데, 특히 Deque의 경우는 삽입과 삭제가 양 방향에서 모두 일어날 수 있어요
-
💡 [자료구조] 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..
-
[자료구조] 메모리 구조와 동적 할당 - 프로그래밍 언어별로 어떻게 다를까? - C/C++/Java/Python| 자료구조 & 알고리즘/자료구조 2021. 6. 16. 11:28
프로세스 메모리 구조 먼저 메모리 구조를 살펴볼 필요가 있겠습니다. 기본적인 메모리 구조는 컴퓨터 과학의 영역이기 때문에 프로그래밍 언어별로 다르지 않고 모두 이 구조를 따릅니다. 다만 가상머신을 경유하는 언어들의 경우 가상머신에서 이 구조를 다르게 구분하여 사용하는 경우는 있습니다. 이는 아래에서 다루겠습니다. 프로그램이 프로세스되면 크게 코드 영역(text)과 데이터 영역(data + bss)으로 나뉩니다. [1] 코드 영역 코드 영역은 말 그대로 수행될 명령어가 자리잡는 곳으로, 프로세스가 실행할 코드와 매크로 상수가 기계어의 형태로 저장된 공간입니다. 컴파일 타임(Compile Time)에 결정되고 중간에 코드를 바꿀 수 없게 READ-ONLY로 지정되어 있습니다. [2] 데이터 영역 데이터 영역..