컴퓨터 프로그래밍(암호학, 알고리즘)

하노이탑 문제는 알고리즘계에 있어 고전에 속한다. 특히 재귀호출(Recursion)에 대해 공부할 때 빠지지않고 등장하는 단골 문제이다. 그러나, 실제로 하노이탑 문제 풀이를 깊숙히 이해하는 것은 그리 쉽지 않고, 응용된 문제들은 꽤 어렵다. 이 페이지에서는 기본문제부터 응용문제까지 ..

/* 에라토스 테네스의 체 */ int p[10001]; p[1] = 1; for (int i = 2; i <= 10000; i++) { if (p[i] == 0) { for (int j = i * i; j <= 10000; j += i) p[j] = 1; } } /* 멱승 구하기 */ long long power(long long a, int e){ long long y = 1; while (e){ if (e & 1) y *= a; //홀수이면 밑수를 한번 더 a *= a; e >>= 1; } return y; } /* GCd */ int gcd(int a, int..

/* KMP */ 1)pi 테이블 만들기 pi[1] = 0; for (int i = 2; i <= M; i++) { pi[i] = pi[i - 1] + 1; while (true) { if (B[pi[i]] == B[i]) { //같으면, pi[i] = pi[i - 1] + 1 가 그대로 유지 break; } if (pi[i] == pi[pi[i - 1]] + 1) { //z=pi[pi[i-1]] + 1 로 표현하는게 핵심 pi[i] = 0; break; } pi[i] = pi[pi[i - 1]] + 1; //pi[i] = z } } 2)테이블 이용해서 문..

/* merge sort */ void merge(int s, int m, int e){ int i = s, j = m + 1; for (int k = s; k <= e; ++k) //왼쪽 a[i] 또는 오른쪽 a[j]임. //왼쪽의 경우는 i<=m 이면서 j>e 혹은 왼쪽게 오른쪽꺼보다 작은 경우. 나머지는 전부 오른쪽 buf[k] = (i <= m && (j>e || a[i] <= a[j])) ? a[i++] : a[j++]; } void merge_sort(int s, int e){ if (..

/* DP. 1로 만들기 – 3가지 연산(나누기3, 나누기2, 빼기1)이용 1 만들기 최소연산횟수 */ D[i]: 숫자 i에 대해서 최소 연산 횟수 D[i] = min(D[i-1]+1, (i%2==0) ? D[i/2], (i%3==0) ? D[i/3]) D[1]=1, D[2]=1, D[3]=1 /* DP. 피보나치 */ D[0] = 0 D[1] = 1 D[i] = D[n-2] + D[n-1] /* DP. 파스칼의 삼각형 */ D[i][j] = (j==0 || j==i) ? 1 : D[i-1][..

/* 기하 Basic structure */ struct Point{ double x, y; Point(){} Point(double _x, double _y){ x = _x; y = _y; } Point operator + (const Point& rhs) const{ return Point(x+rhs.x, y+rhs.y); } Point operator - (const Point& rhs) const{ return Point(x - rhs.x, y - rhs.y); } bool operator < (const Point& rhs){ return (x != rhs.x) ? (x < rhs.x) : (y < rhs.y); } Point operato..

/* Permutation */ void permu(int n, int r, int idx){ if (idx == r){ for (int i = 0; i < r; ++i) printf("%c ", buf[i]); printf("\n"); } for (int i = 0; i < n; ++i){ if (used[i]) continue; used[i] = 1; buf[idx] = str[i]; permu(n, r, idx + 1); used[i] = 0; } } /* Combination */ void combi(int n, int r, int s, int idx) { if (idx == r){ for (int i = 0; i < r; ++i) printf("%..

1. -2진수 (백준 2089) 2. 진법 변환- Base Conversion (백준 11576) --------------------------------- 1. -2진수 (백준 2089 ) 2진법은 부호 없는 2진수로 표현이 된다. 2진법에서는 20, 21, 22, 23이 표현 되지만 -2진법에서는 (-2)0 = 1, (-2)1 = -2, (-2)2 = 4, (-2)3 = -8을 표현한다. 10진수로 1부터 표현하자면 1, 110, 111, 100, 101..

1. 벽부수고 이동하기 (백준 2206) 2. 미로만들기 (백준 2665) 3. 말이 되고픈 원숭이(백준 1600) --------------------------------------------------- 1. 벽부수고 이동하기 (백준 2206) NxM행렬이 있을 때, (1,1)에서 (N,N)까지 벽을 피해서 이동할 수 있는 최소이동수를 찾으시오. 단, 벽을 한 번 깨는 찬스 사용가..

1. 최대 힙 (백준 11279) 힙에 대한 주요 핵심 - 힙은 complete tree이다. ==> perfect에서 leaf의 오늘쪽 몇 개가 없는 트리 - 배열을 사용해서 구현. 루트 인덱스가 1 - push(x)의 경우, 배열의 가장 끝에 값을 넣은 후, 트리의 위쪽 방향으로 가면서, 선조 노드와의 값을 비교해서 바꿔가면서 루트까지..