[취업준비일지] - 129

1.게이트로 연산한 결과를 저장해야 하기 때문에 latch라는 개념이 추가되는데
or과 and를 통해가 각각 1과 0을 기록할 수 있다.

a, b가 or 게이트를 통과한 뒤 그 결과값을 다시 a와 비교할 경우
a가 1이 들어가면 그 뒤로는 a에 어떤 값을 넣더라도 1이 기록되며

a, b가 and 게이트를 통과한 뒤 그 결과값을 다시 b와 비교할 경우
한번 0이 들어가게 되면 그 뒤로는 a에 어떤 값을 넣어도 0이 될 수 밖에 없기 때문에
0이 기록된다고 볼 수 있다.

이 각각의 0과 1을 기록하는 latch를 통해 
1을 넣으면 무조건 1이 기록되는 or latch를 통해 1을 기록하고
그 결과값에 다시 and latch를 연결시켜 0을 입력할 경우 0이 기록되게 한다.
이를 통해 0 입력, 1입력을 통해 저장된 값이 0과 1로 고정되게 할 수 있다.

여기서 한발자국 더 나아가면 입출력의 Write 여부도 결정할 수 있는데
write enable 가능 여부의 true/false와 입력값의 true/false를 0과 1로 표현하면
and로 두 조건 모두 1,1이 되야 and gate를 통과할 수 있기 때문에 
write enable가 0이 될 경우 수정이 불가능해진다.
이를 gate latch라고 부른다.

gate latch가 8개가 모여서 8비트를 표기할 수 있게 되고
이 그룹을 하나의 숫자를 저장할 수 있는 register라고 부른다.

초기에는 8개의 gate latch를 통해 만들어진 8비트를 하나의 register라고 했지만
8, 16, 32를 걸쳐 이제는 보통 64비트가 하나의 register로 사용된다.

여기서 register의 단위인 8비트, 16비트, 32비트, 64비트가
우리가 잘 알고있는 윈도우 32비트, 64비트 할 때 그 비트 단위가 되며
32비트는 대략 43억, 64비트는 32비트의 제곱(43억*43억)만큼의 데이터 처리가 가능하다.


2.cpu의 각각의 명령을 처리하기 위해서 내부적으로 규칙적인 clock이 작동하는데
최초의 단일 cpu는 740kHz로 초당 74만번 정도의 처리가 가능했으며 
현재의 기가헤르츠는 초당 10억 사이클의 처리 속도를 의미한다.

이 clock의 속도를 끌어올릴 경우 당연히 처리 속도도 빨라질 수 밖에 없는데
우리가 오버클락이라고 부르는 행동이 바로 이 clock의 속도를 강제적으로 올리는 것 이었다.

cpu의 비약적인 발전과 명령어 집합의 확장으로 성능은 좋아졌지만
이제 데이터의 입출력이 처리 속도를 따라가지 못하는 문제가 발생했고 
이를 해결하기 위해 cpu 내부에 Cache를 넣어 문제를 해결해줄 수 있었다.

Cache는 한번의 요청에서 덩어리로 데이터를 가져와 이미 있는 데이터의 경우
BUS를 이용하지 않고 값을 그대로 사용하기 때문에 엄청난 속도적 이점이 있는데
단점으로는 가져와서 사용하는 데이터는 그 시점의 사실일 뿐
현재 그 데이터가 실제 그 값인지를 보장해주지는 않는다는 것이었다.

이런 불일치하는 데이터를 dirty bit라고 칭하며
캐시가 가득 차서 교류가 필요할 때 dirty bit를 체크하고 
dirty bit를 교체하는 방식으로 해결할 수 있다.

Pipeline이라는 방식에서도 동일한 문제가 발생하는데
a -> b -> c -> d의 순서로 작업이 진행되야 하는 경우
단순히 a,b,c,d의 순서대로 처리만 한다면 4의 시간이 소모되지만 
개별적인 a,b,c,d를 각각 병렬적으로 처리한다면 
아래와 같이 1초에 a,b,c,d 4가지를 처리할 수 있다.

1,2,3,4,5,6,7,8(시간)

a,b,c,d
  a,b,c,d
    a,b,c,d
      a,b,c,d

        a,b,c,d

하지만 병렬적으로 가져온 상황에서 기존 데이터가 수정된다면 문제가 발생할 수 있는데  
문제 발생을 막기 위해 out-of-order라는 비순차적 실행 방식을 통해 해결한다.


3.userEvent를 사용해 상호작용을 한 다음 초기화하고 싶을 경우
user.clear()를 사용해야 하는데 이것 또한 userEvent기 때문에 await를 사용해야 한다.

const x = await screen.findXXXX()
await user.clear(x)

 

 

 

 

