오딩이

출처 : https://www.acmicpc.net/problem/17471 17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net 🔍 Solve 조합을 이용한 완전 탐색이며, dfs를 사용했습니다. 다음과 같은 순서로 구현했습니다. 1. 그래프(배열) 만들기 - 조합 2. 선거구 연결 - 그래프 탐색(dfs) 3. 인구수 파악 부분집합이 아닌 조합을 사용한 이유는, 배열 1이 뽑혔으면 배열 2는 배열 1의 여집합이기 때문에 부분 조합을 사용하면 중복되는 배열이 반환됩니다. 따라서 1부터 N/2까지의 개수를 뽑는 조합을 사용했습니다. 조합..

출처 : https://www.acmicpc.net/problem/3190 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 🔍 Solve 문제 그대로 따라 하는 시뮬레이션 문제입니다. 해당 문제는 방향을 전환하는 문제이므로, 방향 배열을 순서를 지켜서 만들어야 합니다. 저는 동->남->서->북 순서로 시계방향으로 돌아가는 순서로 만들었습니다. 방향을 전환할 때 L(왼쪽으로 90도)라면 방향 배열의 인덱스를 -1해주고, D(오른쪽으로 90도)라면 방향배열의 인덱스를 +1 해주었습니다. (0~4의 범위를 벗어날 때 예외..

출처 : https://www.acmicpc.net/problem/18429 18429번: 근손실 웨이트 트레이닝을 좋아하는 어떤 대학원생은, 현재 3대 운동 중량 500의 괴력을 소유하고 있다. 다만, 하루가 지날 때마다 중량이 K만큼 감소한다. 예를 들어 K=4일 때, 3일이 지나면 중량이 488로 www.acmicpc.net 🔍Solve 순조부의 전형적인 순열 문제입니다. 순열은 서로 다른 n개 중 r개를 택하며, 순서를 고려합니다. 주의해야 할 점은 n이 12를 넘어가면서(12!) 시간 복잡도가 폭발적으로 증가합니다. 해당 문제는 n이 8까지이므로, 무리없이 돌릴 수 있었습니다. 운동 키트의 증량 증가량을 담은 배열을 선언하고 해당 배열을 순열 함수를 돌립니다. permutation의 매개변수는 ..

최장 증가 수열 : Longest Increasing Subsequence 📌 최장 증가 수열이란? 어떤 배열이 있을 때, 배열의 순서를 유지하면서 크기가 점진적으로 커지는 가장 긴 부분수열을 추출한 것입니다. 예를들어, [4, 2, 3, 1, 5, 6]이라는 배열이 있을 때 LIS는 [2, 3, 5, 6]이 됩니다. 점차 증가하는 배열은 [4, 5, 6] 또는 [2, 3, 5, 6] , [3, 5, 6] 등 여러 부분집합이 있을 수 있지만, 그 중 부분집합의 최대 배열을 의미하므로 LIS는 [2, 3, 5, 6]이 됩니다. 🔍 가장 먼저 생각해 볼 수 있는 풀이는 완전탐색(Brute-Force)입니다. 수열의 모든 부분 집합을 구하여 그 부분 집합이 증가 수열인지를 판단합니다. 완전탐색으로 풀 경우 부..