투투

이번에는 트리를 Python으로 표현하는 것과 순회하는 방법에 대해 알아보도록 한다. 트리의 표현 Python 리스트를 통해 아래의 트리를 표현해보려고 한다. 아래의 코드를 보면 2차원 리스트를 생성한 것을 알 수 있는데 -1은 비어있음을 의미하고 각각 왼쪽 자식 노드와 오른쪽 자식 노드를 의미한다. N = 6 tree = [[-1, -1] for _ in range(N)] 이제 각각의 노드에 왼쪽 자식 노드와 오른쪽 자식 노드를 입력받는다. 비어있을 때는 -1을 입력하도록 하였다. 각각 입력받은 것을 해당 노드의 0번 인덱스(왼쪽 자식 노드)와 1번 인덱스(오른쪽 자식 노드)에 저장한다. for i in range(N): left, right = map(int, input().split()) tree[..

트리는 계층적 구조를 표현하는데 적합한 자료구조이다. 또한 트리로 표현한 후에 데이터들을 탐색했을 때 효율적인 문제들이 존재한다. 따라서 이번에는 트리의 기본적인 구조를 알아보도록 한다. 트리의 기본 [그림 1]은 트리를 나타낸 것이다. 트리는 노드들이 간선으로 연결되어 있으며 마치 나무를 뒤집어 놓은 듯한 느낌을 받을 수 있다. 트리는 그래프의 한 종류라고 할 수 있다. 하지만 그래프와 달리 순환되는 구조를 갖고있지 않다. 왜냐하면 트리는 N개의 노드와 N-1개의 간선으로 이루어져 있기 때문에 하나의 노드를 시작으로 탐색을 진행했을 때 다시 처음 위치로 돌아오지 못한다. 트리를 구성하는 용어들 트리의 구조를 파악하는 사용되는 용어들이 존재한다. 루트 노드 : 노드 A처럼 트리에서 최상위에 존재하는 노드..

스택 스택은 후입선출(Last In First Out)의 구조를 갖고있다. 따라서 가장 늦게 들어온 데이터가 가장 먼저 반출된다. 이는 상자를 아래에서 위로 하나씩 쌓아올리는 것으로 생각할 수 있다. 상자를 쌓아올린 뒤에 상자를 다른 곳에 옮길 때 중간이나 처음이 아닌 가장 위에있는 상자를 먼저 들어서 옮기는 것이 효율적이다. 큐 큐는 선입선출(First In First Out)의 구조를 갖고있다. 따라서 가장 먼저 들어온 데이터가 가장 먼저 반출된다. 이것은 식당에 손님들이 줄을 서는 것을 생각해보면 알 수 있다. 손님들이 식당 앞에 줄을 선 후에 입장할 때는 가장 먼저 온 손님 즉, 가장 앞에 있는 손님들이 먼저 식당에 입장한다. 스택과 큐는 어려운 개념이 아니다. 하지만 이러한 성질을 이해했을 때 ..

Array와 Linked List가 무엇인지 안다면 그 차이는 쉽게 알 수 있을 것이다. Array 배열은 특정 크기만큼 연속된 메모리 공간에 데이터를 저장하는 자료구조이다. 만약 int형 데이터 3개를 저장할 수 있는 배열을 생각해보자. 그렇다면 아래의 그림처럼 연속된 공간에 메모리를 확보하여 데이터를 이곳에 저장할 수 있게 된다. 위의 그림에서 볼 수 있듯이 연속된 공간에 데이터들이 나열되어 있기 때문에 처음 주소만 알면 다른 위치도 쉽게 알 수 있을 것이다. 따라서 배열은 랜덤으로 접근하는 것이 가능하다. 그렇다면 어떻게 랜덤으로 접근하는 것이 가능할까? C언어로 예를 들어보면 배열을 선언했을 때 배열의 주소는 배열에 저장되어 있는 첫 번째 원소의 주소와 같다. 이때 4번째 데이터를 조회한다고 하면..

오늘은 Hash Table라는 자료구조에서 충돌이 발생하는 이유와 충돌이 발생하지 않도록 하기 위해서는 어떻게 해야 하는지 알아본다. 먼저 Hash Table은 저장되는 데이터가 (key, value)처럼 하나의 쌍을 이루는 자료구조를 말한다. 이때 key가 존재하지 않는 value는 저장할 수 없으며 key가 중복되어서는 안 된다. 해쉬 함수 학생들의 정보를 Hash Table에 저장하려고 한다. 이때 학생들의 학번을 key로 하는데, 학번이 2020103과 같은 형태로 되어있어서 배열의 크기를 이에 맞춰서 선언해야하며 배열을 생성하더라도 쓰지 않는 공간이 많기 때문에 효율적이지 못하다. 따라서 학번을 해쉬 함수로 전달하여 반환된 값을 key로 설정하려고 한다. 해쉬 함수는 다음과 같다. 학번을 입력하..