전체 글

스택과 큐는 데이터를 제한적으로 접근할 수 있는 나열 구조로 가장 기본적인 자료구조 중 하나이다. 1. 스택(Stack) 데이터를 차곡차곡 쌓아올린 형태의 자료구조로 후입선출(Last in First Out) 개념이다. 스택에 나중에 들어간 놈이 먼저 나온다고 생각하면 된다. 그림과 같이 Stack에 데이터를 추가하는 작업을 push, 제거하는 작업을 pop 이라고 한다. StackOverflow(오버플로우): 스택이 가득차서 더 이상의 데이터를 추가할 수 없는 경우 ● stack.push(x) - 스택에 데이터를 추가 ● stack.pop() - 스택의 최상위 데이터를 삭제 ● stack.top() - 스택의 최상위 데이터를 반환 ● stack.empty() - 스택이 비었는지 확인 ● stack.si..

이분 탐색 또한 앞서 포스팅 했던 Brute force와 마찬가지로 solved.ac의 Class2에서 등장하는 알고리즘이다. 이분 탐색은 문제를 푸는 하나의 도구로 굉장히 중요하며 자유자재로 사용할 수 있어야 한다. 먼 미래지만 세그먼트 트리를 형성할 때 이분 탐색과 비슷한 형식으로 트리를 형성하고 그리디(Greedy) 등의 알고리즘과 함께 나와도 이상하지 않을 정도로 사용 빈도가 꽤 높다. 우리가 어떤 배열이나 벡터에서 숫자를 찾을 때 최악의 시간복잡도는 O(n)으로 선형 시간(Linear time)을 갖는다. (** 알고리즘의 실행 시간이 데이터가 증가함에 따라 선형적으로 증가할 때의 시간을 선형시간이라고 함.) 하지만 이분 탐색의 시간복잡도는 log2(n)으로 선형 탐색에 비해 빠른 시간 안에 원..

아마 solved.ac를 통해서 문제를 풀다보면 구현이나 수학 문제를 제외하고 가장 처음 접하는 알고리즘일 것이다. (주위에 물어보면 그래도 들어는 봤다라고 하는 사람이 많았다.) 이름은 거창하지만 이 기법은 모든 가능성을 빠짐없이 탐색하는 방법이다. 이 표현도 다시 표현하면 노가다 정도로 말할 수 있겠다. 사실 일반 구현문제하고 비슷하다. 브루트 포스라고 해서 특별한 방법이 있는 것이 아니라 가능한 모든 경우의 수를 전부 확인할 수 있도록 코드를 짜면 그게 Brute force 탐색이다. 그럼 속으로 그냥 다 해보면 되는거니까 완전 쉬운거 아닌가? 라고 생각할 수 있는데 다 탐색하도록 코드를 구상하는 것이 생각보다 쉽지 않다. 구현력을 상당히 많이 필요로 하는 알고리즘이다. 코딩테스트에서도 거의 빠짐없..

어떤 코드가 잘 짠 코드이고, 어떤 코드가 못짠 코드일까? 코드의 가독성, 메모리, 시간 등 여러 요소가 있겠지만 그중에서 효율성(시간)에 관련된 빅오 표기법에 대해 쓰려한다. ● Big-O Notation 정의는 다음과 같다. 전공서적에 있는 것을 그대로 옮긴 것인데, 해석한 그대로이다. n이 n0 보다 큰 경우에서 어떠한 양의 정수 c를 g(n)에 곱해도 함숫값이 f(n)보다 크거나 같은 경우 함수f(n)의 시간복잡도를 O(g(n))이라고 한다. 다시말하면, 어떤 알고리즘의 실행시간이 f(n)을 따라간다고 할때 그 알고리즘은 적어도 cg(n)보다는 빠른 시간에 작동된다는 뜻이다. 예를 들어, - f(n) = 5n²+3n+7는 O( n²) - f(n) = 6n+1은 O(n) - f(n) = 8n³+2n..

https://www.acmicpc.net/problem/20500 20500번: Ezreal 여눈부터 가네 ㅈㅈ 문제의 답을 $1\,000\,000\,007$로 나눈 나머지를 출력한다. www.acmicpc.net 우선 1과 5로만 이루어진 숫자가 15의 배수가 되기 위해서는 마지막 숫자가 5로 끝나야 한다. 마지막 숫자가 5로 끝나면 경우의 수는 3가지이다. 15로 나눴을 때 나머지가 5인경우, 10인 경우, 0인 경우. dp[i][0] 을 i자리수면서 나머지가 0인 경우, dp[i][1]을 i자리수면서 나머지가 5인경우, dp[i][2]를 i자리수면서 나머지가 10인 경우로 생각했다. 저렇게 나누고 4자리수까지 나머지가 0,5,10인 경우를 세 보았는데 다음과 같은 규칙이 보였다. dp[i][0] ..

https://www.acmicpc.net/problem/10835 10835번: 카드게임 첫 줄에는 한 더미의 카드의 개수를 나타내는 자연수 N(1 ≤ N ≤ 2,000)이 주어진다. 다음 줄에는 왼쪽 더미의 카드에 적힌 정수 A(1 ≤ A ≤ 2,000)가 카드 순서대로 N개 주어진다. 그 다음 줄에는 오 www.acmicpc.net 1. 왼쪽 카드만 버리는 경우 2. 왼쪽 카드와 오른쪽 카드를 버리는 경우 3. "왼쪽 카드 < 오른쪽 카드" 를 만족하여 오른쪽 카드만 버리는 경우 이 세가지 경우를 모두 고려해주어야 한다. dp[left][right] 는 왼쪽 카드와 오른쪽 카드를 left장, right장 버렸을 때 점수의 최댓값이다. 코드는 다음과 같다. #include #include using ..