[ TIL ] 프로그래머스 DAY6 : DFS, BFS, 그리디

🙋🏻‍♂️

지금 정리하는 내용은 일부 오타나 잘못된 내용이 기입되어 있을 수 있습니다. 가급적 오류를 줄이겠지만 일부분 발생할 수 있다는 점 양해부탁드립니다. 잘못된 내용 수정이나 추가 설명이 필요할 때 댓글로 알려주시면 감사하겠습니다.

🍪 배운 목록

• BFS, DFS
• 그리디
• 실습 여행경로
• 실습 큰수 만들기

🍽 배운 내용 요약 및 중요한 것

DFS

깊이우선탐색으로 보통 재귀 또는 스택으로 구현합니다.

예시코드

//input 배열이나 노드 등의 값이 arr로 주어질때

let visited = Array(arr.length).fill(false);

const DFS = (L)=>{
	if(L > 조건) return;
    
    for(let i = 0; i < arr.length; i++){
        if(문제에 맞는 조건 && visited === false){
          visited[i] = true;
          DFS(L + 1);
          visited[i] = false;
    	}
    }
}

DFS(1);

BFS

너비우선탐색으로 보통 큐로 구현합니다.

예시코드

//input 배열이나 노드 등의 값이 arr로 주어질때

let visited = Array(arr.length).fill(false);

const queue = [];

queue.push(arr[0]);
visited[0] = true;

while(queue.length > 0){
	const shift = queue.shift();
    
    arr.forEach((item, index)=>{
    	if(visited[index]) return;
    	
    	if(문제 조건){
        	visited[index] = true;
            queue.push(item);
        }
    })
}

그리디

주어진 그때 그때의 상황에서의 최적의 해를 구해서 최종답을 반환하는 알고리즘입니다.

따라서 문제의 전체적인 부분에서 최적의 해를 구하지는 못할 수도 있지만 직관적으로 처리가 가능하고 최적해를 주어진 조건과 기준에서만 구해도 예외가 없는 경우 사용하면 n 또는 n * log( n )의 시간복잡도를 얻을 수 있습니다.

위 알고리즘 같은 경우 일관적인 풀이형식이 없기때문에 나오면 까다로운 문제 중 하나라고 생각됩니다.

실습

여행경로

내 풀이

출발지가 같은 경우 알파벳 순서로 가야하기 때문에 먼저 sort()로 정렬을 해주고 이후 DFS를 돌려줍니다. 이때 재귀 종료 조건은 티켓을 전부 사용했는지와 알파벳 순서로 정답을 반환하기 위한 answer가 초기값인지를 확인한 후 DFS를 돌리면서 중첩해온 path 배열을 answer에 할당하면 정답이 됩니다.

큰수만들기

내 풀이

뽑아야할 수를 정해놓고 while문으로 해당 숫자까지 뽑으면 반복을 종료하게 설정해줍니다. 내부에는 최대값와 해당 인덱스 값을 얻기 위한 변수를 생성하고 반복문을 돌리면서 변수에 값을 할당해줍니다. 이때 조건으로 현재 max값보다 크고 해당 인덱스값에서 주어진 숫자 배열 끝까지 잘랐을때 길이가 남은 뽑는 수보다 작지 않을 경우에만 최대값과 인덱스에 값을 할당합니다. 이후 실제로 해당 배열에서 최대값이 걸린 인덱스를 포함하는 곳까지 splice로 잘라주고 answer에 최대값을 중첩해주면 정답이 나옵니다.

하지만...
위 풀이는 효율성을 만족시키지 못한 풀이로 시간초과가 무려 4개나 떴습니다. 결국 그리디하게 풀지 못했다는 것입니다. 사실 풀이는 보면 점점 반복을 돌리는 배열은 줄어드나 배열을 처음부터 끝까지 탐색한다는 사실은 변하지 않아 시간초과가 나온 것입니다.

정석풀이

뽑는 수에 집중하기 보다 제가하는 수에 집중하여 for문 안에서 while문으로 조건을 주어 스택과 제거횟수 변수를 조작해 스택에 조건에 부합하는 값들을 넣고 마지막으로 제거가 주어진 제거횟수만큼 되지 않았을때를 대비한 제거while문으로 엣지케이스를 잡아 최종적으로 join("")하여 문자열을 정답으로 반환합니다.

🧘🏻‍♂️ 어려웠던 점 및 후기

실습문제는 풀었던 문제였지만 역시 ... 다시 풀어도 헤매는 나를 발견했다.
이렇게 풀었던 문제를 다시 한번 복기해보는 것도 나쁘지 않다는 생각이 들었다. 그리고 그리디를 적용하는 문제는 좀더 그리디하게 생각하는 법을 길러야겠다고 느꼈다.

🔗 참조

프로그래머스 코테연습