Algorithm/알고리즘 문제해결 전략(7)
-
[알고리즘 문제해결 전략]6장. 무식하게 풀기_⑤
CLOCKSYNC in algospot problem 문제 ID시간 제한메모리 제한제출 횟수정답 횟수 (비율)CLOCKSYNC10000ms65536kb75972989 (39%)출제자출처분류JongManIOI 1994보기문제그림과 같이 4 x 4 개의 격자 형태로 배치된 16개의 시계가 있다. 이 시계들은 모두 12시, 3시, 6시, 혹은 9시를 가리키고 있다. 이 시계들이 모두 12시를 가리키도록 바꾸고 싶다.시계의 시간을 조작하는 유일한 방법은 모두 10개 있는 스위치들을 조작하는 것으로, 각 스위치들은 모두 적게는 3개에서 많게는 5개의 시계에 연결되어 있다. 한 스위치를 누를 때마다, 해당 스위치와 연결된 시계들의 시간은 3시간씩 앞으로 움직인다. 스위치들과 그들이 연결된 시계들의 목록은 다음과 같..
2018.12.30 -
[알고리즘 문제해결 전략]6장. 무식하게 풀기_④
BOARDCOVER in algospot problem 문제 ID시간 제한메모리 제한제출 횟수정답 횟수 (비율)BOARDCOVER2000ms65536kb63352902 (45%)출제자출처분류JongMan알고리즘 문제 해결 전략보기문제H*W 크기의 게임판이 있습니다. 게임판은 검은 칸과 흰 칸으로 구성된 격자 모양을 하고 있는데 이 중 모든 흰 칸을 3칸짜리 L자 모양의 블록으로 덮고 싶습니다. 이 때 블록들은 자유롭게 회전해서 놓을 수 있지만, 서로 겹치거나, 검은 칸을 덮거나, 게임판 밖으로 나가서는 안 됩니다. 위 그림은 한 게임판과 이를 덮는 방법을 보여줍니다.게임판이 주어질 때 이를 덮는 방법의 수를 계산하는 프로그램을 작성하세요.입력력의 첫 줄에는 테스트 케이스의 수 C (C
2018.12.29 -
[알고리즘 문제해결 전략]6장. 무식하게 풀기_③
PICNIC in algospot problem 문제 ID시간 제한메모리 제한제출 횟수정답 횟수 (비율)PICNIC1000ms65536kb96664136 (42%)출제자출처분류JongMan알고리즘 문제 해결 전략보기 문제안드로메다 유치원 익스프레스반에서는 다음 주에 율동공원으로 소풍을 갑니다. 원석 선생님은 소풍 때 학생들을 두 명씩 짝을 지어 행동하게 하려고 합니다. 그런데 서로 친구가 아닌 학생들끼리 짝을 지어 주면 서로 싸우거나 같이 돌아다니지 않기 때문에, 항상 서로 친구인 학생들끼리만 짝을 지어 줘야 합니다.각 학생들의 쌍에 대해 이들이 서로 친구인지 여부가 주어질 때, 학생들을 짝지어줄 수 있는 방법의 수를 계산하는 프로그램을 작성하세요. 짝이 되는 학생들이 일부만 다르더라도 다른 방법이라고 ..
2018.12.29 -
[알고리즘 문제해결 전략]6장. 무식하게 풀기_②
BOGGLE in algospot problem 문제 ID시간 제한메모리 제한제출 횟수정답 횟수 (비율)BOGGLE10000ms65536kb101291635 (16%)보글(Boggle) 게임은 그림 (a)와 같은 5x5 크기의 알파벳 격자인 게임판의 한 글자에서 시작해서 펜을 움직이면서 만나는 글자를 그 순서대로 나열하여 만들어지는 영어 단어를 찾아내는 게임입니다. 펜은 상하좌우, 혹은 대각선으로 인접한 칸으로 이동할 수 있으며 글자를 건너뛸 수는 없습니다. 지나간 글자를 다시 지나가는 것은 가능하지만, 펜을 이동하지않고 같은 글자를 여러번 쓸 수는 없습니다.예를 들어 그림의 (b), (c), (d)는 각각 (a)의 격자에서 PRETTY, GIRL, REPEAT을 찾아낸 결과를 보여줍니다.보글 게임판과 ..
2018.12.29 -
[알고리즘 문제해결 전략]6장. 무식하게 풀기_①
Preview 1. 재귀 호출과 완전 탐색2. 최적화 문제3. 많이 등장하는 완전 탐색 알고리즘 1. 재귀 호출과 완전 탐색 재귀 함수:?자신이 수행할 작업을 유사한 형태의 여러 조각으로 쪼갠 뒤 그 중 한 조각을 수행하고 나머지를 자신을 호출해 실행하는 함수완전 탐색? 컴퓨터의 빠른 계산 능력을 이용하여 가능한 경우의 수를 일일이 나열하면서 답을 찾는 방법 **재귀 호출의 기저사례: 더 이상 쪼개지지 않는 가장 작은 작업 EX> 0부터 N까지의 숫자들 중 M개를 선택하는 방법에 대한 논의 1234567for(int i = 0; i
2018.12.28 -
[알고리즘 문제해결 전략]5장. 알고리즘의 정당성 증명
Preview 알고리즘의 정확한 증명을 위해서 수학적인 기법을 동원하여 증명한다. 1. 귀납법2. 귀류법3. 그외 다른 기술들 1. 귀납법 반복적인 구조를 갖는 명제들을 증명하는데 유용하게 사용된다. 단계를 나눠 보자 1단계 증명하고 싶은 사실을 여러 단계로 나누자. 2단계 첫단계의 내용이 성립함을 보이자. 3단계 한 단계에서 증명하고 싶은 내용이 성립한다는 가정하에 그 다음 단계도 성립함을 보이자. 반복문을 통해 귀납법의 정당성을 고려해 보자 1단계 반복문 진입시에 불변식이 성립함을 보인다. 2단계 반복문 내용이 불변식을 깨뜨리지 않음을 보인다. 다르게 말하면, 반복문 내용이 시작할때 불변식이 성립했다면 내용이 끝날 때도 불변식이 항상 성립함을 보인다. 3단계 반복문 종료시에 불변식이 성립하면 항상 우..
2018.12.27