분류 전체보기
-
조약돌 놓기 문제Algorithm with C/DFS 2020. 9. 16. 19:22
문제 출처 문제 i열에 돌을 둘 수 있는 가지수를 살펴보자. 위의 임시 테이블에 i열을 다음과 같이 설정하자. i열에 돌을 둘수 있는 경우의 수를 파악하자. 아래와 같이 4가지 경우가 있음을 알 수 있다. i열에 돌을 둘 수 있는 가지수는 4가지임을 알 수 있다. 우선 최적 부분구조의 존재를 확인해보자. n열 중 1열부터 i열까지 돌을 놓는 경우에 1열부터 i열까지의 합의 최고치를 생각해보자. 위에서처럼 i열에는 4가지 패턴 중 하나의 경우로 돌이 놓여질 것이다. (1). i열이 패턴1로 놓여 있을 경우의 최고점 (2). i열이 패턴2로 놓여 있을 경우의 최고점 (3). i열이 패턴3으로 놓여 있을 경우의 최고점 (4). i열이 패턴4로 놓여 있을 경우의 최고점 그리고, 다음과 같은 경우에 대해서도 생각..
-
N 개의 계단Algorithm with C/DFS 2020. 9. 16. 18:58
문제 N 개의 계단을 사람이 오른다고 하자. 한 번에 1계단 오르기도 하고, 2계단이나 3계단씩 오르기도 한다. 계단을 오르는데 몇 가지 방법이 있는가? 문제 분석 N 번째 계단에 도달하는 방법을 생각해보자. N - 1 번째 계단에서 한 계단 더 올라 N 번째 계단에 도달했을 수도 있고, N - 2 번째 계단에서 두 계단을 뛰어 N 번째 계단에 도달했을 수도 있고, N - 3 번째 계단에서 세 계단을 한 번에 뛰어 N 번째 계단에 도달했을 수도 있다. 그러므로, 마지막 계단에 오르는 방법의 가짓수는 그 전 세 계단에 도착하는 경우의 수를 전부 더한 것이다. 구현 프로그램 실행결과 소스 파일
-
이동 경로의 가지수를 구하라.Algorithm with C/DFS 2020. 9. 16. 18:47
문제 본인이 프로그래밍을 한 이후에 올바르게 값이 출력이 되는지 궁금할 것이다. 이 문제에서 구하는 경로의 개수는 아래와 같이 표현된다. 위와 같이 식이 세워지는 이유를 찾아보자. X번 오른쪽으로, 그리고 Y번 아래쪽으로 진행하여 만들 수 있는 모든 경로의 수를 세야 한다. 이 경로는 ( X + Y ) 개의 이동 단계로 구성된다. 경로 하나를 만들려면, X + Y 번 이동하는 가운데 X번은 오른쪽으로 움직이도록 해야 한다. 그러므로, 전체 경로의 수는 ( X + Y ) 가운데 X의 항목을 뽑는 경우의 수와 같다. 그래서, 위와 같은 이항식이 나온다. 문제 분석 위의 문제의 초점은 로봇이 움직이는 방향이다. 로봇은 두 방향으로만 움직이는 것이 가능하다. 그리고, 시작위치와 끝 위치가 주어져 있다. 여기서 ..
-
스택의 활용 - 미로 탐색C 자료구조/3. 스택( Stack ) 2020. 9. 16. 18:13
참고 문헌 설명 미로에서 탈출하기 위해서는 미로를 체계적으로 탐색하여야 할 것이다. 출구를 찾는 기본적인 방법은 시행 착오 방법으로서 하나의 경로를 선택하여 한 번 시도해보고 안되면 다시 다른 경로를 시도하는 것이다. 문제는 현재의 경로가 안 될 경우에 다른 경로를 선택해야 한다는 것으로 가능한 경로들이 어딘가에 저장되어 있어야 한다. 그리고, 현재 위치에서 가능한 경로 중에서 가장 가까운 경로이면 좋을 것이다. 따라서 가능한 경로들이 저장되는데 그 중에서 가장 최근에 저장한 경로가 쉽게 추출되는 자료구조를 사용해야 할 것이다. 따라서 결론은 "스택"이 후보가 된다. 현재 위치에서 갈 수 있는 칸들의 좌표를 스택에 기억하였다가 막다른 길을 만나면 가장 가깝고, 아직 가보지 않은 칸으로 다시 돌아가서 새로..
-
List SortC 자료구조/Sort Basic 2020. 9. 15. 19:25
구현 방식에는 두 가지 방법이 있다. 1. 데이터를 리스트에 모두 저장하고 나서 리스트 정렬하는 방식 리스트에서 먼저, 정수값이 들어있는 배열(정렬되지 않은 )을 리스트에 데이터를 다 집어 넣고나서, 해당 리스트에서 정렬을 하는 방법을 만들어 보고자 한다. 정렬을 할 때, 여기서 버블 정렬을 이용했다. 프로그램 실행결과 소스 파일 2. 데이터를 리스트에 저장하면서, 리스트를 정렬하는 방식 배열의 데이터를 리스트에 넣어줄때, 정렬을 하면서 노드 생성하는 것을 만들어 볼 것이다. 두 가지 방식으로 만들어 볼 수 있다. 두 함수들을 차례로 보자. 아래는 나머지 부분이다. AddDataTwo함수의 실행결과 AddDataOne함수의 실행결과 소스 파일
-
Shell SortC 자료구조/Sort Basic 2020. 9. 15. 18:19
참고문헌 삽입정렬의 문제점 삽입정렬의 최대 문제점은 요소들이 삽입될 때, 이웃한 위치로만 이동한다는 것이다. 만약 삽입되어야할 위치가 현재 위치에서 상당히 멀리 떨어진 곳이라면 많은 이동을 해야만 제자리로 갈 수 있다. 쉘 정렬에서는 요소들이 멀리 떨어진 위치로도 이동할 수 있다. 구현 방식 삽입 정렬이 어느 정도 정렬된 배열에 대해서는 대단히 빠른 것에 착안한 방법이다. Shell정렬은 삽입 정렬보다 빠르다. 삽입 정렬의 최대 문제점은 요소들이 삽입될 때, 이웃한 위치로만 이동한다는 것이다. 만약 삽입되어야 할 위치가 현재 위치에서 상당히 멀리 떨어진 곳이라면 많은 이동을 해야만 제자리로 갈 수 있다. 쉘정렬에서는 요소들이 멀리 떨어진 위치로도 이동할 수 있다. 삽입 정렬과는 다르게 쉘 정렬은 전체의 ..
-
Insertion SortC 자료구조/Sort Basic 2020. 9. 15. 17:58
참고 문헌 삽입 정렬의 장점과 단점 삽입정렬은 연결리스트에서 최적. 그리고 정렬할 데이터들이 얼추 정리가 됬을때, 가장 최적화. 최악은 자료들이 정 반대로 정렬되어있을때 연산량이 많다. 구현 version1 삽입 정렬의 원리는 손 안의 카드를 정렬하는 방법과 유사하다. 새로운 카드를 기존의 정렬된 카드 사이의 올바른 자리를 찾아 삽입함으로써, 정렬이 유지되게 한다. 이와 같은 작업을 새로 삽입될 카드의 수만큼 반복하게 되면 전체 카드가 정렬된다. [그림 1] 정렬되어 있지 않은 리스트의 첫 번째 숫자가 정렬된 리스트의 어느 위치에 삽입되어야 하는가를 판단한 후, 해당 위치에 이 숫자를 삽입하게 되면 정렬된 리스트의 크기는 하나 커지게 ..