티스토리

훈이의 개발일기

검색하기

블로그 홈

훈이의 개발일기

chaehun97.tistory.com/m

천천히, 하나씩

구독자: 2

방명록 방문하기

주요 글 목록

[자료구조] - 트리(Tree) 트리란?트리는 계층적 구조를 가지는 자료구조로, 노드(Node)와 그 사이의 연결인 엣지(Edge)로 구성된다.부모-자식 관계를 통해 노드들이 계층적으로 연결된 형태를 가진다.트리는 일반적으로 계층적 데이터를 표현, 검색, 정렬과 같은 문제를 해결하는 데 사용된다. 트리의 기본 구성 요소노드(Node) : 트리의 기본 단위, 데이터와 자식 노드에 대한 정보를 담고 있다.(Root, Parant, Child, Leaf 등에 해당된다.)엣지(Edge) : 트리의 각 노드가 부모와 자식 노드를 연결하는 선이다.부모(Parent) : 자식을 가진 노드이다.자식(Chlid) : 부모 노드로부터 연결된 노드이다.서브트리(Subtree) : 트리의 한 노드와 그 노드의 자식들로 구성된 트리이다.리프(Leaf) : 자.. 공감수 1 댓글수 0 2025. 3. 14.
[자료구조] - 연결 리스트(Linked List)[1] 연결리스트(Linked List)란 연결리스트(Liked List)는 데이터 요소들을 순차적으로 저장하는 선형 자료구조이다. 각 요소는 데이터와 다음 요소를 가리키는 포인터로 이루어져 있다. 따라서 연결 리스트는 메모리에서 연속적으로 할당되지 않는 노드들이 포인터를 통해 연결되어 있는 형태를 가지고 있다. 핵심 특징 동적할당 요소를 추가하거나 삭제할 때마다 필요한 만큼의 메모리를 동적으로 할당하므로, 크기가 동적으로 조절될 수 있다. 삽입 및 삭제 용이성 요소의 삽입 및 삭제가 쉽다. 요소를 삽입할 때는 새로운 요소를 추가하고, 삭제할 때는 해당 요소를 연결에서 제거하면 된다. 메모리의 효율성 연결 리스트는 데이터 요소들이 메모리에서 연속적으로 배치되지 않기 때문에, 데이터 요소들 간의 간격이 듀오적으로.. 공감수 0 댓글수 0 2024. 3. 20.
배열 (Array) 배열의 특징 배열은 연속된 메모리 공간에 순차적으로 저장된 데이터 모음이다. 프로그래밍 언어에서 동일 데이터 타입을 저장 하며, 다른 타입의 요소를 저장할 수 없다. 배열을 구성하는 각각의 값을 요소(element), 배열에서 위치를 가리키는 숫자를 인덱스(index)라고 한다. 배열의 시간 복잡도 Operation average case worst case 읽기(read) O(1) O(1) 삽입(insert) O(n) O(n) 삭제(delete) O(n) O(n) 탐색(search) O(n) O(n) 시간 복잡도의 특징은 항상 최악의 상황을 고려한다. 읽기의 시간복잡도는 특정 인덱스로 바로 접근이 가능하기 때문에 O(1)이다. 삽입의 시간 복잡도는 원하는 인덱스에 삽입, 그 이후의 인덱스는 오른쪽 한칸.. 공감수 0 댓글수 1 2023. 12. 22.
스택(Stack)과 큐(Queue) 스택(Stack)과 큐(Queue) 스택과 큐는 제약을 갖는 배열이다. 제약하는 데이터 구조를 사용하면 잠재적 버그를 막을 수 있으며 문제를 해결하는 새로운 사고방식을 제공한다. 또한, 제약을 제대로 이해해서 작성한 코드는 다른 개발자에게 익숙하고 명쾌하게 읽힌다. 그 알고리즘이 그러한 제약을 가진 채로 동작함을 알게 된다. 스택(Stack) 스택 연산을 묘사하자면 (Last In, First Out) 후입선출을 뜻한다. 처음 들어간 원소가 마지막에 나온다. 스택은 다음과 같은 세 가지 제약이 있다. 데이터는 스택의 끝에만 삽입 가능 데이터는 스택의 끝에서만 삭제 가능 스택의 마지막 원소만 읽을 수 있음 또 한, 스택의 특징은 스택의 끝을 top 스택의 시작을 bottom 스택의 top에서 원소를 제거하.. 공감수 0 댓글수 0 2023. 5. 23.
해시 테이블(hash table) 해시 테이블(hash table) 대부분의 프로그래밍 언어는 해시 테이블(hash table)이라는 자료 구조를 포함한다. 빠른 읽기라는 놀랍고 엄청난 장점이 있고, 해시, 맵, 해시 맵, 딕셔너리, 연관 배열 등의 이름을 갖는다. 다음은 해시 테이블을 사용해 파이썬으로 구현한 메뉴이다. (파이썬에서는 딕셔너리라 부른다.) menu = { "one" : 1, "two" : 2, "three" : 3, "four" : 4, "five" : 5 } 쌍으로 이루어져 있으며, 첫번째 항목을 키(key)라 부르고, 두 번째 항목을 값(value)이라 부른다. 파이썬에서는 다음과 같은 문법으로 키의 값을 룩업할 수 있다. print(menu["two"]) # 2 해시 테이블의 값 룩업은 딱 한단계만 걸리므로 평균적.. 공감수 1 댓글수 1 2023. 5. 6.
삽입 정렬(insertion sort) 이전의 포스팅에서 버블 정렬과 선택 정렬을 알아보았는데, 둘 다 효율성은 O(N2)이지만 선택 정렬이 실제로는 두배 더 빠르다는 것을 알 수 있었다. 이번에는 삽입 정렬(insertion sort)을 배우면서 최악의 경우가 아닌 다른 시나리오를 분석하는 것에 중점을 두고 어떠한 장점이 있는지 알아 보겠다. 삽입 정렬의 수행 순서 삽입 정렬을 수행 할 배열은 [2, 4, 7, 1, 3] 이다. 먼저 loop1이다. 먼저 인덱스 1의 값을 확인한다. 임시로 인덱스1(값2)를 삭제한 후 temp_value 변수에 저장한다 인덱스 - 1(값4)와 비교한다. 4가 2보다 크므로 4를 오른쪽으로 쉬프트 한다. 더이상 비교할 인덱스가 없으므로 temp_value를 -1인덱스에 삽입한다. 첫번쨰 루프의 결과는 [2, .. 공감수 0 댓글수 0 2023. 5. 6.
선택 정렬(selection sort) 이전에는 효율성이 O(N2)인 데이터 정렬 알고리즘인 버블 정렬(bubble sort)을 살펴보았다. 이번에는 선택 정렬(selection sort)라는 다른 정렬 알고리즘을 알아보고 버블 정렬과 효율성을 비교해 보겠다. 선택 정렬의 루프를 알아보자. 먼저 인덱스 0에 들어 있는 값을 확인하며 시작하여 최솟값으로 지정한 후, 다음 인덱스와 비교한 다음 최솟값을 결정한다. loop1 min_Index = 0 (값 = 5) [5, 3, 2, 1, 4] 인덱스 0과 1의 비교 min_Index = 1 (값 = 3) [5, 3, 2, 1, 4] 인덱스 1과 2의 비교 min_Index = 3 (값 = 2) [5, 3, 2, 6, 4] 인덱스 2과 3의 비교 min_Index = 3 (값 = 2) [5, 3, 2.. 공감수 0 댓글수 0 2023. 4. 29.
버블 정렬(Bubble Sort) 버블 정렬은 단순 정렬(simple sort)중 하나로 알려져있으며 매우 기본적인 정렬 알고리즘이지만 더욱 빠르다고 알려진 정렬 알고리즘보다 비효율적이다. 버블 정렬 예제를 살펴보자. 먼저 [ 6, 3, 1, 2, 4, 5 ] 이라는 배열을 정렬하고 싶다고 가정하자. 1loop [ 6, 3, 1, 2, 4, 5 ] 먼저 6과 3을 비교하여 순서가 맞지 않음을 확인하고 6과 3을 교환한다. [3, 6, 1, 2, 4, 5 ] 그다음으로 6과 1을 비교하여 순서가 맞지 않음을 확인하고 6과 1을 교환한다. [3, 1, 6, 2, 4, 5 ] [3, 1, 2, 6, 4, 5 ] [3, 1, 2, 4, 6, 5 ] 1loop result = [3, 1, 2, 4, 5, 6 ] 이렇게하여 1loop가 끝난다. 2.. 공감수 2 댓글수 0 2023. 4. 29.
이진 검색(Binary Search) 이진 탐색은 정렬된 데이터에서 특정한 값을 찾고자할 때 O(logN)의 성능으로 빠르게 값을 찾을 수 있는 장점이 있다. 2023.04.20 - [Data Structures & Algorithms] - 빅오 big-O 빅오 big-O 빅오 표기법 서로 간의 시간복잡도를 쉽게 소통할 목적으로 자료구조와 알고리즘의 효율성을 간결하게 일관된 언어로 설명하기 위한 수학적 언어이다. 빅오 표기법을 이용해 주어진 알고리즘 chaehun97.tistory.com O(logN)의 설명은 이전의 글에서 간략하게 써둔 것이 있으니 참고해보자.. 부족한 설명으로 이해가 되지 않을 수 있으니.. 다른 포스팅을 보는 것이 효율적일 수도 있다. 나중에 수정할 예정이니 참고만 해보자. 아마도 코드로 구현해보면 어떤 식으로 효율적.. 공감수 1 댓글수 0 2023. 4. 28.
빅오 big-O 빅오 표기법 서로 간의 시간복잡도를 쉽게 소통할 목적으로 자료구조와 알고리즘의 효율성을 간결하게 일관된 언어로 설명하기 위한 수학적 언어이다. 빅오 표기법을 이용해 주어진 알고리즘의 효율성을 쉽게 분류하고 이해 할 수 있다. 표기 : O(N) 빅오의 실행 속 O(1) → O(log N) → O(N) → O(N log N) → O(N^2) → O(N) → O(2^N) 아랫단계에 어떤 수를 곱하든 데이터가 커지다 보면 언젠가 윗 단계가 더 느려진다. 빅오의 N단계 빅오의 표현은 괄호 안에 있다. O(1)은 가장 빠른 알고리즘으로 분류한다. 데이터가 늘어나도 단계수는 증가하지 않는다. N이 얼마든 항상 상수단계에서만 필요하다. 빅오의 본질 데이터가 늘어날때 알고리즘의 성능이 어떻게 바뀌는지가 관건이다. 데이터.. 공감수 1 댓글수 0 2023. 4. 20.
자료구조의 연산 읽기 자료구조내 특정위치를 찾아보는 것 컴퓨터는 딱 한 단계로 배열을 읽을 수 있으며, 프로그램에서 배열을 선언하면 연속된 빈 메모리 공간을 할당한다. 모든 메모리주소에 한번에 접근가능하며 배열을 할당할 때 어떤 메모리주소에서 시작하는지 기록해둔다. 배열은 기초적인 자료구조이지만 빠르게 읽을수 있는 강력한 자료구조이다. 검색 자료구조내 특정 값을 찾는 것 인덱스 제공 후 값을 반환하며 읽기에 비해 오래걸리며, 찾는 값이 가장 마지막 순서에 있다면 모든 값을 검색해야 한다. 배열에 값이 있다고 확신도 불가하다. N개로 이루어진 배열은 선형검색에 최대 N단계가 필요하다. 삽입 자료구조에 새로운 값을 추가하는 것 배열에 새 데이터를 삽입할 때 어디에 삽입하는가에 따라 효율성이 다르다. 배열에 맨끝에 삽입할때는.. 공감수 1 댓글수 0 2023. 4. 9.
스택(stack) 스택(stack) 이란? - 스택은 데이터를 일시적으로 저장하기 위해 사용하는 자료구조이다. - 입력과 출력 순서는 후입선출(LIFO, Last In First Out), 가장 나중에 넣은 데이터를 가장 먼저 꺼낸다. - 스택에 데이터를 넣는 작업을 push, 데이터를 꺼내는 작업을 pop 이라고 한다. 스택은 마치 컵에 따른 물과 같은 것 같아요. 물을 마시려고 컵에 따르면 제일 위에 물이 나오는 것 처럼요! 컵 이미지 : flaticon 공감수 1 댓글수 0 2022. 12. 13.

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.