독학두비니

Coding_Algorithm/DS_Algorithm

[C로 쓴 자료구조론] 1장 연습문제-9번(이항계수) 풀이

9번 문제 9. 이항 계수를 계산하는 반복 함수를 작성하고 이를 순환함수로 변환하라 일단 이 문제는 두가지 방법으로 풀이 할 예정입니다. 첫 번째 방법은 정의로, 두 번째 방법은 성질로 풀 예정입니다. 일단 이항 계수는 우리가 확통시간에 배운 C입니다. 조합이요 이게 정의입니다. 혹시라도 모르시는 분들을 위해. 이렇게 하면 그냥 팩토리얼로 계산만 하면 되죠? 팩토리얼 구현에 대한 함수는 전글 보시면 될 것 같습니다. 링크는 여기 https://dokhakdubini.tistory.com/191?category=847037 [C로 쓴 자료구조론] 1장 연습문제-7번(팩토리얼) 풀이 문제 7. 계승 함수 n!은 n1일때 n*(n-1)!의 값을 갖는다. n!을 계산하는 순환함수와 반복 함수를 모두 C로 작성하..

Coding_Algorithm/DS_Algorithm

[C로 쓴 자료구조론] 1장 연습문제-8번(피보나치 수열) 풀이

9번이 8번함수를 구현하면 해결되서 그냥 같이 씁니다. 8번 문제 8. 피보나치 수열은 다음과 같이 정의된다. f(i)를 계산하는 순환 함수와 반복 함수를 모두 C함수로 작성하여라. 이것도 전형적인 재귀함수 꼴이죠? 재귀함수가 힘든사람은 여기! https://dokhakdubini.tistory.com/190?category=814319 [재귀함수] 재귀함수 구현할 때 염두에 두면 좋은 것들 작년에 c언어를 처음 배울 때도 재귀함수에 대해서 배웠는데 너무 어려워서 그냥 무시한 적이 있었는데 물론 그랬다가 지금 충분히 고통을 받을 수 있었습니다. 그래서 재귀함수와 함께 지지고 볶고 하다가 결국.. dokhakdubini.tistory.com 함수 안에는 n=0일 때와 n=1일때만 구현하고, 나머지 경우는 ..

Coding_Algorithm/DS_Algorithm

[C로 쓴 자료구조론] 1장 연습문제-7번(팩토리얼) 풀이

문제 7. 계승 함수 n!은 n1일때 n*(n-1)!의 값을 갖는다. n!을 계산하는 순환함수와 반복 함수를 모두 C로 작성하여라. 이거 재귀함수 근본문제죠? 재귀함수가 어려우신 분들은 제가 며칠 전 작성한 글 참고해 주시면 좋을 것 같습니다. 글은 여기! https://dokhakdubini.tistory.com/190?category=814319 [재귀함수] 재귀함수 구현할 때 염두에 두면 좋은 것들 작년에 c언어를 처음 배울 때도 재귀함수에 대해서 배웠는데 너무 어려워서 그냥 무시한 적이 있었는데 물론 그랬다가 지금 충분히 고통을 받을 수 있었습니다. 그래서 재귀함수와 함께 지지고 볶고 하다가 결국.. dokhakdubini.tistory.com 그래서 일단 함수를 작성할 때는 n

Coding_Algorithm/DS_Algorithm

[C로 쓴 자료구조론] 1장 연습문제-6번(제수) 풀이

문제 6. 어떤 양의 정수 n에 대해 이 자신의 모든 제수들의 합인지를 알아내는 C프로그램을 작성하여라. 즉 n이 1

Coding_Algorithm/DS_Algorithm

[C로 쓴 자료구조론] 1장 연습문제-5번(비둘기집) 풀이

문제 5. 비둘기 집 원칙(pigeon hole principle)이란 함수가 f가 n개의 상이한 입력에 대해 n개보다 작은 상이한 출력이 나온다면 a!=b이고 f(a)=f(b)인 2개의 입력 a, b가 존재한다는 것이다. 이와 같이 입력 값이 상이하면서 함수 값이 같은 a, b를 찾는 C프로그램을 작성하여라. 확통시간에 어디선가 본것같은 이 느낌.... x와 y를 정해놓고 그걸 찾는 알고리즘을 짜면 되겠죠 #include #include #include #define MAX 30 // 배열의 최대 크기 #define FUN(x) (x*x - 100*x + 8) // 임의의 함수 정의 int find(int result, int n); int output[MAX] = { 0 }; // 각 변수의 함수결과..

Coding_Algorithm/DS_Algorithm

[C로 쓴 자료구조론] 1장 연습문제-4번(정렬) 풀이

4번 문제풀이입니다. 4. 정수 x, y, z를 오름차순으로 출력하는 C프로그램을 작성하라. 사실 이건 그냥 정렬하는 방법을 찾으라는 소리죠? 선택정렬, 버블정렬, 퀵정렬 등 여러가지 정렬이 있는데 이전에 포스팅했던 정렬 포스트들 올립니다. https://dokhakdubini.tistory.com/172?category=847037 [자료구조] 선택정렬(Selection Sort)에 대하여 Data_Structure 선택정렬에 대하여 About. Selection Sort 정의: 1개이상의 서로 다른 정수를 가장 작은순서부터 배열하는 정렬 배열할때 가장 작은 수부터 배열하고싶으면, 가장 작은 숫자를 찾아서 맨 처음, 그.. dokhakdubini.tistory.com (버블정렬, 퀵정렬 추가예정)

