본문 바로가기

분류 전체보기213

순환-하노이탑 문제 하노이탑 문제- 막대 A, B, C가 주어졌을 때 막대 A에 쌓여 있는 원판 3개를 막대 C로 옮기되 아래 조건들을 만족해야 함한 번의 하나의 원판만 이동맨 위에 있는 원판만 이동크기가 작은 원판 위에 큰 원판을 쌓을 수 없음중간의 막대 B를 사용할 수 있으나 앞의 조건들을 지켜야 함- 막대의 개수가 많아질수록 문제가 복잡해짐→ 순환을 이용하여 문제 해결(순환이 일어날수록 문제의 크기(=옮겨야 하는 디스크의 개수)가 작아짐) n개의 원판이 A에 쌓여 있는 경우1. 위에 쌓여 있는 n-1개의 원판을 B로 이동2. 제일 밑에 있는 원판을 C로 이동3. B에 있던 n-1개의 원판을 C로 이동void hanoiTower(int n, char A, char B, char C) { //A에 쌓여있는 n개의 원판을 .. 2024. 7. 3.
반복-피보나치 수열 계산 피보나치 수열- 앞의 두 숫자를 더해 뒤의 숫자를 만듦- 0, 1, 1, 2, 3, 5, 8, 13, 21, ... 순환 호출을 사용하여 구현int fib(int n) { if (n == 0) return 0; else if (n == 1) return 1; else return fib(n - 2) + fib(n - 1);}- 순환 호출이 진행될수록 계산 횟수 증가- 복잡도 T(n)=T(n-1)+T(n-2)+C- 시간 복잡도 O(2^n) 반복을 이용하여 구현int fib_iter(int n) { if (n == 0) return 0; if (n == 1) return 1; int pp = 0; int p = 1; int result = 0; for (int i = 0; i - result=p+pp: 앞.. 2024. 7. 3.
순환-거듭제곱 계산 순환을 사용하지 않고 x의 n제곱 값을 구하는 함수 작성double slow_power(double x, int n) { int i; double result = 1.0; for (i = 0; i - 루프 1회당 한 번의 곱셈이 필요하고 루프의 횟수는 n회- O(n)의 시간복잡도 순환을 사용하여 x의 n제곱 값을 구하는 함수 작성 1. 알고리즘power(x, n) :if(n==0) return 1;else if(n==짝수) return power(x^2, n/2);else if(n==홀수) return x*power(x^2, (n-1)/2);- x^n=(x^2)^(n/2)이므로double power(double x, int n) { if (n == 0) return(1); else if ((n % 2) .. 2024. 7. 3.
순환 순환(recurion): 어떤 알고리즘이나 함수가 자기 자신을 호출하여 문제를 해결하는 프로그래밍 기법 ex) 팩토리얼- n!을 정의하는 데 (n-1)!이 사용- (n-1)!을 정의하기 위해 다시 (n-2)!가 필요int factorial(int n){ if(n- C언어로 팩토리얼 계산 구현순환 호출의 내부적인 구현- 하나의 함수가 자기 자신을 다시 호출하는 것은 다른 함수를 호출하는 것과 동일- 복귀 주소가 시스템 스택에 저장되고, 호출되는 함수를 위한 매개변수와 지역 변수를 할당받음→ 자기 자신의 시작 위치로 점프 순환 알고리즘의 구조- 자기 자신을 호출하는 부분과 순환 호출을 멈추는 부분으로 구성- 멈추는 부분이 없다면 스택을 모두 소모할 때까지 순환 호출을 반복하다 오류 발생if(n 순환 vs 반.. 2024. 7. 3.
자료구조와 알고리즘 자료구조와 알고리즘 자료구조(data structure): 프로그램에서 자료들을 정리하여 보관하는 여러 가지 구조- 자료구조가 결정되면 그 자료구조에서 사용할 수 있는 알고리즘이 결정됨 알고리즘(algorithm): 컴퓨터로 문제를 풀기 위한 단계적인 절차- 문제와 컴퓨터가 주어진 상태에서 문제를 해결하는 방법을 정밀하게 장치가 이해할 수 있는 언어로 기술한 것- 특정한 일을 수행하는 명령어들의 집합 입력: 0개 이상의 입력이 존재해야 함출력: 1개 이상의 출력이 존재해야 함명백성: 각 명령어의 의미가 명확해야 함유한성: 한정된 수의 단계 후에 반드시 종료되어야 함유효성: 각 명령어들은 실행 가능해야 함자연어흐름도(플로우차트)의사 코드(pseudo code): 알고리즘 기술에만 사용되는 언프로그래밍 언어.. 2024. 7. 3.
[명품자바] 7장 실습문제(10~13) 10. 그래픽 편집기 작성 [난이도 7]- Vector 이용- 추상 클래스 Shape와 이를 상속받는 Line, Rect, Circle 클래스- "삽입", "삭제", "모두 보기", "종료" 4가지 그래픽 편집 기능abstract class Shape { public Shape() {} public void paint() {draw();} abstract public void draw();}class Line extends Shape{ @Override public void draw() { System.out.println("Line"); }}class Rect extends Shape{ @Override public void draw() { System.out.println("Rect"); }}cl.. 2024. 7. 1.

티스토리툴바