(1).백준 1927번 최소 힙은 이름 그대로 최소 힙을 구현하는 문제였다.
예전에 힙에 대해 적당히 알고 이진정렬로 슬쩍 최소값만 출력하는 시도를 해보다가 실패하고
최소 힙보다 쉬운 문제로 class 3 난이도를 통과했었다..

힙 구성을 다시 꼼꼼히 살펴보니 생각만큼 어렵지는 않았는데
아래와 같은 수도코드를 먼저 작성했다.
1.heap에 push, pop하는 함수 구현
2.순회하며 입력이 0이 아닌 경우 push, 0인 경우 pop, arr이 빈 경우 0 추가
3.push 함수는 배열의 마지막에 push한 다음 부모노드와 비교해 거슬러 올라가다가
  최종 목적지(index 0)에 도착하거나 부모보다 클 경우 중단
4.pop 함수는 최상단 값을 return하는 것은 맞지만
  그 값을 다시 채워야 하기 때문에 마지막 값을 index 0에 넣어준 다음
  자식 노드들 중 더 작은 값이 있을 경우 교체를 반복한다.
 (자식 노드들 중 본인보다 작은 값이 없을 경우 중단)
 *길이가 1일 경우 무한 리필되는 경우 확인 후 early return 적용

작성 원리는 push, pop에서 나타나듯이 새로운 값의 추가 및 제거를 할 경우
추가의 경우에는 배열의 마지막에 추가한 다음 부모 노드를 찾아간다.
여기서 중요한 것은 부모노드를 찾는 방식인데
노드에 들어가는 순서처럼 완전이진트리 형태로 index를 추가해보면 일정한 규칙을 찾을 수 있다.
   0
 1   2
3 4 5 6
바로 자식 노드는 부모 노드의 index값의 두배에 1과 2를 더한다는 것이다.

이를 통해 부모 노드는 Math.floor((indexNow-1)/2)로 구하게 되었고
현재 조회하는 index가 root node(최상단)이거나 
부모 노드보다 작을 경우 중단하고 그게 아닐 경우에는 while로 계속 반복진행했다.

이를 통해 마지막에 추가된 값이 올라갈 수 있는 최대치만큼 올라가 
정상적으로 구조화된 최소힙이 생성된다.

그 뒤에는 다시 값을 제거해야 하는데
최소 힙인만큼 당연히 최상단(root)에 있는 최소값을 출력해야 한다.

그 자리에는 마지막 index에 위치한 값을 root node에 넣어주는데
그 값이 최소값인지 확인이 필요하기 때문에
자식 노드들과 비교하며 그 중 최소값과 자리를 교체해주고
교체된 index의 위치를 현재 위치로 변경한 다음 다시 자식 노드와 비교해 변경한다.

중단 시점은 자식 노드들이 모두 현재 index의 작지 않을 경우인데
크다가 아닌 작지 않다를 사용하는 이유는 [5,5,5,5]가 있을 경우 교체가 필요하지 않으며
최하단인지 여부를 체크하기도 복잡한데 undefinde와 비교는 false가 나오기 때문에
추가적인 확인이 필요없다는 장점이 있기 때문이다.

사실 입력 제거 두가지를 구현하고 나면 그 뒤로는 for문 입출력이기 때문에
추가적으로 어려운 점은 없다.

const input = `23
0
1
2
12345678
0
0
0
0
32
0
3
6
9
12345
23
0
0
8
0
0
0
0
0`.split('\n').map(Number)

let arr = []
let result = []

const pushToHeap = (num) => {
    arr.push(num)
    let indexNow = arr.length-1
    while(indexNow > 0){
        const parentNode = Math.floor((indexNow-1)/2)
        if(arr[indexNow] < arr[parentNode]){
            const temp = arr[parentNode]
            arr[parentNode] = arr[indexNow]
            arr[indexNow] = temp
            indexNow = parentNode
        }
        else{
            break
        }
    }
}

const popFromHeap = () => {
    const popNumber = arr[0]
    const lastNum = arr.pop()
    if(arr.length === 0){
        return popNumber
    }
    arr[0] = lastNum
    
    let indexNow = 0
    while(arr[indexNow] > arr[indexNow*2+1] || arr[indexNow] > arr[indexNow*2+2]){
        const [child1, child2] = [indexNow*2+1, indexNow*2+2]
        if(arr[child1] > arr[child2]){
            const temp = arr[child2]
            arr[child2] = arr[indexNow]
            arr[indexNow] = temp
            indexNow = child2
        }
        else{
            const temp = arr[child1]
            arr[child1] = arr[indexNow]
            arr[indexNow] = temp
            indexNow = child1
        }
    }
    return popNumber
}

for(let i = 1 ; i < input.length ; i++){
    if(input[i] !== 0){
        pushToHeap(input[i])
    }
    else if(input[i] === 0 && arr.length === 0){
        result.push(0)
    }
    else{
        result.push(popFromHeap())
    }
}
console.log(result.join('\n'))