본문 바로가기

알고리즘/Algospot

 (14)
[완전 탐색] 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. 좋은 코..

티스토리툴바