알고리즘 - Sorting Networks

알고리즘에 대해 공부를 시작했다.

막막하다. 

이전부터 수없이 많이 들었지만

정작

 

"알고리즘이 무엇인지 설명 해주세요?"

라고 물으면 ... 대답을

할 수가 없었다.

공부시작 전에 용어정리부터 하고 

시작했다.

 

Youtube도 찾아보고 위키백과도 찾아보고 

등등등... 결론은

규칙? rule? 모델을 만들기 전 

집합체라고 이해했다.

 

오늘은 아에 책과 강의를 펴놓고

이해하는 것을 정리해서

나의 이해단계가 어느정도인지 알아보고싶다.

 

 

위키에서 알고리즘은 이렇게 말해주더라.

알고리즘(영어: algorithm), 셈법은 수학과 컴퓨터과학, 언어학 또는 엮인 분야에서 어떠한 문제를 해결하기 위해 정해진 일련의 절차이다. 계산을 실행하기 위한 단계적 절차를 의미하기도 한다. 즉, 문제 풀이에 필요한 계산절차 또는 처리과정의 순서를 뜻한다. 프로그램명령어의 집합을 의미하기도 한다.

명령어 - 위키백과, 우리 모두의 백과사전

https://ko.wikipedia.org/wiki/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

알고리즘 - 위키백과, 우리 모두의 백과사전

 

부분 중 오늘 공부는 Sorting Networks를 이해해보았다.

그 중 첫번째 하위개념인 

 

1. Comparison Networks

 

Compatator를 통해 x와 y가 뒤바뀐다.

x'는 작은 값, y'는 큰 값으로 결과가 도출되어야 한다.

7, 3을 비교해서 > 결론은 3, 7이나오면 된다.

 

입력값을 2개에서 4개로 늘리면 위 그림과 같이 좀 더 복잡해진다.

그래도 입력값이 9, 5, 2, 6으로 넣으면 결과는 

낮은값이 위로 높은 값이 밑으로 가야된다.

2, 5, 6, 9가 나오면 정상이다.

여기서 depth라는 개념이 나오는데 실행시간으로 설명되지만.

나의 이해단계는 a1이 b1까지 가는 수로 이해했다. 

 

예를 들어 2번 a1은 2번 비교를 했으니 a1의 depth는 2이다.

또, a3는 b3까지 가는데 비교를 3번 했으니 a3의 depth는 3이다.

이 입력값들의 대표적인 depth 값을 말하자면

a1부터 a4까지 depth 중 가장 큰 값을 말하면된다.

 

결과적으로 이 입력값 9, 5, 2, 6의 depth 값은 3이다.

 

두번째

 

2. The zero-one principle.

 

공부할 땐 이해됬는데 

다시보니 무슨말인지 모르겠다.

0하고 1을 넣어서 대입하면 1이 반드시

밑으로 내려간다는 개념으로 이해한 것인디.

중요한것은. 

어떤 함수를 입력값에 넣어도 출력값에 영향이 없다. 

*함수는 단순 증가 함수 일때 ^^

 

 

3. Bitonic Sorting Network

바이토닉이라는 개념이 나온다.

먼저

Bitonic Sequence라는 용어를 이해하면

증가하다가 감소, 또는 감소하다가 증가, 증가하다가 감소하다가 증가.

이런패턴으로 만든다는것이다.

(1234621), (7621234), (123432345)

 

바이토닉 소팅 네트워크라는 말은

바이토닉 시퀀스를 소팅한 거라고 한다.

즉 위에 3개 숫자 집단을 소팅한것.!

 

4. Half Cleaner

하프 크리너

반으로 쪼개쪼개 

단순구조로 만들어 소팅하는거 

5. Merging Network

두개의 소팅된 입력값을

하나의 소팅된 출력값으로 결과도출하는거^^

 

이만. 

 

역시 공부할 때랑 정리할 때랑 

기억력이 다르구만. 

또 다시 심도있게 공부해보자...