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

deep neural network에서의 backpropagation backpropagation 원래 backpropagation(역전파)는 학습 방식이 아니라 perceptron에서 loss function의 기울기를 계산하는 알고리즘을 뜻하지만, 넓은 의미에서는 기울기를 이용한 학습 방식으로 쓰인다. 참고 : https://en.wikipedia.org/wiki/Backpropagation delta rule https://en.wikipedia.org/wiki/Delta_rule delta rule의 정의와 증명 delta rule은 backpropagation 방법 중 하나이다. delta rule은 왜 multi-layer에서 사용할 수 없는가... 본론5에서와 같이 처음에는 신경망학습에서 d..

theta가 필요한 이유 위의 그림은 theta가 없을 때의 연산을 나타낸 것이다. 이 때 활성화 함수가 sigmoid라면 입력이 (0,0)일 때 출력이 다른 수가 나오는 경우를 만족할 수 있을까? theta가 없다면 net은 입력이 (0,0)일 때 항상 0이다. 따라서 출력은 sigmoid 함수를 거쳐 항상 1/2 이 나온다. (0,0)의 입력에서 다른 출력이 나오게 하려면 sigmoid 함수를 output축(y축) 방향으로 움직일 수 있어야한다. 이 역할을 위해서 theta는 존재하는 것이다! net = x1*w1 + x2*x2 + theta , O = f(net) = f(theta) 이므로 theta 만큼 그래프를 net축으로 이동한 것처럼 생각할 수 있다. 왼쪽 기존의 sigmoid 함수에서 (0..

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

신경망의 원리 이제 multi-layer perceptron을 이용할 수 있게 되었지만, 정확히 구동시키기 위해 알아야할 것이 있다. 주어진 input을 가지고 계산을 해서 output을 낼 수는 있지만, output 값이 주어진 정답과 다를 때 학습하는 기능을 아직 구현하지 못했다. 여기서 학습이란 w값을 조정하는 것을 말한다. w값을 조정하는 학습을 하기 위해서는 랜덤, 조금씩 옮겨보기 의 방식보다는 미분을 사용하는 것이 좋다. w에 대한 Error의 미분값을 구한 후 반대쪽으로 일정치만큼 움직여야 하므로 Error를 w의 식으로 나타낼 수 있어야 하고, 조정되는 w의 값을 이와 관련하여 표현할 수 있어야한다. 결국 error를 줄이기 위해 w값을 조정하는 과정에 error에 대한 w의 미분값이 필요..