문제여섯사람이일곱개의발판위에있다. 빈발판을중심으로세사람은왼쪽에서가운데를보고서있고, 다른세사람은오른쪽에서가운데를보고서있다. Figure: 양창모 ( 청주교육대학교컴퓨터교육과 ) Problems and Algorithms 2015 년여름 1 / 35

목표왼쪽에서있던세사람을오른쪽으로, 오른쪽에서있던사람을왼쪽으로이동한다. 가운데발판은여전히비어있어야한다. 최소의움직임으로목표를달성하도록한다. Figure: 양창모 ( 청주교육대학교컴퓨터교육과 ) Problems and Algorithms 2015 년여름 2 / 35

규칙모든사람은발판위에서있어야한다. 왼쪽에있는사람은오른쪽으로만, 오른쪽에있는사람은왼쪽으로만이동해야한다. 한사람뒤에빈발판이있으면그사람을넘어갈수있다. 한번에한사람만한번움직일수있다. Figure: 양창모 ( 청주교육대학교컴퓨터교육과 ) Problems and Algorithms 2015 년여름 3 / 35

문제 흰돌과검은돌이가운데빈칸을중심으로왼쪽과오른쪽에놓여있다. Figure: 양창모 ( 청주교육대학교컴퓨터교육과 ) Problems and Algorithms 2015 년여름 4 / 35

목표흰돌을오른쪽으로, 검은돌을왼쪽으로이동한다. 가운데한칸을비워놓는다. 최소의움직임으로목표를달성하도록한다. Figure: 양창모 ( 청주교육대학교컴퓨터교육과 ) Problems and Algorithms 2015 년여름 5 / 35

규칙흰돌은오른쪽으로만, 검은돌은왼쪽으로만이동해야한다. 진행방향에다른색의돌이있고그뒤에빈칸이있다면다른색의돌을넘어갈수있다. 한번에돌하나를한칸만움직일수있다. Figure: 양창모 ( 청주교육대학교컴퓨터교육과 ) Problems and Algorithms 2015 년여름 6 / 35

양창모 ( 청주교육대학교컴퓨터교육과 ) Problems and Algorithms 2015 년여름 7 / 35

패턴찾기흰돌과검은돌이각각 2개일경우위치를바꾸려면몇번움직여야하는가? 흰돌과검은돌이각각 4개일경우위치를바꾸려면몇번움직여야하는가? 흰돌과검은돌이각각 5개일경우위치를바꾸려면몇번움직여야하는가? 흰돌과검은돌이각각 10개일경우위치를바꾸려면몇번움직여야하는가? 흰돌과검은돌이각각 n 개일경우위치를바꾸려면몇번움직여야하는가? 일반적인규칙을찾을수있는가? 양창모 ( 청주교육대학교컴퓨터교육과 ) Problems and Algorithms 2015 년여름 8 / 35

패턴찾기흰돌과검은돌이각각 2개일경우위치를바꾸려면몇번움직여야하는가? 흰돌과검은돌이각각 4개일경우위치를바꾸려면몇번움직여야하는가? 흰돌과검은돌이각각 5개일경우위치를바꾸려면몇번움직여야하는가? 흰돌과검은돌이각각 10개일경우위치를바꾸려면몇번움직여야하는가? 흰돌과검은돌이각각 n 개일경우위치를바꾸려면몇번움직여야하는가? 일반적인규칙을찾을수있는가? 양창모 ( 청주교육대학교컴퓨터교육과 ) Problems and Algorithms 2015 년여름 8 / 35

패턴찾기흰돌과검은돌이각각 2개일경우위치를바꾸려면몇번움직여야하는가? 흰돌과검은돌이각각 4개일경우위치를바꾸려면몇번움직여야하는가? 흰돌과검은돌이각각 5개일경우위치를바꾸려면몇번움직여야하는가? 흰돌과검은돌이각각 10개일경우위치를바꾸려면몇번움직여야하는가? 흰돌과검은돌이각각 n 개일경우위치를바꾸려면몇번움직여야하는가? 일반적인규칙을찾을수있는가? 양창모 ( 청주교육대학교컴퓨터교육과 ) Problems and Algorithms 2015 년여름 8 / 35

