Algorithm Strategies

[Algorithm Strategies] 03. Exhaustive Search - Board Cover

1. Exhaustive Search 1.1 Board Cover - Recursive Function 1.1.1 Problem - H ✕ W 크기의 게임판이 있는데, 검은 칸과 흰 칸으로 구성된 격자 모양을 하고 있음 - 모든 흰 칸을 세 칸짜리 L자 모양의 블록으로 덮고 싶음 - 자유롭게 회전 가능, 서로 겹치거나 검은 칸을 덮거나 게임판 빡으로 나가서는 안됨 - 게임판이 주어질 때 이를 덮는 방법의 수를 계산하는 프로그램 작성 - 입력 첫 줄에는 테스트 케이스의 수가 주어짐 - 각 테스트 케이스의 첫 줄에는 두 개의 정수 H, W가 주어지고 H줄에 W 글자로 게임판의 모양이 주어짐 1.1.2 Algorithm Strategy - 각 삼각형을 덮는 방식은 4가지 방식이 존재 - ㄱ, ㄱ 반대, ㄴ, ..

[Algorithm Strategies] 02. Exhaustive Search - Picnic

1. Exhaustive Search 1.1 Picnic - Recursive Function 1.1.1 Problem - 소풍 때 학생들을 두 명씩 짝을 지어 행동 - 서로 친구가 아닌 학생들끼리 짝을 지어 주면 서로 싸우거나 같이 돌아다니지 않기 때문 - 항상 서로 친구인 학생들끼리만 짝을 지어야 함 - 각 학생들의 쌍에 대해 이들이 서로 친구인지 여부가 주어질 때, 방법의 수를 계산하는 프로그램 작성 1.1.1.1 Input - 입력의 첫 줄에는 테스트 케이스 수, 각 테스트 케이스의 첫 줄에서는 학생의 수, 친구 쌍의 수가 주어짐 - 다음 줄에 m개의 정수 쌍으로 서로 친구인 두 학생의 번호가 주어짐 - 번호는 모두 0부터 n - 1사이의 정수이고, 같은 쌍은 입력에 두번 주어지지 않음, 학생들의..

[Algorithm Strategies] 01. Exhaustive Search - Boggle

1. Exhaustive Search 1.1 Boggle - Recursive Function 1.1.1 Problem - 보글은 5 ✕ 5 크기의 알파벳 격자를 가지고 하는 게임 - 이때 게임의 목적은 상하좌우 / 대각선으로 인접한 칸들의 글자들을 이어서 단어를 찾아내는 것 - 각 글자들은 대각선으로도 이어질 수 있으며, 한 글자가 두번 이상 사용될 수도 있음 - 주어진 칸에서 시작해 특정 단어를 찾을 수 있는지 확인하는 문제 1.1.2 Algorithm Strategy - 다음 글자가 될 수 있는 칸이 여러 개 있을 때 이 중 어느 글자를 선택해야 할지 미리 알 수 없음 - 완전 탐색을 이용하여 단어를 찾아 낼 때까지 모든 인접한 칸을 하나씩 시도 - 그 중 한칸이라도 단어를 찾을 수 있으면 성공, ..