오딩이

출처 : https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 🔍 Solve dp배열을 사용해서 풀었습니다. 처음엔 점화식이 너무 안 보여서 공책에 합이 1부터 10까지 나올 수 있는 모든 경우의 수를 적어보았습니다. dp의 기본적인 문제인 페인트칠하기와 규칙이 비슷해 보이는데 어떻게 풀 수 있을까 고민하다가 동전의 종류에따라 개수를 따로 세어주니 규칙을 찾을 수 있었습니다. 예제와 같이 동전의 종류가 1, 2, 5가 있습니다. 이 동전의 종류들을 담..

🔍 완전 탐색 완전 탐색 방법은 문제의 해법으로 생각할 수 있는 모든 경우의 수를 나열해보고 확인하는 기법입니다. 코딩 테스트 문제를 풀 때, 우선 완전 탐색으로 접근하여 답을 찾고, 성능 개선을 위해 다른 알고리즘을 사용하며 시간과 메모리를 줄여나가는 것이 좋습니다. 보통 순열, 조합, 부분집합과 같은 조합적 문제와 함께 푸는 문제들이 많이 출제되는데, 만약 조합된 결과에 순서가 의미가 있다면 순열, 순서가 의미가 없다면 조합, 선택하는 개수가 고정되지 않고 상황에 따라 다르다면 부분집합을 사용합니다. 🔍 순열 (permutation), 중복순열 순열은 서로 다른 것들 중 몇 개를 뽑아서 한 줄로 나열하는 것입니다. 즉, 서로 다른 n개중 r개를 택하는 것이죠!(nPr)순열은 팩토리얼과 연관되어있는데,..

출처 : 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의 범위를 벗어날 때 예외..