본문 바로가기

▶ 자연과학

【Java】 자바로 이진트리와 수식 계산 자바로 이진트리와 수식 계산 추천글 : 【Java】 Java 목차 Q. 수식이 입력되면 수식의 결과를 출력하는 계산기를 만들자. Ex. 입력: 24+4*(5-3), 출력: 32 Step1. 수식계산 알고리즘을 이진트리로 접근해 보자. 1)에서 8) 순으로 조건문을 적용한다. 1) 각 연산자의 서열은 다음과 같다; + > - > * > / > (, ) > 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 2) 어떤 노드에 특정 연산자를 추가할 때 그 노드가 null이면 그 노드는 그 연산자를 저장하는 새로운 노드가 된다. 3) '('를 저장하는 노드에 ')' 이외의 연산자를 추가할 때 왼쪽 자식노드에 그 연산자를 추가한다. 4) '('를 저장하는 노드에 연산자 ')'를 추가할 때 두 괄호 사이의 부분을 ..
【코딩】 C 언어로 이항계수 C 언어로 이항계수(binomial coefficient) 추천글 : 【C 언어】 C 언어 목차 1. O(n) 어려운 문제라면 자료형의 크기 제한으로 쓸 수 없는 방법이다. #include #include double x = 1; int i = 0; int n, r; void a(){ if(i < r){ x *= (double) (n - i) / (double) (r - i); i ++; a(); } } int main(int argc, char *argv[]) { scanf("%d %d", &n, &r); a(); printf("%.lf", x); return 0; } 2. O(n2) memorization 기법이라 불리는 이 방법은 메모리 제한이 문제된다. #include #include #defin..
【코딩】 C 언어로 콜라츠의 추측 C 언어로 콜라츠의 추측(Collatz conjecture) 추천글 : 【C 언어】 C 언어 목차 콜라츠의 추측은 1937년에 처음으로 이 추측을 제기한 로타르 콜라즈(Lothar Collatz)의 이름을 딴 것으로, 3n+1 문제, 우박수 문제라고도 불린다. 콜라츠의 추측은 임의의 자연수를 입력해도 다음 알고리즘은 항상 끝이 난다는 것이다. 1. n을 입력받는다. 2. 만약 n이 1이면 멈춘다(STOP). 3. 만약 n이 1이 아닌 홀수이면 3n + 1을 한다. 4. 만약 n이 짝수이면 2로 나눈다. 5. 2 ~ 4를 반복한다. 만약 n이 22라면 위 알고리즘은 다음과 같은 값을 출력한다. 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1 이 알고리즘은 우리가 다루는 대부분의..
【코딩】 C 언어로 행렬식 C 언어로 행렬식(Determinant) 추천글 : 【C 언어】 C 언어 목차 1. 행렬식의 성질 [본문] 2. 코드 [본문] 1. 행렬식의 성질 [목차] 2. 코드 [목차] #include #include /* This source is for finding determinant value by using minor determinant expansion */ int det(int n, int (*Matrix)[n]){ if(n == 1) return Matrix[0][0]; int i, j, k; int minor_Matrix[n][n-1][n-1]; for(k = 0; k < n; k++){ for(i = 0; i < n - 1; i++) for(j = 0; j < n; j++){ if(j < k)..
【코딩】 C 언어로 큰 수 처리 C 언어로 큰 수 처리 추천글 : 【C 언어】 C 언어 목차 #include #include #define Max 100 /* This program can help you calculate huge numbers (∈ ℕ) */ // Using the function 'strlen()' is not that efficient int max(char *array_I, int array_I_size, char *array_II, int array_II_size){ // array_I ≥ array_II → 1 // array_I array_II_size) return 1; else if(array_II_size > array_I_size) retu..
【코딩】 C 언어로 연속수 C 언어로 연속수 추천글 : 【C 언어】 C 언어 목차 Q. 몇 개(≥ 2)의 연속된 자연수를 더해서 주어진 수를 만드는 방법의 수를 구하라. 예를 들어, 15 = 7 + 8 = 4 + 5 + 6 = 1 + 2 + 3 + 4 + 5 로서 총 4가지 방법이 존재한다. Lemma. 주어진 수 N에 대해 N = a × b, a = 2k꼴, 2 ∤ b라고 하자. 이때 문제에서 요구하는 방법의 수는 b의 약수의 개수와 같다. Proof. n부터 k개의 자연수를 더하는 것을 고려하자. n + (n + 1) + ··· + (n + k - 1) = (2n + k - 1) ÷ 2 × k = N ⇔ (2n + k - 1) × k = 2N 이때 k가 2N의 약수임을 알 수 있다. 임의의 2N의 약수 k에 대해, n이 정의되..
【코딩】 C 언어로 소인수분해 (Integer Factorization) C 언어로 소인수분해(Integer Factorization) 추천글 : 【C 언어】 C 언어 목차 #include #include /* This source is for integer factorization */ int main(int argc, char *argv[]) { int n; scanf("%d", &n); int i = 2; // "1" is not prime, so starting with "2" is reasonable while(1){ if(n == 1) break; if(n % i == 0){ printf("%d ", i); n = n / i; i --; // primes can devide the given number many times } i ++; } return 0; } 입..
【코딩】 C 언어로 "이상한 나라의 셈법" C 언어로 "이상한 나라의 셈법" 추천글 : 【C 언어】 C 언어 목차 Q. 어떤 나라에서는 이진법을 사용한다. 그런데 그 나라의 사람들은 0이 연속적으로 붙는 수를 싫어한다. 숫자를 셀 때도 0이 연속적으로 붙는 수를 싫어한다. 그래서 다른 나라와 무역을 할 때 어려움이 따른다. 이 나라의 왕은 이 문제를 해결하기 위해 자기 나라 숫자를 십진법으로 바꾸는 프로그램을 만들려고 한다. 왕을 도와 프로그램을 작성하여라. (ref)] 입력 이 왕국에서 사용하는 수 n을 입력한다. (이때 입력되는 것은 이진법이고, 0이 연속적으로 붙는 수는 없다.) (1 ≤ n ≤ 221) 참고 : 1 → 1, 10 → 2, 11 → 3, 101 → 4, 110 → 5, 111 → 6, 1010 → 7 출력 n을 십진법으로 출..

티스토리툴바