안되면 외우자
티어같은건 전혀 의미없다고 생각하지만...그래도 대충 본인의 수준을 소개하자면
대략 이렇다.
글로 정리해보자면 다음과 같다.
- 대기업 코테는 고사하고 사이트에서 한 문제 풀때마다 쩔쩔맨다😂
- dp, bfs, 이분탐색, 다익스트라(사실 아예 모름)에 약하다.
- 프로그래머스 1~2레벨, 백준 ~실버1,2까지는 수월하게 푼다. 그 다음단계에서는 풀이의 감은 잡지만, 코드로 구현하지 못함. or 아예 접근 방식을 모름
- 비전공자
그리고 큰 문제가 있었음. 개발자라면 어느정도 수준의 알고리즘은 풀줄 알아야 한다고 생각했다.
그래서 그런지...외우거나 대충 보고 넘긴 적이 없음.
이게 하다보니까 큰 문제였다.
수학 공식을 잘 알지도 못하면서 응용 문제를 풀려고 한 격이다.😱
자존심 버리고 못한다는 걸 인정하고 일단 외우자.
외우면서 이해하자. 이해했는데 응용하지 못해도...그래도 일단 외우자. 코딩도 마찬가지였다.
접근법과 템플릿(코드를 어떻게 작성하는지 큰 틀)을 외우다보니 이전보다 실력이 늘 수 있었음!
그럼 외우러 가보자! 약한 분야부터 하나씩 살펴볼 것이다.
BFS
약한 분야중 하나인 BFS. 일단 생각나는대로 정의를 해보자.
- 너비 우선 탐색. 트리나 그래프에서 자주 쓰인다. 다차원 배열 탐색에서도 많이 쓰인다. 큐를 이용한다. 즉, 먼저 들어온게 먼저 나간다.(FIFO)
- 좌표에서 특정 두 좌표의 최단 거리를 구할때 쓰인다. 왜냐하면, bfs는 인접한 모든 방향(노드)을 탐색하기때문에, 도착점의 좌표에서 거리를 가져오면 그게 최단 거리다.
예시문제) row x col배열내 최단거리 탐색
//row x col크기의 배열
const bfs = () => {
const dx = [-1,0,1,0];
const dy = [0,1,0,-1];
const visited = Array.from({length:row}, () => Array(col));
const queue = [];
//시작점이 (0,0)일 때. 방문하고, 큐에 넣어둔다.
visited[0][0] = 1;
queue.push([0,0])
//큐에 값이 남아있을 때 까지
while(queue.length){
const [x,y] = q.shift(); //원래는 큐를 구현해서 처리한다.
for(let k = 0; k < dx.length; k++){
const nx = x + dx[k];
const ny = y + dy[k];
if(nx < 0 || ny < 0 || nx >= row || ny >= col) continue; //배열 범위를 벗어나서 탐색한 경우
if(visited[nx][ny] || board[nx][ny] === '장애물') continue //방문하였거나, 보통 지도에 장애물이
visited[nx][ny] = 1; //방문표시
queue.push([nx,ny])
}
}
}핵심을 외워보자!
dx,dy는 각 상(x-1,y) , 하(x+1,y), 좌(x,y-1), 우(x,y+1)를 탐색하기위해 만들어진 배열이다.- 큐에서 꼭 FIFO로 꺼내야지만 bfs탐색이 가능하다.
while문을 사용하기 전 시작점은 방문처리후 큐에 넣어준다.- 범위를 벗어나거나 장애물이 있을때도 잘 처리해준다.
이게 BFS의 핵심이다!
DFS
BFS는 그런대로 수월하게 풀지만, DFS는 잘 생각을 못한다. 특히 재귀쪽이라 그런가 더 어렵게 느껴진다.
예를들어 조합, 순열등을 구하는 문제가 나올때 쥐약이다. 재귀로 구해야하는데...😓
일단 생각나는대로 정의를 해보자.
- 깊이우선 탐색 방식이다. 현재 인접한 방향중 한 방향(노드)을 골랐으면, 거기로 쭉 간다. 왜냐하면, 스택을 이용한 LIFO기 때문이다! => 제일 최근에 넣은 방향(노드)를 꺼내서 사용하기 때문이다.
- DFS는 보통 재귀로 구현한다. (스택을 대신해서?)
내가 생각한 정의는 이랬다. 실제 문제를 풀때도 보통 재귀를 이용했다.(기억이 안나면 템플릿을 뒤져보곤 했다)
하지만 BFS에서 큐를 스택으로 바꾸기만하면, 놀랍게도 DFS로직이 된다!
예시문제) DFS로 탐색
//row x col크기의 배열
const dfs = () => {
const dx = [-1,0,1,0];
const dy = [0,1,0,-1];
const visited = Array.from({length:row}, () => Array(col));
const stack = [];
//시작점이 (0,0)일 때. 방문하고, 큐에 넣어둔다.
visited[0][0] = 1;
stack.push([0,0])
//큐에 값이 남아있을 때 까지
while(stack.length){
const [x,y] = stack.pop(); //원래는 큐를 구현해서 처리한다.
for(let k = 0; k < dx.length; k++){
const nx = x + dx[k];
const ny = y + dy[k];
if(nx < 0 || ny < 0 || nx >= row || ny >= col) continue; //배열 범위를 벗어나서 탐색한 경우
if(visited[nx][ny] || board[nx][ny] === '장애물') continue //방문하였거나, 보통 지도에 장애물이
visited[nx][ny] = 1; //방문표시
stack.push([nx,ny])
}
}
}신기하구나!
지금까지 DFSF라면 재귀로만 작성했는데, 오히려 이 템플릿이 더 직관적이고 속도도 빠를 것 같다.
다만, 조합, 순열등을 이용할땐 재귀를 이용하는게 더 직관적이다. 하지만 어렵다.
재귀
재귀는 자기자신을 호출하는 함수이다. baseCondition이 무조건 있어야 탈출할 수 있다.
여기까지는 그래그래 하고 이해할 수 있다. 하지만 재귀 문제와 마주했을땐 어떻게 풀어야할지 감이 잡히질 않는다.
예를들면 하노이 탑 문제. 풀이를 보면 쉽게 이해간다. 이동 순서를 그냥 적어둔거네?
결국 귀납법으로 사고한 것이다. 그치만 인간은 귀납법 사고에 약하다! 바로 떠올릴수 없다.
그러면 어떻게 해야할까? => 재귀 템플릿 자체를 머릿속에 박아놓는다.
예시문제) 하노이의 탑
하노이 탑은 다음과 같이 생각한다.
n개 원판을 기둥1에서 기둥3으로 옮긴다.
이때 옮기는 순서를 출력하시오.
- 기둥1에서 n-1 ~ 1번원판까지를 기둥2(6-a-b)로 옮긴다.
- 기둥1에서 기둥3으로 n번째 원판을 옮긴다.
- 기둥2(6-a-b-)에서 기둥3으로 n-1 ~ 1번원판까지를 기둥3으로 옮긴다.
참고로 6-a-b는 3번기둥을 표현하기 위한 수식이다.
간단하지 않은가?
const hanoi = (from, to,n) => {
if(n === 1){
console.log(`${from}에서 ${to}로 옮깁니다`);
return;
}
hanoi(from, 6-from-to, n-1);
console.log(`${a}에서 ${b}로 옮깁니다`);
hanoi(6-from-to, to, n-1);
}
hanoi(1,3,n);귀납법 사고로 식과 basecondition을 세운뒤, 그냥 될거라는 믿음을 가져라. 그게 중요하다!
