본문 바로가기

알고리즘

 (403)
[1065] 한수 [1. 문제 재정의 및 추상화] 문제에서 한수에 대한 정의 => 어떤 양의 정수 X의 각 자리가 등차수열을 이루는 수 요구사항 => N 이 주어졌을 때 1보다 크거나 같고, N보다 작거나 같은 한수의 개수를 출력 1
[4673] 셀프 넘버 [1. 문제 재정의 및 추상화] d(n) = n + {n 의 각 자리수의 합} ex) d(75) = 75 + 7 + 5 = 87 여기서 n 을 d(n) 의 생성자라 하며, 생성자가 없는 숫자를 셀프 넘버라 한다. ex) 1, 3, 5, 7, 9, ... 요구사항 => 10000보다 작거나 같은 셀프 넘버를 한줄씩 출력해야 함. [2. 해결 계획] 셀프 넘버는 생성자가 없으므로, d(n) 수열에서 가장 처음에 온다 할 수 있다. 계산된 d(n) 은 셀프 넘버가 아니므로, 출력하지 않도록 한다. 10K+1 길이를 갖는 배열을 생성하고, 셀프 넘버인 n 을 index 로 하는 경우 그 값을 0으로하고, 셀프 넘버가 아닌 경우 그 생성자를 저장하도록 한다. [3. 계획 검증] 메모리 제한은 크게 상관 없어 보임..
[분할 정복] QUADTREE [1. 문제 재정의 및 추상화] [2. 해결 계획] [3. 계획 검증] [4. 구현] #include #include #include // 좌상단으로 계속 재귀적으로 들어가다보면, // 언젠가 b, w 를 만나게 됨 // 그 다음 문자가 우상단에 위치하는 것 이므로 // 참조자 형태로 offset 을 받아서 업데이트 해야 함. std::string solve(const char quadtree[], int &offset) { assert(offset < strlen(quadtree)); const char head = quadtree[offset]; // 다음 구역을 확인하기 위해 // 먼저 offset 을 업데이트 함. offset++; if (head == 'b' || head == 'w') { co..
[완전 탐색] CLOCKSYNC [1. 문제 재정의 및 추상화] 각 스위치들은 모두 적게는 3개에서 많게는 5개의 시계가 연결되어 있다. 한 스위치를 누를때마다 연결된 시계는 3시간씩 앞으로 움직임 (3->6, 6->9, 9->12, 12->3) 모든 시계를 12시로 돌려놓기 위해 스위치를 눌러야 할 최소 횟수를 출력해야 함 불가능 할 경우 -1을 출력 [2. 해결 계획] 경우의 수가 아니라 최소 횟수를 계산해야 함 그러나 일단 시작은 완전 탐색에서 시작해보도록 스위치를 누르는 순서는 중요하지 않다? [3. 계획 검증] 동일한 스위치를 4번 누르면 결국 처음 상태와 같아짐. 따라서 완전탐색으로 진행 시 전체 경우의 수는 4^10=1,048,576 으로 완전 탐색으로도 충분해 보임 [4. 구현] #include #include #incl..
[완전 탐색] BOARDCOVER [1. 문제 재정의 및 추상화] H*W 크기의 게임판에서 모든 흰 칸을 세칸짜리 L 자 모양의 블록으로 덮어야 함. 이 형태의 블록은 회전해서 놓을 수 있지만, 서로 겹치거나, 검은색 칸을 덮거나, 게임판 밖으로 나가서는 안됨. '#' 은 검은 칸, '.' 은 흰 칸을 의미함 H,W 는 최소 1 에서 최대 20 이며, 흰 칸의 수는 50을 넘지 않는다. 흰 칸을 덮는 경우의 개수를 계산해야 함. [2. 해결 계획] 가능한 경우의 수 이므로 완전 탐색 방식을 사용해 본다. 흰 칸의 개수가 3의 배수가 아니면 어떤 방식으로도 흰 칸을 모두 덮을 수 없다. => L 자 모양은 세칸 짜리 이다. 블록을 놓는 순서는 중요하지 않다. => (A):└, (B): ┘가 있을 때 (A) 를 먼저 놓고, (B) 를 놓나 ..
[완전 탐색] PICNIC [1. 문제 재정의 및 추상화] 학생들을 두명 씩 짝을 짓는다. 단, 항상 서로 친구인 학생들 끼리만 짝을 지어야 한다. 각 학생들의 쌍에 대해 이들이 서로 친구인지 여부가 주어진다. 학생들을 짝 짓는 경우의 수를 계산해야 한다. 학생 수는 최소 2명에서 최대 10명이고, 친구 쌍에 대해서 같은 쌍은 입력에 두번 주어지지 않는다. 64MB 이하의 메모리를 사용해야하고, 1초 내 실행되어야 한다. [2. 해결 계획] 가능한 경우의 수를 계산해야 하므로, 완전 탐색 방식을 사용해 본다. 재귀 호출을 이용해 완전 탐색을 해야하므로, 각 답을 만드는 과정을 여러개의 조각으로 나눈다. Base Case => 모든 학생이 짝을 지은 경우 같은 학생을 두번 짝지어주는 것은 중복 되므로, 중복되지 않게 각 단계에서 남..
알고리즘 분석 [1. 문제] 1차원 배열에서 연속된 부분 구간 중 그 합이 최대인 구간을 찾기 ex) [-7, 4, -3, 6, 3, -8, 3, 4] => [4, -3, 6, 3] 이 그 합이 10으로 최대가 됨. [2. 알고리즘에 따른 시간 복잡도] O(N^3) Bruteforce 방식 #include #include #include #include int inefficientMaxSum(const std::vector& input) { const int N = input.size(); int ret = std::numeric_limits::min(); for (int i = 0; i < N; i++) { for (int j = i; j < N; j++) { int sum = 0; for (int k = j; k ..
알고리즘 문제 해결 전략 [1. 문제 해결 단계] 문제를 읽고 이해한다. 문제를 익숙한 용어로 재정의 한다. (= 재정의와 추상화) => 문제를 자신만의 언어로 풀어 써본다. 어떻게 해결할지 계획을 세운다. => 사용할 알고리즘과 자료구조를 선택한다. 계획을 검증한다. 프로그램으로 구현한다. 어떻게 풀었는지 돌아보고, 개선할 방법이 있는지 확인한다. [2. 문제 해결 전략] 직관과 체계적인 접근 단순한 방법에서 시작 할 수 있는가? => 무식하게 풀 수 있는가? => Bruteforce => 알고리즘 효율성의 기준선을 정해주는 효과가 있다. 문제 풀이 과정을 수식화 할 수 있는가? => 손으로 문제를 풀어보는 습관 문제를 단순화 할 수 있는가? => 문제의 좀더 쉬운 변형판? => 문제의 제약 조건을 제거해본다. [3. 좋은 코..
7103 static int N, sels[5]; static int table[32767 + 1]; static int __solution(int s, int v, int cnt) { if (v == N) { //해당 수를 이루는 조합을 확인 할 수 있다. return 1; } if (cnt
5648. 원자 소멸 시뮬레이션 typedef struct { int y, x, dir, k; }info; static int N; static int board[4096][4096]; static int visit[4096][4096]; static int collision[4096][4096]; static int d[4][2] = { 1, 0, -1, 0, 0, -1, 0, 1 }; static vector vec; static int solution() { int x, y, dir, K, ret = 0; scanf("%d", &N); for (int cnt = 0; cnt < N; cnt++) { scanf("%d %d %d %d", &x, &y, &dir, &K); x += 1000; y += 1000; x *= 2; y *=..

티스토리툴바