이런 글은 술 먹지 않고 진지하게 써야 하는데

혼술을 하고 아무것도 할 게 없을때 쓰는게 유머네.

코드포스 레드는 고사하고 블루 턱걸이 하는 놈이

전산수학이 어쩌구저쩌구 쓰는 것도 유머고.

 

0) 들어가기 전에

전산 수학은 참 재미있는 가정을 가지고 세상을 해석한다.

 

a. 비교는 2개 끼리만 가능하다.

사람은 슥 훑어보고 뭐가 젤 큰지 근사치를 낼 수 있다.

사람은 본능적으로 집단 을 단위로 평가할 수 있지만,

전산 수학에서는 이 평과과정이 2 개체 끼리 비교하는 것을 가정한다.

이로 인해서 정렬이나 최대/최소값 추출 방식이 직감과 많이 달라진다.

 

b. 절대 잊지 않는다.

전산수학은 결국 요약하면,

- 횡/종 중 어느 방향으로 먼저 탐색할 것인가

- 먼저 요청 할 수 있는 모든 경우를 정리해둘 것인가? 요청이 올 때 마다 구할 것인가?

라고 생각한다.

심오한 부분에서는 달라지겠지만, 일반적으로 마주치는 문제는 저 2 조건을 어떻게 조합하느냐의 4가지 문제로 요약된다.

하지만 사람은 모든 경우를 정리해둔 경우, 절대 효율적으로 동작하지 않는다.

결과물을 잊기 때문이다.

 

그 외에 여러 특이사항이 있지만,

전산수학을 알면 현실세계에서 판단해야 할 일을 좀더 효율적으로 할 수 있어서 말한다.

 

 

 

1) 정렬 응용

 

우리 엄마나, 할머니는 돈을 주면 꼭 정렬을 하는 취미가 있다.

그러나 두 분 다 모두 몹시 비효율적으로 정렬을 한다.

두 분 모두 정렬은 지폐의 방향에 한정하는 수준이지만,

옆에서 보면 정렬하는 과정이 몹시 한심하다.

처음엔 정렬해서 줬지만, 두 분의 취미를 존중하는 차원에서 요즘에는 그냥 인출한 그대로 주는 편이다.

 

어떻게 정렬할 것인가?

전산에서 정렬은 퀵정렬을 베이스로 하는 경우가 많다.

하지만 단언컨데 인간이 하기엔 퀵정렬은 별로 효율적이지 않다.

인간은 퀵정렬을 하느니 삽입정렬을 하는 편이 유리하다.

현실에서는 데이터를 밀어넣는데 n의 시간이 들지 않기 때문에.

하지만 비 직관적이지만 인간의 계산순서를 고려하면 기수정렬이 가장 유리하다.

 

일반적인 사람이 돈을 정렬하는 방법은 아래와 같다.

 

1. 정렬하는 방향을 정한다. (얼굴이 보이는지 여부, 숫자가 위를 향하는지 아래를 향하는지 여부)

(i번째 장을 볼 때, i-1번째 장은 정렬되어있다.)

2. [0~i) 까지의 지폐를 i번째 장과 같게 회전한다.

이 결과 [0~ i]번째 종이는 같은 방향을 향한다.

3. 모든 종이가 같은 방향을 향하면, 원하는 방향으로 회전한다.

 

2번째 스텝은, i번째 종이가 어느 방향인지를 판단하는 a시간, [0~i) 장을 회전하는 b시간이 걸리며

최악의 경우 n장을 정렬할때 n * (a+b)시간, 최선의 경우 n * a 시간이 걸린다.

 

보통의 경우 b >> a 다.

판단에는 0.1초도 안걸리지만, 회전하는데는 1초는 걸린다.

따라서 회전을 최대한 적게 하는 것이 이득인데, 이는 알 수 없다.

이때 당신이 전산수학을 알고 기수정렬을 안다면?

고정적으로 n* a + 3 * b 시간이 든다.

구체적인 방법은 아래와 같다.

 

1. 지폐의 방향에 따라 놔둘 공간 4군데를 정한다.

2. i번째 지폐의 방향에 따라 위의 4 공간 중 한 곳에 놔둔다.

3. 지폐를 다 분배했다면, 회전하며 한 뭉치로 합친다.

 

포커카드를 정렬할때에는 모양, 숫자 모두 정렬하기 때문에 위와 같은 짓을 하지 않지만,

화투카드를 정렬할 때에는 12월로 나눈 다음, 위와 같이 정렬한다.

엄마도, 할머니도 위와 같은 정렬을 할 줄 안다.

그럼에도 돈을 정렬할 때에는 이걸 써야 한다고 생각하지 않는다.

안타까운 현실이다.

 

 

 

2) 쿼리 응용

