전체 글 (87) 썸네일형 리스트형 자료구조 문제 정리 (4) 그래프 [그래프의 순회 : BFS, DFS] (1)다음 그래프를 너비 우선 탐색(BFS), 깊이 우선 탐색(DFS) 방법으로 방문할 때각 정점을 방문하는 순서로 옳은 것은? *시작 정점은 A이다, 알파벳 순서대로 방문한다.너비 우선 탐색(BFS)시작정점 A와 인접한 노드 B,F를 모두 삽입해야 하므로 A B F가 큐에 삽입되고 이 순서대로 방문한다A B F C D E 순서대로 방문한다깊이 우선 탐색(DFS)시작 정점 A의 인접한 노드 중 하나만 선택하는데 알파벳 순서대로 선택하게 되면 A,B가 된다.A B C D E F 순서대로 방문한다 그래프의 깊이 우선 탐색은 스택을, 너비 우선 탐색은 큐를 이용한다. (2)다음 그래프의 정점 A에서부터 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)을 수행할 때, 방.. 자료구조 문제 정리 (3) 트리 1. 이진트리이진트리(BST) 부모를 중심으로 좌측에는 모두 부모보다 작은 데이터가 우측에는 모두 부모보다 큰 데이터가 위치한다(데이터가 위에서부터 들어와서 루트노드를 거쳐서 위치를 찾아감)https://www.youtube.com/watch?v=Smmz7MT4oxM 일반 트리와 다르게 공집합을 허용한다.각 노드는 최대 2개의 자식 노드를 갖는다.어떤 노드에서 루트 노드에 이르는 경로는 유일하다.n개의 노드를 가진 이진 트리는 n-1개의 간선을 갖는다.노드(node)가 11개 있는 트리의 간선(edge) 개수 = 10개이진트리와 일반트리의 차이점이진트리의 모든 노드는 차수가 2 이하이다.일반트리는 자식 노드의 개수에 제한이 없다.일반 트리와는 달리 이진트리는 노드를 하나도 가지고 있지 않을 수도 잇다.서.. 자료구조 문제 정리 (2) 스택, 큐 1. 스택(1)자료의 삽입과 삭제가 포인터에 의해 정해진 위치에서 수행되는 것을 제한된 자료구조라 하고, 스택과 큐가 해당된다.스택은 후입선출(LIFO) 형태로 포인터 top이 가리키는 곳에서만 삽입과 삭제를 수행한다큐는 선입선출(FIFO) 형태로 삽입은 포인터 rear가 가리키는 곳에서, 삭제는 포인터 front가 가리키는 곳에서 수행한다.스택은 같은 쪽에서 삽입과 삭제가 수행되고, 큐는 서로 다른 쪽에서 삽입과 삭제가 수행된다.스택과 큐의 주요 작업은 삽입(push) 삭제(pop)이며 시간복잡도는 O(1)이다.스택과 큐 모두 배열이나 연결 리스트로 구현 가능하다.스택은 서브루틴 호출이나 인터럽트 발생 시의 복귀 주소 관리, 순환적 프로그램 처리, 후위 표기 방식, 이진트리 순회, 깊이 우선 탐색 등.. 이전 1 2 3 4 5 ··· 29 다음
