후위표기법으로 계산기 만들기 계산기 관련 외주가 들어와서 해보던 중, 예전에 배웠던 후위표기법을 사용해야했다. 그런데 기억이 안나서 검색 없이 혼자 구현하려다 보니 너무 어려웠다... 검색해보니까 stack을 이용해서 후위표기법을 만드는 간단한 방법이 나와있어서 까먹지 않기 위해 기록한다. 후위 표기법 수식 트리 후위 표기법이란 계산식에서 계산을 위해 사용하는 표기법이다. 예제와 함께 살펴보자. 수식 : 9x3+1-3%3 수식이 주어졌을 때 비연산자와 연산자로 나눈 후, 각 항목을 하나의 노드라고 생각하면 트리 형태로 만들 수 있다. 이러한 트리는 수식을 트리라는 자료구조로 만든 것이니 수식트리, 즉 Expression Tree라고 불린다. 트리 순회와 표기법 트리를 순회하는 방식에는 prefix(전위)..

그래프 탐색 그래프를 탐색하는 기법에는 대표적으로 2가지가 있다. 너비 우선 탐색인 BFS(Breadth-First Search)와 깊이 우선 탐색인 DFS(Depth-First Search)이다. BFS BFS는 큐를 이용하여 구현한다. 설명 트리로 예를 들었지만, 모든 그래프에서 마찬가지로 동작한다. 루트 노드를 queue에 넣는다. queue의 노드를 하나 꺼낸 후, 해당 노드와의 인접 노드를 모두 queue에 넣는다. 위의 방식을 모든 노드가 완료될 때까지 반복한다. stack에 들어간 순서를 보면 다음과 같다. 1=>2=>3=>4=>5=>6=>7=>8 따라서 트리에서 BFS를 실행하여 탐색을 하는 것은 레벨 순회를 하는 것과 같다. DFS DFS는 스택을 이용하여 구현한다. 설명 트리로 예를 들..

트리 용도 용어 정리 종류 이진 트리 일반 트리 스레드 이진 트리 구현 배열 표현법 연결리스트 표현법 트리 활용 탐색 집합 표현 허프만 코드 트리 트리란 그래프의 한 종류로 무방향 연결 비순환 그래프(Connected Undirected Acyclic Graph)이다. 루트 노드가 존재하고, 루트 노드를 제외한 모든 노드의 in-degree가 1인 방향그래프라고 말할 수도 있다. 계층적인 구조를 가지며 그래프의 한 종류이므로 비선형 자료구조에 속한다. 용도 계층적인 조직을 표현하기 위해 사용되거나, 컴퓨터의 디렉토리 구조 / 인공지능의 decision tree 등에 이용된다. 또한 자료의 탐색 / 정렬 / DB 구성이나 분자구조식 설계 등에서도 다양하게 이용된다. (결정트리)(이진탐색) 용어 정리 노드 ..

문제 : 백준 1260번 _ DFS와 BFS 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 2 초 128 MB 87845 28912 16832 31.543% 문제 그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다. 입력 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로..