감공사

😢 단순 비교도 가능하지만, 정렬로 쉽게 풀 수 있는 문제

😊 각종 정렬을 이용해 풀 수 있음(여기선 선택정렬 selection sort)

😢 N개의 수열을 받아서 X보다 작은지 판단하는 문제

😊 N, X을 먼저 입력받고, N만큼 loop, a는 X보다 작은지 판단하여 출력

😢 iterate & swap!

😊 입력 받는 두 수(a, b)를 반복해서 입력해줘야하며,
a++, b--로 두 수를 증가 또는 감소시키는 것을 반복해야한다.
두 수가 같아졌을 경우 반복문을 빠져나오는 조건을 걸어줘야한다(a < b)

😢 단순 출력 문제

😊 row가 증가할 때마다 n-row만큼 줄어들도록 *을 출력하면 된다
row는 1개씩 증가하니
5를 입력받았을 경우
5-0, *****
5-1, ****
5-2, ***
5-3, **
5-4, *

😢 단순 출력 문제(그래도 생각이 조금은 필요)

😊 *(별)은 row(행)의 수만큼 출력, 공백은 그 나머지 라는 생각을 통해 해결 가능

즉, 5를 입력받으면

1. 공백4개 별1개
2. 공백3개 별2개
3. 공백2개 별3개
4. 공백1개 별4개
5. 공백 0개 별5개

n을 입력받으면

for (int row = 0; row < n; row++) {
	for (int col = 0; col < n - row - 1; col++) cout << ' ';
    	for (int col = 0; col <= row; col++) cout << '*';
  	cout << '\n';
}

😢 단순 출력 문제

😊 1개부터 입력 받는 숫자만큼 1개씩 증가하는 별 출력

😢 중복 조합 문제

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

😢 중복 순열 문제
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