2020-06-01 TIL

Facts

• 알고리즘 문제 자바스크립트로 x만큼 간격이 있는 n개의 숫자, 직사각형 별찍기 문제를 풀었다. 1렙은 이제 2문제 남았다.
• ER다이어그램으로 채팅App의 데이터베이스 설계도를 그렸다.
• 운영체제의 가상메모리에서 페이지 대치 알고리즘중 선입선출대치, 최적페이지 대치, 최근최소 사용, LRU 근접 알고리즘에 대해서 정리했다.
• 컴퓨터 통신의 시초가 되고있는 전화 통신의 발전 과정에 대해서 조사하고 정리했다.

Feelings

• 어느정도 자료구조나 알고리즘, 네트워크에 대한 기본지식을 어느정도 소지하고 위 자료를 보니까 확실히 머리에 잘 들어온다는 느낌이 들었다.
• ER다이어그램으로 데이터베이스 설계도를 처음 그려봤는데 요즘 읽고있는 객체지향의 사실과 오해 책에서 보았던 객체의 관계에 대해서 많이 대치 되는 것 같다.

Findings

• 첫번째 선입선출 알고리즘은 가장 기본적이도 간단한 대치 알고리즘이지만 가장 적재가 오래된 페이지부터 대치한다는 것이 불확리하거나 정당한 방법이 아닐수있다.
• 최적 페이지 대치 알고리즘은 향후 사용될 가능성이 가장 낮은 페이지부터 대치한다는것이 사용자가 보기에는 가장 효과적인 방법이라고 생각하겠지만, 이론적으로는 향후 사용될 가능성이 가장 낮은 것을 찾기는 어려운 부분이기 대문에 현실적으로는 적용하기 어려워서 다른 방법들과 비교하는 용도로만 사용되는 것 같다.
• 최근 최소 사용 알고리즘은 과거에 쌓아놓았던 기록을 이용해서 가장 최근에 사용한적이 없는 페이지를 찾아서 앞으로도 사용될 가능성이 가장 낮은것으로 판단하고 대치하는 알고리즘이다. 어떤 페이지가 가장 오래전에 사용되었는지를 아는 방법에는 계수기, 스택을 이용한 순서결정 방법이 사용된다. LRU 근접 알고리즘은 2가지 알고리즘을 사용하는데 첫번째는 각 페이지에 8비트의 길이의 참조 비트를 부여해서 페이지가 사용될때마다 최상위 비트를 1로 바꾸고 사용될때마다 오른쪽으로 한칸씩이동해서 이 결과값을 통해서 어떤 페이지를 대치할것인지를 결정하는 알고리즘인 것 같다.
• 두번째 시계 알고리즘을 사용하는데 모든 페이지에 1비트의 참조비트를 부여하고 페이지가 사용될 때마다 참조 비트를 0에서 1로 전환하고 참조비트가 1인 페이지를 내보낸다. 참조비트가 1인 페이지는 참조비트를 0으로 바꾸고 한번의 기회를 더준다. 다음 검사에서 참조 비트가 0이면 대치대상이 되고 그동안 또 사용되어 1로 되어 있으면 0으로 바꾼다.
• 비효율적인 알고리즘도 있고 존재는 하지만 사실상 구현 방법이 존재하지 않아 사용하지 않는 알고리즘도 있는 것 같다. 하지만 모두가 기록된 자료나 스택 큐 를 이용한 방법을 사용한다는 것에서 어느정도 공통점이 있다는 것을 알았다.

Future Action Plan

• 앞으로 내가 하던공부 이외에 다른 공부를할때 그냥 대충 받아적고 넘어가지 말고 어느정도 공부를 하고 정리하도록 하자.