'자료구조 및 실습' 카테고리의 글 목록 (4 Page)

본문 바로가기

자료구조 및 실습 - [2] 재귀 실습문제 - 하노이탑 (2) 재귀문제 중 '하노이의 탑' 문제가 있다. 맨 처음에는 하노이의 탑을 재귀로 푼다는 생각을 하지 못했다. 어느 부분에서 재귀를 찾을 수 있는지 보자. 규칙 찾기 먼저 하노이의 탑에는 규칙이 존재한다. 1. 한 번에 한개의 원판만 옮길 수 있다. 2. 큰 원판이 작은 원판 위에 있어서는 안 된다. 먼저 원판이 1개인 경우부터 생각해보자. 원판이 1개인 경우 단순하게 A에서 C로 옮겨주면 된다. 베이스 케이스가 될 것이다! 그럼 원판이 두개인 경우를 보자. 원판이 두개인 경우, 큰 원판이 C에 먼저 깔려야 작은 원판이 그 위에 올라갈 수 있기 때문에 먼저 큰 원판을 C로 옮기기 위해 작은 원판을 B로 옮긴다. 이후 큰 원판을 C로 옮긴다. 마지막으로 작은 원판을 B에서 C로 옮긴다. 그럼 원판 3개인 경우도..

자료구조 및 실습 - [2] 재귀 (1) 재귀 알고리즘 재귀 알고리즘이란 알고리즘 자신을 사용해 정의된 알고리즘을 말한다. 다시 말해 자기 자신을 알고리즘 안에서 계속 호출하는 것이다. 재귀 알고리즘은 계속해서 자기 자신을 호출하기 때문에 자칫하면 무한루프를 돌 수 있다. 따라서 재귀 함수를 구성할 때에는 두 가지 요소가 필요하다. 재귀 케이스 (Recursion) : 차후의 재귀호출은 작아진 부문제들(subproblems)을 대상으로 이루어진다. 베이스 케이스(base case): 부문제들이 충분히 작아지면, 알고리즘은 재귀를 사용하지 않고 이들을 직접 해결한다 다시 말해 재귀함수는 더 작아지는 방향으로 진행되어야 하고 (베이스 케이스를 향해 진행됨) 베이스 케이스에서는 더 이상 재귀를 사용하지 않고 알고리즘이 종료되어야 한다. 재귀의 작동원..

자료구조 및 실습 - [1] 알고리즘 분석 실습문제 (나머지 연산, 비트행렬에서 최대 1행 찾기, 누적 평균) (3) 문제 1 - 나머지 연산 ‘%’(modulo) 연산자는 나눗셈의 나머지를 반환한다. 덧셈과 뺄셈 연산자만을 사용하여 a를 b로 나눈 나머지를 반환하는 modulo(a, b) 함수와 이를 테스트할 프로그램을 작성하시오. 단, a ≥ 0, b > 0 인 정수다. ※ 힌트: modulo(a, b) 함수는 O(a/b) 시간에 실행하도록 작성할 수 있다. #입력 예시 1 >>> 17 3 // 17 % 3 2 #입력 예시 2 >>> 6 3 // 6 % 3 0 #입력 예시 3 >>> 0 5 // 0 0 def modulo(a,b): temp = True while temp: if a>=b: a=a-b else : temp = False print(a) a = int(input()) b = int(input()) mo..

자료구조 및 실습 - [1] 알고리즘 분석 (2) 지난 포스팅에서는 알고리즘 분석에 필요한 기본적인 것들을 적었다. 의사 코드를 활용하여 알고리즘을 표현하기도 하는데, 전에 배웠듯이 사용하는 하드웨어와 소프트웨어에 관계없이 실행시간을 추정해야 한다. 이때 임의접근기계 모델(Random Access Machine, RAM)을 사용하는데, 하나의 중앙처리장치(CPU) 무제한의 메모리셀 을 사용하고, 메모리 셀들은 순번으로 나열되며 어떤 셀에 대한 접근이라도 동일한 시간 단위(상수)가 소요된다고 가정한다. 또한 원시 작업(Primitive Operations)의 최대 개수를 입력크기의 함수 형태로 결정할 수 있는데, 원시 작업이란 알고리즘에 의해 수행되는 기본적인 계산을 의미한다. 예를 들어 산술식/논리식의 평가 (EXP) 변수에 특정값을 치환 (ASS) 배..

이전 1 2 3 4 5 다음

티스토리툴바