[TIL] 2022-03-28 / 6일차

 

오늘 배운 내용

 

프로그래머스 입국심사 문제 풀이

 

코딩테스트 연습 - 입국심사

 

제한사항

• 입국심사를 기다리는 사람은 1명 이상 1,000,000,000명 이하입니다.
• 각 심사관이 한 명을 심사하는데 걸리는 시간은 1분 이상 1,000,000,000분 이하입니다.
• 심사관은 1명 이상 100,000명 이하입니다.

우선 문제의 제한사항을 살펴보면 n의 입력값으로 최대 1,000,000,000명이라고 주어진다. 시간 복잡도를 생각했을 때, 로그 시간 내로 풀어야 적절하고 방법은 이진 탐색을 떠올릴 수 있어야 한다.

 

심사관은 100,000명 이하로 주어졌기에 선형 시간내로 탐색해도 괜찮다고 파악할 수 있어야 한다.

 

입국심사를 기다리는 사람 수 n, 각 심사관이 한 명을 심사하는 데 걸리는 시간이 담긴 배열 times가 매개변수로 주어질 때, 모든 사람이 심사를 받는 데 걸리는 시간의 최솟값을 return 하도록 solution 함수를 작성해주세요.

문제 설명 마지막 단락을 보면, "심사를 받는데 걸리는 시간의 최솟값을 return 하도록"이라고 적혀있다. 최솟값을 찾는 문제는 결정 문제라고 할 수 있다.

• 결정 문제 = 이진 탐색 = 파라메트릭 서치
• 이진 탐색과 파라메트릭 서치

GitHub - mieumje/Javascript_basic: Javascript 기초

 

문제를 풀기전 고려할 사항들은 위와 같고, 문제를 풀기 위한 접근법은 다음과 같다.

 

이진 탐색을 통해 최솟값을 찾을 때 까지 주어진 시간을 계속해서 반으로 줄여나가야 된다. 최소 시간이 좌측의 끝, 최대 시간(최악의 경우)이 우측의 끝이다. 좌측과 우측의 중간값을 구하고, 최솟값을 찾아나가며 줄여나간다. 예를 들어 30분이라는 시간이 주어졌을 때, 7분씩 걸리는 심사관과 10분씩 걸리는 심사관이 주어진 시간 동안 최대 입국 심사를 처리하면 7명을 처리할 수 있다(30/7의 내림 + 30/10의 내림 = 4 + 3). 입력 값으로 주어진 6명보다 많이 처리할 수 있기 때문에 시간을 줄여도 된다(우측 끝의 값을 중간값 바로 전으로 변경).

 

접근 방법을 코드로 구현하면 다음과 같다.

 

우선, 이진 탐색은 주어진 입력이 정렬되어 있어야 사용할 수 있기에 입력 값을 정렬해주고 좌측값과 우측 값을 구해준다.

 

times.sort((a, b) => a - b);
let left = 1; // 최소 시간
let right = times[times.length - 1]* n; // 최대 시간
// 쵀대 시간은 10억 * n

 

그리고 최소 값(시간의 최소 값)을 찾기 위해 좌측끝과 우측 끝이 만나는 지점까지 반복해서 탐색한 후, 최소 값에서 1을 더한 값을 구해주면 된다.

 

while(left<=right){
    let mid = Math.floor((left + right) / 2);
    const sum = times.reduce((prev, curr) => prev + Math.floor(mid / curr), 0); // 누적 초기 값 = 0으로 초기화
    console.log(left, mid, right, sum)
    if(sum < n){    // mid 시간 동안 처리할 수 있는 인원이 n보다 작으면
        left = mid + 1; // mid 시간 이하는 모두 n명 이하만 처리 가능
    }else{    // mid 시간 동안 처리할 수 있는 인원이 n보다 크면
        right = mid - 1; // mid 시간 이상은 모두 n명 이상 처리 가능
    }
}

 

자바스크립트 reduce()

 

