시냅스

단일 연결 리스트 (Singly Linked List) 단일 연결 리스트는 각 노드들이 한 줄로 연결되어 있는 자료구조이다. 이름에서 말하듯이 데이터를 담고 있는 노드들이 연결되어 있는데, 노드의 포인터가 다음이나 이전의 노드와의 연결을 담당하게 된다. 연결 리스트는 늘어선 노드의 중간지점에서도 자료의 추가와 삭제가 O(1)의 시간에 가능하다는 장점을 갖는다. (다만, 오늘 구현할 것은 tail을 갖지 않는 linked list로 1번의 반복문을 거치게 된다.) 다만, 기존 링크를 해제하거나 삽입할 때에는 기존 링크의 전이나 다음 노드 관리에 대해 유의해야 한다. 또한 배열이나 트리 구조와는 달리 특정 위치의 데이터를 검색해 내는데에는 O(n)의 시간이 걸리는 단점도 갖고 있다. 특히 단일 연결 리스트는..

배열 리스트 (Array List) 배열리스트는 자료를 순서대로 저장하는 자료구조로, 논리적 순서(저장)와 물리적 순서(저장)가 동일하다. 원소의 위치 인덱스는 0부터 시작하고, 정적배열로 최대 갯수가 정해져 있고,이는 배열과 동일하다. C에서는 라이브러리로 배열리스트를 지원하지 않기 때문에, 개발자가 직접 구현해야하는 기능으로는, 리스트 생성 원소 추가 원소 추가 가능 여부 판단 원소 반환 원소 제거 리스트 초기화 리스트 삭제 를 꼽을 수 있다. 특징 저장순서가 순차적이기 때문에 Index가 곧 위치로, 탐색(O(1))에 용이하지만, 배열이 공백을 허용하지 않아 삽입이나 삭제 시에는 노드가 끊기지 않아야 하기 때문에, 삽입이 됐을 떄에는 기존 노드를 뒤로 미루거나, 삭제가 됐을 때에는 원래 노드들을 앞..

Graph - DFS 와 BFS에 쓰이는 걔... - Vertex(정점) == Node, Edge(간선) 으로 표현한다. - Node == Vertex : 위치 - Edge (간선) : 위치 간의 관계, 노드 간 연결된 선 - 인접 정점 (Adjacent Vertex) : 간선으로 직접 연결된 노드 - 참고 : - 정점의 차수 : 무방향 그래프에서 하나의 정점에 인접한 정점의 수 - 진입 차수 : 방향 그래프에서 외부에서 오는 간선의 수 - 진출 차수 : 방향 그래프에서 외부로 향하는 간선의 수 - 경로 길이 : 경로를 구성하기 위해 사용된 간선의 수 - 단순 경로 : 처음 정점과 끝 정점을 제외하고 중복된 정점이 없느 ㄴ경로 - 사이클 : 단순 경로의 시작 정점과 종료 정점이 동일한 경우 - 방향이 없..