목록전체 글 (127)
JB의 이모저모
https://www.acmicpc.net/problem/2307문제그림 1은 어떤 도시의 주요 지점과 그 지점들 간의 이동시간을 나타낸 그래프이다. 그래프의 노드는 주요 지점을 나타내고 두 지점을 연결한 도로(에지)에 표시된 수는 그 도로로 이동할 때 걸리는 분 단위의 시간을 나타낸다. 두 지점 a와 b를 연결하는 도로는 도로(a,b)로 표시한다.그림 1예를 들어 도로(1,2)와 도로(2,3)를 통하여 지점1에서 지점3으로 갈 때 걸리는 시간은 3분이다. 도로는 모두 양방향이라고 가정하므로 도로(a,b)와 도로(b,a)를 지날 때 걸리는 시간은 항상 같다고 한다.어떤 범죄용의자가 입력 데이터에 표시된 도시로 진입하여 이 도시를 가장 빠른 시간 내에 빠져나가고자 한다. 그런데 이 사실을 알고 있는 경찰이..
자료구조(Data Structure)자료 구조란 데이터를 저장하고 구성하는데 사용되는 저장컴퓨터에서 데이터를 효과적으로 사용할 수 있도록 구성하는 특정 방식. 아이디어는 다양한 작업의 공간 및 시간 복잡도를 줄이는 것이다. 자료 구조의 분류 선형 데이터 구조 데이터 요소가 순차적으로 또는 선형적으로 배열되고, 각 요소가 이전 및 인접 요소에 연결된 데이터 구조를 선형 데이터 구조라고 한다배열(Array)연결 리스트 (Linked List)큐 (Queue)스택(Stack)비선형 데이터 구조데이터 요소가 순차적으로 또는 선형적으로 배치되지 않은 데이터 구조를 비선형 데이터 구조라고 합니다. 비선형 데이터 구조에서는 단일 실행으로 모든 요소를 순회할 수 없습니다. 트리(Tree)
트리(Tree)노드(node)와 간선(edge)로 연결되어 있고 비선형 자료구조 트리의 용어노드 (node)트리를 구성하고 있는 기본 요소노드에는 키 또는 값과 하위 노드에 대한 포인터를 가지고 있음간선 (edge)트리를 구성하기 위해 노드와 노드 사이를 연결하는 선루트노드 (Root Node)트리 구조에서 최상위에 있는 노드단말 노드(Leaf Node)하위에 다른 노드가 연결되어 있지 않은 노드내부 노드 ( Internal Node)단말 노드를 제외한 모든 노드, 루프 노드도 포함부모노드 (Parent Node)자식 노드를 가진 노드I,J의 부모노드는 D 이다자식노드 (Child Node)부모 노드의 하위 노드노드 D의 자식 노드는 I,J형제 (Sibling)같은 부모 노드를 가지는 노드깊이 (Dept..
스택 (Stack)LIFO(Last In First Out) 원칙을 따르는 선형 데이터 구조가장 마지막에 삽입된 요소가 가장 먼저 꺼내진다. 스택의 장점단순성 : 간단하고 이해하기 쉬운 데이터 구조효율성 : 스택에 대한 푸시 및 팝 작업은 O(1) 시간 복잡도를 가지므로 데이터에 효율적으로 접근 가능제한된 메모리 사용 : 푸시된 요소만 저장하면 되므로 다른 데이터 구조에 비해 메모리 효율성이 높다 스택의 단점제한된 접근 : 스택은 맨 위에서만 접근할 수 있으므로 스택의 중간의 요소를 검색하거나 수정하는 것이 어렵다오버플로우 가능성 : 스택에 수용 가능한 것보다 더 많은 요소가 추가되면 오버플로우 오류가 발생하여 데이터 손실이 발생한다제한된 용량: 스택은 고정된 용량을 가지므로, 저장해야 할 요소의 수가 ..