컴퓨터과학에서 말하는 problem

1. definition

 

problem이란 최종적으로 바라는 것과 현재 인식하는 것의 차이

 

machine learning 문제에서는 target<바라는 것>과 prediction<현재 인식하는 것>의 차이는 loss로 주어지고 이것이 문제 problem이다.

 

loss를 0으로 보내려고하는 것이 problem solving이고 보낼 때 사용한 수단이 solution

 

2. example

 

$x^{2} + 2x + 1 = 0$으로부터 x가 얼마인지 구하려는 문제가 주어졌다면

 

현재 인식하고 있는 상태인 $x^{2} + 2x + 1 = 0$이 initial state

 

최종적으로 구하고자하는 x=-1이 terminal state

 

initial state와 terminal state의 차이가 problem

 

initial state부터 한 단계, 한 단계 나아가는 과정이 decision

 

 

 

팩맨 게임, 스타크래프트, 바둑 같은 것도 initial state에서 terminal state로 나아가는 problem solving 과정이다.

 

 

3. bubble sort

 

bubble sort는 뒤섞인 리스트 배열에서 크기 순으로 정렬시키는 알고리즘

 

위에서부터 연속하는 2개씩 비교하여 앞의 것이 작으면 그대로 두고 크면 순서를 바꿈

 

initial state 3,6,2,9,5에서 bubble sort를 이용하여 2,3,5,6,9라는 terminal state로 가고 싶은 것

 

3,6을 보면 3이 작으니 그대로 두고 6,2로 이동

 

6이 더 크니까 2,6으로 순서를 바꿈

 

6,9로 이동하면 6이 더 작으니 그대로 두고 다음으로 이동

 

9,5에서 9가 더 크니까 순서를 바꿔 5,9로 만들고 처음부터 다시 시작

 

반복하면 2,3,5,6,9를 얻고 $O(N^{2})$의 계산 비용이 들어간다고 함

 

bubble sort 알고리즘 그림

 

 

이런 계산을 사람이 하다가 너무 힘들어서 자동으로 해주길 바라는 마음에서 컴퓨터가 등장함

 

컴퓨터는 initial state에서 유한 번의 decision을 자동으로 해줘서 terminal state까지 이동시켜주는 기계임