문제 이해 단계 https://www.acmicpc.net/problem/12933 "quack"이라는 문자열이 존재하면 오리가 한 마리 있다는 의미인데, 이 문자들이 여러 개 겹쳐있다. 특이한 점은 quackquack 이런 식으로 연속적으로 문자열을 이을 수 있는 경우에는 한 마리로 취급한다는 것이다. 이런 조건일 때 오리를 최소로 했을 때의 오리 수를 구하는 문제. 문제 접근 단계 어떻게 풀지 고민하다가 힌트를 보고 감을 잡았다. 녹음: quqaquuacakcqckkuaquckqauckack 오리 1: ____q_u__a___ck_______________ 오리 2: __q__u_ac_k_q___ua__ckq_u__ack 오리 3: qu_a_______c___k__qu___a_ck___ 힌트에서는 오..

문제 이해 단계 https://www.acmicpc.net/problem/18427 N명의 학생이 각각 최대 M개의 블록을 가지고 있다. 학생들이 가지고 있는 블록은 전부 길이가 다르다. 예를 들어 1번 학생이 높이가 2,3,4인 블록을 가지고 있는 것처럼 모두 길이가 다르다. 높이 H가 주어지는데, N명의 학생이 순서대로 최대 1개를 사용해서 블록을 쌓을 때 정확히 높이 H가 될 수 있는 경우의 수를 구하는 문제 문제 접근 단계 일단 해당 문제의 키워드에 주목했다. 1. 최대 1개까지 쓸 수 있다.(안 써도 된다) 2. 1번 학생 ~N번까지 순차적으로 블록을 쌓는다. 1번 조건에서 해당 문제가 여러 가지 경우의 수로 나뉘는 것을 계산하는 문제라는 것을 알았고, 무엇보다도 2번째 조건에서 순서가 고정되어..

