[취업준비일지] - 150

오늘은 동기분의 질문을 통해 css에 대해 다시 한번 생각해보는 시간을 가졌고

웹게임을 개발한다고 하시는 동기분을 보며 서버가 필요없는 웹게임 개발에 대한 이런저런 아이디어를 얻을 수 있었다.

 

현대 공개 채용 및 농협 공개채용 관련 서류처리 때문에 시간이 부족하다.

 

시간초과 메모리초과에 대해 이런저런 생각을 더 많이 할 수 있는 문제를 해결한 후

이력서쪽에 더 신경을 쓰고 있다.

class 3에 속해있기 때문에 대중적인 문제인데 2등을 했다.

 

 

 

 

 

(1).백준 9019번 DSLRd은 각각의 명령어를 통해 현재 값에서 목적 값을 만드는 경로를 구하는 문제였다.

D는 Double, S는 Subtract, L은 Left, R은 Right인 것 같은데
0~9999의 1만개의 숫자로 제한되어 있기 때문에 각 숫자 처리도 약간 고민해야 한다.
(사실 숫자 고민은 브론즈단계에서 끝날 문제다)

어제 시도할 때는 간단하게 bfs로 접근한다고만 생각하고 시도했지만 시간초과로 터져버렸고
LR, RL 중복제거 시도, 빠른 리턴, 이중배열 쪼개기, 방문경로 무시 등의 시도를 진행했다.
도중 메모리 초과를 해결하기 위해 여러가지 확인을 해도 처리가 되지 않았고
방문경로 무시 코드를 제대로 작성하지 않아 메모리 초과가 되었던 것으로 확인되었다.

결국 모두 경로 체크는 진행해야 통과될 수 있었으며
시간 초과를 해결하기 위해 검색 및 gpt 질문등을 진행했지만
gpt는 0,1로 만든 코드를 boolean으로 변경하라는 시덥지 않은 조언을 했는데
결과적으로 확인해보면 메모리 사용량은 0.1%도 절약하지 못하고 
시간은 10%가량 더 늘어나는 것을 볼 수 있었고
[[a,b], [a2,b2], [a3,b3]]형태의 이중배열로 관리하던 데이터를
[a,a2,a3], [b,b2,b3] 형태의 배열 두개로 관리하게 되니 시간은 6.5%빨라지고 
메모리는 7.8%더 사용하는 것을 보고 더 집중이 필요한 형태로 선택할 수 있게 되었다.
route check boolean   48244kb   4832ms  
route check 0,1            48288kb   4428ms  
이중배열 두개로 쪼개기   52100kb   4156ms

하단의 주석은 문제해결을 위해 진행했던 수도코드다.
//기존의 코드에서 shift를 stack으로 바꾸기 위해 queue를 stack으로 변경했고
//그렇게 하기 위해 동일 depth의 작업을 처리한 다음 다음 depth로 진행되게 newStack에 작업을 저장했다.
//또한 RL LR과 같은 이동은 의미없기 때문에 체크 후 추가하지 않는 방식을 선택했다.
//기존 shift방식으로 처리할 때 "99 5"의 9글자 탐색을 진행할 때 1분 이상 걸렸던 것과 다르게 
//35ms밖에 걸리 않는 것을 확인할 수 있다.
//0 573으로 할 경우 무려 12글자가 나오는데 1초도 걸리지 않았다.
//메모리가 초과되어 메모리 최적화 탐색을 위해 이중배열을 단일배열로 변경도 해보고 했지만
//문제는 해결되지 않았고 route 체크를 통해 해결할 수 있었다.
//마지막으로 이중배열 쪼개기를 다시 시도해봐서 결과를 비교해보니 시간면에서 6.5% 더 빨라졌지만 
//7.8% 메모리를 더 사용하는 것을 볼 수 있었는데 아무래도 구조분해할당과 배열생성에 소모되는 시간인 것 같다.
// route check boolean 48244kb 4832ms  
// route check 0,1 48288kb 4428ms  
//이중배열 두개로 쪼개기 52100kb 4156ms

const input = `1
0 573`.split('\n')

const result = []

const bfs = (start, goal) => {
    const visited = new Array(10000).fill(1)
    visited[start] = 0
    let stackNum = [start]
    let stackStr = ['']
    while(stackNum.length){
        const newStackNum = []
        const newStackStr = []
        while(stackNum.length){
            const number = stackNum.pop()
            const str = stackStr.pop()
            const D = (number*2)%10000
            const S = (10000+number-1)%10000
            const L = (number*10)%10000 + Math.floor(number/1000)
            const R = (number%10)*1000 + Math.floor(number/10)
            if(D === goal){
                return(str + 'D')
            }
            else if(visited[D]){
                visited[D] = 0
                newStackNum.push(D)
                newStackStr.push(str+'D')
            }
            
            if(S === goal){
                return(str + 'S')
            }
            else if(visited[S]){
                visited[S] = 0
                newStackNum.push(S)
                newStackStr.push(str+'S')
            }
            
            if(L === goal){
                return(str + 'L')
            }
            else if(visited[L]){
                visited[L] = 0
                newStackNum.push(L)
                newStackStr.push(str+'L')
            }
            
            if(R === goal){
                return(str + 'R')
            }
            else if(visited[R]){
                visited[R] = 0
                newStackNum.push(R)
                newStackStr.push(str+'R')
            }
        }
        stackNum = newStackNum
        stackStr = newStackStr
    }
}


for(let i = 1 ; i < input.length ; i++){
    const [start, goal] = input[i].split(' ').map(Number)
    result.push(bfs(start, goal))
}

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