바야흐로,,,

삼성 기출 문제 중에 '뱀' 이란 녀석에게 당하고 난 후, 스택과 큐의 개념을 더 확실히 잡고자(원래도 알고는 있지만) 매번 상기하기 위해 개념 정리를 다시 하려고 이 게시글을 작성 함 [03.09]

당시, DFS로 부셔보려다 테스크 케이스는 모두 통과하였으나, 논리적인 오류가 있음을 파악하고 아~ 이건 DFS로 하면 엄청 고생하겠구나를 깨닫고, 조금만 더 생각해보니 아! 큐를 쓰면 ~? 생각해보니 개쉬운 문제로 느껴졌다 ...

따라서~ 스택과 큐 개념을 그냥 부셔놓고 가겠다는 MIND

First, Stack(스택)

• 스택은 뭘까?

스택은 나중에 들어온 애들이 먼저 나가는 동방예의지국에서 용납할 수 없는 자료구조다

그런데, 이런 놈을 이용하는 알고리즘이 있다 ? 그건 ,,, 내가 뱀한테 썼다가 조짐을 당했던 DFS, 즉 재귀다 재귀

재귀는 들어온 놈이 가장 아래에 깔리고, 깊이 우선 탐색으로 쭉쭉 들어가서 나중에 들어온 놈이 Return ~ 되면, 즉 가장 늦게 들어온 놈이 나가는 방식으로 진행된다

Second, Queue(큐)

• 큐란 뭘까?

큐는 먼저 들어간 놈이 먼저 나가는 정상적인(?!) 자료구조다 ~

보통 코테 문제 풀 때는 import deque~ 해서 deque를 이용해가지고, popleft 함수나 appendleft같은 거 써먹어서 시간 복잡도를 줄이는 데 많이 사용된다 (실제로 이점은 많은 걸로 아는데 대충 이것만 알아도 잘 써먹음)

그래서, 이 자식은 보통 최단거리 구하거나, 그래프 탐색할 때 사용되는 BFS에 많이 사용된다.

참 보면 보통 문제들이 재귀보다 BFS를 더 좋아하는 것 같기도 하다.

BFS, DFS 개념은 잘 아는데 어느 알고리즘이 더 좋을 지, 구현하기 편할지 이런 것과 같은 연습을 더 많이 해야겠다
오늘은 일단 여기까지