Coding_Algorithm/DS_Algorithm

[C로 쓴 자료구조론] 1장 연습문제-3번(Boolean출력) 풀이

1장 연습문제-3번(Boolean출력) 풀이입니다. 3. n개의 Boolean 변수 x1, x2, x3, ... ,xn이 주어졌을 때, 이 변수들이 가질 수 있는 가능한 모든 진리 값의 조합을 구하고자 한다. 예를 들어 n=2이면 , , , 와 같은 네 가지 경우가 존재한다. 이를 구하는 C프로그램을 작성하여라. 정말 '이 문제를 어떻게 풀면 좋을까'를 조금 생각해보면 Boolean은 true혹은 false의 값만 가능하기 때문에 전체 경우의 수는 2^n개입니다. 이 경우들을 어떻게 출력하면 좋을까 생각했는데, 수형도를 이용하는 방법으로 구현을 해보았습니다. 일단 위 경우는 n=3일때 가능한 수형도입니다. 첫 번째 경우의 수부터 여덟번째 경우의 수까지 순서대로 출력하면 될 것 같네요! 이런 수형도의 꼴을..

Coding_Algorithm/DS_Algorithm

[C로 쓴 자료구조론] 1장 연습문제-2번(Horner법칙) 풀이

문제 우선 Horner의 법칙을 간단하게 알아봅시다. https://jackpot53.tistory.com/119 그냥 여기 보고 옵시다. 여기가 설명 제일 잘되어있는듯 한줄정리를 하자면 한 항씩 계산을 하자니 효율성이 떨어져서 다른 계산했던 값들을 다시 가져다 쓰는 방법입니다. 그냥 코드로 하나하나 설명하는 방법이 훨신 나을 것 같네요 #include #define MAX_SIZE 101 double horner(int *coeff, int n, int x); int main() { int coeff[MAX_SIZE] = { 1, 2, 3, 4, 5 };// 1 + 2x + 3x^2 + 4x^3 + 5x^4 int n=5;//몇차다항식인지 알려주는 상수 double result, x; printf("x..

Coding_Algorithm/DS_Algorithm

자료/사이트

보호되어 있는 글입니다.

Coding_Algorithm/DS_Algorithm

[C로 쓴 자료구조론] 1장 연습문제-1번 풀이

제가푼거라 틀릴수도 있습니다. 지적은 언제나 환영 1. 다음과 같은 두 문장을 생각해보자. (a) 양의 정수 x, y 및 z에 대해 x^n+y^n=z^n이 되는 n의 최대 값은 2인가? (b) 5를 0으로 나눠 x에 저장하고 10번 명령문으로 분기하라. 두 문장은 알고리즘의 다섯 가지 조건 중 하나를 만족하지 않는다. 어느 조건에 어긋나는가? Sol) 우선 알고리즘의 다섯 가지 조건은 다음과 같습니다. 1. 입력, 출력; 외부에서 0개 이상 입력을 받아 1개 이상 출력을 생성해야 한다. 2. 명확성; 각 단계가 단순해야 하며, 모호하지 않아야 한다. 3. 유한성; 한정된 수의 작업 후에는 반드시 끝나야 한다. 4. 효과성; 모든 명령이 수행 가능하여야 한다. 5. 효율성; 알고리즘이 효율적이여야 한다. ..

Coding_Algorithm/DS_Algorithm

희소행렬 덧셈 구현

#include #include #include "smatrix.h" //time complexity : O(n^2) void smadd(matrix a, matrix b, matrix d) { assert((a != NULL) && (b != NULL) && (d != NULL)); assert((a[0].row == b[0].row) && (a[0].col == b[0].col)); assert(a[0].col > 0); int i = 1, j = 1, k = 1; d[0].row = a[0].row; d[0].col = a[0].col; while (i

Coding_Algorithm/DS_Algorithm

[자료구조] 이원/이진 탐색(binary search)에 대하여

Data_Structure 이원/이진탐색에 대하여 About. Binary Search !이론 설명! 우리가 단어가 100개 등록되어있는 사전에서 단어를 알아서 찾아주는 프로그램을 작성한다고 합시다. 그러면 우리가 생각할 수 있는 알고리즘 중 가장 쉬운 방법은 첫번째부터 100번째까지, 찾는 단어와 사전에 등록되어있는 단어를 같은지 비교하는 알고리즘이 있겠죠. 우선 이런 알고리즘을 이용을 한다면 구현하기에는 매우 쉽겠지만, 사전 후반에 있는 단어들을 찾는 경우나, 사전에 등재되어있지 않은 단어를 찾는 경우 무조건 비교과정을 100번가까이 반복해야하는 점이 효율적이지 못하다고 할 수 있겠죠. 그래서 이런 상황에서는 이원 탐색을 이용하면 더 효율적인 알고리즘을 구현할 수 있습니다. 이원 탐색에 대한 설명은 ..