C++ 알고리즘 (3) 썸네일형 리스트형 DFS와 BFS C++로 구현해보자! (재귀, 스택, 큐) 1. 개념 이해하기 (1) DFS (Depth First Search) DFS는 Depth First Search의 약자로, 말 그대로 깊이를 우선하여 탐색한다는 얘기이다. 아래 GIF 파일을 보고 쉽게 이해해보자. 1번 노드와 인접한 노드는 2, 5, 9 가 있는데 인접한 노드 중 숫자가 작은 곳 부터 들러보자. 2번 노드와 인접한 노드는 3이 있다. 바로 간다. 3번 노드와 인접한 노드는 4가 있다. 바로 간다. 더 이상 깊게 들어갈 수 없으니 바로 직전 노드인 3번 노드로 돌아간다. 3번 노드에서 가보지 않았던 더 깊은 노드가 없으므로 직전 노드인 2번 노드로 돌아간다. 마찬가지 이유로 1번 노드로 돌아간다. 이 때, 1번 노드에서 가보지 않은 더 깊은 노드가 있으므로, 그 중 숫자가 작은 5번 노.. DFS와 N-Queen 1. N-Queen 문제 살펴보기 이번 포스팅에서는 백준 9663번 문제, N-Queen에 대해서 알아보자. 해당 문제는 백준 '단계별로 풀어보기' 22단원인 백트래킹 단원에 속한 문제이다. 우선 문제를 한 번 보겠다. 흠.. 읽다보니 기시감이 느껴진다. 어디선가 많이 본 종류의 퍼즐문제인데... 필자는 어린 시절 닌텐도DS로 많은 게임을 접해왔다. 그 중 레이튼교수와 이상한 마을이라는 게임이 있는데, 마을 안에서 수수께끼를 풀어나가며 마을 안의 사건들을 해결해나가는 재미있는 게임이다. 안해봤다면 모바일 버전으로도 출시가 되었으므로 한 번쯤 해보는 것을 추천한다. 아무튼 해당 게임에 등장하는 수수께끼 중에 문제의 조건과 정확히 일치하는 문제가 있으니, 바로 '체스판의 퀸' 문제이다. 저번 하노이의 탑부터.. 하노이의 탑으로 보는 재귀함수 1. 하노이의 탑 문제 살펴보기 이번 포스팅에서는 백준 11729번 문제, 하노이의 탑에 대해서 알아보자. 해당 문제는 백준 '단계별로 풀어보기' 21단원인 재귀 단원의 마지막 문제이다. 우선 문제를 한 번 보겠다. 어린 시절 부모님이 장난감으로 사줬던 하노이의 탑을 정말 재밌게 가지고 놀았던 기억이 있다. 며칠 가지고 놀다보니 어느 순간 최소 이동횟수로 이동하는 방법을 깨닫고는 급격히 흥미가 식어버렸지만... 아무튼 추억의 장난감 하노이의 탑을 '최소 이동횟수'로 이동시키는 이동 순서를 출력하는 프로그램을 만들어보자. 2. 알고리즘 설계 N층짜리 하노이의 탑을 1번 타워에서 2번 타워로 최소 이동횟수만에 이동시키는 방법은 아래와 같이 생각해볼 수 있다. 1. N-1층짜리 하노이의 탑을 1번 타워에서 3.. 이전 1 다음
