C^n을 구할 때 이를 O(N)으로 구하는 방법은 굉장히 간단하다. for 문을 돌리며 결과값에 C를 n번 곱해주면 된다. 그러나 C^n은 O(log n)의 시간복잡도로도 구할 수 있는데, 바로 분할 정복법을 사용한 풀이이다. #include using namespace std; int pow(int a, int k) { //a^k, k>0 if (k == 0) { return 1; } else if (k == 1) { return a; } else if (k == 2) { return a * a; } else { if (k % 2) { return pow(a, (k - 1) / 2) * pow(a, (k - 1) / 2) * a; } else { return pow(a, k / 2) * pow(a, k..
우선 nCk를 구하는 방법은 굉장히 다양하다. Brute force n! / k! * (n - k)!의 성질을 이용해 구하는 방법이 대표적인데, 이는 for문을 두번 돌리고 그 두 값을 서로 나눠주는 것으로 구현이 가능하다. ex. 6C2 = (6 * 5) / (2 * 1) 재귀와 DP 그러나 숫자가 커지면 팩토리얼값이 long long에도 저장하기 어려울 만큼 커질 수 있다. 이를 방지하기 위한 두번째 방법이 파스칼의 삼각형을 이용한 방법이다. 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 파스칼의 삼각형을 C라는 2차원 그리드라고 생각하면, C(a, b)는 C(a-1, b-1) + C(a-1, b)임을 알 수 있다. 즉 바로 윗칸 + 왼쪽 윗칸을 더한 값이 해당 칸의 값인 셈이다. (빈칸은 0..
백준 12865 #include #include using namespace std; int arr[101][100001] = { 0 }; int weights[101]; int values[101]; int main() { int n, k; cin >> n >> k; for (int i = 1; i > weights[i] >> values[i]; // 맨 윗줄은 0으로 채워두고 시작. } for (int i = 1; i = weights[i]) { arr[i][j] = values[i] + arr[i - 1][j - weights..
분할 정복법 분할 -> 정복(풀이) -> 조합의 과정을 통해 하나의 큰 문제를 여러 개의 작은 문제로 분할하고 풀이한 후 재조합하는 접근방식. 분할 정복법을 사용하는 알고리즘으로 병합 정렬(merge sort)과 퀵소트(quick sort)가 있다. 재귀함수를 사용하는 특성 상 메모리 소모가 막심해질 수 있다. 분할 정복법의 사용 조건 1. 문제를 작은 여러 개의 Sub-problem들로 쪼갤 수 있어야 함. 2. Sub-problem들의 결과를 합쳐 큰 문제에 대한 답을 구할 수 있어야 함. function F(x): if F(x)가 간단 then: return F(x)를 계산한 값 else: x 를 x1, x2로 분할 // x1, x2 = G(x)처럼 값을 분할하는 함수를 별도로 제작하는 경우도 많다..
**개인 필기용 글이라 두서가 없을 수 있습니다. 선택 정렬 활용도 낮음 배열을 스캔해 가장 작은 수를 맨 앞으로 가져다 놓는다. 맨 앞칸을 제외한 나머지 배열을 스캔해 해당 배열에서 가장 작은 수(전체에서 두번째로 작은수)를 맨 앞으로 가져다 놓는다. 더 스캔할 배열이 없을 때까지 위 과정을 반복한다. 버블 정렬 활용도 낮음 1번째 인덱스부터 정렬을 시작한다. (n = 1) 인덱스 n, n+1을 비교한다. n > n+1 이면 서로 위치를 바꾸고(swap), 아니면 n을 1 증가시킨다. 이렇게 n이 array.length() - 1 까지 도달하면 이 과정을 처음부터 다시 반복한다. 루프 한 번을 도는 동안 단 한차례도 swap이 일어나지 않았다면 정렬이 완료된 상태이다. 삽입 정렬 활용도 낮음 2번째 인..
**개인 필기용 글이라 두서가 없을 수 있습니다. 최단 경로 알고리즘 다익스트라 노드들의 cost INF로 초기화한다. 현재 노드 cost + 인접 노드와의 거리 < 인접 노드의 cost 일 경우 인접 노드의 cost를 전자의 값으로 변경한다. 인접한 모든 노드를 다 방문했다면 다음 노드로 이동한다. 이때 다음 노드를 결정하는 방법으로는 BFS, DFS도 쓸 수 있지만 그리디 알고리즘을 통해 최적화하는 것이 일반적이다. (즉 가장 cost가 낮은 노드를 다음 노드로 설정) 목적지 노드에 도착했다면 해당 노드의 cost가 최단 거리이다. (만약 최단 경로를 구하고 싶다면 각 노드마다 부모 노드를 기록한 후 목적지 노드에서 재귀함수로 경로를 역추적하면 된다.) 더보기 다익스트라는 이차원 배열로 구현할 수도 ..
디자인 패턴은 분명 알아둔다면 많은 도움이 될 수 있다. 또 다른 개발자들과 소통할 때 편리함을 더해주기도 한다. 하지만 모든 상황에서 디자인 패턴을 남용한다면 여러 문제가 발생할 수 있다. 간단히 구현할 수 있는 기능을 지나치게 복잡하게 구현하는 결과를 초래할 수 있고, 무엇보다 디자인 패턴에만 의존하다 보면 사고 자체가 유연해지지 못해 디자인 패턴으로 해결할 수 없는 상황을 마주쳤을 때 문제를 해결할 수 있는 능력을 기르지 못할 수도 있다. 때문에 디자인 패턴은 어디까지나 일종의 가이드라인으로서만 사용하는 것이 좋다.
목표: 서로 다른 State들에 대해 같은 동작을 실행해야 할 때, 이를 긴 if else if 문으로 실행하는 것보다 더 나은 방법을 찾는 것이 state 패턴의 목표이다. 예시 상황: 포토샵과 유사한 프로그램을 구현한다고 가정해보자. 선택한 tool에 따라 mouseDown(), mouseUp()이 실행될 때마다 다른 결과가 도출되어야 한다. 접근1: if else if 문을 사용한다. package state; public class Canvas { private ToolType currentTool; public void mouseDown() { if (currentTool == ToolType.SELECTION) { System.out.println("Selection MouseDown"); }..
