알고리즘/코드트리 문제풀이41 코드트리 [자바 java] 동전 거슬러주기 https://www.codetree.ai/missions/2/problems/coin-change?utm_source=clipboard&utm_medium=text 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 거슬러줄 금액과 동전의 종류가 나오면, 거슬러줄 수 있는 최소한의 동전 수를 출력하는 문제이다. 이 문제는 dp를 사용했다. 0부터 해당 금액까지의 dp배열을 선언하고, 사용할 수 있는 동전들을 하나 쓰는 방법을 모두 비교하여 최솟값을 넣도록 하였다. import java.util.*; import java.io.*; import java... 2023. 8. 13. 코드트리 [자바 java] 부분수열의 합이 m https://www.codetree.ai/missions/2/problems/the-sum-of-the-subsequences-is-m?utm_source=clipboard&utm_medium=text 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 이 문제는 동전문제와 비슷하다. 하지만 이 문제에서 유의할 점은 동전을 오직 한번만 사용해야한다는 것이다. 이를 위해 합으로 만들어야 하는 수만큼 dp 값을 만들고, 뒤에서부터 탐색을 진행한다. 순서는 상관이 없으니 고려하지 않는다. 0 10000 10000 10000 10000 10000 여기서 만약 .. 2023. 8. 12. 코드트리 [자바 java] 조삼모사 https://www.codetree.ai/problems/three-at-dawn-and-four-at-dusk?utm_source=clipboard&utm_medium=text 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 위와 같은 업무가 주어졌을 때 아침과 저녁에 할 일의 분배가 최대한 비슷하게 만드는 문제이다. 나는 백트래킹을 이용한 브루트포스를 사용했다. 우선, 아침에 할 일과 저녁에 할 일을 묶는데 한번 사용하고, 아침과 저녁에 할 업무를 전부 더해서 값을 구하는데 한번 더 사용했다. 또한 거의 모든 배열은 사용하기 용이하게 하기 위해서.. 2023. 8. 11. 코드트리 [자바 java] 최소 경로로 탈출하기 https://www.codetree.ai/missions/2/problems/escape-with-min-distance?utm_source=clipboard&utm_medium=text 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 이전에 풀었던 네방향 탈출하기 문제와 유사하다. 하지만 다른 점이 있다면 도착까지 거쳐온 칸수를 세야한다는 점이다. 이 문제는 dfs보다는 bfs로 푸는 것이 좋은데 그 이유는 bfs는 경로를 탐색하다가 가장 빨리 도착점을 발견한 시점이 최소거리이지만, dfs는 도착점을 발견했더라도, 그 경로가 최소인지 알기 위해서는.. 2023. 8. 10. 코드트리 [자바 java] 정수 사각형 최대 합 https://www.codetree.ai/missions/2/problems/maximum-sum-path-in-square?utm_source=clipboard&utm_medium=text 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 행렬에서 1,1에서 n,n까지 가는데 거쳐간 위치에 있던 숫자의 합이 최대가 되도록 하는 문제이다. 나는 dp배열을 하나 더 만들었다. 이는 1,1에서 dp각각의 칸까지 이동할 때 경로상에 있는 숫자를 더한 최대값을 의미한다. 제일 위 칸은 위에서 오는 경우가 없다. 왼쪽에서 오는 경우밖에 없으니까 왼쪽 값에 해당.. 2023. 8. 8. 코드트리 [자바 java] 피보나치 수 https://www.codetree.ai/missions/2/problems/fibonacci-number?utm_source=clipboard&utm_medium=text 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 수가 주어지면 해당 수 번째의 피보나치수를 구하는 문제이다. 첫번째와 두번째 피보나치 수는 1이므로 이들이 주어지면 바로 1을 출력하게 하였고 나머지 수들은 주어진 수 만큼 dp배열을 만들고, dp[0],dp[1]에 1을 넣은 후 2부터 차례대로 전과 전전 dp값을 더한 값을 넣었다. 위 과정이 다 실행되면, dp에 있는 제일 끝 .. 2023. 8. 8. 이전 1 2 3 4 5 6 7 다음
