오딩이

문제 : https://www.acmicpc.net/problem/2225 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 🔎 Solve 다이나믹 프로그래밍(DP)을 이용하여 풀었습니다. 해당 문제를 표를 만들어서 생각해보면 점화식을 쉽게 만들어낼 수 있습니다. 문제에서 예제 입력 2번과 같이 N=6, K=4일 때를 예로 들어보겠습니다. 2차원 int형 배열을 만들어서 행에는 K (1~4)를, 열에는 N (0~ 6)을 나타내는 배열을 만들어줍니다. dp 0 1 2 3 4 5 6 1 2 3 4 해당 dp.배열을 K개의 숫자로 N을 만들 수 있는 경우의 수를 채워줍니다. 이때, K가 1개일 때는 각 숫자 자신만이 가능하니 1로 채워줍니다...

문제 : https://www.acmicpc.net/problem/25192 25192번: 인사성 밝은 곰곰이 첫번째 새로운 사람이 들어온 뒤 pjshwa, chansol, chogahui05은 모두 곰곰티콘으로 인사했다. 두번째 새로운 사람이 들어온 뒤 pjshwa와 chansol은 다시 곰곰티콘으로 인사했다. www.acmicpc.net 🔍Solve 사실 이 문제는 이모티콘이 너무 귀여워서 끌렸습니다,, 문제는 중복되는 문자열을 한 가지 경우로 처리하는 아주 간단한 HashSet의 기본 유형입니다. 단, 한가지 주의할 점은 ENTER(새로운 사람이 채팅방에 입장)가 입력되었을 때 다시 곰곰티콘으로 인사를 하는 구조이므로, ENTER입력이 들어오면 현재까지 HashSet의 크기를 count에 더해주고 ..

출처 : 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)순열은 팩토리얼과 연관되어있는데,..