1. 문제 25416번: 빠른 숫자 탐색 5 x 5 크기의 보드가 주어진다. 보드는 1 x 1 크기의 정사각형 격자로 이루어져 있다. 보드의 격자에는 -1, 0, 1중 하나의 숫자가 적혀 있다. 격자의 위치는 (r, c)로 표시한다. r은 행 번호, c는 열 번호 www.acmicpc.net 2. 풀이 전형적인 미로 탐색 문제이다. BFS의 개념을 이해하고 있다면 Standard와 같은 문제이므로 큰 어려움 없이 풀이가 가능하다. 네 방위(동, 서, 남, 북)로 움직일 수 있는 학생이 움직일 수 없는 조건에 대해서만 적절하게 체크해주면 풀이가 가능하다. 까다로운 조건 없이 좌표계에서 이동만 하는 것이며, `1`이 적힌 어딘가에 있는 지점으로 도달해야하므로 BFS가 가장 적합한 수단이라고 볼 수 있다. 학..

BFS(너비 우선 탐색) 알고리즘에 대해 알아보기 전에 필수적으로 알아봐야 할 자료구조는 바로 그래프(Graph)다. 그래프는 실질적으로 프로그래밍 언어 라이브러리 상에서 제공하기 보다는 추상적인 자료구조로써 개념을 차용하여 알고리즘에 응용하여 푸는 경우가 많으므로, 자료구조 카테고리가 아닌 알고리즘 카테고리에서 함께 다루고자 한다. 그래프 그래프의 정의 및 개념 그래프(G)는 정점 집합(V)과 간선 집합(E)으로 구성된 자료구조로, 대상과 대상 간의 관계를 나타내는 자료구조다. 그래프는 다들 너무나도 익숙하게 들어봤을 '쾨니히스베르크(Königsberg) 다리'를 보고 수학자 오일러가 '한붓그리기' 문제를 해결하기 위해 고안한 것으로 알려져 있기도 하다. 이 고안법에서 중요한 것은, 각 육지를 잇는 다..

개요 스택 자료구조에 대해서 알아본다. 스택(Stack)이란? 스택은 데이터를 저장할 객체와 객체에 적용할 수 있는 연산을 함께 정의한 추상 자료형으로써, 앞으로 다룰 큐(Queue), 데크(Deque)와 같이 자료 구조 형태에 이름이 붙었다는 것에서 큰 의의를 갖는 자료형이다. 스택은 너무나도 잘 알려져 있기에 간단하게 특징을 살펴본다. 위 이미지에서 6개의 선으로 간단하게 표현해서 알아보기 힘들 수는 있지만, 아래 용어정의들을 통해서 스택의 개념을 온전히 이해할 수 있을 것이라 생각한다. 1. LIFO(Last In First Out) 스택은 한쪽 끝에서만 자료를 넣고 뺄 수 있는데, 가장 늦게 들어간 자료가 가장 먼저 나오게 된다. 2. TOP 한쪽 끝에서만 데이터 입출입이 발생한다고 하였는데, 스..

특정한 문제를 풀이함에 있어 큰 문제를 작은 문제로 나뉘어서 푸는 방법들에 대해서는 앞선 포스트들을 통해 계속해서 언급하였다. 오늘 다룰 분할정복(Divide & Conquer)은 그 패러다임을 가장 직관적으로 다루는 테크닉이라고 볼 수 있다. 주어진 문제를 둘 이상의 부분 문제로 나눈 뒤 각 문제에 대한 답을 계산하고, 각 부분 문제의 답으로부터 전체 문제의 답을 계산해내는 것 분할정복은 아래의 세 구성요소로 다시 생각해볼 수 있다. Divide : 문제를 더 작은 문제로 분할하기 Merge : 각 문제의 답을 원래 문제에 대한 답으로 병합 Base Case : 더 이상 분할하지 않고 곧장 풀 수 있는 매우 작은 문제 세 구성요소에 대해서는 부가적인 설명이 필요없을 것으로 보이나, 분할정복으로 특정 문..

