Study with book/윤성우 열혈 자료구조
다익스트라(Dijkstra) 알고리즘 구현
1.개요 드디어 다익스트라 알고리즘 구현을 끝냈다. 이 알고리즘을 연구하고 구현하는데 4일 정도가 소요된 것 같다. 다른 사이트들을 참고하면서 나만의 코드 스타일로 만들기 위해서 많은 노력을 했다. 다익스트라 알고리즘은 방향성과 가중치가 있는 그래프에서 최단거리를 구하는 알고리즘이다. 이번 다익스트라는 정점을 단순히 int값이 아닌 string값으로 입력받아 출력해주는 것을 목표로 구현했다. 다익스트라는 우선순위 큐를 이용해서 구현하는 것이 핵심이다. 방문한 정점에 인접한 정점들을 전부 우선순위 큐에 넣고 작은 가중치로 정렬된 우선순위 큐에서 빼내면서 최단거리를 구한다. 물로 그냥 큐를 사용해도 최종적으로는 최단거리로 갱신이되지만 우선순위 큐를 사용하면 이 갱신하는 작업을 없앤다. 다익스트라는 유명한 커..
크루스칼(Kruscal) 알고리즘 구현
[KruscalAlgorithm.cpp] 참고자료 http://makefortune2.tistory.com/39
후기 표기법 계산(stack사용)
1. 개요 - stack을 이용한 후기 표기법 계산은 쉬움 - 중위 표기법을 후위 표기법으로 바꾸는 코드가 까다롭게 느꼈음 - 풀이 방식 1) 문자열(char[])을 매개변수로 받는 함수 구성 2) double형 타입의 스택 선언(왜 double형이냐? 나누기 연산때문에) 3) 문자열 하나하나 따서 숫자면 스택에 넣고 문자면 스택에서 2개 빼내서 연산 후 다시 스택에 넣기 4) 문자열이 길이만큼 3번 반복 2. 코드 3. 정리 - char 타입의 문자를 isdigit()이란 함수를 통해서 숫자인지 아닌지를 구분할 수 있음 기억해 둘 것!! - 그리고 char타입이 숫자라면 X - '0' 를 통해서 정수형으로 변경할 수 있다는 것도 기억해 둘 것!! 참고자료 윤성우의 열혈 자료구조
후위표기법 BinaryTree로 나타내기
[MakeExpTree.h] [MakeExpTree.cpp] [MakeExpTreeMain.cpp] 참고자료 윤성우의 열혈 자료구조
중위표기법을 후위표기법으로 변경(Stack 사용)
"중위표기법을 후위표기법으로 변경(Stack 사용)" [InfixToPostfix.cpp] 참고자료 윤성우의 열혈 자료구조
트리 구현하기
[BinaryTree.h] [BinaryTree.cpp] [BinaryTreeMain.cpp] 참고자료 윤성우의 열혈 자료구조
하노이타워 알고리즘
1. 개요 - 하노이탑을 이해하면 보통 재귀함수를 완벽하게 이해할 수 있다고 한다. - 근데 솔직히 난 아직도 재귀가 낯설다. (더 파고들어가야할 듯) - 부분집합 출력하는 문제에도 재귀가 나오는데 부분집합 출력을 공부하면서 재귀가 잘 이해가지 않아서 하노이탑을 다시 살펴본다. 2. 문제 - N사에서 물어본 문제로 기억함 - HanoiTowerSol(5, 'A', 'B', 'C')인 경우 몇번 이동한 것일까?? 아래 해설 참고 3. 코드 4. 해설 HanoiTowerSol(1, 'A', 'B', 'C') 일 때 1번 이동이 있었음.(1번의 출력을 의미) HanoiTowerSol(2, 'A', 'B', 'C') 는 HanoiTowerSol(1, 'A', 'B', 'C')을 2번 호출한다는 것을 알 수 있음..
트리2
[이진 트리]• 트리 중에서 가장 많이 쓰이는 트리이다.• 정의- (1) 공집합이거나- (2) 루트와 왼쪽 서브 트리, 오른쪽 서브 트리로 구성된 노드들의 유한 집합으로 정의된다. 이진 트리의 서브 트리들은 모두 이진트리여야 한다.• 정의에서 ‘이진 트리’의 개념이 재귀적으로 들어간다는 점에 유의하자! 이진트리의 서브 트리도 이진트리의 성질을 만족하여야 한다는 것! • 위 그림은 이진트리인지를 알아보자.• 먼저 SUB3을 보자. SUB3은 하나의 노드 D로만 이루어져 있다. 만약 노드 D를 SUB3의 루트라고 생각하면 D의 왼쪽, 오른쪽 서브트리는 공집합이다. 하지만 정의 (1)에 의해서 공집합도 이진트리이므로 정의 (2)에 의하여 SUB3은 루트와 공집합 서브트리 2개를 갖는 이진트리이다.• SUB1은..
트리1
[트리의 개념]• 리스트, 스택, 큐 등이 선형 자료구조라고 한다면 트리는 비선형(계층적) 자료구조이다.• 계층적 자료구조는 ‘회사 조직’, ‘의사 결정 트리’ 등의 형태를 표현한다.• 리스트, 스택, 큐 등이 데이터 삽입, 삭제, 조회 등에 초점을 맞춘 자료구조라고 한다면, 트리는 어떠한 형태를 표현하는데 초점을 맞춘 자료구조다.• 그렇다고 트리에서 삽입, 삭제, 조회가 중요하지 않다는 것이 아니다. 단순히 무언가를 표현하는 것에 최적화된 자료구조라는 뜻이다. [트리의 용어] • 노드: 트리의 구성 요소에 해당하는 A, B, C, D, E, F, G, H, I, J, K를 노드(node)라 한다.• 루트: 계층적인 구조에서 가장 높은 곳에 있는 노드인 A가 루트가 된다.• 서브 트리: 전체 노트 집합 ..