1. 개괄탐색에도 전략은 존재한다이게 당연하다면 당연한 이야기일 수도 있는데, 어떠한 배열 내에서 자신이 원하는 값을 찾을 때에도 나름의 원소를 찾는 방법, 다른 말로 "전략"이 존재합니다.약간의 예시를 들어 보죠. 흔히들 "업다운 게임"이라고 불리는, 진행자가 생각해 둔 숫자를 찾기 위해 참가자들이 숫자를 제시하면 진행자가 생각한 수와 비교해서 참가자가 제시한 수가 큰지 작은지를 묻는 과정을 반복해 가며 수를 찾는 게임입니다. 이 게임도 엄밀히 말하면 탐색이죠. 1부터 (예를 들면) 100까지의 수 중 단 하나를 찾아 내야 하니까요. 이 게임에서 얼마나 훌륭한 전략을 세우는지가 게임을 유리하게 운용할 수 있는 열쇠가 됩니다.알고리즘도 마찬가지로, 탐색을 위해 여러 가지 전략을 사용합니다. 이번 장에서는..

1. 정렬의 전략전략이 필요할까?저는 컴퓨터공학과를 처음 접하는 후배들에게 간혹 "컴퓨터는 너희가 생각하는 것 그 이상으로 멍청하단다!"라는 이야기를 자주 하곤 합니다. 그 예시로 자주 드는 문제가 하나 있는데요. 제가 여러분에게 수열 하나를 줄 테니, 이를 비내림차순으로 정렬해 보십시오.$$\{1, 5, 4, 0, 8, 6, 3, 7, 9, 2\}$$아마 여러분의 사고 회로는 다음과 같지 않을까 사료됩니다.제시된 수열은 $\left[0, 9\right]$를 만족하는 정수 총 10개를 모두 포함하고 있다.따라서, 이 수열을 비내림차순으로 정렬하면 $\{0, 1, 2, 3, 4, 5, 6, 7, 8, 9\}$가 될 것이다.하지만, 컴퓨터가 1.을 수행할 수 있을까요? 어이없는 이야기이지만, 컴퓨터가 1.을..

1. 개괄"그리디한 알고리즘"이란?영어로 "탐욕스러운", "욕심 많은"이라는 뜻을 가진 Greedy라는 영단어가 있습니다. 오늘 배우게 될 알고리즘은, 이 Greedy라는 단어에서 그 어원을 따온 알고리즘으로, 한글로는 "탐욕법", 영어로는 Greedy Algorithm이라는 이름을 갖고 있습니다.단적으로 Greedy라는 단어 하나만으로 알고리즘을 설명하게끔 이름이 설정되어 있다니, 참 재미있죠? 탐욕법은 실제로 Greedy한, 즉 각 단계마다 지금 가장 좋은 방법을 선택하는 방식을 사용합니다.성립할 수 있는 알고리즘인가?일단 지금까지 우리가 배운 내용에 대해 생각해 보면, 알고리즘을 푸는 과정에서 우리는 가급적 "거의 모든 경우"를 다 따져 보곤 했습니다. 그러한 시점에서 보면, 뭔가 "지금 가장 좋은..

1. 가장 긴 증가하는 부분 수열연속해서 커지거나 작아지는 수열[참고 예제] BOJ #11053: 가장 긴 증가하는 부분 수열 11053번: 가장 긴 증가하는 부분 수열https://www.acmicpc.net/problem/11053다음의 문제를 생각해 봅시다.$n$개의 수가 나열된 수열이 주어진다. 이때, 그 수열 안에서 연속해서 커지거나(같은 경우도 포함), 연속해서 작아지는(같은 경우도 포함) 수열 중 가장 긴 것의 길이를 구하시오.DP 문제 중에서 굉장히 잘 알려진 문제로, 흔히들 최대 증가 부분 수열 문제, 영어로는 Longest Increasing Subsequence, 줄여서 LIS 문제라고도 합니다. LIS라고 하면 최대 증가 부분 수열 자체를 의미하는 게 더 크니 참고하셔도 될 듯 합니..