입국심사 문제를 풀기위해 누적 값을 구할 때 사용했던 함수이다. reduce()는 배열의 각 요소를 누적시킨 값을 구할 수 있다.

 

Array.prototype.reduce() - JavaScript | MDN

 

let arr = [1,2,3,4,5]
let sum = arr.reduce((prev, curr) => prev + curr, 0);

 

reduce() 함수의 콜백 함수에서 initialValue를 제공하지 않으면 reduce()는 인덱스 1부터 시작해 콜백 함수를 실행하고, 첫 번째 인덱스를 건너뛴다.

 

너비 우선 탐색, 깊이 우선 탐색(Breadth-First Search, Depth-First Search)

 

BFS

 

그래프 탐색 알고리즘으로, 같은 깊이에 해당하는 정점부터 탐색한다.

 

BFS의 특징

1. Queue를 이용해 구현 가능
2. 시작 지점에서 가까운 정점부터 탐색
3. V = 정점, E = 간선일 때, 시간 복잡도는 O(V+E)

 

DFS

 

그래프 탐색 알고리즘으로, 최대한 깊은 정점부터 탐색한다.

 

DFS의 특징

1. Stack을 이용해 구현 가능
2. 시작 정점에서 깊은 정점부터 탐색
3. V = 정점, E = 간선일 때, 시간복잡도는 O(V+E)

 

프로그래머스 여행경로 문제 풀이

 

코딩테스트 연습 - 여행경로

 

주어진 항공권을 모두 사용해 방문하는 공항 경로를 출력하는 문제다. 출발점은 항상 "ICN"으로 고정되어 있고, 모든 도시를 방문할 수 없는 경우는 주어지지 않는다.

 

예제 #2를 살펴보면,

["ICN", "SFO", "ATL", "ICN", "ATL", "SFO"] 순으로 방문할 수도 있지만
["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"] 가 알파벳 순으로 앞섭니다.

가능한 경우의 수가 2개 이상일 경우 알파벳 순서가 앞서는 경로가 우선이 된다.

 

주어진 2차원 배열의 모든 원소가 쓰이고, 시작점은 언제나 "ICN" 그리고 경우의 수가 여럿이 존재한다면 알파벳 순으로 정렬된 값이 정답이 된다.

 

문제를 풀기 위해 2차원 배열의 각 원소의 첫 번째 원소를 dictionary의 key값으로 사용하고 해당 원소의 두 번째 원소를 value로 사용한다. 이를 통해 항공권(key 값)으로 방문할 수 있는 곳(value 값)을 나타낸다.

• dictionary = {출발점 : 도착점}

시작 값 "ICN"을 기준으로 dictionary를 탐색하며 stack에 쌓아준다. dictionary의 값(value)이 있을 경우, stack에 push 해 주고 해당 값을 다음 dictionary의 key 값으로 활용한다. 만약 dictionary의 값(value)이 없는 경우 stack에서 pop 하여 정답을 구한다.

 

function solution(tickets) {
    let answer = [];
    let dict = {};
    for(const ticket of tickets){
        if(dict[ticket[0]]) dict[ticket[0]].push(ticket[1])
        else dict[ticket[0]] = [ticket[1]]
    }
    
    for(let key in dict){
        dict[key].sort().reverse();
    }
    
    let stack = ["ICN"];
    
    while(stack.length > 0){
        let from = stack[stack.length - 1];

        if(dict[from].length > 0) {
            stack.push(dict[from].pop());
        } else answer.push(stack.pop());
    }

    return answer.reverse()
}

처음 작성한 코드로 테스트 케이스 2번을 돌렸을 땐 정답이 나왔지만, 테스트 케이스 1번에서 예외를 생각하지 못했다. 그래프상 끝 정점("IAD")은 dictionary에 할당되지 않아 undefined라서 length를 반환하지 못한다. 이때의 예외를 추가해 주었다.

 