쿼리는 단순이 요청을 말하는 것인데, 여기서 말하고자 하는 쿼리 응용이란

- 먼저 요청 할 수 있는 모든 경우를 정리해둘 것인가? 요청이 올 때 마다 구할 것인가?

앞에서 말한 이 개념인데, 모든 경우를 미리 정리해둔 것이다.

 

아마 부서간 협조를 많이 하는 개붕이라면 이미 쓰고 있을 것이다.

간단하다.

앞에서 받은 요청의 결과물을 저장해둔다. (ex : 신입사원이 왔는데 뭘 해야 하나요?)

그 후 같은 요청이 오면 저장해둔 결과물을 그대로 전송한다. (ex : 첨부한 메일을 참조하세요.)

 

이게.. 전산수학..?

 

 

3) 탐색 응용

- 횡/종 중 어느 방향으로 먼저 탐색할 것인가

이미 만카이 상태라 제대로 글을 쓰지 못해, 원래 쓰고자 하는 바를 잘 못 쓰고 있지만.

옆에서 보면 자기가 한 메모를 검색기능을 의존하지 않고는 기억하지 못하는 사람이 너무 많다.

그러면 어떻게 탐색할 것인가는 몹시 중요한 문제다.

신입이들은 그냥 자기 머리를 포기하고 검색기를 쓰는 경향이 많지만, 굳이 사람의 머리를 쓰고 싶다면 다음과 같다.

 

종방향 먼저 탐색(깊이 우선 탐색)

일단 모든 폴더의 끝단 까지 가서, 메로를 하나 하나 열어보는 것이다.

메모를 제대로 된 구성 없이 아무데나 저장했을 때에는 이것이 유리하다.

하지만, 이 것을 인간이 하느니 차라리 검색기로 검색하는 편을 권장한다.

 

횡방향 먼저 탐색(브랜치 우선 탐색)

폴더 이름만 보고 해당 폴더를 들어갈지 말지를 판단한다.

원하는 메모를 찾을 가능성이 높지만, 새 메모를 저장 할 때, 적절한 폴더에 넣어야 하는 문제가 있다.

게다가 폴더구조를 제대로 짤 필요가 있다는 점에서 힘들어하는 사람이 많다.

 

요즘에는 메일이나 메모를 한 폴더에 다 집어넣고 검색기에 의존하는 사람이 많은데,

아직까지는 검색기에 의존하는 것 보다는, 브랜치 우선 탐색을 할 수 있도록 메모를 배치하는 사람이 원하는 메모를 찾을 가능성이 높다.

하지만.. 언젠가는 검색기가 더 우수할지도.

 

 

4) 자료구조 응용

큐, 스택, 링크드 리스트, 트리, 그래프 등등 여러 자료구조가 있지만

블루 턱걸이인 내 입장에서 현실세계에서 응요할만한 자료구조는 원형 큐 밖에 없다.

편의점 음료 냉장고는 큐의 형태고, 쌀포대같은건 스택 형태로 동작한다.

현실에 이미 존재하는 것과 같은 자료구조를 학문적으로 정의한거지.

의식적으로 쓸 자료구조는 원형 큐라고 생각한다.

 

이런데 쓸 수 있다.

신발을 돌아가면서 골고루 쓰기

마스크를 연속해서 쓰지 않되, n일을 쓰고 나면 버리기

https://velog.io/@inyong_pang/15%EA%B0%95-%ED%99%98%ED%98%95-%ED%81%90Circular-Queues

 

n개의 구성요소를 가정할 때, n+1 개의 공간을 마련한다.

이는 반드시 1칸의 빈칸을 보장하게 된다.

먼저 신발을 골고루 신는 경우를 이야기 하자면

 

원형 큐는 크게 n+1개의 공간, 헤더, 테일 의 3가지 구성요소를 가진다.

먼저 헤더는 헤더 위치의 오른쪽에 위치한 물건을 사용한다.

해당 물건을 사용한다면, 헤더는 오른쪽으로 이동한다.

테일은 해당 위치에 물건을 넣는다. 물건을 큐에 넣는다면 테일은 오른쪽으로 움직인다.

(오른쪽 왼쪽은 반대로 써도 된다.)

신발을 골고루 쓰는 것은, 출근할 때 헤더 위치의 신발을 신고, 퇴근해서 그 신발을 테일위치에 놔두면 된다.

그러면 모든 신발을 골고루 쓰게 된다.

 

마스크를 연속해서 쓰지 않되, n일을 쓰고 버리기도 위와 같다.

한가지 차이점은 테일의 위치가 n일 때, 해당 마스크를 버리고 새 마스크를 넣는다는 차이점이 있다.

 

 

 

5) 부작용

이딴 이야기를 하면, 컴공 사이에서도 이상한놈 취급 당한다.