인공신경망 Perceptron 효과적으로 출력값을 계산하는 방법은?
1. 문제
25341번: 인공 신경망
첫째 줄에 입력층의 입력 크기 $N$, 은닉층의 인공 신경 개수 $M$, 출력값을 계산해야 하는 횟수 $Q$가 공백으로 구분되어 주어진다. $(1 \leq N,M,Q \leq 2\,000)$ 둘째 줄부터 $M$번째 줄에 걸쳐 은닉층의
www.acmicpc.net
인공 신경망의 가중치와 편향이 주어지고 입력값이 주어질때 출력값을 계산하면 되는 문제
2. 풀이
이게 어렵나? 생각하고 덤볐는데 엄청 어렵네..?
처음에는 그냥 문제에서 주어진대로... 정직하게 구현했다
인공신경망 m줄을 입력받고...
입력되는 가중치 개수, 입력값 순서들, 가중치들, 편향으로 주어지니까
이걸 짤라서 리스트에 나눠 담았지
from sys import stdin
n,m,q = map(int,stdin.readline().split())
neural_list = []
bias_list = []
input_neural_list = []
for _ in range(m):
neural = list(map(int,stdin.readline().split()))
c = neural[0] #신경망 입력 개수
input_neural = []
for i in range(c):
input_neural.append(neural[1:][i]-1)
input_neural_list.append(input_neural)
neural_weight = []
for i in range(c):
neural_weight.append(neural[1+c:][i])
neural_list.append(neural_weight)
bias_list.append(neural[-1])
그리고 다음 줄은 출력층의 인공신경망 가중치, 편향이 주어진다니까
final_neural = list(map(int,stdin.readline().split()))
final_weight = final_neural[:-1]
final_bias = final_neural[-1]
이걸 받고,... 이제 q줄만큼 질문이 주어지니까
은닉층 먼저 계산해서 리스트에 순서대로 담고
리스트 다 담으면 출력층에서 계산해서 프린트 하는걸로
for _ in range(q):
input_list = list(map(int,stdin.readline().split()))
output_list = []
final_output = 0
#은닉층에서 계산
for weight,bias,input_loc in zip(neural_list,bias_list,input_neural_list):
output_value = 0
for loc,w in zip(input_loc,weight):
output_value += input_list[loc]*w
output_value += bias
output_list.append(output_value)
#출력층 계산
for output_value,weight in zip(output_list,final_weight):
final_output += (output_value*weight)
final_output += final_bias
print(final_output)
근데 당연히 시간 초과다...
그래서 쓸모없는 연산을 많이 했나보다 했는데..
질문이 여러개 주어질때 시간안에 문제를 해결할려면 가장 기본적인 전략은
매 질문마다 똑같은 연산을 반복해서 수행하면 낭비라는 것
똑같은 연산은 질문을 처리하기 전에 미리 해두고
매 질문에는 서로 다른 연산만 수행해야한다는 점이다
예를 들어 위와 같이 인공 신경망이 주어진다고 생각해보자.
출력층 Y가 어떻게 계산되는지 생각해본다면...
$A_{1} = x_{1}w_{1} + x_{2}w_{2} + b_{1}$
$A_{2} = x_{1}w_{1} + x_{3}w_{3} + b_{2}$
$A_{3} = x_{2}w_{2} + x_{3}w_{3} + b_{3}$
가 출력층으로 들어가면..
$Y= A_{1}k_{1} + A_{2}k_{2} + A_{3}k_{3} + b_{4}$
그런데 처음에 입력으로 주어지는 값이 w, b, k이다.
그리고 매 질문마다 x값이 달라지는것이고
그러니까 x값은 컨트롤 할수 없더라도 w,b,k는 질문을 처리하기 전에 미리 정리해둔다면.. 시간을 아낄 수 있을 것이다
$A_{1}k_{1} = x_{1}w_{1}k_{1} + x_{2}w_{2}k_{1} + b_{1}k_{1}$
$A_{2}k_{2} = x_{1}w_{1}k_{2} + x_{3}w_{3}k_{2} + b_{2}k_{2}$
$A_{3}k_{3} = x_{2}w_{2}k_{3} + x_{3}w_{3}k_{3} + b_{3}k_{3}$
따라서 wk를 계산한 리스트를 구하고, bk를 계산한 리스트를 담아둔다면...?
그러면 wk를 계산한 리스트를 순회해서 여기에는 순서에 맞는 input값을 곱해주기만 하면... 될 것 같다
그래서 마지막 출력층을 입력받고 나서, wk를 계산하기로 했지
final_neural = list(map(int,stdin.readline().split()))
for i in range(m):
for j in range(len(neural_list[i])):
neural_list[i][j] = final_neural[i] * neural_list[i][j]
bias_list[i] = bias_list[i] * final_neural[i]
그러면 neural_list에는 wk가 있고 bias_list에는 bk가 있으니까...
질문 처리할때도 반복문 줄어들어서 시간좀 줄어들것 같았는데
for _ in range(q):
input_list = list(map(int,stdin.readline().split()))
final_output = 0
for weight,bias,input_loc in zip(neural_list,bias_list,input_neural_list):
output_value = 0
for loc,w in zip(input_loc,weight):
output_value += input_list[loc]*w
output_value += bias
final_output += output_value
final_output += final_neural[-1]
print(final_output)
여전히 통과 못해..
다른데서 쓸데없는 연산을 수행했나??
for _ in range(m):
neural = list(map(int,stdin.readline().split()))
c = neural[0] #신경망 입력 개수
input_neural = []
for i in range(c):
input_neural.append(neural[1:][i]-1)
input_neural_list.append(input_neural)
neural_weight = []
for i in range(c):
neural_weight.append(neural[1+c:][i])
neural_list.append(neural_weight)
bias_list.append(neural[-1])
input부분에서 for i in range(c):를 너무 남발한것 같더라고..
저걸 없앨 수 있을 것 같아
for _ in range(m):
neural = list(map(int,input().split()))
c = neural[0] #신경망 입력 개수
input_neural = []
neural_weight = []
for i in range(c):
input_neural.append(neural[1:][i]-1)
neural_weight.append(neural[1+c:][i])
input_neural_list.append(input_neural)
neural_list.append(neural_weight)
bias_list.append(neural[-1])
근데 append()가 O(1)이니까 큰 차이 없는 것 같기는 한디..
이번엔 wk와 bk계산할때..
final_neural = list(map(int,stdin.readline().split()))
for i in range(m):
for j in range(len(neural_list[i])): ##매번 len()을 쓴다고?
neural_list[i][j] = final_neural[i] * neural_list[i][j]
bias_list[i] = bias_list[i] * final_neural[i]
매번 len()함수를 써버리면... 최악의 경우 O(2000)이라 시간좀 쓸것 같더라고
어차피 입력에서 첫번째 값이 가중치 개수라서.. 그거 쓰면 없앨 수 있을 것 같아
len_list = []
for _ in range(m):
neural = list(map(int,stdin.readline().split()))
c = neural[0] #신경망 입력 개수
len_list.append(c) #입력 개수를 리스트에 담아두고..
input_neural = []
neural_weight = []
for i in range(c):
input_neural.append(neural[1:][i]-1)
neural_weight.append(neural[1+c:][i])
input_neural_list.append(input_neural)
neural_list.append(neural_weight)
bias_list.append(neural[-1])
final_neural = list(map(int,stdin.readline().split()))
for i in range(m):
for j in range(len_list[i]): #len함수는 피하자고
neural_list[i][j] = final_neural[i] * neural_list[i][j]
bias_list[i] = bias_list[i] * final_neural[i]
물론 여전히 통과는 못해...
그 뒤로 여러번 고민한 결과... 출력층 계산에 전개를 덜 했다는 걸 깨달았다
$A_{1}k_{1} = x_{1}w_{1}k_{1} + x_{2}w_{2}k_{1} + b_{1}k_{1}$
$A_{2}k_{2} = x_{1}w_{1}k_{2} + x_{3}w_{3}k_{2} + b_{2}k_{2}$
$A_{3}k_{3} = x_{2}w_{2}k_{3} + x_{3}w_{3}k_{3} + b_{3}k_{3}$
여기서 wk, bk를 미리 구해놓는다는 것은 좋았지만...
이게 조금 더 미리 계산을 해보면
$Y= A_{1}k_{1} + A_{2}k_{2} + A_{3}k_{3} + b_{4}$가 이렇게 되니까..
$Y = x_{1}w_{1}k_{1} + x_{2}w_{2}k_{1} + b_{1}k_{1} + x_{1}w_{1}k_{2} + x_{3}w_{3}k_{2} + b_{2}k_{2} + x_{2}w_{2}k_{3} + x_{3}w_{3}k_{3} + b_{3}k_{3} + b_{4}$
를 정리해보자고..
$Y = x_{1}(w_{1}k_{1}+w_{1}k_{2}) + x_{2}(w_{2}k_{1}+w_{2}k_{3}) + x_{3}(w_{3}k_{2}+w_{3}k_{3}) +b_{1}k_{1}+ b_{2}k_{2} + b_{3}k_{3} + b_{4}$
따라서 입력으로 주어지는 은닉층, 출력층 인공신경망 가중치, 편향은 일정하므로, 질문을 처리하기 전에
$[w_{1}k_{1}+w_{1}k_{2}, w_{2}k_{1}+w_{2}k_{3}, w_{3}k_{2}+w_{3}k_{3}]$
형태로 정리해둔다면?
질문으로 주어지는 입력 데이터 $[a_{0}, a_{1}, a_{2}]$가 들어오면... 미리 계산해둔 저 리스트에
인덱스로 순회해서 대응하는 원소끼리 곱한다음에 더해주기만 하면 끝이다
그러면 저렇게 어떻게 정리해둬??
우리는 입력값으로 input data가 어디 출력층에 들어가는지도 입력을 받는다
크기가 n+1인 0이 들어간 리스트로 초기화하고, 해당 출력층에 들어가는 위치를 index로 해서 wk를 누적합해주면 그만이다
all_neural_list = [0]*(n+1)
for i in range(m):
c = neural_list[i][0]
final_bias += (neural_list[i][-1] * final_neural[i])
for j in range(c):
all_neural_list[neural_list[i][1+j]-1] += final_neural[i]*neural_list[i][1+c+j]
그러면 이제 통과가능..
from sys import stdin
n,m,q = map(int,stdin.readline().split())
neural_list = []
#m개의 은닉층 인공신경망을 입력받는다
for _ in range(m):
neural = list(map(int,stdin.readline().split()))
neural_list.append(neural)
#출력층 인공신경망
final_neural = list(map(int,stdin.readline().split()))
#출력층 인공신경망 마지막 원소는 bias
final_bias = final_neural[-1]
#크기가 n+1인 빈 리스트 초기화
#wk를 구해서 해당 위치에 맞게 넣어줄 것
all_neural_list = [0]*(n+1)
#m개의 출력층 인공신경망을 순회해서
for i in range(m):
c = neural_list[i][0] #가중치 개수
#bias의 총합 bk는 하나의 항으로 계산되므로 계속 누적합 시켜준다
final_bias += (neural_list[i][-1] * final_neural[i])
#input data가 들어가는 위치를 index로 해서
#wk를 누적합 시켜준다
for j in range(c):
all_neural_list[neural_list[i][1+j]-1] += final_neural[i]*neural_list[i][1+c+j]
for _ in range(q):
input_list = list(map(int,stdin.readline().split()))
#bk의 총합 + b를 구해준다.
final_output = final_bias
#xwk를 구해준다
for i in range(n):
final_output += (all_neural_list[i] * input_list[i])
print(final_output) #최종값은 xwk + bk + b
3. 되돌아보기..
어떻게 보면 알고리즘 해결의 가장 기본이지
"중복되는 계산은 1번만 한다"
"수많은 질문을 처리하기 전에 중복되는 계산은, 미리 해둔다"
간단한 사칙연산이지만... 미리 계산해둔다면 효율적으로 계산할 수 있다
마지막 최적화 아이디어가 조금 중요했다고 본다..
빈 배열 초기화해서 input값이 곱해지는 위치에 맞는 인덱스에 wk를 누적합 시켜주는..
all_neural_list = [0]*(n+1)
for i in range(m):
c = neural_list[i][0]
final_bias += (neural_list[i][-1] * final_neural[i])
for j in range(c):
all_neural_list[neural_list[i][1+j]-1] += final_neural[i]*neural_list[i][1+c+j]
'알고리즘 > 구현,시뮬레이션' 카테고리의 다른 글
| 문자열 정렬할 때 실수하기 쉬운부분 복기하기 -줄서기- (0) | 2023.01.29 |
|---|---|
| 1차원 convolution 연산을 효율적으로 하는 계산하는 방법은? (0) | 2022.12.10 |
| 프로그래밍으로 뱀을 만드는 방법? -뱀- (0) | 2022.11.13 |
| 주사위를 구현하는 방법 - 주사위 굴리기 - (0) | 2022.11.12 |
| 조금 더 어려운 시뮬레이션 연습하기 -미세먼지 안녕!- (0) | 2022.11.08 |
