728x90 반응형 백준 알고리즘58 [백준 1520][Java] 내리막 길 https://www.acmicpc.net/problem/1520 풀이굉장히 어려웠던 문제입니다. DFS와 메모이제이션 기법을 적절히 사용해야 하는 문제였습니다. 풀이를 생각하지 못 하고 검색을 통해 해결했습니다. 첫 번째는 완전 탐색을 떠올렸습니다. DFS와 백트래킹 기법을 사용해서 완전 탐색을 하면 갈 수 있는 길의 개수를 구할 수 있습니다. 하지만 N과 M의 최대 크기는 500이었고 최대 칸의 개수는 250,000이었기 때문에 시간 초과가 발생합니다. 두 번째는 DP를 떠올렸습니다. dp[x][y]를 "좌표 (x, y)까지 도착할 수 있는 경우의 수"라고 정의하면 문제를 해결할 수 있을 것 같았습니다. 그래서 (0, 0)부터 (n-1, m-1)까지 dp 값을 구하면 해결할 수 있을 것 같았는데 문제.. 2025. 2. 17. [백준 15486][JAVA] 퇴사 2 가장 끝 날짜부터 첫 날짜로 오면서 dp를 수행했다. dp[i]의 의미는 끝 날짜부터 i 날짜까지 얻을 수 있는 최대 이익이다. dp[i]의 값은 다음 두 가지 경우를 고려해야 한다. i번째 날짜에 해당하는 상담을 진행한다.i번째 날짜에 해당하는 상담을 진행하지 않는다.두 경우 중 큰 값을 골라야 한다. 1번을 생각해보자. 해당 날짜에 상담을 진행할 경우 그 상담으로 받을 수 있는 금액과 그 상담이 끝난 날짜 이후부터 얻을 수 있는 최대 이익을 더하면 최대 이익이 된다. 2번을 생각해보자. 해당 날짜에 상담을 진행하지 않을 경우 그 날짜 이후부터 상담으로 얻을 수 있는 최대 이익이 해당 날짜의 최대 이익이 된다. 두 경우 중 더 큰 값이 최대 이익이 된다. 여기서 중요한 점은 특정 날짜 이후부터 상담으로.. 2025. 2. 15. [백준 1781][Java] 컵라면 https://www.acmicpc.net/problem/1781 문제 풀이그리디로 풀 수 있는 문제입니다. 변수는 두 가지가 존재합니다.데드라인컵라면 수가장 단순하게 생각해보면 단위 시간을 늘리면서 해당 데드라인에서 얻을 수 있는 최대 컵라면 수를 고를 수 있습니다. 하지만 이 방법은 현재 시점에서 최적의 선택이 최적의 해를 보장할 수 없습니다.예를 들어 데드라인이 1이고 컵라면 수가 1인 것과 데드라인이 2이고 컵라면 수가 9인 것이 있다고 합시다.데드라인이 1일 때 최적의 선택은 데드라인이 2인 문제를 푸는 것입니다.그런데 데드라인이 2인 문제를 풀어버리면 다음 데드라인 2일 때 아무것도 선택하지 못 합니다.데드라인이 1일 때 1인 문제를 풀고 2일 때 2인 문제를 풀어야 최적의 해가 됩니다. 즉 .. 2025. 2. 9. [CodeTree] 십자 모양 폭발 (중력) https://www.codetree.ai/missions/2/problems/cross-shape-bomb/description 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요.www.codetree.ai 알고리즘시뮬레이션특정한 알고리즘을 요구하는 문제는 아니고 단순 시뮬레이션, 구현 문제이다.문제 해결 과정이 문제는 폭탄을 터뜨린 다음 중력이 작용했을 때 숫자들의 상태를 출력하는 문제이다. 먼저 폭탄이 터져서 숫자들이 사라졌다는 것을 0으로 표현한다. 숫자는 무조건 1이상 100이하이기 때문에 0이라면 숫자들이 터졌다는 것을 의미한다. 폭탄이 터질 때는 동서남북으로 터지기 때문에.. 2024. 8. 24. 이전 1 2 3 4 ··· 15 다음 728x90 반응형