데이터표채우기 쌍의수 돌의수 최소이동횟수 1 2 3 2 4 8 3 6 15 4 8 5 10 6 12 양창모 ( 청주교육대학교컴퓨터교육과 ) Problems and Algorithms 2015 년여름 9 / 35

데이터표채우기 쌍의수 돌의수 최소이동횟수 1 2 3 2 4 8 3 6 15 4 8 5 10 6 12 숫자들사이에패턴을찾을수있는가? 양창모 ( 청주교육대학교컴퓨터교육과 ) Problems and Algorithms 2015 년여름 10 / 35

숫자들사이의패턴 1 2 + 2 1 = 3? 2 2 + 2 2 = 8? 3 2 + 2 3 = 15? 양창모 ( 청주교육대학교컴퓨터교육과 ) Problems and Algorithms 2015 년여름 11 / 35

쌍의수 돌의수 최소이동횟수 다른표현 1 2 3 1 2 + 2 1 2 4 8 2 2 + 2 2 3 6 15 3 2 + 2 3 4 8 24 4 2 + 2 4 5 10 35 5 2 + 2 5 6 12 48 6 2 + 2 6 n 2n n 2 + 2n n(n + 2) 양창모 ( 청주교육대학교컴퓨터교육과 ) Problems and Algorithms 2015 년여름 12 / 35

Figure: 흰돌과검은돌이각각 2 개일경우위치를바꾸는과정 양창모 ( 청주교육대학교컴퓨터교육과 ) Problems and Algorithms 2015 년여름 13 / 35

돌세개씩 2 조자리바꾸기 1 Move the piece in square 2 to square 3. 2 Jump the piece in square 4 to square 2. 3 Move the piece in square 5 to square 4. 4 Jump the piece in square 3 to square 5. 5 Jump the piece in square 1 to square 3. 6 Move the piece in square 0 to square 1. 7 Jump the piece in square 3 to square 0. 8 Jump the piece in square 4 to square 2. 9 Jump the piece in square 6 to square 4. 10 Move the piece in square 5 to square 6. 11 Jump the piece in square 3 to square 5. 12 Jump the piece in square 1 to square 3. 13 Move the piece in square 2 to square 1. 14 Jump the piece in square 4 to square 2. 15 Move the piece in square 3 to square 4. 양창모 ( 청주교육대학교컴퓨터교육과 ) Problems and Algorithms 2015 년여름 14 / 35

돌의개수에영향을받지않는방법즉, 알고리즘을찾자. 패턴을찾아야한다. 패턴을쉽게찾기위하여숫자대신색으로표시한다. 데이터가많을수록패턴을찾기쉬우므로흰돌과검은돌이각각 4 개일때자리바꾸기를살펴보자. 양창모 ( 청주교육대학교컴퓨터교육과 ) Problems and Algorithms 2015 년여름 15 / 35

돌의개수에영향을받지않는방법즉, 알고리즘을찾자. 패턴을찾아야한다. 패턴을쉽게찾기위하여숫자대신색으로표시한다. 데이터가많을수록패턴을찾기쉬우므로흰돌과검은돌이각각 4 개일때자리바꾸기를살펴보자. 양창모 ( 청주교육대학교컴퓨터교육과 ) Problems and Algorithms 2015 년여름 15 / 35

돌의개수에영향을받지않는방법즉, 알고리즘을찾자. 패턴을찾아야한다. 패턴을쉽게찾기위하여숫자대신색으로표시한다. 데이터가많을수록패턴을찾기쉬우므로흰돌과검은돌이각각 4 개일때자리바꾸기를살펴보자. 양창모 ( 청주교육대학교컴퓨터교육과 ) Problems and Algorithms 2015 년여름 15 / 35

돌의개수에영향을받지않는방법즉, 알고리즘을찾자. 패턴을찾아야한다. 패턴을쉽게찾기위하여숫자대신색으로표시한다. 데이터가많을수록패턴을찾기쉬우므로흰돌과검은돌이각각 4 개일때자리바꾸기를살펴보자. 양창모 ( 청주교육대학교컴퓨터교육과 ) Problems and Algorithms 2015 년여름 15 / 35

문제를푸는유용한방법문제를단순하게만든다. 중요하지않은것을제거한다추상화 abstraction. 동일한것을하나로묶는다패키지로만들기 packaging. 문제를작게나누어푼다분할정복 divide and conquor. 양창모 ( 청주교육대학교컴퓨터교육과 ) Problems and Algorithms 2015 년여름 16 / 35

