오늘은 뭐 할까?

트리Degree : 자식 노드의 개수Size : 자기 자신을 포함한 모든 자식 노드의 개수High : 현재 위치부터 Leaf까지의 거리Depth : 루트에서부터 현재 노드까지의 거리트리는 루트에서부터 시작하며 루트는 자식을 가지고 자식은 부모와 Edge(간선)으로 연결되어 있다. 트리는 그래프와 비슷하게 보이기 때문에 트리 = 그래프라는 의문점이 생길수도 있지만그래프와는 아주 큰 자이점이 있는데, 바로 트리는 항상 단방향이기 때문에 순환구조를 가질 수 없다얼핏 보면 DAG도 순환하지 않기 때문에 이것은 그래프가 아니라 트리라고 봐야하지 않을까라는 생각이 들수도 있는데트리의 경우 그래프와는 다르게 단 하나의 부모노드를 가진다는 특성을 가지고 있기 때문에 DAG를 트리라고 생각하는 것은 잘못된 것이라 할 수..

연결 리스트 (Linked List)데이터가 연속된 공간에 저장되어 있지 않고, 떨어져 있더라도 연속된 공간에 저장되어 있도록 하는 리스트동적으로 새로운 노드를 삽입하거나 삭제하기 간편하다연결구조를 통해 물리 메모리를 연속적으로 사용하지 않아도 된다데이터를 구조체로 묶어 포인터로 연결되어 있다배열과 달리 인덱스에 접근하기 위해서는 전체를 순서대로 읽어야 한다연결 리스트 핵심요소Node : 연결 리스트의 기본 단위데이터 필드 : 노드에 저장된 데이터링크 필드 : 다음 노드를 가르킨다Head : 연결 리스트에서 가장 처음 위치하는 노드, 리스트 전체를 참조하는데 사용Tail : 연결 리스트에서 가장 마지막에 위치하는 노드, Tail 노드의 링크 필드는 Null을 저장하고 있다 연결 리스트 구현 (Python..

배열을 하나로 분리해서 다시 합치면서 정렬하는 알고리즘시간 복잡도  : $O(nlog_2n)$ 예시[6, 5, 3, 1, 8, 4, 7, 2]# 1. 배열을 반으로 나누기[6, 5, 3, 1] [8, 4, 7, 2]# 2. 배열의 개수가 하나가 될때까지 나누기[6, 5] [3, 1] [8, 4] [7, 2][6] [5] [3] [1] [8] [4] [7] [2]# 3. 두 개씩 낮은 숫자을 비교하여 정리하면서 합치기[5, 6] [1, 3] [4, 8] [2, 7][1, 3, 5, 6] [2, 4, 7, 8][1, 2, 3, 4, 5, 6, 7, 8]  코드 구현def mgsort(arr): if len(arr)

지정된 값(Pivot)을 기준으로 지정된 값 보다 작은 값과 큰 값으로 나누어 정렬하는 알고리즘분할 (Divide) : pivot을 중심으로 정렬할 자료를 2개의 부분집합으로 나눔정복 (Conquer) : 부분집합의 원소 중 pivot보다 큰 값과 작은 값으로 나눔부분집합이 더 이상 나누어질 수 없을 때까지 분할과 정복을 반복 수행시간 복잡도 : 평균 수행 시간 복잡도 $O(log_2n)$, 최악의 수행 시간 복잡도 $O(n^2)$코드 구현def qsort(arr): if len(arr) == 0: return [] pivot = arr[0] equl = [pivot] high = [] low = [] for i in range(1, len(arr)): ..

1. 컴퓨터 구조 컴퓨터의 구조는 그림에서 보는 바와 같이 구성되어 있다. 하드웨어에 대해서는 보통 어떤 것인지 잘 알고 있기 때문에 이번 글에서는 건너띄고 지금 이 글을 작성하는 도중에도 잘 사용하고 있지만.. 누군가가 물어봤을 때 '그 왜 윈도우에서 프로그램 그거!!'라고 밖에 대답이 나오지 않는 소프트웨어에 대해 자세히 알아보고자 한다 먼저 소프트웨어는 위와 같이 사용자 프로그램과 운영체제로 나뉘어져 있으며 사용자 프로그램은 어제도 플레이 했었던 롤, 구글 크롬 등 컴퓨터를 이용하는 말 그대로 사용자가 직접 사용할 수 있는 프로그램을 말하고 운영체제는 윈도우, 리눅스, Mac과 같이 롤과 구글 크롬이 잘 작동할 수 있는 그런 환경을 만들어주는 프로그램이며 앞선 사용자 프로그램과는 달리 사용자가 직접..

1. 배열컴퓨터가 데이터를 기억하는 방식을 알기 위해 필요합니다 예를 들어 'HELLO'라는 단어를 컴퓨터는DATAHELLOINDEX01234HELLO의 단어를 하나씩 INDEX 주소를 할당해서 기억하게 되는데  파이썬에서 HELLO의 O를 찾기 위해서는a = "HELLO"a[4]라고 했을 때 O라는 값을 불러올 수 있게 됩니다 이를 통해 배열은 데이터를 빠르게 접근할 수 있는 장점을 가지게 됩니다 하지만 배열은 데이터를 변경(추가, 삭제)할 때 쉽지가 않다는 단점을 가지는데, 예를 들어 HELLO에 MY라는 단어를 추가해서 데이터를 만들고자 할 때 초기의 배열은 HELLO에 맞춰 5칸만 할당되어 있기 때문에 7칸이 필요한 HELLOMY라는 데이터는 만들 수 없게 됩니다 따라서 새로운 배열을 생성해서 H..