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

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

6.8 문제: 시계 맞추기 (문제 ID: CLOCKSYNC, 난이도: 중) 문제 4x4 격자 형태로 배치된 열여섯 개의 시계가 있습니다. 이 시계들은 모두 12시, 3시, 6시, 혹은 9시를 가리키고 있는데, 이 시계들이 모두 12시를 가리키도록 바꾸고 싶습니다. 시계의 시간을 조작하는 유일한 방법은 열 개의 스위치들을 조작하는 것으로, 각 스위치들은 모두 적게는 세 개에서 많게는 다섯 개의 시계에 연결되어 있습니다. 한 스위치를 누를 때마다, 해당 스위치와 연결된 시계들의 시간은 3시간씩 앞으로 움직입니다. (12시일때는 3시로, 3시=>6시, 6시 =>9시, 9시=>12시) 스위치들과 그들이 연결된 시계들의 목록이 주어지고 현재 가리키는 시간들이 주어졌을 때 모든 시계를 12시로 돌리기 위해 최소한 ..

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글자인 경우 성공 둘의 순서는 바뀌..

문제 : 알고리즘 문제 해결 전략 [록페스티벌] p6 문제 커다란 공연장을 빌려서 록 페스티벌을 개최하려고 합니다. 이 페스티벌은 여러 날 동안 진행되며, 하루에 한 팀의 밴드가 공연장에서 콘서트를 하게 됩니다. 전체 밴드를 몇 팀 섭외할 지는 아직 결정하지 않았지만, 페스티벌의 간판 스타인 L개의 팀은 이미 섭외가 끝난 상태입니다. 따라서 페스티벌은 최소 L일 이상 진행하게 됩니다. 이번에 사용할 공연장은 하루 빌리는 데 드는 비용이 매일 매일 다릅니다. 때문에 공연 일정을 잘 정해서 공연장 대여 비용을 줄이려고 합니다. 앞으로 N일간의 공연장 대여 비용을 알고 있다고 합시다. 이 중 L일 이상을 연속해서 대여하되, 공연장을 하루 빌리는 데 드는 평균 비용을 최소화하려면 어떻게 공연장을 빌려야 할까요?..

머리말 처음부터 완전한 체계를 갖추고 발전하는 학문은 없으므로, 발전 과정에서 학자들은 모두 어둠 속에서 직관에 의존해 헤매게 된다.(삽질한다.) 1. 문제 해결과 프로그래밍 대회 1.1 도입 메모리, 시간 제한, 재사용성, 간결성 을 고려해야함 이러한 제약 조건과 요구사항을 이해하고 최선의 방법을 찾아내는 것이 '문제해결능력' 1.2 프로그래밍 대회 그래픽 인터페이스 x 텍스트 => 텍스트 시간 제한, 메모리 제한 존재 다양한 알고리즘 설계기법, 자료구조 사용 정답, 오답의 여부가 명확 빠르고 객관적인 피드백을 주기 때문 제출한 프로그램의 실행 시간, 메모리 사용량이 제공 작은 변경이 어떻게 영향을 끼치는지 볼 수 있음 작은 작업이라 완벽하게 작성할 수 있음 경쟁하는 환경 경쟁은 동기가 되기도 함 제출..