본문 바로가기

전체 글

 (86)
자료구조 문제 정리 (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) 배열, 리스트 1. 자료구조선형구조 (배열, 리스트, 스택, 큐)데이터의 항목 사이의 관계가 1:1이며, 선후 관계가 명확한 1개의 선의 형태를 갖는 리스트 구조를 말한다.각 자료 항목 사이의 관계의 표현 방법과 항목의 입출력 방법에 따라 배열, 연결리스트, 스택, 큐, 데크로 나뉘어진다.비선형 구조 (트리, 그래프)데이터의 항목 사이에 1:n 또는 n:m 관계를 갖는 그래프적 특성을 갖는 형태트리, 그래프가 속한다.그래프는 사이클을 허용하며 트리는 사이클을 허용하지 않는다 2. 알고리즘 컴퓨팅 사고에서 주어진 문제의 중요한 특징만으로문제를 간결하게 재정의함으로써 문제 해결을 쉽게 하는 과정을 말한다.알고리즘의 특성은 다음과 같다.입력 : 외부에서 제공되는 자료가 있을 수 있다(0개 이상의 입력이 존재)출력 : 반드시..

티스토리툴바