흰돌과검은돌이각각 4 개일때바꾸기 1 Slide the white piece. 16 Jump the black piece. 2 Jump the black piece. 17 Jump the black piece. 3 Slide the black piece. 18 Jump the black piece. 4 Jump the white piece. 19 Slide the white piece. 5 Jump the white piece. 20 Jump the white piece. 6 Slide the white piece. 21 Jump the white piece. 7 Jump the black piece. 22 Slide the black piece. 8 Jump the black piece. 23 Jump the black piece. 9 Jump the black piece. 24 Slide the white piece. 10 Slide the black piece. 11 Jump the white piece. 12 Jump the white piece. 13 Jump the white piece. 14 Jump the white piece. 15 Slide the black piece. 양창모 ( 청주교육대학교컴퓨터교육과 ) Problems and Algorithms 2015 년여름 17 / 35

흰돌과검은돌이각각 3 개일때위치정보를제거하여다시쓰자. 1 Slide the white piece. 2 Jump the black piece. 3 Slide the black piece. 4 Jump the white piece. 5 Jump the white piece. 6 Slide the white piece. 7 Jump the black piece. 8 Jump the black piece. 9 Jump the black piece. 10 Slide the white piece. 11 Jump the white piece. 12 Jump the white piece. 13 Slide the black piece. 14 Jump the black piece. 15 Slide the white piece. 양창모 ( 청주교육대학교컴퓨터교육과 ) Problems and Algorithms 2015 년여름 18 / 35

패턴을찾을수있는가? 일반적인문제에대한해를찾으려면패턴을찾아야한다. 패턴 양창모 ( 청주교육대학교컴퓨터교육과 ) Problems and Algorithms 2015 년여름 19 / 35

패턴을찾을수있는가? 일반적인문제에대한해를찾으려면패턴을찾아야한다. 패턴 양창모 ( 청주교육대학교컴퓨터교육과 ) Problems and Algorithms 2015 년여름 19 / 35

패턴을찾을수있는가? 일반적인문제에대한해를찾으려면패턴을찾아야한다. 패턴 양창모 ( 청주교육대학교컴퓨터교육과 ) Problems and Algorithms 2015 년여름 19 / 35

패턴찾기 - 하나를밀고몇번뛰어넘는다. 1 Slide the white piece. 2 Jump the black piece. 3 Slide the black piece. 4 Jump the white piece. 5 Jump the white piece. 6 Slide the white piece. 7 Jump the black piece. 8 Jump the black piece. 9 Jump the black piece. 10 Slide the white piece. 11 Jump the white piece. 12 Jump the white piece. 13 Slide the black piece. 14 Jump the black piece. 15 Slide the white piece. 양창모 ( 청주교육대학교컴퓨터교육과 ) Problems and Algorithms 2015 년여름 20 / 35

패턴찾기 - 하나를밀고몇번뛰어넘는다. 1 Slide the white piece. 16 Jump the black piece. 2 Jump the black piece. 17 Jump the black piece. 3 Slide the black piece. 18 Jump the black piece. 4 Jump the white piece. 19 Slide the white piece. 5 Jump the white piece. 20 Jump the white piece. 6 Slide the white piece. 21 Jump the white piece. 7 Jump the black piece. 22 Slide the black piece. 8 Jump the black piece. 23 Jump the black piece. 9 Jump the black piece. 24 Slide the white piece. 10 Slide the black piece. 11 Jump the white piece. 12 Jump the white piece. 13 Jump the white piece. 14 Jump the white piece. 15 Slide the black piece. 양창모 ( 청주교육대학교컴퓨터교육과 ) Problems and Algorithms 2015 년여름 21 / 35

패턴찾기 - 하나를밀고몇번뛰어넘는다. 1 Slide the white piece. 1 Slide the white piece. 2 Jump the black piece. 2 Jump 1 black piece. 3 Slide the black piece. 3 Slide the black piece. 4 Jump the white piece. 4 Jump 2 white pieces. 5 Jump the white piece. 전반부 6 Slide the white piece. 5 Slide the white piece. 7 Jump the black piece. 6 Jump 3 black pieces. 8 Jump the black piece. 9 Jump the black piece. 10 Slide the white piece. 7 Slide the white piece. 11 Jump the white piece. 8 Jump 2 white pieces. 12 Jump the white piece. 후반부 13 Slide the black piece. 9 Slide the black piece. 14 Jump the black piece. 10 Jump the black piece. 15 Slide the white piece. 11 Slide the white piece. 양창모 ( 청주교육대학교컴퓨터교육과 ) Problems and Algorithms 2015 년여름 22 / 35