while(stack.length > 0){
    let from = stack[stack.length - 1];

    if(dict[from] == undefined){
        answer.push(stack.pop());
    } else if(dict[from].length > 0) {
        stack.push(dict[from].pop());
    } else answer.push(stack.pop());
}

 

그리디(Greedy)

 

매 선택에서 지금 이 순간 가장 최적인 답을 선택하는 알고리즘으로 최적해를 보장해 주지 않는다.

 

2022.03.11 - [Developer/Python] - [파이썬] 그리디(Greedy) 알고리즘

[파이썬] 그리디(Greedy) 알고리즘

 

그리디 알고리즘의 특징

• 보통 최적해를 구하는 알고리즘보다 빠른 경우가 많다(선형 시간만에 끝나는 경우가 많다).
• 그리디 알고리즘에서 파생된 알고리즘 : 크루스칼, 다익스트라 알고리즘
• 직관적인 문제풀이에 적합

 

프로그래머스 큰 수 만들기 문제 풀이

 

코딩테스트 연습 - 큰 수 만들기

 

처음 문제를 보고 생각해낸 아이디어는 주어진 number를 정렬해 k만큼의 최솟값(정렬된 number에서 k번째 인덱스까지의 값)을 빼고 새로운 값을 만들려고 했으나, 2번째 케이스에서 탈락했다.

 

다음 고려한 것이 주어진 numbers에서 0 ~ k번째 인덱스까지 slice()하여 최대 그 사이에서의 최대 값을 구하고 최댓값 보다 작은 값은 삭제하려고 했으나, 무한 루프에 빠져 해결하지 못했다(해결했다 하더라도 다른 예외 케이스를 찾지 못했을 것).

 

이선협 멘토님의 풀이는 0번째 인덱스부터 탐색하며 stack에 값을 저장한다. 이때, 탐색하는 값이 stack의 top 값보다 큰 경우 stack의 요소들을 pop 해준다(count 값이 k가 될 때까지, 현재 값이 stack의 top 보다 크다면 계속). 그리고 이 상태에서 채점을 하면 테스트 케이스 12번을 통과하지 못하는데 반례는 "654321"처럼 애초에 큰 수로 정렬되어 있는 경우이다. 이 때는 k만큼 문자열을 뒤에서 잘라주도록 한다.

 

if(count<k){
    answer = stack.slice(0,stack.length - k).join("");
}else{
    answer = stack.join("");
}

 

부족한 점

• 프로그래머스 네트워크 문제 풀이
• PR 피드백 정리
• 코드 리뷰

 

느낀 점

1주 차가 지나고 2주 차 첫날이다. 27일 11시 30분쯤 과제를 PR 했다. 이찬희 멘토님이 얼마 지나지 않아 피드백을 해주셨다. 아직 시간을 들여서 피드백을 차근차근 보지 않았지만, 그동안 습관처럼 작성한 코드에 대한 피드백도 보였다. 전역 변수를 사용하는 점, 특정 메소드가 외부 스코프의 변수를 수정하는 점이 무의식적으로 코드를 작성할 때 나왔던 것 같다. 그리고 재귀적으로 풀어내는 방법, Return Early Pattern, .eslintrc.js 를 관리하는 방법에 대해 탐구할 필요가 있다.

 

개인적으로 교육 과정을 너무나도 듣고 싶었던 이유가 피드백 때문이다. 이 전까지 코드를 작성하거나 학교에서 과제를 할 때 겉으로 보이는 게 전부였던 터라 코드에 대한 피드백을 받아보지 못했다. 우아한 테크코스 프리코스를 진행하며 피드백에 소중함을 알았고, 데브코스 프론트엔드 2기를 진행하며 앞으로 받을 무수한 피드백들이 너무나도 소중하게 여겨질 것 같다.

 

오늘부터 4월 3일까지 코드 리뷰 기간이 주어진다. 팀원들의 코드를 직접 보고 리뷰할 기회가 주어졌다. 코드 리뷰에 대해 낯설기 때문에 꼼꼼히 찾아보고 진행해야 할 것 같고 재미있을 것 같다.