본문 바로가기

재귀3

[알고리즘] ep5-3++) 분할통치법 vs DP 문제) 여행의 최소비용을 구하는 알고리즘을 작성하라.airtelDC(분할통치 버전)와 airtelDP(동적프로그래밍 버전)를 구현하고 실행시간을 비교 프로그램 요구사항: 1)  각 해결버전의 정방향, 역방향 버전 가운데 자유롭게 하나를 선택하여 구현하라. 2)  출력예시: 최종적으로 다음과 같이 인쇄되어야 한다. ※ 참고1) 아래는 MAX = 30인 경우의 인쇄결과임.2) X.XXXXXXXX는 cputime in milliseconds.  주의:반드시 아래 가이드라인의 main 함수 내용과 동일하게 실행하고 출력을 구하라.n = 6로 한 테스트실행 결과가 수작업실행 결과와 일치하는지 확인한 후 n = MAX로 한 본실행을 시도할 것.경로가 아닌 최소비용만을 요구하는 문제이므로, 만약 최소비용 경로가 두 .. 2024. 7. 24.
[자료구조] ep2+) 하노이 탑 구현 하노이 탑이란? B 기둥을 이용해서 A 기둥에 놓인 크기가 다른 원판을 C 기둥으로 옮기는 문제이다. 이때 원판은 한 번에 한 개씩만 옮길 수 있으며, 작은 원판 위에 큰 원판이 놓일 수 없다.+ 이동횟수 공식은 (2^n - 1) 회이다 e.g. n = 1인 경우 1회의 이동, n = 2인 경우 3회의 이동, n = 3인 경우, 7회의 이동       문제)원반의 개수 N을 입력받아, 하노이 탑 문제의 수행과정을 출력하는 프로그램을 작성해라     의사코드)n: 이동해야 할 원반 수from: 출발 기둥aux: 보조 기둥to: 목표 기둥  모식도)  //A에 1~N 쌓여있음 A     B     C 1 2 . . N//N-1개를 A에서 C를 거쳐 B로 이동 A     B     C N     1      .. 2024. 4. 7.
[자료구조] ep2) 재귀(Recursion) ㅇ재귀(recursion): 종료조건을 만족하기 전까지 자기 자신을 계속해서 호출→ 종료조건을 잘 설정해야 한다진행 방향: 종료조건을 향하여 진행작동 원리: stack을 생각하자 (LIFO, 후입선출)   이 작동원리에 대한 마인드셋이 너무 너무 중요하다예를 들어 재귀함수는 3건의 요청이 들어온다 하면 한 함수가 3건의 요청을 처리하는 것이 아닌, 각각 3개의 함수가 1건의 요청을 처리하는 것이다 (재귀함수를 이해하기 위한 최고의 그림이자 예시이다, 세종대 컴공 교수님들 최고!)          참고 및 출처: 실전 C프로그래밍(나중채교수님, 한동일교수님), 데이터 구조 원리와 응용(국형준교수님), C언어로 쉽게 풀어 쓴 자료구조(천인국) 2024. 4. 7.