달공이와 임베디드

알고리즘 문제를 풀 때, 곤란한 상황이 발생할 때가 있다. 문제를 잘못 이해하는 것이다. 그래서 처음 문제를 읽을 때 집중해서 읽는 것이 중요하다. 처음 문제를 보고 이해한 것은 다음과 같았다. A, B 위에 있는 아치형 곡선이 겹치지 않으면 좋은 단어다. 그러나, 진짜 문제는 다음과 같았다. A, B 를 짝지었을 때, 곡선이 겹치지 않고 짝이 지어지면 좋은 단어다. 즉, 짝이 지어져야 한다는 것을 간과했었다. 다음과 같이 구현할 수 있다. #include #include #include #define input_size 100000 + 1 using namespace std; deque st; char input[input_size]; int n; int main() { cin >> n; int cnt..

본 문제는 "(" 와 ")" 로 표현되는 쇠막대기의 수를 구하는 문제이다. 이런 류의 문제를 풀 때면 종종 실수하는 것이 있다. 왜 그렇게 되는지 증명하려 한다는 것. 왜 "(", ")" 의 표현만으로 잘라진 쇠막대기의 수를 모두 나타낼 수 있는지를 생각한다는 점이다. 뭐 번쩍이는 두뇌로 1:1 매핑되는 것을 순간적으로 알아차릴 수 있다면 말리지 않겠지만, 그냥 1:1 매핑이 된다고 가정하고 문제로 넘어가는 것이 상책이다. 그 가정 하에서 1:1 매핑되는 공식만 알아차리면 된다. 공식은 다음과 같다. ※ stack 부분 (state update) "( )" 이면, stack pass, "(" 이면, stack +1, ")" 이면, stack -1 ※ calculate 부분 "( )" 이면, stack s..

https://www.acmicpc.net/problem/1065 1065번: 한수 어떤 양의 정수 X의 각 자리가 등차수열을 이룬다면, 그 수를 한수라고 한다. 등차수열은 연속된 두 개의 수의 차이가 일정한 수열을 말한다. N이 주어졌을 때, 1보다 크거나 같고, N보다 작거나 같은 한수의 개수를 출력하는 프로그램을 작성하시오. www.acmicpc.net 부르트포스에 분류되는 문제이다. 시간제한이 2초, n=1000, O(n) 복잡도로 해결하였다. #include using namespace std; int main() { int n; int ret; cin >> n; if (n

지난 포스팅에서 STL deque을 사용하면, stack과 queue를 구현할 수 있고 element access 할 수 있어, STL stack, queue 를 사용할 때보다 편리한 점이 있다고 소개했었다. 이번 시간에는 해당 예제를 살펴보도록 하겠다. 아래와 같은 map이 있다고 하자. 우리가 알고자 하는 것은 (0, 0)에서 (6, 5)로 가는 모든 경로와 최소 거리이다. int map[7][7] = { { 1, 0, 0, 0, 0, 1, 0}, { 1, 1, 0, 0, 0, 1, 0}, { 0, 1, 1, 1, 1, 1, 0}, { 0, 1, 1, 0, 0, 1, 1}, { 1, 1, 0, 0, 0, 1, 0}, { 1, 0, 0, 0, 1, 1, 0}, { 1, 0, 0, 0, 1, 1, 0},..

STL unordered_map ? 이름이 생소할 수도 있겠다. 그냥 hash 자료구조라고 생각하면 된다. hash 자료구조는 언제 쓰는가? 검색이 빨라야할 때 쓴다. 특히, 특정 string을 통해 값을 구할 때 key(string) - value(int) 빠르게 찾을 수 있다. 계속 강조하지만, 빠른 것이 장점이다. 이름에서부터 느낄 수 있듯 ordered (sorted)를 기대하면 안 된다. 여기서 말하는 ordered 는 key의 정렬을 의미한다. sorted + key(string) - value(int) 구조를 원하면, STL map을 사용하라. 참고로 unordered_map은 hash 기반으로 map은 tree 기반으로 구현되기 때문에 unordered_map의 key들은 정렬되어 있지 않..

"deque" 디큐가 아니다. 덱이라고 부른다. deque를 사용하여, queue와 stack을 구현할 수 있다. STL에 queue와 stack 이 있는데, 왜 따로 구현하냐고? http://www.cplusplus.com/reference/queue/queue/ queue - C++ Reference container_typeThe second template parameter (Container)Type of the underlying container www.cplusplus.com http://www.cplusplus.com/reference/stack/stack/ stack - C++ Reference container_typeThe second template parameter (Contai..

인접 행렬 그래프 1 단방향 그래프 인접 행렬로 그래프를 나타냄 dfs-recursion 3번 노드 출발점 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 #include #include using namespace std; int graph[7][7] = { {0, 0, 0, 0, 1, 0, 0}, {1, 0, 0, 0, 0, 0, 0}, {0, 1, 0, 1, 0, 0, 0}, {0, 1, 0, 0, 1, 0, 0}, {0, 0, 0, 0, 0, 1, 0}, {0, 0, 0, 0, 0, 0, 1}, {0, 0, 0, 0, 0,..

https://www.acmicpc.net/problem/1463 문제 정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다. X가 3으로 나누어 떨어지면, 3으로 나눈다.X가 2로 나누어 떨어지면, 2로 나눈다.1을 뺀다. 정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오. 입력 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. 출력 첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다. 123456789101112131415161718192021222324252627282930313233343536373839404142#include using namespace std; const int N ..