전체 글
-
1. 이진 트리를 구성하기C 자료구조/5. 트리( Tree ) 2020. 6. 11. 15:04
트리의 링크 표현법 링크표현법에서는 노드가 구조체로 표현되고, 각 노드가 포인터를 가지고 있어서 이 포인터를 이용하여 노드와 노드를 연결하는 방법이다. 이진 트리를 링크 표현법으로 표현하여 보면 아래와 같다. 아래와 같은 이진 트리가 있다고 가정하자. 위의 이진 트리를 링크 표현법을 이용해서 그리면 아래와 같다. 위 내용을 바탕으로 프로그래밍을 해보자. 프로그램 결과창 위 프로그램 소스에 문제가 생겼다. 그 이유는 메인함수에서 트리를 생성(동적할당)하는데, 프로그램이 종료가 될 때, 해제를 해줘야 한다. 그 부분이 없다. 이는 뒤에 할 이진 트리의 순회를 하고나서 해결하도록 한다. 물론, 메인 함수 내에서 free함수를 호출해서 이를 해결할 수 있다. 아래는 소스파일
-
1. Stack 직접 만들기C 자료구조/3. 스택( Stack ) 2020. 6. 10. 12:01
우리는 아래의 포스트에서 라이브러리로 구현되어 있는 스택을 사용해봤다. designatedroom87.tistory.com/7?category=868809 0. stack library 맛 보기 제공하는 스택을 쓰기 위해서는 C++의 template에 대한 이해가 필요. main.cpp 프로그램 결과 designatedroom87.tistory.com 스택은 라이브러리로 구현이 되있기는하나, 속도가 느리며, 입맛대로 바꿀수 없다. 그렇기 때문에, 직접 만들어 봐야 한다. 스택의 기본적 모양은 아래와 같다. 아래의 Top은 연결 리스트에서의 Head와 역할이 같다. 스택은 나중에 들어간 데이터가 가장 맨 위에 위치한다. 여러개의 함수 및 구조체를 정의함에 따라 프로그램이 길어져 파일분할 합니다. 프로그램 ..
-
5. The Tower Of Hanoi ( 하노이 타워 )C 자료구조/1. 재귀함수 2020. 6. 10. 10:26
원반이 3개인 경우의 그림부터 보자. 가장 작은 원반을 1번, 가장 큰 원반을 3번이라고 하자. [그림 1 : 3개의 원반을 가지는 하노이의 탑 문제 ] 위의 그림에서 원반의 이동의 순서를 알아보도록 하자. 각 이동단계는 아래의 그림들과 같다. [ 그림 Step 1 ] [ 그림 Step 2 ] [ 그림 Step 4 ] [ 그림 Step 5 ] [ 그림 Step 6 ] [ 그림 Step 7 ] 위 그림을 통해 알 수 있는 규칙은 아래와 같다. 이 규칙은 원반이 4개인 경우에 대해서도 성립한다. 1. A막대기에 꽂혀있는 1번 원반과 2번 원반을 막대기 B로 이동시킨다. 2. 그리고 나서 가장 큰 원반인 3번 원반을 막대기 C로 이동시킨다. 3. B 막대기에 꽂혀있는 1번 원반과 2번 원반을 막대기 C로 이동..
-
4. BinarySearch( 이진 탐색 )C 자료구조/1. 재귀함수 2020. 6. 8. 19:15
이진 탐색에서 반드시 배열은 정렬되어 있어야 한다. 아래는 이진탐색의 수도 코드이다. 위의 의사코드를 보면 list는 탐색할 배열, low는 탐색 시작 인덱스, high는 탐색 마지막 인덱스이다. list[low]에서 list [high]에서의 탐색은 list[low]에서 list[middle-1]의 탐색이 되거나 list[middle+1]에서 list[high]에서의 탐색이 된다. 이들 2가지의 탐색은 원래 문제의 크기를 반으로 줄인 부분 문제가 되고, 따라서 재귀 호출을 이용하여 쉽게 만들 수 있다. 맨 처음에 BinarySearch함수의 탐색 범위는 low가 0, high가 n-1이 되어 배열 전체가 탐색 범위가 된다. 재귀 함수의 탈출조건은 low가 high보다 커지는 경우로 이 경우는 탐색 실..
-
3. memoization을 통해 Fibonacci Sequence의 연산량 줄이기C 자료구조/1. 재귀함수 2020. 6. 8. 12:10
피보나치 수열이 무엇인지 잘 모르면 아래로 이동해서 보고 오자. designatedroom87.tistory.com/3?category=868275 2. Fibonacci Sequence( 피보나치 수열 ) 아래는 피보나치 수열의 점화식이다. 아래는 프로그램 소스이다. 아래는 피보나치 수열의 7번째 항을 구할 때, 호출되는 그림이다. 중요한 문제는 피보나치 수열의 7번째 항을 구할 때, 피보나치 designatedroom87.tistory.com 아래는 memoization 방법을 이용해 피보나치 수열을 구할 알고리즘이다. 앞서, 피보나치 수열을 구할 때, 이미 구한 항의 값을 다시 구하는 것이 문제라 하였는데, 여기서 기록을 통해 이를 해결하고자 한다. 즉, 기록한 항이 있으면 그 값을 리턴하면 되고,..
-
2. Fibonacci Sequence( 피보나치 수열 )C 자료구조/1. 재귀함수 2020. 6. 8. 11:48
아래는 피보나치 수열의 점화식이다. 아래는 프로그램 소스이다. 아래는 피보나치 수열의 7번째 항을 구할 때, 호출되는 그림이다. 중요한 문제는 피보나치 수열의 7번째 항을 구할 때, 피보나치 수열의 4번째 항을 중복으로 구한다. 즉, 이미 알아낸 항의 값을 다시 구하려고 한다. 이에 대한 한 가지 방법은 뒤에서 설명하도록 한다. 아래로 이동해서 중복을 제거하는 방법을 알아보자. designatedroom87.tistory.com/4 3. memoization을 통해 Fibonacci Sequence의 연산량 줄이기 피보나치 수열이 무엇인지 잘 모르면 아래로 이동해서 보고 오자. designatedroom87.tistory.com/3?category=868275 2. Fibonacci Sequence( 피..
-