[취업준비일지] - 133

1.마우스의 기원은 초기 마우스 형태가 쥐의 꼬리가 달린 것 처럼 생긴 덩어리였기 때문에
마우스라는 이름을 가지게 되었고 
GUI의 발전에 따라 더 직관적인 사용방식이 필요해졌는데
여러 창들을 책상에서 작업을 하듯 이리저리 옮기며 사용할 수 있게 구성해 
따로 교육받지 않아도 자연스럽게 사용할 수 있는 방식으로 구현되었고
그러한 기원에 따라 Desktop Metaphor라고 부르며
현재 컴퓨터를 데스크탑 컴퓨터라고 부른다.


2.안티얼라이징은 생각보다 단순한 기술이었는데 
기존의 그래픽은 구현된 내용의 경계를 이어가며 픽셀로 표현하기 때문에
충분히 큰 규모의 픽셀을 사용하지 않을 경우 계단현상이 나타나는데
안티얼라이징은 경계 내부는 동일한 색상을 사용하며 경계선에 있는 블록의 경우
색감을 낮춰 덜 신경쓰이게 만드는 기법이었다.


3.cs영상을 시청하던 도중 눈치챈 것인데
자막 또한 생각보다 대단한 기법이 들어가지 않은 구현이었다.
실수로 드래그한 자막이 이동하는 모습을 보고 수상함을 느끼고 개발자도구를 열어보니 
유튜브의 자막 또한 div 태그로 감싸져있는 것을 볼 수 있었다.

동영상에 추가적으로 자막 여부와 시간마다 갱신되는 것을 통해
div 태그 내부 값을 변경시키며 자막을 변경할 수 있을 것 같고
노래방처럼 자막이 계속해서 변하는 것 또한
각 자막마다 자막과 지속시간 등을 받아  
애니메이션 효과를 통해 계속해서 노래속도에 따라 이동하게 만들 수 있었던 것 같다.


4.그래픽을 나타낼 때 여러개의 그림이 중복되는 경우 처리하는 방식에는 여러가지가 있지만
대표적으로 painter`s algorithm과 z-buffering이 있다.

painter`s algorithm은 각 그림의 우선순위를 결정하고
우선순위가 낮은(멀리 떨어진) 그림을 먼저 그린 다음
그 위에 우선순위에 따라 그림을 덮어씌우게 되면
중복된 부분의 경우 최우선(가장 가까운)의 그림을 볼 수 있게 된다.

우선순위가 5, 3, 1인 3x3의 사각형이 충돌했다고 했을 때 아래와 같이 나타난다.

55333
55333
51113
 111
 111

 

 

하지만 z-buffering의 경우에는 모든 그림을 다 그리는 것이 아니라
각각의 위치에 우선순위를 메기게 되는데 
여기에서는 무한을 임시로 우선순위 9라고 가정하자면
아래와 같이 각각의 위치에 우선순위에 따른 그림을 표기하고
최고우선순위값만 표기한 다음 한번에 칠하는 방식이다. 

9999999
9553339
9553339
9511139
9911199
9911199

 

 

물론 결과는 같지만 더 많은 그림의 충돌이 일어날수록 
한번만 그리면 되는 z-buffering이 효율적이라고 볼 수 있지만
우선순위를 메기는 방식에 따라 동급 우선순위의 경우 충돌이 일어날 수 있고
Z-Fiighting이라는 깜빡임 현상이 나타날 수 있다.


5.그래픽은 위에서 다루는 폴리곤으로 구성되어있으며
3d는 수많은 폴리곤들의 연산을 동시다발적으로 해야하는데
cpu는 이런 연산에 특화되어 있지 않고 병렬적 처리 또한 특화되지 않았기 때문에
폴리곤 연산에 특화되어있으며 한번에 대량의 처리가 가능한 GPU를 사용하게 되었다.





(1).백준 4655 Hangover는 카드를 옆으로 쌓아 
일정 길이를 달성하기 위해 몇장의 카드가 필요한지를 묻는 문제로 
각 카드가 무너지지 않게 하기 위해 
1/2, 1/3, 1/4 등 점점 옆으로 가는 길이를 줄이는 규칙을 가지고 있다.

여러개의 테스트케이스가 있기 때문에 for문에서 각각의 input값을 함수에 넣고
return된 값들을 백틱을 이용해 요구하는 문장으로 변형시켜 result에 담아 한번에 출력했다.

numberAdder함수에서는 기본 0의 sum으로 시작해서 1/2, 1/3 등을 계속 더하며 count++를 하고
입력된 값을 target으로 두고 sum과 비교하다가 sum이 더 크거나 같아진 경우 중단한 다음
return count를 통해 여태 몇장을 쌓았는지를 반환했다.

