단어변환 문제 두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수 있습니다. 2. words에 있는 단어로만 변환할 수 있습니다. 예를 들어 begin이 "hit", target가 "cog", words가 ["hot","dot","dog","lot","log","cog"]라면 "hit" -> "hot" -> "dot" -> "dog" -> "cog"와 같이 4단계를 거쳐 변환할 수 있습니다. 두 개의 단어 begin, target과 단어의 집합 words가 매개변수로 주어질 때, 최소 몇 단계의 과정을 거쳐 begin을 target..

네트워크 문제 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다. 컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크의 개수를 return 하도록 solution 함수를 작성하시오. 제한사항 컴퓨터의 개수 n은 1 이상 200 이하인 자연수입니다. 각 컴퓨터는 0부터 n-1인 정수로 표현합니다. i번 컴퓨터와 j번 컴퓨터가 연결되어 있으면 computer..

타겟넘버 문제 n개의 음이 아닌 정수들이 있습니다. 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다. -1+1+1+1+1 = 3 +1-1+1+1+1 = 3 +1+1-1+1+1 = 3 +1+1+1-1+1 = 3 +1+1+1+1-1 = 3 사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요. 제한사항 주어지는 숫자의 개수는 2개 이상 20개 이하입니다. 각 숫자는 1 이상 50 이하인 자연수입니다. 타겟 넘버는 1 이상 1..

효율적인 화폐 구성 문제 N가지 종류의 화폐가 있다. 이 화폐들의 개수를 최소한으로 이용해서 그 가치의 합이 M원이 되도록 하려고 한다. 이 때 각 화폐는 몇 개라도 사용할 수 있으며, 사용한 화폐의 구성은 같지만 순서만 다른 것은 같은 경우로 구분한다. 예를 들어 2원, 3원 단위의 화폐가 있을 때는 15원을 만들기 위해 3원을 5개 사용하는 것이 가장 최소한의 화폐 개수이다. 입력조건 1

바닥공사 문제 2 X N의 바닥을 1 x 2, 2 x 1, 2 x 2 로 채운다고 할 때 바닥을 채우는 모든 경우의 수를 구하는 프로그램을 구하시오. 바닥을 채우는 방법의 수를 796796으로 나눈 나머지를 출력할 것 제한사항 1

개미 전사 문제 일직선으로 이어진 식량 창고에서 최소한 한 칸 이상 떨어진 식량 창고를 약탈해야한다. 식량 창고 N에 대한 정보가 주어졌을 때 얻을 수 있는 식량의 최댓값을 구하는 프로그램을 작성하시오 제한사항 3

1로 만들기 문제 정수 x가 주어질 때 정수 x에 사용할 수 있는 연산은 다음과 같이 4가지이다. x가 5로 나누어떨어지면, 5로 나눈다. x가 3으로 나누어떨어지면, 3으로 나눈다. x가 2로 나누어떨어지면, 2로 나눈다 x에서 1을 뺀다. 정수 x가 주어졌을 때, 연산 4개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오. 제한사항 1 1 Min(2, 1) = 1 4를 1로 만들 수 있는 횟수 최솟값? 4 - 1 = 3 => 3을 1로 만들 수 있는 횟수 + 1 = 2 4 / 2 = 2 => 2를 1로 만들 수 있는 횟수 + 1 = 2 Min(2, 2) = 2 일반화 해보면 dp[i] = min (dp[i - 1] + 1 , (dp[i //2] + 1 or dp[i ..

동적계획법 (Dynamic Programming) 동적 계획법이란 큰 문제를 작게 나누고, 같은 문제라면 한 번씩만 풀어 문제를 효율적으로 해결하는 알고리즘 기법이다. 분할 정복과 다른 점은 문제들이 서로 영향을 미치고 있다는 점이다. 동적 계획법의 경우 한 번 해결한 문제를 다시금 해결한다는 점이 특징이다. 그렇기 때문에 이미 해결된 부분 문제에 대한 답을 저장해 놓고, 가져다 쓰는 것이다. 동적 계획법은 다음 조건을 만족할 때 사용할 수 있다. 큰 문제를 작은 문제로 나눌 수 있다. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다. 동적 계획법을 구현하는 방식에는 2가지가 있는데 탑 다운 방식과 바텀 업 방식이다. 탑다운 방식은 재귀 함수를 이용한다. 큰 문제를 해결하기 위해 작은 ..