패턴찾기 - 하나를밀고몇번뛰어넘는다. 흰돌과검은돌이각각 3 개일때 ( 밀기 1번 뛰어넘기 1번 ) ( 밀기 1번 뛰어넘기 2번 ) ( 밀기 1번 뛰어넘기 3번 ) ( 밀기 1번 뛰어넘기 2번 ) ( 밀기 1번 뛰어넘기 1번 ) ( 밀기 1번 뛰어넘기 0번 ) 흰돌과검은돌이각각 4 개일때 ( 밀기 1번 뛰어넘기 1번 ) ( 밀기 1번 뛰어넘기 2번 ) ( 밀기 1번 뛰어넘기 3번 ) ( 밀기 1번 뛰어넘기 4번 ) ( 밀기 1번 뛰어넘기 3번 ) ( 밀기 1번 뛰어넘기 2번 ) ( 밀기 1번 뛰어넘기 1번 ) ( 밀기 1번 뛰어넘기 0번 ) 양창모 ( 청주교육대학교컴퓨터교육과 ) Problems and Algorithms 2015 년여름 23 / 35

패턴찾기 - 하나를밀고몇번뛰어넘는다. 흰돌과검은돌이각각 3 개일때 ( 밀기 1번 뛰어넘기 1번 ) ( 밀기 1번 뛰어넘기 2번 ) ( 밀기 1번 뛰어넘기 3번 ) ( 밀기 1번 뛰어넘기 2번 ) ( 밀기 1번 뛰어넘기 1번 ) ( 밀기 1번 뛰어넘기 0번 ) 흰돌과검은돌이각각 4 개일때 ( 밀기 1번 뛰어넘기 1번 ) ( 밀기 1번 뛰어넘기 2번 ) ( 밀기 1번 뛰어넘기 3번 ) ( 밀기 1번 뛰어넘기 4번 ) ( 밀기 1번 뛰어넘기 3번 ) ( 밀기 1번 뛰어넘기 2번 ) ( 밀기 1번 뛰어넘기 1번 ) ( 밀기 1번 뛰어넘기 0번 ) 양창모 ( 청주교육대학교컴퓨터교육과 ) Problems and Algorithms 2015 년여름 23 / 35

패턴찾기 - 하나를밀고몇번뛰어넘는다. 흰돌과검은돌이각각 n( 4) 개일때 ( 밀기 1번 뛰어넘기 1번 ) ( ) ( 밀기 1번 뛰어넘기 x번 ) ( 밀기 1번 뛰어넘기 y번 ) ( ) ( 밀기 1번 뛰어넘기 2번 ) ( 밀기 1번 뛰어넘기 1번 ) 밀기 1번 ) 양창모 ( 청주교육대학교컴퓨터교육과 ) Problems and Algorithms 2015 년여름 24 / 35

패턴찾기 - 하나를밀고몇번뛰어넘는다. 흰돌과검은돌이각각 n( 1) 개일때뛰어넘기횟수를 1부터 n 까지 1씩증가시켜가면서밀기와뛰어넘기를한다. ( 밀기 1번 뛰어넘기 1번 ) ( 밀기 1번 뛰어넘기 2 번 ) ( ) ( 밀기 1번 뛰어넘기 x번 ) 뛰어넘기횟수를 n 부터 1까지 1씩감소시켜가면서밀기와뛰어넘기를한다. ( 밀기 1번 뛰어넘기 n 1번 ) ( 밀기 1번 뛰어넘기 n 2 번 ) ( ) ( 밀기 2번 뛰어넘기 1번 ) ( 밀기 1번 뛰어넘기 1번 ) 양창모 ( 청주교육대학교컴퓨터교육과 ) Problems and Algorithms 2015 년여름 25 / 35

