알고리즘/acmicpc
-
SW 역량테스트 기출 문제집 분석알고리즘/acmicpc 2017. 4. 21. 20:12
백준 온라인 저지에서 삼성 SW 역량테스트 기출 문제집을 발견 했다. 분명히 시험시간에 감독관이 외부에 유출하지 말라고(말아달라고) 했을 텐데 싸트 문제처럼 이것도 외부 유출은 막을 수 없나 보다. 재미 삼아 여기 있는 문제들을 한 번 풀어 봤는데 문제들이 공통적으로 뚜렷한 경향이 있었다. 이번 포스트에서는 (문제집에 올라온 기출 문제들이 모두 사실이라는 전제 하에) 기출 문제를 분석하고 취준생 입장에서 어떻게 준비하는 것이 좋을 지를 정리 해봤다. 기출 문제 분석 1. 시뮬레이션 문제가 대부분 대부분의 문제들이 고급 알고리즘 없이도 풀 수 있다. 여기서 고급 알고리즘은 다익스트라나 최소 스패닝 트리 같이 대학교 알고리즘 강의에서 배우는 내용들을 말한다. 물론 기출로 나온 문제들을 고급 알고리즘을 적용한..
-
10422알고리즘/acmicpc 2017. 4. 5. 23:03
문제를 보자마자 DP를 써야 한다는건 직감했는데 식을 어떻게 세워야 할지 쉽게 감이 오지 않았다. 가장 직감적으로 들었던 식은 이렇다. 문자열의 길이가 K인 경우의 식은 아래와 같이 구할 수 있다고 생각했다. 1. dp[K] = dp[K-2] 2. dp[K] += dp[2]*dp[K-2] + dp[4]*dp[K-4] + ... dp[K-2]*dp[2] 이미 괄호의 개수가 정해진 K-2개의 문자열에 괄호를 끼운다고 생각하면 반드시 올바른 괄호가 되므로 1번 식은 성립한다. 2번 식은 나머지 경우들을 처리하는 식인데, K개의 괄호식을 만든다고 생각할 때 앞부분에 해당하는 괄호의 경우의 수 와 뒷부분에 해당하는 괄호의 경우의 수를 곱해주면 길이가 K인 문자열을 구할 수 있다고 생각했다. 하지만 위의 식은 중복..
-
1937알고리즘/acmicpc 2016. 9. 6. 18:50
모든 경로를 탐색하려고 하면 경우의 수가 무척 많아져서 어렵다. 여기서는 문제의 조건을 잘 살펴야 한다. - 판다는 상,하,좌,우 중 하나의 경로로 이동한다 - 대나무의 양은 증가하는 순서여야 한다. 위 두가지 조건만을 이용해서 dp를 만들어 줄 수 있다. dp[x][y]는 어떤 위치(x,y)로 도달 할 때 판다가 최대 살 수 있는 일 수를 가지고 있다고 하자. 그럼 다음과 같은 점화식을 적용 할 수 있다. dp[x][y] = (상하좌우에 있는 대나무중 현재 위치의 대나무보다 양이 작은 값들의 dp중 가장 큰 것) + 1 이해를 돕기 위해 그림으로 부연 설명을 하면.. 파란색으로 칠해둔 위치의 dp값을 업데이트 하려고 한다. 이때 파란색 위치로 접근 할 수 있는 경로는 (x,y)위치의 상하좌우중 (x,y..
-
4095알고리즘/acmicpc 2016. 8. 15. 21:54
행렬안에서 1로 이루어진 최대 정사각형을 찾는문제. 가장 쉽게 생각한다면 모든 점에서 만들 수 있는 최대 정사각형을 탐색해보는 방법이 있지만 이럴경우 O(N^4)로 시간초과가 날 수 밖에 없다. 하지만 구하고자하는 사각형의 형태가 정사각형인점을 잘 이용하면 다이나믹 프로그래밍을 이용해 O(N^2)안에 해결 할 수 있다. 어떠한 위치에서 정사각형을 만들 때, 이전에 만들어진 정사각형의 정보를 활용할 수 있는 방법을 생각해보자. 4번(X, Y) 위치를 꼭지점으로 하는 정사각형을 만들려고하자. 그러면 4번위치 주위에 1, 2, 3번의 사각형들을 생각해볼 수 있다. - 1번은 (X-1, Y-1)을 오른쪽 아래 꼭지점으로 할 때 가장 큰 정사각형이다. - 2번은 4번에서 위로 그을 수 있는 최대 선분의 길이다. ..
-
11437알고리즘/acmicpc 2016. 7. 30. 14:21
LCA를 푸는 문제다. LCA 최적화 알고리즘은 이미 정리해두었으니 넘기자. 문제에 주어진 간선을 가지고 어떻게 트리의 형태로 만드느냐가 LCA를 풀기 위한 조건이다. 일반적으로 간선에 대한 자료구조들은 2차원 배열을 이용해서 표현하지만 N이 10000을 넘어가면 2차원 배열의 최대 크기를 초과하게된다. C++에서는 vector를 사용해서 위와같은 문제를 간단히 해결 할 수 있지만 경우에 따라서 vector를 사용하지 못하는 상황도 존재한다. 간선 정보들을 필요할 때 마다 신속히 접근하는 자료구조가 중요한데 매번 모든 간선 정보O(N)를 찾아볼 수도 없을 노릇이다. 이런 경우에는 특정 경우 대해서 정렬을 해주는 방법이 유용하다. 간선에 대한 정보를 from들에 대해서 정렬을 해주고 각각의 시작점을 확인해..
-
2253알고리즘/acmicpc 2016. 7. 24. 13:10
위 문제는 가속/감속을 최대 1 만큼 한다는 것에 힌트가 있다. 돌의 개수가 최대 10000개 일 때 최대로 낼 수 있는 속도는 142이다. K*(K+1)/2 < 10000 현재 위치의 돌과 돌에 도착할 때의 속도로 새롭게 정점을 표현한다면 최대 정점의 개수는 10000 * 142 로 배열 내에서 선언이 가능한 범위가 된다. dp[N][V] : N번째 돌에 V번째 속도로 도착할 때의 최소 점프횟수 이제 각각의 정점을 방문해서 다음 위치에 움직일 때 최소 횟수로 움직이는 값을 업데이트 해주면 된다. #include #define MAXN 10000 int dp[MAXN + 5][200]; int forbid[MAXN]; int main() { int N, M; int i, j, tmp; int ans; f..
-
11049알고리즘/acmicpc 2016. 7. 24. 12:14
DP의 예시로 알고리즘 책에서 자주 나오는 유형 DP는 배열의 인덱스 값을 얼마나 유용하게 잘 사용하느냐에 달려있는 것 같다. dp[FROM][TO] : FROM부터 TO까지의 행렬들을 곱할 때의 값 위 값을 통해서 지속적으로 업데이트 해나가면 문제를 풀 수 있다. #include #define MAXN 500 int dp[MAXN][MAXN]; int data[MAXN][2]; int main() { int N; int i, j, len; freopen("input.txt", "r", stdin); scanf("%d", &N); for (i = 0; i < N; i++) scanf("%d%d", &data[i][0], &data[i][1]); for (len = 1; len < N; len++) { f..
-
2229알고리즘/acmicpc 2016. 7. 24. 11:38
나이순으로 정렬이 이미 되었으니 해야 할 일은 여기서 연속된 배열을 어떻게 여러개로 나눠서 최대의 점수를 내는 조를 만드느냐이다. (문제가 나이 정렬을 해주지 않고 냈으면 더 어려울 뻔 했는데 친절하게 나이 정렬을 해준 뒤에 문제를 풀라고 했다) 위 문제는 DP로 풀 수 있다. 먼저 다음과 같은 배열을 선언한다 dp[FROM][TO] : FROM학생부터 TO학생까지 조를 짤 때의 최대의 점수가 나오는 경우 목표는 FROM, TO까지 무조건 최대의 점수를 가지는 것이며 어떻게 분할 되는지는 상관하지 않는다 FROM에서 TO까지의 범위를 차근차근 늘려서 1번 학생부터 N번 학생가지 포함되는 경우까지 만들어준다. #include #define MAXN 1000 #define MAX(A, B) ((A) > (B..