알고리즘
-
메뉴 리뉴얼알고리즘/프로그래머스 2021. 5. 29. 18:09
문제 푸는 키 포인트는 두개다. 1. 손님들마다 주문한 단품 메뉴 목록에서 가능한 조합을 목록으로 만든다. 손님이 최대 주문 할 수 있는 단품 메뉴의 개수가 10개다. 그러면 10개로 만들 수 있는 조합의 개수는 2^10 - 1개. 알고리즘 시험 문제에서 풀 수 있을 만큼의 범위다. 단품의 개수가 2개 이상인 조합만 고려대상이지만 이건 일단 무시하도록 하자. 코딩으로 조합 목록을 만드는 방법은 다양하게 있을텐데 내 경우에는 비트마스크를 사용했다. 만약 손님이 5개를 주문 했다면 총 31가지 조합이 만들어지므로, 1 ~ 31 까지 For 루프를 돌고 각 회차별로 비트를 확인 해서 단품 목록을 포함 시킬 것인지 말 것인지를 결정한다. for (int i = 0; i < orders.size(); i++) {..
-
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인 문자열을 구할 수 있다고 생각했다. 하지만 위의 식은 중복..
-
카쿠로알고리즘/algospot 2016. 12. 11. 16:49
스도쿠나 N-Queens 문제들을 마주할 때면 가슴이 답답하다. 냅색이나 LIS 처럼 차곡차곡 상황들을 쌓아 갈 수 없을 뿐더러 두더지 게임 처럼 하나의 조건을 해결하면 또 다른 문제가 튀어나오니 도대체 어떻게 풀어야 할 지 감을 잡을 수 없었다. 이러한 유형의 문제를 보면 정말 머리 좋은 친구들이 푸는건가보다 하고 그냥 넘어 갔던 것 같다. 알고리즘 해결 전략에서는 스도쿠, N-Queen 그리고 가쿠로 문제처럼 특정한 제약에 해당하는 답을 찾는 문제를 제약 충족 문제라고 한다. 조합 탐색 문제들 중에 하나인데 먼저 조합 탐색은 기존에 사용했던 알고리즘(DP, 탐욕법 등등)을 사용 할 수 없고 가지치기를 통해 검사 할 필요가 없는 경우들을 미리 쳐내는 방법이다. 제약 충족 문제는 조합 문제에서 한 발 더..
-
모듈러 나눗셈 연산 처리하기알고리즘/자료구조 2016. 12. 10. 12:14
프로그래밍 문제에서 가끔 이런 연산을 요구하는 문제들이 있다. (N/K) % MOD N과 K의 값이 작으면 N과 K의 값을 먼저 계산 하고 나서 모듈러 연산을 취해주면 문제가 없다. 하지만 N과 K값이 64bit 이상으로 변수에 넣을 크기를 초과하는 경우 앞의 나눗셈 계산은 정상적인 값을 내놓지 않을 것이고 모듈러 연산은 정상이 아닌 값을 받아 처리해 결론적으로 잘못된 값을 낸다. 주로 N과 K를 팩토리얼로 받는 조합의 경우의 수를 구할 때 난감하다 -> nCr % MOD 인 경우 이런 경우를 해결 하기 위해 모듈러 연산의 나눗셈을 계산하는 특별한 방법이 존재한다. 모듈러 연산에서 나눗셈 N/K는 K로 나누는 대신에 K의 곱셈 역원(multiple inverse)를 곱하는 방식으로 이뤄진다. 곱셈 역원은..
-
완전순열(교란순열)알고리즘/자료구조 2016. 12. 4. 20:52
어떤 배열의 원소 Xi의 위치가 i라고 할 때 모든 원소들이 자기의 위치에 존재하지 않을 때 이를 완전 순열이라고 한다. X2 X1 X4 X3 점화식을 통해 원소의 개수에 따라 완전순열의 개수를 구할 수 있다. 공식은 다음과 같다 a(n) = (n-1) * (a(n-1) + a(n-2)) 증명을 하면, 1 부터 N까지 오름 차순으로 이뤄진 배열이 있다고 하자 여기서 배열내의 원소중 1의 위치를 X로 옮기려고 한다. 이럴 경우 두가지 경우가 발생한다. - X를 1의 위치로 옮기는 경우 -> N-2의 개수로 완전순열을 구하는 경우와 같다.- X를 1의 위치로 옮기지 않는 경우 -> N-1의 개수로 완전순열을 구하는 경우와 같다. 1이 선택 할 수 있는 X 의 개수는 N-1개 이므로 이를 점화식으로 나타내면 ..
-
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번에서 위로 그을 수 있는 최대 선분의 길이다. ..