분류 전체보기76 깊이 우선 탐색(dfs) dfs 대해 알아보기 전에 그래프에 대한 기초가 필요하다. https://hongcode.tistory.com/32https://hongcode.tistory.com/32를 참고 하자. 깊이 우선 탐색(dfs) DFS(Depth First Search) 이름 뜻 그대로 루트 노드나 임의의 노드에서 시작하여 최대로 진입할 수 있는 깊이까지 탐색하고 다시 돌아와 다른 노드로 같은 방식으로 탐색하는 방법을 말한다. 장점 최선의 경우, 가장 빠른 알고리즘이다. 운이 좋게 항상 해에 도달하는 올바를 경로를 선택하다면, dfs가 최소 실행시간에 해를 찾는다. bfs에 비해 저장공간의 필요성이 적다. 백트레킹을 해야 하는 노드들만 저장해주면 된다. 단점 찾은 해가 최적이 아닐 가능성이 있다.(알고리즘은 항상 최악의경.. 2022. 3. 11. 그래프(Graph) 현실 세계의 사물이나 추상적인 개념 간의 연결관계를 표현한 것 일반적이고 강력한 자료구조 정점(Node or Vertex)과 간선(Edge or Branch)으로 구성 G=(V, E)로 표현 가능 , V: 정점 집합 / E: 간선 집합 주요 용어 정리 경로 Path 끝과 끝이 서로 연결된 간선들을 순서대로 나열한 것 단순 경로: 경로 중 한 정점을 최대 한 번만 지나는 경로 의미(일반적) ex) A --> E로 가는 경로 A --> B --> E A --> B --> C --> E A --> B --> D --> E 사이클 cycle 시작한 점에서 끝나는 경로 a.k.a. ‘회로’ 단순 사이클: 같은 정점을 두 번 이상 방문하지 않는 사이클 (일반적 / 시작점 제외) ex) 단순 사이클 A --> B -.. 2022. 3. 11. 벡터(Vector) Vector는 동적 배열 구조를 구현한 것으로 맨 끝에서만 삽입 삭제가 일어나는 구조이다. 동적으로 크기가 변하고 메모리가 연속적이기 때문에 자동으로 배열의 크기를 조절할 수 있고 유연하게 객체의 추가 및 삭제가 가능하다는 일반 배열과의 차이점을 보여준다. 어떻게 사용하는가? #include // vector를 포함하고 있는 헤더파일 vectorv; // vector의 크기를 정하지 않았을 경우 선언법(다른 자료형도 가능) vectorv(10); // vector의 크기를 정한 경우 선언법 ex)크기 10 vectorv(10,1); // 크기를 10으로 정하고 데이터를 전부 1로 초기화하는 경우 선언법 v[idx]; // 벡터 v의 idx번째의 원소를 참조한다. v.front(); // 벡터 v의 첫번째.. 2022. 3. 11. 덱(Deque) 디큐 혹은 덱이라고 부르며 쉽게 설명하면 스택(Stack) + 큐(Queue)인 구조라고 생각하면 된다. 스택 + 큐 구조 (엄밀히 말하면 아님) 앞과 뒤 2방향에서 원소를 삽입하거나 삭제할수 있다. 여러 메모리 블록에 나뉘어 저장된다. 어떻게 사용하는가? #include // dequeue가 포함된 헤더파일 deque dq; // int형 덱 선언, 다른 자료형을 넣어도 됨 dq.push_front(x); // 덱에 데이터 x를 앞에서 입력한다. dq.pop_front(); // 덱의 데이터를 앞에서 삭제한다. dq.push_back(x); // 덱에 데이터 x를 뒤에서 입력한다. dq.pop_back(); // 덱의 데이터를 뒤에서 삭제한다. dq.size(); // 덱의 크기를 반환한다. dq.em.. 2022. 3. 11. 이전 1 ··· 9 10 11 12 13 14 15 ··· 19 다음
