문제 유형
10이하의 N개의 자연수가 주어지면 이 중 M개를 뽑아 일렬로 나열하는 방법을
모두출력합니다.
필요자료구조
int n // (자연수 갯수),
int m // (뽑기 횟수),
int arr[] // (n개 만큼 자연수 입력),
int ch[] // (백트래킹 배열),
int L // (현재 레벨),
DFS() 메서드 // 핵심 로직,
핵심 문제 해석
첫째로 모두라는 키워드가 등장한 순간부터 DFS를 생각해볼 수 있다.
DFS는 모든 경로의 수를 구할 때 사용되는 알고리즘이기 때문이다.
그래서 바로 DFS로 접근했다.
둘째로 순열은 중복되는 경우가 없어야 한다.
이 점을 잘 생각하고 문제를 풀이해나가야 한다.
핵심 코드
public void DFS(int L){
if(L == m){
for(int x : result){
System.out.print(x + " ");
}
System.out.println();
}else{
for(int i = 0; i < n; i++){
if(ch[arr[i]] == 0){
ch[arr[i]] = 1;
result[L] = arr[i];
DFS(L+1);
ch[arr[i]] = 0;
}
}
}
}개선된 점
논리적으로 문제에 접근하려고 노력했다.
예전에는 막히는 순간이 왔을 때 코드를 다 지우고
"아 대체 왜 안되는거야.. 처음부터 다시시작해보자..!"
라는 식으로 접근했었는데
지금은 논리적으로 어느 부분에서 내가 막혔지?
어느 부분을 해결해야하지?
와같은 방식으로 접근한다.
문제 풀이 과정
처음부터 백트래킹을 생각할 수 있었던건 아니다.
DFS 알고리즘을 그려보고, 자료구조를 생각해보고, 조건문을 세워보고, 스택프레임 만들어보면서 풀이했다.
백트래킹을 생각하지 못한 상태에서 조건문을 세우려다보니 무언가 막힌 느낌이 들었다.
중요한건 어느 부분에서 막혔느냐를 논리적으로 파악하는 것.
알고리즘 그림을 그려보면 DFS로 뻗어나갔을 때 이전 인덱스와 중복되지 않아야한다는 사항을 조건문으로 만들어야 했다.
어떻게 할 수 있을까 하다가 check 배열을 생각해냈다.
check 배열은 생각했지만, 스택프레임이 제거되면서 check된 인덱스를 0으로 초기화해줬어야 했다.
그때 백트래킹이 생각났다.
백트래킹의 위치가 어디였지?
DFS 재귀함수를 호출하는 다음 라인이었지, 일단 거기다 선언해보자.
그리고 나서 스택프레임을 그려봤다. 정답에 가까워지는 순간이었다.
하지만 거기서 내가 헷갈렸던 부분은 스택프레임에서 백트래킹이 어느 시점에 호출되느냐였다.
그리고, 고민하다가 내린 결론은 L == m이 되어 return 하게 되면 다음 라인으로 이동하므로 그때 빽트래킹이 일어나면서
해당하는 ch[arr[i]] 값이 0이 된다.
이건 내가 논리적으로 생각해서 내린 결론이고, 그게 실제인지 디버그로 확인해봤다.
내가 생각한대로 흘러갔다.
느낀점
첫째로 논리적으로 문제에 접근하고 정확히 어느 부분에서 문제가 발생했고, 어려움을 느끼는지 고민해보자.
둘째로 처음 알고리즘을 풀이할 때에 비해서 알고리즘 풀이 능력이 많이 향상됨을 느낀다.
문제 유형 파악, 자료구조 파악, 알고리즘 파악, 논리적으로 문제 해결하기, 알고리즘 그려보기 등의 방식이 많이 도움되는걸 느낀다.
더 잘하려고 노력하자
