본문 바로가기

분류 전체보기215

백준 2775: 부녀회장이 될테야(java/C) 문제 풀이 2차원 배열을 사용해 풀 수 있을 것 같다 우선 k층 n호의 사람 수를 정리해 보면 아래와 같다.각 호실 별 사람 수를 저장할 int형 2차원 배열 aptArr를 설정했으며 층수에 관계없이 1호는 항상 1명이 거주하고, 0층의 k호에는 k명이 거주한다.그 외의 경우 (같은 층 바로 전 호의 사람 수) + (아래 층 같은 호의 사람 수)인 것을 알 수 있으므로aptArr[0][n]=n; //0층 n호는 n명aptArr[k][1]=1; //1호는 항상 1명aptArr[k][n]=aptArr[k][n-1]+aptArr[k-1][n];로 정리할 수 있다. for문을 사용하여 aptArr 배열을 먼저 완성한 다음, T 횟수만큼 k와 n을 입력받아 해당하는 호실의 사람을 꺼내 오는 방식으로 풀이하였다.. 2024. 7. 6.
배열의 응용: 다항식 표현 을 예시로 설명  1. 모든 계수를 배열에 저장하는 방법예시 다항식을 위와 같이 다시 쓸 수 있다. 모든 차수에 대한 계수 값들의 리스트인 (10, 0, 0, 0, 6, 3)을 배열 coef에 저장하고 다항식의 차수는 변수 degree에 저장하면, 하나의 다항식이 하나의 degree 변수와 하나의 coef 배열을 필요로 하므로 이들을 묶어 구조체를 만들고 이 구조체를 사용하여 하나의 다항식을 표현할 수 있다.#define MAX_DEGREE 101 //다항식 최대 차수+1typedef struct { int degree; //차수 float coef[MAX_DEGREE]; //계수 배열} polynomial;void main() { polynomial a = { 5, {10, 0, 0, 0, 6, 3} .. 2024. 7. 5.
순환-하노이탑 문제 하노이탑 문제- 막대 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.

티스토리툴바