7.2 문제 : 쿼드 트리 뒤집기 (문제 ID:QUADTREE, 난이도: 하) 대량의 좌표 데이터를 메모리 안에 압축해 저장하기 위해 사용하는 여러 기법 중 쿼드 트리란 것이 있습니다. 주어진 공간을 항상 4개로 분할해 재귀적으로 표현하기 때문에 쿼드 트리라는 이름이 붙었는데, 이의 유명한 사용처 중 하나는 검은 색과 흰 색밖에 없는 흑백 그림을 압축해 표현하는 것입니다. 쿼드 트리는 2^N*2^N 크기의 흑백 그림을 다음과 같은 과정을 거쳐 문자열로 압축합니다. 이 그림의 모든 픽셀이 검은 색일 경우 이 그림의 쿼드 트리 압축 결과는 그림의 크기에 관계없이 b가 됩니다. 이 그림의 모든 픽셀이 흰 색일 경우 이 그림의 쿼드 트리 압축 결과는 그림의 크기에 관계없이 w가 됩니다. 모든 픽셀이 같은 색이 ..

7. 분할 정복 7.1 도입 분할 정복( Divide & Conquer)은 가장 유명한 알고리즘 디자인 패러다임으로, 각개 격파라고 설명할 수 있음 주어진 문제를 둘 이상의 부분 문제로 나눈 후, 재귀 호출을 이용해 각각의 답을 계산하고, 부분 문제의 답을 이용해 전체의 답을 계산하는 방식 알고리즘 구성 divide 문제를 더 작은 문제로 분할 merge 각 문제의 답을 전체 문제의 답으로 병합 base case 더이상 답을 분할하지 않고 풀 수 있는 매우 작은 문제 적용가능한 문제의 특성 문제를 부분 문제로 나누는 자연스러운 방법이 존재해야함 부분 문제의 답을 조합해 전체 문제의 답을 계산하는 효율적인 방법이 있어야함 장점 대부분의 경우에서 작업을 빠르게 처리해줌 예제 : 수열의 빠른 합과 행렬의 빠른..

6.5 문제 : 게임판 덮기 (문제 ID: BOARDCOVER, 난이도: 하) 문제 H X W 크기의 게임판이 있습니다. 게임판은 검은 칸과 흰 칸으로 구성된 격자 모양을 하고 있는데 이 중 모든 흰 칸을 세 칸짜리 L자 모양의 블록으로 덮고 싶습니다. 이때 블록들은 자유롭게 회전해서 놓을 수 있지만, 서로 겹치거나, 검은 칸을 덮거나, 게임판 밖으로 나가서는 안 됩니다. 다음 그림은 한 게임판과 이를 덮는 방법을 보여줍니다. 게임판이 주어질 때 이를 덮는 방법의 수를 계산하는 프로그램을 작성하세요. 시간 및 메모리 제한 프로그램은 2초 안에 실행되어야 하며, 64MB 이하의 메모리를 사용해야만 합니다. 입력 입력의 첫 줄에는 테스트 케이스의 수 C(C=0 and tmp[0]=0 and tmp[1]=0 ..

6.3 문제: 소풍 (문제 ID: PICNIC, 난이도: 하) 문제 안드로메다 유치원 익스프레스반에서는 다음 주에 율동공원으로 소풍을 갑니다. 원석 선생님은 소풍 때 학생들을 두 명씩 짝을 지어 행동하게 하려고 합니다. 그런데 서로 친구가 아닌 학생들끼리 짝을 지어 주면 서로 싸우거나 같이 돌아다니지 않기 때문에, 항상 서로 친구인 학생들끼리만 짝을 지어야 합니다. 각 학생들의 쌍에 대해 이들이 서로 친구인지 여부가 주어질 때, 학생들을 짝 지을 수 있는 방법의 수를 계산하는 프로그램을 작성하세요. 짝이 되는 학생들이 일부만 다르더라도 다른 방법이라고 봅니다. 예를 들어 다음 두 가지 방법은 서로 다른 방법입니다. (태연,제시카)(써니,티파니)(효연,유리) (태연,제시카)(써니,유리)(효연, 티파니) 시..

예제: 보글 게임 (문제 ID: BOGGLE, 난이도: 하) 문제 5*5 크기의 알파벳 격자를 가지고 하는 게임. 게임의 목적은 상하좌우 / 대각선으로 인접한 칸들의 글자들을 이어서 단어를 찾아내는 것입니다. 각 글자들은 대각선으로도 이어질 수 있으며, 한 글자가 두 번 이상 사용될 수도 있습니다. 주어진 칸에서 시작해서 특정 단어를 찾을 수 있는지 확인하는 문제를 풀어 봅시다. 입력 1 1 PRETTY 출력 True 풀이 간단한 방법 생각 완전 탐색 문제 분할 첫 글자 찾기 => 다음 글자를 주변에서 찾기 기저 사례 선택 더 이상의 탐색 없이 간단히 답을 낼 수 있는 경우 처음 주어진 위치가 원하는 단어의 첫 글자가 아닌 경우 실패 1에 해당하지 않고 원하는 단어가 1글자인 경우 성공 둘의 순서는 바뀌..