1. 다이나믹 프로그래밍올 것이 왔다드디어 저희는 알고리즘의 꽃을 배울 차례가 되었습니다. 바로 동적 계획법, 영어로는 Dynamic Programming, 줄여서 DP라고 부르는 그 녀석이죠. 이것[#]과는 아무 연관이 없는 용어이니 참고해 두시면 좋겠습니다.사실 DP는 그 이름과는 다르게 전혀 다이나믹하다고 볼 만한 특징은 별로 없습니다. 그렇다고 영어 원어인 Dynamic과 연관이 있냐고 하면 그건 또 아닙니다. 그럼 대체 왜 Dynamic한 프로그래밍 기법이냐, DP의 고안자인 리처드 어니스트 벨먼( Richard Ernest Bellman)은 그냥 Dynamic이 멋있는 단어라는 이유로 이 단어를 선택했다고 합니다. 이걸 한글로 옮기는 과정에서 그냥 "Dynamic"을 "동적"으로 해석해 버린 ..

1. 개괄분할 + 정복분할 정복이라는 용어를 처음 보면, 뭔가 전혀 안 어울릴(?) 듯한 두 개의 용어가 붙어 있습니다. 분할과 정복이라니, 대체 이게 무슨 말일까요?단순히 생각하자면 (1) 분할 (2) 정복 이라는 방향성으로 접근하는 게 좀 더 편합니다. 그러니까 문제를 분할한 다음에 분할된 문제들을 정복하는 방식이라는 건데, 좀 더 쉽게 이해가 되려나요? 분할 정복(Divide & Conqure)의 정확한 정의는, 주어진 문제를 둘 이상의 부분 문제로 나눈 뒤, 각 부분 문제의 답으로부터 전체 문제의 답을 계산해 나가는 문제 해결 전략입니다.분할 정복과 재귀 호출의 차이그렇다면, 단순히 문제를 나눈다는 점에서는 재귀 호출과 뭔 차이가 있는 건가 싶을 수 있겠지만, 분할 정복이 재귀 호출과 가지는 가장..

1. 잘 알려진 알고리즘들알고리즘을 설계한다는 것이제 우리는 기초적인 자료 구조에 대한 많은 내용들을 공부하였습니다. 이제부터 본격적으로, PS에서 사용되는 알고리즘을 알아보도록 합시다. 그런데 다만, 알고리즘은 어떻게 설계해야 할까요?사실 알고리즘을 설계한다는 건 생각보다 까다로운 작업입니다. 뭐 알고리즘이 요구하는 작업이 쉽다면 모르겠지만, 알고리즘이 너무 많은 걸 요구한다거나, 그렇지 않다 하더라도 요구사항에 대해 별로 생각하지 않고 시작한다면 알고리즘 설계가 얼마나 어려운지 바로 감이 잡힐 겁니다.그래서 알고리즘을 설계할 때는 다양한 전략과 관점이 필요합니다.알고리즘 설계 전략흔히 알고리즘을 설계할 때는, 우선적으로 여러 가지 전략적인 선택이 필요하고, 혹여 필요하다면 한순간의 영감이 도움이 될 ..

1. FIFO와 LIFO선입선출과 후입선출지금부터 우리는, 동적 배열 이외에 알고리즘 이론과 PS에서 가장 많이 쓰이는 자료 구조인 큐, 스택, 덱을 다루게 될 것입니다. 그런데, 그 이전에 한 가지 알아야 할 개념이 있는데요. 바로 선입선출과 후입선출이라는 개념입니다.먼저, 선입선출과 후입선출을 한자어 그대로 해석해 보죠. 선입선출(先入先出)을 해석하면 먼저 들어온 게 먼저 나간다는 의미이고, 후입선출(後入先出)을 해석하면 나중에 들어온 게 먼저 나간다는 의미입니다. 뭔가 감은 잡히는데, "먼저 들어온 게" 또는 "나중에 들어온 게" "먼저 나간다"는 게 대체 정확하게 무슨 의미일까요?자, 우리 놀이공원에 갔을 때를 생각해 봅시다. 여느 놀이공원이든, 인기 있는 어트랙션을 타기 위해서는 긴 대기줄을 기..

1. 벡터그 벡터 아님대학교에서 Calculus를 배우신 분이라면, 벡터에 대해 모르시는 분은 없으리라고 생각합니다. 흔히들 크기만을 가지는 양인 "스칼라"와 비교하여 크기와 방향을 모두 가진 "벡터"를 떠올리시는 분들이 많죠. 하지만 C++에서는, 특히 STL에서는 벡터라 함은 조금 다른 대상을 지칭합니다.C++를 배울 때 한 번 이상 다루는 내용이 바로 1차원 배열입니다. 일반적으로 C에서는 다음과 같은 방식으로 배열을 선언합니다.int val[10];위와 같이 선언하면, 10개의 값을 저장할 수 있는 val이라는 배열을 만들 수 있게 됩니다.하지만, C++ STL을 사용하다 보면 일반적으로는 위의 방식이 아닌, "벡터"라는 방식을 사용하여 1차원 배열을 활용합니다. 벡터는 다음과 같이 선언됩니다.#..

1. 동적 배열과 정적 배열배열의 한 가지 허점프로그래밍을 하다 보면, 필연적으로 같은 종류의 자료 여러 개를 함께 놓고 생각해야 하기 마련이죠. 그래서 프로그래밍 언어들은 이 자료들을 효율적으로 다룰 수 있게끔 자료 구조를 하나 만들었는데 그것이 바로 여러분들이 많이 사용하는 배열입니다.다만, 배열에는 다소 큰 문제점들이 여럿 존재합니다. 이를 알아보기 위해 배열의 선언에 대해 한번 생각해 보죠.int list[30]우리가 이 배열의 크기를 30에서 바꿀 수 있을까요? 없습니다. 이는 굉장히 중요한 사실인데, 이 배열에 30개보다 더 많은 개수의 자료를 넣을 수 없다는 것을 의미하기 때문입니다.이외에도 배열의 원소들의 순서를 유지하면서 배열에 원소를 끼워 넣는 등의 과정이 상당히 난해하다는 등의 문제점..