공대생 기록장

프로그램 = 자료구조 + 알고리즘 프로그램의 자료구조와 알고리즘으로 만들어진다. 그러므로 개발자가 효율적인 프로그램을 작성하기 위해서는 자료구조란 무엇이고 어떤 종류가 있는지, 어떻게 하면 효율적인 알고리즘을 구현할 수 있을지를 고민해야 한다. 또한, 이 둘의 설명과 더불어 크고 복잡한 문제를 단순화시킬 수 있는 데이터 추상화 개념을 숙지해야 한다. 자료 구조란? 자료구조란 자료를 효율적으로 사용하기 위해 자료의 특성에 따라 분류하고 구성, 저장, 처리하는 모든 작업이다. 알고리즘이란? 알고리즘이란 특정한 일을 수행하기 위한 명령어의 유한 집합을 말한다. 기준 입력: (외부)원인 >= 1 출력: 결과 >= 1 명백성: 모호하지 않은 명확한 명령 유한성: 한정된 수의 단계 후에는 반드시 종료 유효성: 각 ..

그래프(Graph) 그래프(Graph)는 정점들이 간선들을 통해 연결된 자료 구조이다. 여러 개의 고립된 부분 그래프들(Isolated Subgraphs)로 구성될 수 있다. 1) 무방향 그래프(Undirected Graph) VS 방향 그래프(Directed Graph) 무방향 그래프는 간선으로 이어진 양쪽 정점 모두 상대편 정점으로 이동할 수 있다. 방향 그래프는 방향성이 존재하여 화살표 방향으로만 이동할 수 있다. 2) 가중치 그래프(Weighted Graph) 가중치 그래프는 간선에 가중치가 할당된 그래프로 '네트워크(Network)'라고도 한다. 3) 연결 그래프(Connected Graph) VS 비연결 그래프(Disconnected Graph) 연결 그래프는 무방향 그래프에 있는 모든 정점쌍..

※ Direct Address Table 크기가 U인 테이블에서 key를 이용하여 데이터를 저장하는 자료구조이다. 중복되는 key는 없다고 가정한다. 시간 복잡도가 O(1)로 검색, 삽입, 삭제가 매우 빠르다는 장점이 있으나, 적재율이 낮다면 실제 대부분의 메모리 공간은 낭비된다는 단점이 있다. 해시 테이블(HashTable) 해시 테이블(Hash Table)이란 해시 함수를 사용해서 변환된 값을 인덱스(index)로 삼아 key-value 쌍으로 데이터를 저장하는 자료구조로, Direct Address Table에서의 공간 낭비를 줄이고 시간 복잡도를 낮추기 위해 만들어졌다. 기본연산으로는 탐색(Search), 삽입(Insert), 삭제(Delete)가 있다. 해시 함수(Hash Function): 입..

1. 트리(Tree) 트리(Tree)는 값을 가진 노드(Node)와 노드들을 연결해주는 간선(Edge)으로 이루어진 계층적 자료구조이다. 사이클을 이루지 않으며 계층 구조를 나타낸다는 점이 그래프와의 가장 큰 차이점이다. 자식 노드는 0개 이상의 자식 노드를 가지며 트리 자료구조는 양방향 연결 리스트를 이용하여 구현한다. 트리는 비선형 자료구조이며, 계층적(Hierarchical) 자료구조라고도 불린다. 트리 자료구조는 주로 컴퓨터의 디렉터리 구조, 조직도 등에 이용된다. 깊이(depth): 루트 노드에서 어떤 노드에 도달하기 위해 거쳐야 하는 간선의 수 레벨(level): 트리의 특정 깊이를 가지는 노드의 집합 높이(height): 트리의 최대 깊이 차수(degree): 각 노드가 자식 노드와 연결된 ..

1. 스택(Stack) 스택(Stack)은 먼저 들어간 요소가 가장 나중에 나오게 되는 선입후출의 구조를 가진 선형 자료구조이다. 이러한 스택의 구조적 특징을 LIFO(Last In First Out)이라고 한다. 스택의 대표적인 연산으로는 push(), peek(), pop()이 있다. 스택을 구현하기 위해서는 배열 / 연결리스트 사용이 가능하며, 주로 배열을 통해 구현된다. 일반적인 스택은 메모리의 크기가 정적이지만, 동적 배열을 이용하여 동적 스택을 만들 수도 있다. 스택 자료구조는 주로 웹 브라우저 방문기록(뒤로가기), 후위 표기법 계산, 문자열 뒤집기, 재귀 등에 사용되며, 거의 모든 애플리케이션을 만들 때 사용된다. 2. 큐(Queue) 큐(Queue)는 먼저 들어간 요소가 가장 먼저 나오게 ..

배열(ArrayList) 배열은 쌍의 집합으로, 같은형의 변수를 여러 개 담을 수 있는 자료구조이다. 1차원 배열과 2차원 배열 등 여러 차원이 존재할 수 있다. 한 번 선언된 배열의 정적인 메모리 크기로 인한 문제를 해결하기 위해 동적 배열이 등장하였다. 동적 배열의 원리는 데이터가 추가되면서 메모리가 꽉 차면 메모리의 크기를 보통 2배를 늘려주고 데이터들을 모두 복사하는 방법으로, 이를 더블링(Doubling)이라고 한다. 특징 인덱스를 이용하므로 배열 내 요소의 탐색은 O(1)의 시간복잡도를 가진다. 배열의 데이터의 삽입과 삭제 시 데이터의 이동이 빈번하게 발생한다. 데이터의 삽입과 삭제에서의 시간복잡도는 최선의 경우 O(1), 최악의 경우 O(n)을 가진다. 고정된 크기의 저장공간이므로 할당된 크..