화요밍의 개발로그

맵 Map 자료구조란? 저장된 데이터가 키 key와 값 value로 하나의 쌍을 이루는 자료구조를 말합니다. 키가 존재하지 않는 값은 저장할 수 없으며, 모든 키는 중복되지 않습니다. 키를 통해 값을 바로 구할 수 있으므로 데이터를 검색하는데 O(1)의 시간복잡도가 소요됩니다. 배열을 기반으로 하는 Map 배열을 기반으로 맵을 구현하면 index 값으로 데이터를 저장 및 검색이 가능하므로 O(1)이 소요됩니다. 그러나 배열은 컴파일 이전에 크기를 정해줘야 하므로 배열 사이즈를 넘어가는 key 값은 사용할 수 없는 문제가 있습니다. 즉, key값의 범위가 배열 사이즈를 초과하는 경우 수용할 수 없습니다. 이러한 문제를 해결하기 위해 나온 자료구조가 해쉬 테이블 Hash Table입니다. 해시 테이블 Has..

그래프 Graph란? 간선 Edge과 정점 Vertex으로 이루어진 자료구조이며, 정점 간의 관계를 표현하는 조직도입니다. 정점에는 데이터가 저장되며, 간선을 통해 정점과 정점 사이의 관계를 알 수 있습니다. 그래프 용어 정점(Vertex, 노드 Node): 데이터가 저장됨 간선(Edge, 링크 Link): 정점들을 연결하는 선, 정점과 정점 사이의 관계를 표현 인접 정점(Adjacent Vertex): 간선에 의해 연결된 정점(6과 4는 서로 인접 정점임) 차수(Degree): 무방향 그래프에서 각 정점에 연결된 Edge의 개수(5의 차수는 3) 진출 차수(Out-degree): 방향 그래프에서 각 정점으로부터 나가는 간선의 개수 진입 차수(In-degree): 방향 그래프에서 각 정점으로 들어오는 간..

트리 Tree란? 계층적 관계(Hierarchical Relationship), 부모-자식 관계를 표현하는 비선형 자료구조입니다. 트리는 사이클이 없고, 서로 다른 두 노드를 잇는 길이 하나인 그래프의 일종입니다. 컴퓨터의 Directory 구조, 조직도, 족보 등이 트리의 대표적인 예입니다. 트리 구성요소 노드 Node: 트리를 구성하고 있는 각각의 요소 간선 Edge: 트리를 구성하기 위해 노드와 노드를 연결하는 선, 노드가 N개이면 간선은 N-1개를 가짐 루트 노드 Root Node: 트리 구조에서 최상위에 있는 노드 단말 노드 Terminal Node(외부 노드 External Node, Leaf Node): 자식 노드가 없는 노드 내부 노드 Internal Node(비단말 노드): 하나 이상의 ..

스택 Stack 나중에 들어간 원소가 먼저 나오는 후입선출, Last In First Out(LIFO)의 선형 자료구조입니다. 접시처럼 차곡차곡 쌓이는 구조로 데이터를 삽입하면 Top에 위치하며, Pop 연산을 할 때 Top에 위치한 데이터가 빠져 나옵니다. 데이터의 삽입/삭제는 O(1)의 시간복잡도가 소요됩니다. 스택의 활용 웹 브라우저 방문기록(뒤로가기): 가장 나중에 열린 페이지부터 다시 보여줌 연산자 후위 표기법 계산 수식의 괄호 검사: 연산자 우선순위 표현을 위한 괄호 검사 프로그램에서의 시스템 스택 실행 취소(Undo): 가장 나중에 실행된 것부터 실행을 취소함 역순 문자열 만들기: 가장 나중에 입력된 문자부터 출력 안드로이드의 액티비티: 사용자의 동작으로 인해 새로운 화면이 띄워지면 Push..

리스트란? 추상적 자료형으로 순서를 가지고 일렬로 항목들을 나열한 구조를 말합니다. 데이터가 순차적으로 저장되어 한 줄로 연결된 형태를 띄기 때문에 선형 구조라고 합니다. 중복된 데이터의 저장이 가능합니다. 리스트는 구현 방법에 따라 배열을 기반으로 구현된 순차 리스트와 메모리의 동적 할당을 기반으로 구현된 연결 리스트로 나뉩니다. 또한, 연결 리스트는 연결 방식에 따라 단일 연결 리스트, 원형 연결 리스트, 이중 연결 리스트로 구현할 수 있습니다. 리스트와 집합 집합은 특정한 값들을 저장하는 추상 자료형입니다. 하지만 집합에서는 데이터들의 순서가 존재하지 않고 중복되지 않는다는 점에서 리스트와 다릅니다. 리스트와 배열 어떻게 보면 배열을 리스트의 일종이라고 할 수 있지만, 배열과 리스트는 다릅니다. 먼..

자료구조란? - 데이터를 표현하고 저장하는 방법이다. 자료구조는 컴퓨터에서 자료를 효율적으로 관리하고 구조화시키는 방법으로 한 마디로 말하자면 '데이터의 표현 및 저장 방법'이라고 할 수 있다. 자료구조는 정수, 실수, 문자, 문자열과 같은 단순구조 뿐만 아니라 리스트, 스택, 큐와 같은 선형구조, 트리, 그래프와 같은 비선형 구조, 순차파일,색인파일, 직접파일과 같은 파일 구조로 크게 분류된다. 따라서 int형 변수도 데이터를 표현하고 저장하는 하나의 방법이므로 넓은 의미에서 자료구조에 속한다고 볼 수 있다. 자료구조와 알고리즘 자료구조와 알고리즘은 연관성이 높다. 각각의 과목을 공부하기 위해 도서관에 가서 책을 고르면서 보니, 두 내용을 한 번에 다루는 책이 많았다. 알고리즘 책에서 자료구조에 대한 ..