const input = `1.00
3.71
0.04
5.19
0.00`.split('\n').map(Number)

const result = []
const numberAdder = (target) => {
    let sum = 0
    let count = 0
    for(let i = 2 ; i < 10000 ; i++){
        sum += 1/i
        count++
        if(target <= sum){
            break
        }
    }
    return count
}

for(let i = 0 ; i < input.length-1 ; i++){
    result.push(`${numberAdder(input[i])} card(s)`)
}

console.log(result.join('\n'))

 

(2).백준 1697번 숨바꼭질은 또 동기분과 이름이 같은 수빈이를 돕는 문제였다.
현재 위치와 동생의 위치가 주어지고 +1, -1, *2(순간이동)을 할 수 있을 때
몇번의 이동을 통해 동생을 찾을 수 있는지를 구하는 문제로
처음에는 dp를 생각했지만 단방향이 아닌 양방향으로 진행할 수는 없었다.

다익스트라도 떠오르고 고민하던 찰나에 하단의 알고리즘 분류를 볼 수 있었고
너비 우선 탐색(bfs)라고 분류된 것을 보고 바로 가까운 거리부터 탐색이 되니
찾는 즉시 중단하면 그것이 바로 최적의 경로라는 것을 알 수 있었다.

반복문 내부에 공통되는 부분들이 많이 있었기 때문에
outer를 외부 while문에 태그를 붙여준 다음
외부에 함수를 빼서 일괄처리를 하려고 했지만
함수 자체가 while문 외부에 존재해서 그런지 태그로 while문 종료 기능이 작동하지 않았다.
결국 수동으로 비교 및 break 처리를 해줬다.

제출 전 edge case 확인을 위해 더 작은 숫자로 넣었는데 "1 0"으로 넣자 출력이 되지 않았다.
문제를 확인해보니 routeCheck라는 배열은 target*2로 넉넉하게 줬다고 생각했지만
target이 0이 되면 배일의 길이가 0이되어버려 초기 세팅이 불가능해지는 것이었다.

결국 Math.max(start, target)*2로 어떤 상황이든 처리가 가능한 값으로 변경해주고
실패하기 전에 먼저 발견해서 뿌듯해하며 제출했는데 0.01초만에 실패해버렸다.

문제를 생각해보다가 내가 처리한 방식은 한번의 shift를 걸쳐서 확인하기 때문에
맨 처음 위치가 목표와 동일할 경우를 확인하지 못한다는 사실을 깨닫고 조건체크를 걸어 해결했다.

솔직히 동생을 찾는 시간 문제인데 동일위치에서 이걸 따진다는 것이 조금 답답하고
비현실적인 문제같다는 생각이 잠깐 들었지만 
잘 생각해보면 프로그래밍 자체가 극단적인 예외까지도 처리해줘야 하기 때문에
더 주의해서 해야겠다는 교훈을 얻을 수 있었다.

const [start, target] = `0 0`.split(' ').map(Number)

const routeCheck = new Array(Math.max(start,target)*2).fill(0)
routeCheck[start] = 1
const queue = [start]
if(start === target){
    console.log(0)
}
while(queue.length){
    const nowCheck = queue.shift()
    if(nowCheck > 0 && routeCheck[nowCheck-1] === 0){
        routeCheck[nowCheck-1] = routeCheck[nowCheck]+1
        if(nowCheck-1 === target){
            console.log(routeCheck[nowCheck])
        }
        else{
            queue.push(nowCheck-1)
        }
    }
    if(routeCheck[nowCheck+1] === 0){
        routeCheck[nowCheck+1] = routeCheck[nowCheck]+1
        if(nowCheck+1 === target){
            console.log(routeCheck[nowCheck])
        }
        else{
            queue.push(nowCheck+1)
        }
    }
    if(nowCheck < target && routeCheck[nowCheck*2] === 0){
        routeCheck[nowCheck*2] = routeCheck[nowCheck]+1
        if(nowCheck*2 === target){
            console.log(routeCheck[nowCheck])
        }
        else{
            queue.push(nowCheck*2)
        }
    }
    
}

//1.현재 위치에서 이동할 수 있는 길 3가지 체크
//2.각각 이동 가능한 경우 방문여부를 확인한 다음 미방문인 경우 현재 값+1 저장하고 queue에 넣기
//3.queue.shift로 앞순번을 빼 bfs탐색을 진행하며 목표를 발견한 경우 break 진행하기
//4.edge case 확인차 1,0을 넣었는데 출력이 되지 않아 확인해보니 new Array에 tartget*2만큼 만들었는데 
//  Math.max(target, start로 진행해야 했다.)