C++ 프로그래밍 (5) 썸네일형 리스트형 이분탐색 (binary search) C++ STL 사용법 알아보고, 구현해보자! 1. 정의 살펴보기 오늘은 이분 탐색 알고리즘에 대해서 알아보겠다. 여느 때와 동일하게 위키피디아를 켰다. 장황하게 설명되어 있는데, 핵심 문장을 살펴보면 아래와 같다. 타겟 밸류와 배열의 중간값을 비교하여 일치하지 않았다면 '타겟이 있을 수 없는 절반의 영역을 삭제' 한 후, 나머지 절반의 영역에서 해당 과정을 반복하는 탐색방법이다. 이 탐색은 타겟이 발견될 때까지 계속된다. 라고 되어있다. 요컨데, 내가 초등학생 때 했던 놀이 중 하나와 상당히 닮아 있는 것 같다. 혹시 Up Down 게임을 해 봤다면 이해가 굉장히 쉬울 것 같다. 1부터 100까지의 숫자를 하나 생각하고, 상대가 하나를 추측해서 제시한다. 그럼 나는 내가 생각한 숫자가 더 크다면 UP, 내가 생각한 숫자가 더 작다면 DOWN을 외치.. 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.. C++ sort() 함수에 대해서 알아보자. 1. 정의 살펴보기 백준 단계별로 풀어보기 13장에 해당하는 정렬 단원에서는 algorithm STL에 속해있는 sort() 함수를 사용하는 문제가 등장한다. 우선 sort() 함수가 어떤 함수인지 먼저 알아보기로 했다. cplusplus.com 에서 제시된 sort() 함수의 사양이다. 차례로 살펴보자. 우선 sort 함수의 템플릿을 보면 변수를 2개 입력 받는 경우와, 3개 입력 받는 경우의 두 가지가 있다는 것을 알 수 있다. 이 녀석을 해석해보자. 1. [first, last) 범위에 있는 원소들을 '오름차순'으로 정렬한다. 2. 변수를 2개 입력 받는 경우는 < 연산자를 사용해 정렬하고, 변수를 3개 입력 받는 경우는 comp 변수를 사용해 정렬한다. 3. 동일한 원소의 경우 기존의 순서를 보장.. 이전 1 다음