패턴찾기 - 하나를밀고몇번뛰어넘는다. 흰돌과검은돌이각각 n( 1) 개일때전반부뛰어넘기횟수를 1부터 n 까지 1씩증가시켜가면서밀기와뛰어넘기를한다. 후반부뛰어넘기횟수를 n 1 부터 0까지 1씩감소시켜가면서밀기와뛰어넘기를한다. 양창모 ( 청주교육대학교컴퓨터교육과 ) Problems and Algorithms 2015 년여름 26 / 35

패턴찾기 - 하나를밀고몇번뛰어넘는다. 흰돌과검은돌이각각 n( 1) 개일때 전반부 밀기횟수 Σ n i=1 1 = n, 뛰어넘기횟수 Σn i=1 i = n(n+1) 2 후반부 밀기횟수 Σ 0 i=n 1 = 1, 뛰어넘기횟수 Σ1 i=n 1 i = n(n 1) 2 양창모 ( 청주교육대학교컴퓨터교육과 ) Problems and Algorithms 2015 년여름 27 / 35

뛰어넘기 - 밀기쌍을반복하는것을다음과같이표현할수있다. Figure: 뛰어넘기 - 밀기쌍을반복을표현하는 Pseudo Code 양창모 ( 청주교육대학교컴퓨터교육과 ) Problems and Algorithms 2015 년여름 28 / 35

뛰어넘는횟수를기억하기위한변수 counter 가필요하다. Figure: 전반부의밀기 - 뛰어넘기쌍을반복을표현하는 Pseudo Code 양창모 ( 청주교육대학교컴퓨터교육과 ) Problems and Algorithms 2015 년여름 29 / 35

패턴찾기 - 흰색과검은색을번갈아밀고뛰어넘긴다. 전반부에는뛰어넘기 - 밀기색이다르다. 후반부에는같은색을뛰어넘기 - 밀기색이같고번갈아가면서한다. 1 Slide the white piece. 2 Jump 1 black piece. 3 Slide the black piece. 전반부 4 Jump 2 white pieces. 5 Slide the white piece. 6 Jump 3 black pieces. 7 Slide the white piece. 8 Jump 2 white pieces. 9 Slide the black piece. 후반부 10 Jump the black piece. 11 Slide the white piece. 양창모 ( 청주교육대학교컴퓨터교육과 ) Problems and Algorithms 2015 년여름 30 / 35

패턴찾기 - 흰색과검은색을번갈아밀고뛰어넘긴다. 1 Slide the white piece. 16 Jump the black piece. 2 Jump the black piece. 17 Jump the black piece. 3 Slide the black piece. 18 Jump the black piece. 4 Jump the white piece. 19 Slide the white piece. 5 Jump the white piece. 20 Jump the white piece. 6 Slide the white piece. 21 Jump the white piece. 7 Jump the black piece. 22 Slide the black piece. 8 Jump the black piece. 23 Jump the black piece. 9 Jump the black piece. 24 Slide the white piece. 10 Slide the black piece. 11 Jump the white piece. 12 Jump the white piece. 13 Jump the white piece. 14 Jump the white piece. 15 Slide the black piece. 양창모 ( 청주교육대학교컴퓨터교육과 ) Problems and Algorithms 2015 년여름 31 / 35

알고리즘의전반부만들기 각반복마다미는색과건너뛰는색을바꾸어야하므로 Figure: 색을고려한알고리즘의전반부 양창모 ( 청주교육대학교컴퓨터교육과 ) Problems and Algorithms 2015 년여름 32 / 35

알고리즘의전반부만들기 Figure: 색을고려한알고리즘의전반부 양창모 ( 청주교육대학교컴퓨터교육과 ) Problems and Algorithms 2015 년여름 33 / 35

알고리즘의후반부만들기 건너뛰는횟수 양창모 ( 청주교육대학교컴퓨터교육과 ) Problems and Algorithms 2015 년여름 34 / 35

알고리즘의후반부만들기 미는색과건너뛰는색 양창모 ( 청주교육대학교컴퓨터교육과 ) Problems and Algorithms 2015 년여름 35 / 35

알고리즘의후반부만들기 양창모 ( 청주교육대학교컴퓨터교육과 ) Problems and Algorithms 2015 년여름 36 / 35

알고리즘의후반부만들기 양창모 ( 청주교육대학교컴퓨터교육과 ) Problems and Algorithms 2015 년여름 37 / 35