감공사

😢 중복 조합 문제

😊 각 숫자를 중복으로 뽑아도 되지만,
조합된 숫자가 중복되면 안되므로 전에 뽑았던 숫자를 제외 해야한다.

😢 중복 순열 문제
N과 M (1), (2)를 이해했다면 쉽게 풀 수 있는 문제

😊 모든 수를 뽑아내므로, 방문한 것을 체크할 필요가 없다.
숫자 1개씩 모두 뽑아내는 코드를 작성하면 된다.

📢 Node.js(JavaScript)로 알고리즘을 풀 때, console.log()가 '시간 초과'에 많은 영향을 준다.
수가 큰 알고리즘 문제를 풀 때는, str 변수를 만들어 모든 결과값을 적절하게 저장해놓고
마지막에 console.log() 단 한 번으로 해결하는 것이 좋다. 아니 그렇게 해야 한다.

😢 순열인지 조합인지 문제가 애매하지만, 결과를 보면 조합이다.
Keyword: '고른 수열은 오름차순이어야 한다'

😊 이 문제 역시 N과 M (1)과 마찬가지로 DFS로 해결이 가능하다.

N과 M (1)는 재귀를 위한 for loop에서 index를 항상 맨 처음부터 다시 돌았다면(모든 경우의 수를 위해),
이 문제에서는 지난 숫자는 제외하고 for loop을 진행한다(중복을 피하기 위해)

😢 오랜만에 보는 순열과 조합

😊 DFS(Depth First Search)를 이용해 풀어낼 수 있다.

* Base case

cnt === M일 때, 출력하고 return해준다(입력 받은 길이만큼)

* Recursion

for loop을 열고 재귀를 진행해준다.
방문을 했다면 true, output에 해당 값(i+1) push 그리고 그 다음 숫자를 진행하기 위헤 dfs(cnt+1)를 진행해준다.
depth의 끝까지 진행하기 위해 마지막 값을 pop()하고 해당 방문은 false로 변경해준다.

3. print() function을 이용해 원하는 값의 길이만큼 값을 구할 때마다 출력해준다.

위와 같은 재귀를 이용해 위 문제를 해결할 수 있다. 조금 세세하게 이해하기 위해서는 debugging 추천한다.

📢 지금까지는 대회를 생각하고 C++를 이용해 알고리즘을 푼 것이 아니기 때문에 시간에 그렇게 신경을 쓰지 않았다.
정확한 로직을 이용해 효율적으로 문제를 해결할 수 있으면 된다고 생각했기 때문이다.
하지만 우연히 console.log() 방법을 바꿔보았더니 시간 단축이 엄청나졌다. 앞으로는 console.log를 최소화 해야겠다.
시간 단축에 엄청난 도움이 된다. 성능을 위해서 사소한 하나까지 신경쓰자.

결론은 Solution 2를 추천한다. 출력 방법만 조금 바꿨을 뿐이다.

이해에 도움이 됐던 post 👉 https://yabmoons.tistory.com/115

😢 될 것 같은데, 잘 안풀려서 시간이 좀 걸린 문제
name list를 따로 뽑아놓고 indexOf()로 sort()하면 될 것 같은데 잘 안 됐다. 나중에 다시 시도해보자.

😊
Solution 1)

Array를 최대 나이까지 선언한 후에, 각 나이 index마다 가입한 순서대로(입력 값 순서대로) push 해주면 된다.
가장 간단하며, 가장 빠른 해결 방법이다.

Solution 2)

for loop을 이용해 index를 함께 넣어주고, 나이가 같다면 index를 비교하여 sort()로 해결하는 방법.
아이디어도 좋고, 간편하다. 하지만, 시간이 Solution 1)보다 2배가량 차이난다.

😢 정렬 문제를 많이 접해봤다면 금방 풀 수 있는 문제

😊
Solution 1)

입력 받은 단어 중 가장 큰 단어 길이(max)와 가장 작은 단어 길이(min)를 뽑아오고,
외부 for loop은 단어의 길이만큼, 내부 for loop은 입력 받은 단어 개수만큼 반복한다.
내부 for loop에서 같은 길이의 단어를 배열에 push하고, 배열 길이가 1보다 크다면 해당 배열을 정렬한 후 최종 배열에 push해준다.
이 방법으로 간단하게 해결했다.

Solution 2)

다른 풀이를 참고하던 중에, 기존에는 몰랐던 localeCompare() built-in function과 Set objet를 발견했다.
sort()로 단어의 길이만큼 정렬하고, 같은 길이의 단어가 있다면 localeCompare()를 이용해 정렬이 가능했다.
그렇게 정렬된 배열을 new Set()에 넣어주면 unique한 value를 받아볼 수 있다.
속도도 훨씬 빠르므로 Solution 2를 추천한다.

😢 병합 정렬로 풀어도 해결이 되지 않아 당황했지만, 퀵 정렬(Quick Sort)에 대해 배울 수 있던 문제

😊 O(n log n)를 갖는 퀵 정렬을 이용하면 문제를 해결할 수 있다.
하지만, 아래 소스 1st solution처럼 sort()로도 해결이 가능하다. 하지만, 퀵 정렬보다 시간이 더 걸린다.

퀵 정렬에 대해 참고하기 좋은 포스트 👉 https://coderkoo.tistory.com/7 

퀵 정렬에 대해 참고하기 좋은 유튜브 👉 https://www.youtube.com/watch?v=7BDzle2n47c