03.25.2022 TIL

TIL

Done it

• 이선협 강사님의 강의 내용입니다.
• <문제 유형 파악 방법>
  • 입력에 따라 문제 양상이 달라집니다.
    1. 입력 <= 100
       • 완전탐색
       • 백트래킹
    2. 주로 O(n^3)에서 그 이상까지
  •  
    1. 입력 <= 100,000
       • n * n 2차 배열
       • but 문제에 따라 O(n^2logn)이 나올 수 있다.
    2. 최대 O(n^2) 이내
  •  
    1. 입력 <= 1,000,000
       • 힙, 우선순위 큐
       • 정렬, 위상 정렬
       • 동적계획법
       • 다익스트라(최단거리)
    2. 최대 O(nlogn) 이내
  •  
    1. 입력 <= 1,000,000,000
       • DP, 그리디
    2. 최대 O(n) 이내
  •  
    1. 입력 > 1,000,000,000
       • 이진 탐색
    2. 최대 O(logn) 이내
• 가장 큰 수 Algo

처음에 DFS를 이용하여 전체 순열을 다 찾아 구하는 방식으로 하였습니다

const DFS = (L, sum) => {
    if (L === n) {
        numbersArr.push(sum);
        return;
    }
    else {
        for (let i = 0; i < n; i++) {
            if (numUseArr[i] == 0) {
                numUseArr[i] = 1;
                DFS(L + 1, sum + numbers[i]);
                numUseArr[i] = 0;
            }
        }
    }
}

그러나 시간 복잡도로 인해 Fail이 뜹니다. 그래서 그냥 정렬만 사용해서 문제를 풀어봤습니다. 숫자를 문자로 바꾼 후 문자를 합쳐서 비교하는 방법입니다. => .sort((a, b) => (b + a) - (a + b))이로 인해 문제가 해결되었습니다. :)

 

Feeling

요즘 수업이 다 알고리즘이다 보니 알고리즘만 주구장창 풀고 있습니다.

수업겸해서 문제가 쉬울줄 알고 다 10분안에 풀 수 있을것 같다는 자만심으로 집중을 안하고 했는데 못풀었습니다.

그래서 다시 집중해서 30분 넘게 걸리는 상황이 나와 문제를 더 많이 풀어봐야 겠다는 생각을 가지게 되었습니다. :)

 

REF

프로그래머스 특강