배낭 알고리즘이란? 배낭 문제(Knapsack)는 n개의 물건과 배낭 있을 때, 각 물건에는 가치와 무게가 존재한다. 또한 각 물건은 1개씩만 있다. 배낭에는 담을 수 있는 최대 용량이 존재한다. 이러한 조건일 때, 배낭의 최대 용량을 초과하지 않으면서 배낭에 담을 수 있는 최대 가치의 합을 찾는 문제이다. 해당 그림은 배낭 문제의 예시이다. 지금부터 알고리즘을 설명할 때 해당 예시를 가지고 계속 설명하겠다. 0-1 KnapSack Problem 배낭 문제는 물건을 쪼갤 수 있는 Fraction Knaspack Problem과 물건을 쪼갤 수 없는 0-1 knapSack Problem으로 나뉜다. 이 글에서 설명하고자 하는 것은 0-1 KanpSack Problem이다. 대표적인 DP(Dynamic Pr..

문제 이해 단계 https://www.acmicpc.net/problem/14719 2차원 맵이 주어진다. 이때 같은 층에 열로 가둬질 때 (위 그림처럼) 빗물을 담을 수 있다. 이 조건에서 2차원 맵의 크기가 주어지고, 각 행마다의 높이가 주어질 때 빗물의 총량을 구하는 문제이다. 문제 접근 단계 빗물의 총량을 구하기 위해서는 주어진 2차원 맵을 탐색 하면서 연산할 수 있는 일반화된 알고리즘이 필요하다고 생각했다. 그래서 일반화된 연산식을 만드는 것을 중점으로 생각했다. 첫 번째부터 쌓인 블록부터 탐색한다고 생각한다. 첫 번째 블록과 어떤 블록 사이에는 빗물이 쌓인다. 첫 번째 블록이 빗물을 담는 시작점이라고 생각(즉, 왼쪽 벽)하자. 그렇다면 첫 번째 블록과 쌍이 되는 오른쪽 벽은 어떻게 결정할까? ..

문제 이해 단계 쉽게 말하면 2차원 표가 주어지고 그 표 안에는 사람 수가 적혀 있다. 그리고 입력으로 시작좌표(x, y)와 끝좌표(x, y)가 들어온다 그 사이를 사각형으로 둘러쌓을 때, 그 안에 들어오는 사람수의 총합을 구하는 문제이다. 문제 접근 단계 일단 이 문제를 읽자마자 너무 당연해서 당황했다. 그냥 당연히 좌표제한해서 하나하나씩 세면 되지 않을까? 근데 그러면 문제를 냈을 리가 없지, 하면서 문제 조건을 잘 읽어봤다. 영토 크기는 최대 1024X1024 = 즉 2^20으로 엄청나게 크다. 무엇보다도 계산을 한 번만 하는 게 아니다. 궁금해하는 영토의 개수 K가 최소 100,000개이기 때문에 일반적으로 개수를 세서 더하는 걸로는 딱 봐도 시간초과가 뜰 것 같다. 이전 계산의 결과를 저장하거나..

문제 이해 단계 빨간색 : 누르는 버튼과 대응되는 스위치 파란색 : 버튼에 영향을 받는 스위치 문제는 N개의 스위치와 버튼이 나열되어 있는데 각각 1대 1 대응된다. I번 버튼을 누르면, 그 버튼 번호의 스위치와 양옆에 있는 스위치가 반전된다. 초기 상태와 결과 상태가 주어질 때 초기 상태에서 결과 상태까지 만드는 최수를 구하는 문제이다. 문제 접근 단계 일단 대략적으로 문제의 유형부터 생각해 보기로 했다. DP? 처음에는 Dp로 풀까 생각했었는데, 1. 처음 시작하는 수가 고정되어 있지 않다. 2. n = 1 일 때 3, n = 2 일 때 4.. 뭐 이런 식으로 값이 고정된 것도 아니다. 위의 근거로, dp는 아닌 것 같았다. Greedy? 그리디로 생각한 이유는 간단하다. 그냥 문제에서 "최소를 구해..

구현 사항 - 각 프로세서들이 각자의 queue를 가지고 작업을 수행 -queue 안에는 순차적으로 실행되어야 하는 Job이 존재 - 동시에 모든 큐를 진행해서 Job을 하나씩 처리한다. - 자신의 큐가 비어있으면 다른 큐에서 Job을 뺏어 처리한다. 구현 방식 큐라고는 하지만 처리하는 일은 앞에서 하고 뺏길 때 뺏기는 큐에서는 뒤에서 뺏기기 때문에 앞과 뒤에서 둘 다 요소를 뺄 수 있는 덱을 이용해야 한다. 덱을 이용해서 큐잉 모델 형식으로 구현을 하면 된다고 생각하고 구현하였다. 구현 #include #include #define MAX_DEQUE 100 int total = 0; typedef struct{ char* data[MAX_DEQUE]; int front,rear; }Deque; void..

문제 이해 단계 https://www.acmicpc.net/problem/17485 맵(표)이 하나 주어진다. 목표는 위에서 아래로 가는 것이다. 각 칸에는 점수가 있고 그 점수의 합이 최소가 되도록 하는 것이다. 여기서 규칙이 두 가지 존재한다. 1. 아래쪽으로만 이동 가능하다.(옆, 위로 이동 불가능) 2. 갔단 방향으로 연속 이동 불가능 (왼쪽 대각선, 왼쪽 대각선 이런 식으로 불가능) 이 조건일 때 점수의 합이 최소가 될 때, 그 최소의 점수가 얼마인지 구하는 문제 문제 접근 단계 일단 어떤 식으로 문제를 풀어야 하는지가 중요하다. 규칙 중 '아래쪽으로만 이동 가능하다'를 곰곰이 생각해 보자. 이 말은 한번 내려오면 위로는 다시 가지 못한다는 뜻이다. 즉, 만약 N번째 행까지 이동했다고 했을 때,..