TIL 26: [자료구조/알고리즘] 자료구조 기초

TIL 26: [자료구조/알고리즘] 자료구조 기초

오늘은 자료구조 기초에 대해 학습했습니다. 지난 디너클럽에서 컴공이신 분이 미리 자료구조 스터디를 구하셨다는 말씀을 듣고 자료구조 파트가 많이 어려운가보다 생각했었습니다. 역시나. 어렵고. 중요한. 파트인 것 같습니다...!

자료구조

정의

여러 데이터들의 묶음을 저장하고 효율적으로 다룰 수 있는 방법을 정의합니다.

데이터는 존재만으로 정보를 가지기는 어렵습니다. 따라서 데이터를 분석, 정리, 활용 등을 해야 제대로 활용할 수 있습니다.

종류

스택 (Stack)

Stack은 쌓다라는 뜻을 가지고 있습니다. 책, 동전, 접시 등을 쌓아올리면 맨막지막에 올린 것이 가장 먼저 빠져 나오게 됩니다. 이러한 특징을 가지고 있는 자료구조를 Stack이라고 합니다. 따라서 자료구조 Stack의 특징으로는 입출력이 하나의 방향으로 이루어지는 제한적 접근이 있습니다. 이런 특징을 LIFO/FILO 라고 부릅니다.

브라우저의 뒤로가기, 앞으로 가기 기능 구현이 자료구조 Stack의 예시가 됩니다.

큐 (Queue)

Queue는 줄을 서서 기다리다라는 뜻을 가지고 있습니다. 놀이동산에 대기줄을 보면 제일 먼저 선 사람이 제일 먼저 입장하고, 제일 마지막에 선 사람이 제일 마지막에 입장합니다. 이는 자료구조 Stack과 반대의 특징을 가지고 있습니다. 따라서 FIFO/LILO의 특징을 가지고 있다고도 말합니다.

동영상 스트리밍 앱을 통해 동영상을 시청할 때 다운로드 된 데이터(회색 바까지의 데이터)가 영상을 재생하기에 충분하지 않은 경우가 있습니다. 이 때 동영상을 제대로 재생하기 위해 Queue에 모아 두었다가 동영상을 재생하기에 충분한 양의 데이터가 모였을 때 동영상을 재생합니다.

그래프 (Graph)

그래프는 우리가 보통 생각하는 x, y축이 있는 그래프가 아니라 여러개의 점들이 복잡하게 연결되어 있는 관계를 표현한 자료구조입니다. 핵심용어는 정점(vertex)와 간선(edge)입니다. 정점과 연결되어있는 특징을 이용해서 검색엔진, SNS에서 사람들과의 관계, 네비게이션 등에서 사용된다고 합니다.

그래프는 간선의 연결정도 표현 여부에 따라 비가중치 그래프와 가중치 그래프로 나뉘어 집니다.

이외의 용어들: 무방향 그래프 (undirected graph), 단방향 그래프 (directed graph), 진입차수 (in-degree), 진출차수 (out-degree), 인접(adjacency), 자가루프(self loop), 사이클(cycle)

유튜브에서 봤는데 단방향 그래프의 예시로 트리가 포함된다고 합니다. 화살표로 방향을 표시하지 않는 이유는 당연히 부모노드에서 자식노드, 위에서 아래로 향하기 때문에 표시하지 않는다고 하네요!

인접과 관련해서 행렬과 리스트를 살펴볼 수 있는데요.

인접행렬은 서로 다른 정점들이 인접한 상태인지를 표시한 행렬으로 2차원 배열의 형태로 나타냅니다. 인접하면 1, 인접하지 않으면 0으로 표현합니다. 따라서 두 정점 사이의 관계를 확인하기 편하고, 가장 빠른 경로를 찾고자 할 때 유용합니다.

인접리스트는 각 정점이 어떤 정점과 인접한지를 리스트 형태로 표현한 것을 말합니다. 인접리스트는 인정행렬에 비해 메모리를 효율적으로 사용할 수 있다는 장점이 있습니다.

트리 (Tree)

트리는 Tree UI에서 정리했기 때문에 용어정도만 언급하고 넘어가겠습니다.

깊이, 레벨, 높이, 서브트리

이진 탐색 트리 (Binary Search Tree)

이진 트리는 자식 노드가 최대 두 개인 노드들로 구성된 트리입니다. 그리고 이진 트리에는 정 이진 트리(Full binary tree), 포화 이진 트리 (Complete binary tree), 완전 이진 트리(Perfect binary tree)로 나뉘어집니다.

정 이진 트리: 각 노드가 0개 혹은 2개의 자식 노드를 갖는 트리

포화 이진 트리: 정 이진 트리이면서 완전 이진 트리. 모든 레벨이 가득 채워져있는 트리

완전 이진 트리: 마지막 레벨을 제외한 모든 노드가 가득 차있는 트리. 단, 전부 차 있지 않아도 되지만 왼쪽이 채워져야 합니다.

이러한 이진 트리를 이용해서 이진 탐색 트리는 모든 왼쪽 자식의 값이 루트나 부모보다 작고, 모든 오른쪽 자식의 값이 루트나 부모보다 큰값을 가지는 특징이 있습니다.

Toy Problem 3

이 문제는 시간 내에 못풀었습니다... VS Code에서는 실행이 되는데 코플릿 환경에서는 실행시간 초과로 나오더라구요.. 처음에는 for문, 다음은 이진탐색법, 그 다음은 memoization 활용해서 풀었는데 잘 안됐습니다ㅠ

근데 레퍼런스 보니깐 나름 데이터 저장해서 푸는 형식이고 거의 제 마지막 풀이랑 비슷한 거 같은데 왜 안되는 것인가 계속 고민했습니다. 알고보니 마지막 return true 위치가 잘못 놓여져있더군요..허허 앞으로는 마지막까지 정신 단디 차리고 코드 짜야겠어요!

from http://high-developer.tistory.com/36 by ccl(A) rewrite - 2021-08-27 01:26:32