동적 계획법은 정말 가장 많이 대회에서 출제되는 문제 유형임과 동시에 반드시 알아야만 하는 내용이기도 하다. 명확하게 '이것이 동적 계획법 문제다' 라고 분류하기 보다는 앞선 브루트 포스나 그리디 알고리즘과 같이 문제를 풀어나가는 하나의 방법으로 접근하는 것이 올바르다고 생각한다. 동적 계획법 역시 큰 문제를 작은 문제로 나누는 것에서 출발한다. 지금까지의 내용을 정리하면 아래와 같다. 브루트 포스(Brute Force): 작은 문제 하나하나 다 살펴볼거야! 탐욕법(Greedy): 작은 문제마다 답을 선택해 버릴거야! 그렇다면 동적 계획법의 메커니즘은 어떤 것일까? 다른 작은 문제에서 만들어 놓은 값을 다시 쓸거야! 즉, 작은 문제들로 분류하여 연산을 하는 과정에서 같은 연산을 반복적으로 수행해야 한다면..

앞선 알고리즘 소개 포스트를 통해 완전 탐색을 알아보았는데, 완전 탐색(brute force)의 핵심은 큰 문제를 작은 문제로 분할하여 모든 경우를 탐색해보는 것이었으며 그 중, 작은 문제로의 분할이 가장 핵심이라고 볼 수 있다. 이는 비단 완전 탐색에 국한되는 것이 아니라 향후 다룰 동적 계획법(Dynamic Programming)이든, 지금 다룰 욕심쟁이 알고리즘이든 모든 알고리즘 문제의 가장 기본이 된다고 볼 수 있다. 완전 탐색이 모든 경우에 대해 체크한 후 최적의 해를 골라내는 것이었다면, 욕심쟁이 혹은 탐욕법(Greedy)의 경우 각 단계마다 현재 최선의 방법만을 선택하는 것을 의미한다. 다만 늘 현재의 최선의 해답만을 선택하므로, 앞으로 남은 선택지들에 대한 사항은 고려하지 않게 되는데 이로..

다양한 알고리즘 문제들을 풀이하는 방법들이 있는데 그 중 첫 번째는 역시 브루트 포스(Brute Force) 가 아닐까 싶다. 해킹 기법 중 가장 기본적인 공격 방식 중에 '무차별 대입 공격(brute-force attack)'이라는 것이 있는데, 이는 특정한 암호를 풀기 위해 가능한 모든 값을 대입하는 방식을 의미한다! 쉽게 생각하자면 아래 자전거 자물쇠를 살펴보면 된다. 이 자전거 자물쇠를 푸는 가장 쉬운 방법은 '0000' 부터 '9999'까지 하나씩 돌려보면 될 것이다. 브루트 포스(brute force) 알고리즘 역시 마찬가지다. 다른 말로 '무식하게 풀기'라고도 하는데, 특정한 문제에 발생 가능한 경우의 수를 일일이 나열하면서 답을 찾는 것이다. 최단 거리를 찾기 위해 노드 간의 경로들을 일일..

1. 문제: https://www.acmicpc.net/problem/2504 2504번: 괄호의 값 4개의 기호 ‘(’, ‘)’, ‘[’, ‘]’를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된다. 한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’는 올바른 괄호열이다. 만일 www.acmicpc.net 2. 풀이 Stack을 응용한 대표적인 문제를 꼽으라면 단연 괄호와 관련된 문제라고 할 수 있다. 괄호의 쌍이 올바르게 되어 있는가를 판단할 때 스택의 특성을 가장 적극적으로 활용할 수 있는데, 여는 괄호는 스택에 넣고 닫는 괄호는 스택에서 pop을 해 쌍을 확인함으로써 풀이할 수 있다. 문제 해석에 앞서 잠시 올바른 괄호의 쌍인가를 확인하는 코드를 정리하고 간다. // '()' 소..