본문 바로가기

알고리즘/Algospot

 (10)
[동적 계획법] JLIS [1. 문제 재정의 및 추상화] [2. 해결 계획] 두 수열의 LIS 를 찾은 뒤 각각 합치면 해결 할 수 없다 LIS 를 구하는 재귀 함수의 입력을 두개로 늘려야 함 => 각 수열을 받기 위해 => A[indexA] 와 B[indexB] 에서 시작하는 합친 증가 부분 수열의 최대 길이를 구하는 함수 A[indexA] 와 B[indexB] 중 작은 쪽이 앞에 온다고 가정 이 증가 부분 수열의 다음 숫자는 두가지 경우가 존재 1. A[indexA +1] 이후 또는 2. B[indexA +1] 이후 수열 중 max(A[indexA], B[indexB]) 보다 큰 수 중 하나 => 증가 부분 수열이 되기 위해선 A[indexA], B[indexB] 보다 큰 값이 뒤에 와야 한다. [3. 계획 검증]
[동적 계획법] WILDCARD [1. 문제 재정의 및 추상화] 와일드카드 패턴을 앞에서 한 글자씩 파일명과 비교해서 모든 글자 일치 시, 와일드카드 패턴이 파일명과 대응된다 말함 '?' 는 어떤 글자와도 대응된다 가정함 '*' 는 0글자 이상의 어떤 문자열에도 대응 됨. 주어진 와일드카드 패턴에 대응되는 문자열 출력 ex) 와일드카드 패턴 he?p 에 매치되는 문자열은 아래와 같다 heap, help helpp 는 ? 가 lp 에 대응 될 수 없기 때문이다 패턴이 아닌 문자열은 알파벳 대소문자와 숫자만으로 구성 됨. [2. 해결 계획] 완전 탐색 풀이 #include // w: 와일드카드 패턴 // s: 문자열 bool match(const std::string &w, const std::string &s) { int pos = 0;..
동적 계획법 [1. 도입] 큰 의미에서 분할 정복과 같은 접근 방식을 의미한다 다만, 어떤 부분 문제가 두 개 이상의 문제를 푸는데 사용 될 때 이 문제의 답을 한번만 계산 하고 향후 이 결과를 재활용하여 속도 향상을 노려볼 수 있다. 여기서 두 번 이상 계산 되는 부분 문제를 중복되는 부분 문제라 한다. [2. 메모이제이션] 한 번 계산한 값을 저장해두었다가 재활용하는 최적화 기법 참조적 투명 함수인 경우 적용 가능함 참조적 투명 함수란? => 입력이 고정되어 있을 때 그 결과가 항상 같은 함수 => 함수의 반환 값이 그 입력 값만으로 결정되는지의 여부를 참조적 투명성이라 함. [3. 메모이제이션 구현 패턴] 기저 사례를 먼저 처리 => 입력이 범위를 벗어난 경우, ... 가능한 경우 cache[] 를 모두 -1로..
[분할 정복] FENCE [1. 문제 재정의 및 추상화] 너비가 같은 N 개의 나무 판자에서 잘라낼 수 있는 많은 직사각형 중 가장 큰 직사각형의 넓이 단, 비스듬히 잘라 낼 수 없다. N 은 최대 20000 까지 주어짐 TestCase 는 최대 50 까지 주어짐 [2. 해결 계획] 완전 탐색에서 시작 left = 0 ~ right = N 까지 범위에서 최대 넓이를 찾고 left = 1 ~ right = N 까지 범위에서 최대 넓이를 찾고, ... 분할 정복으로 계산 한다면, A) 가장 넓은 직사각형이 중앙에서 왼쪽에 존재하는 경우 B) 가장 넓은 직사각형이 중앙에서 오른쪽에 존재하는 경우 C) 가장 넓은 직사각형이 왼쪽과 오른쪽에 걸쳐있는 경우 Case C 의 경우, 최초에는 중앙에 두개의 판자를 모두 덮을 수 있게 둘 중 최..
[분할 정복] 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. 좋은 코..

티스토리툴바