이진 신경망

인공 신경망(흔히 신경망이라고 부른다)은 생물학적 신경망에서 착안한 수학적 모델이다. 신경망은 서로 연결된 인공 뉴런의 집단으로 이루어져 있으며, 연결주의적 계산 방식으로 정보를 처리한다.

뉴런이 층이라는 집단으로 묶여 있으면 그 신경망을 층 구조 신경망이라고 한다. 같은 층에 속한 두 뉴런 사이에는 연결이 없다.

신경망에 있는 뉴런의 수를 $q$라 하고 뉴런에 $1$부터 $q$까지 차례로 양의 정수를 붙이자. 뉴런 $i$와 뉴런 $j$ 사이의 연결은 연결 가중치 $w_{i, j}$로 나타낼 수 있다.

신경망은 방향성 비순환 그래프로 나타낼 수 있다. 뉴런은 정점에, 뉴런 사이의 연결은 간선에 대응되며, 각 연결의 연결 가중치는 대응하는 간선의 가중치가 된다.

위 그림의 신경망은 네 개의 층으로 이루어져 있다. 첫 번째 층에는 뉴런 $1$, $2$, $3$이, 두 번째 층에는 뉴런 $4$, $5$가, 세 번째 층에는 뉴런 $6$, $7$, $8$이, 네 번째 층에는 뉴런 $9$ 하나만 있다.

각 뉴런 $i$는 값 $v_{i}$를 가지며, 이 값은 다음 식으로 계산된다.

$v_{i} = \frac{1}{1 + e^{- \sum_{j}^{ } v_{j} \cdot w_{j, i}}}$

층 구조 신경망이 다음 성질을 만족하면 이진 신경망이라고 한다.

• 첫 번째 층의 각 뉴런 $i$의 값 $v_{i}$는 $0$ 또는 $1$이다.
• 뉴런 $a$가 층 $i$에 속하고 뉴런 $b$가 층 $j$에 속하며 $i > j$이면, 뉴런 $a$에서 뉴런 $b$로 가는 연결은 없다. 뉴런 $b$에서 뉴런 $a$로 가는 연결은 가능하다.
• 마지막 층에는 뉴런이 하나만 있고 그 값은 $0$ 또는 $1$이다.
• 각 층에는 뉴런이 하나 이상 있다.

이 문제에서는 $n$개의 인자 $x_{1}$, $x_{2}$, $\ldots$, $x_{n}$을 갖는 이진 함수 $f(x_{1}$, $x_{2}$, $\ldots$ $x_{n})$를 구현하는 이진 신경망을 만들어야 한다.

이 이진 신경망의 첫 번째 층에는 $1$부터 $n$까지 차례로 양의 정수가 붙은 뉴런이 정확히 $n$개 있어야 한다. 뉴런 $i$의 값은 자동으로 $x_{i}$로 정해진다. 나머지 뉴런에는 $n + 1$부터 $q$까지 차례로 양의 정수를 붙인다. 여기서 $q$는 신경망에 있는 뉴런의 수이다. 모든 값 $v_{i}$($n + 1 \leq i \leq q$)는 위에서 주어진 식으로 계산된다.

이 이진 신경망의 마지막 층에는 뉴런이 하나만 있어야 한다. 이 뉴런의 값은 $f(x_{1}$, $x_{2}$, $\ldots$, $x_{n})$와 $10^{-7}$ 이하만큼 차이가 나야 한다.

이진 신경망의 층 수는 $25$를 넘지 않아야 한다. 뉴런의 수 $q$는 $10^{4}$를 넘지 않아야 한다. 연결의 총 개수 $e$는 $3 \cdot 10^{4}$를 넘지 않아야 한다.

첫째 줄에 정수 $n$이 주어진다($2 \leq n \leq 10$). 둘째 줄에 $2^{n}$개의 문자가 주어진다. 각 문자는 '0' 또는 '1'이다. 첫 번째 문자는 $f(0, \ldots, 0, 0)$의 값을, 두 번째 문자는 $f(0, \ldots, 0, 1)$의 값을 나타내는 식으로, 마지막 문자는 $f(1, \ldots, 1, 1)$의 값을 나타낸다.

첫째 줄에 이진 신경망의 층 수 $l$과 뉴런의 수 $q$를 출력한다($2 \leq l \leq 25$, $1 \leq q \leq 10^{4}$).

둘째 줄에 $q$개의 정수 $p_{i}$를 출력한다. $p_{i}$는 뉴런 $i$가 속한 층의 번호이다($1 \leq p_{i} \leq l$).

셋째 줄에 이진 신경망의 연결 개수 $e$를 출력한다($n \leq e \leq 3 \cdot 10^{4}$).

다음 $e$개의 줄 각각에 정수 $a_{i}$, $b_{i}$와 실수 $w_{a, b}$를 출력한다. 이는 $a_{i}$에서 $b_{i}$로 가는 가중치 $w_{a, b}$의 연결을 나타낸다($|w_{a,b}| \le 1000$).