그래프 정의 단순히 노드와 그 노드를 연결하는 간선을 하나로 모아놓은 자료구조 연결되어있는 객체간의 관계를 표현할 수 있는 자료구조 지도, 지하철 노선도의 최단 경로 등.. 용어 정점 (노드) : 데이터가 저장 됨. 간선 (링크) : 노드간의 관계를 나타냄. 인접 정점 : 간선에 의해 서로 연결된 정점 단순 경로 : 같은 간선을 지나가지 않는 경로 차수 : 무방향 그래프에서 하나의 정점에 인접한 정점의 수 (몇개가 한 노드에 연결되었는가) 진출 차수 : 방향그래프에서 사용되는 용어로, 한 노드에서 외부로 향하는 간선의 수 진입 차수 : 방향그래프에서 사용되는 용어로 외부 노드에서 들어온 간선의 수 구현 방식 인접행렬 방식 : 그래프의 노드를 2차원 배열로 만든 것. {: width="50%" height..

트리 정의 계층적인 구조를 나타내는 자료구조 비선형 자료구조 (스트 , 스택, 큐 는 선형 구조임.) 트리는 부모 - 자식 관계의 노드들로 이루어짐. 1개 이상의 노드를 갖는 집합으로 노드들은 아래 조건을 만족함. root 라고 불리는 특별한 노드가 있음 다른 노드들은 원소가 중복되지 않는 n 개의 부속 트리 (subtree)임. 저장법 n-링크 표현법 노드에 n개의 링크를 두고 자식의 개수만큼 링크에 저장한다. 모든 노드는 자식 노드 수에 관계없이 최대 n개의 링크를 갖는다. 각 링크는 부속 트리가 저장된 곳을 링크한다. 왼쪽자식노드 - 오른쪽 형제노드 표현방법 (출처 : https://apape1225.tistory.com/57) 첫번째 링크는 첫번째 자식 노드를 표현 하고, 두번째 링크는 자신의 오..

우선순위 큐 정의 우선순위를 가진 항목들을 저장하는 큐 FIFO 가 아닌 우선순위가 높은 데이터가 먼저 나감. 시뮬레이션 시스템 네트워크 트레픽 제어 운영체제의 작업 스케줄링 ADT create() : 우선순위 큐를 생성함 init(q) : 우선순위 큐 q를 초기화 함 is_empty(q) : 우선순위큐 q가 비었는지 검사함 is_full(q) :우선순위큐 q가 가득 찼는지 검사함 insert(q, x) : 우선순위큐 q에 요소 x 를 추가함 delete(q) : 우선순위큐로부터 가장 우선순위가 높은 요소를 삭제함과 동시에 반환함 find(q) : 우선순위가 가장 높은 요소를 반환함 종류 최대 우선순위 큐 최소 우선순위 큐 구현 방법 배열을 이용 연결리스트를 이용 힙을 이용 힙(heap) 노드의 키들이 ..

Postfix2 이전 포스트에선 postfix로 변환되어있는 수식을 계산하는 코드를 작성하였는데, 이번 포스트에선 infix로 표현된 수식을 postfix로 변환하는 소스코드를 작성하고자 한다. Condition 첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 A~Z의 문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 수식은 주어지지 않는다. 표기식은 알파벳 대문자와 +, -, *, /, (, )로만 이루어져 있으며, 길이는 100을 넘지 않는다. Boj-1918 IDEA 문자열을 입력받아 앞에서부터 읽고 연산자는 스택에 넣은 후 뒤로 보낸다. 피연산자는 뒤로 보내지 않고 바로 출력한다. 괄호가 있다면 괄호도 연산자..

큐 정의 먼저 들어온 데이터가 먼저 나가는 자료구조 구조 FIFO 구조 (First - In - First - Out) : 먼저 들어온 데이터가 먼저 나감 예제 큐 추상데이터타입(ADT) create(max_size) ::= 최대 크기가 max_size인 공백큐를 생성한다. init(q) ::= 큐를 초기화한다. is_full(s) ::= if(size== max_size) return TRUE; else return FALSE; is_empty(s) ::= if(size == 0) return TRUE; else return FALSE; enqueue(q, e) ::= if(is_full(q)) return ERROR_QUEUEFULL; else q의 끝에 e를 추가한다. dequeue(q) ::= i..

스택 정의 쌓아놓은 더미 구조 LIFO 구조 (Last - In - First - Out) : 가장 최근의 데이터가 가장 먼저 나감 pop() : 스택에 데이터를 삭제 push () : 스택에 데이터를 추가 예제 스택 추상데이터타입(ADT) create(size) ::= 최대 크기가 size인 공백 스택을 생성한다. is_full(s) ::= if(스택의 원소수 == size) return TRUE; else return FALSE; is_empty(s) ::= if(스택의 원소수 == 0) return TRUE; else return FALSE; push(s, item) ::= if(is_full(s)) return ERROR_STACKFULL; else 스택의 맨 위에 item을 추가한다 pop(s)..