늘 겸손하게

문제해설 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하는 문제입니다. 단, 주어진 번호가 1개 이상 1,000,000개 이하로 주어지므로 효율적인 자료구조와 알고리즘을 사용해야합니다. 문제풀이 각 전화번호 모두 접두어가 될 가능성이 있으므로 전화번호를 key, true 값을 value로 하는 해시맵을 준비합니다. 각 전화번호를 참조하면서 전화번호의 부분수열이 해시맵의 key로 등록되어 있는지 확인합니다. 이미 등록이 되어있다면 접두어가 있다는뜻이므로 false를 반환하고 없다면 참조하는 전화번호를 해시맵에 등록합니다. 모든 전화번호를 탐색해도 접두어가 발견되지 않는다면 true를 반환합니다. 주의할점은, 길이가 짧은 전화번호부터 먼저 해시맵에 등록을 해야 접두어가 있는 모든 경우를 찾을 수 있습니..

made by : besforyou 문제 풀이 수열의 크기가 1

made by : besforyou 문제풀이 n을 입력받고, n을 1, 2, 3의 합으로 나타내는 모든 경우를 구할 필요없이 과거 기록을 이용하는 dp 알고리즘을 이용하여 해결하면 편리합니다. - n이 1인 경우 1, 2, 3의 합으로 나타내는 방법 1 : 1가지 - n이 2인 경우 1, 2, 3의 합으로 나타내는 방법 1 1 2 : 2가지 - n이 3인 경우 1, 2, 3의 합으로 나타내는 방법 1 1 1 1 2 2 1 3 : 4가지 - n이 4인 경우 1, 2, 3의 합으로 나타내는 방법 1 1 1 1 1 2 1 2 1 1 3 1 1 1 2 2 2 1 3 : 7가지 n이 4인 경우를 보면 3을 1, 2, 3의 합으로 나타낸 모든 경우 + 1 2을 1, 2, 3의 합으로 나타낸 모든 경우 + 2 1을 ..

wrote by : besforyou 문제 해설 n이 주어지고, 위 피보나치 함수를 실행했을때 0과 1이 반환되는 횟수를 출력하는 문제입니다. 단순히 위 함수를 실행해서 반환되는 0과 1의 횟수를 직접 구하는 알고리즘은 시간 초과가 뜹니다. 그래서 dp를 적용하여 문제를 해결해야합니다. 문제풀이 fibonacci(0)은 0을 1번, 1을 0번 반환하고 ---- (a) fibonacci(1)은 0을 0번, 1을 1번 반환합니다. ---- (b) fibonacci(2)는 fibonacci(1) + fibonacci(0)을 반환합니다. 그러므로 0을 1번, 1을 1번 반환합니다. ( a + b ) 위를 통해서, n이 주어졌을때 0과 1이 반환되는 횟수는 함수에 n-1이 주어졌을때 반환한 0과 1의 개수와 함수..