https://www.acmicpc.net/problem/20667풀이먼저 가장 단순하게 생각해보았을 때 크롬 탭 N개 중 1개, N개 중 2개 ... N개 중 N개를 골라서 목표 이상 cpu, memory를 확보하면서 중요도의 합이 가장 낮은 경우를 고르면 된다. 하지만 이 방법은 2^100이라는 경우의 수가 존재하기 때문에 시간 내에 해결할 수 없다. 다음은 DP를 생각할 수 있다. 가장 기초 냅색 문제인 배낭 문제처럼 dp[i][j][k]의 값을 i번째 크롬 탭까지 고려했을 때 확보한 CPU 사용량이 j이면서 확보한 메모리 할당량이 k일 때 중요도 합의 최솟값이라고 정의하면 된다. 그런데 이 방법 또한 시간 내에 해결할 수 없다. N의 최대 값이 100, M의 최대 값이 1,000, K의 최대 값이..

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 값을 구하면 해결할 수 있을 것 같았는데 문제..

가장 끝 날짜부터 첫 날짜로 오면서 dp를 수행했다. dp[i]의 의미는 끝 날짜부터 i 날짜까지 얻을 수 있는 최대 이익이다. dp[i]의 값은 다음 두 가지 경우를 고려해야 한다. i번째 날짜에 해당하는 상담을 진행한다.i번째 날짜에 해당하는 상담을 진행하지 않는다.두 경우 중 큰 값을 골라야 한다. 1번을 생각해보자. 해당 날짜에 상담을 진행할 경우 그 상담으로 받을 수 있는 금액과 그 상담이 끝난 날짜 이후부터 얻을 수 있는 최대 이익을 더하면 최대 이익이 된다. 2번을 생각해보자. 해당 날짜에 상담을 진행하지 않을 경우 그 날짜 이후부터 상담으로 얻을 수 있는 최대 이익이 해당 날짜의 최대 이익이 된다. 두 경우 중 더 큰 값이 최대 이익이 된다. 여기서 중요한 점은 특정 날짜 이후부터 상담으로..

https://www.acmicpc.net/problem/1781 문제 풀이그리디로 풀 수 있는 문제입니다. 변수는 두 가지가 존재합니다.데드라인컵라면 수가장 단순하게 생각해보면 단위 시간을 늘리면서 해당 데드라인에서 얻을 수 있는 최대 컵라면 수를 고를 수 있습니다. 하지만 이 방법은 현재 시점에서 최적의 선택이 최적의 해를 보장할 수 없습니다.예를 들어 데드라인이 1이고 컵라면 수가 1인 것과 데드라인이 2이고 컵라면 수가 9인 것이 있다고 합시다.데드라인이 1일 때 최적의 선택은 데드라인이 2인 문제를 푸는 것입니다.그런데 데드라인이 2인 문제를 풀어버리면 다음 데드라인 2일 때 아무것도 선택하지 못 합니다.데드라인이 1일 때 1인 문제를 풀고 2일 때 2인 문제를 풀어야 최적의 해가 됩니다. 즉 ..

https://www.codetree.ai/missions/2/problems/cross-shape-bomb/description 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요.www.codetree.ai 알고리즘시뮬레이션특정한 알고리즘을 요구하는 문제는 아니고 단순 시뮬레이션, 구현 문제이다.문제 해결 과정이 문제는 폭탄을 터뜨린 다음 중력이 작용했을 때 숫자들의 상태를 출력하는 문제이다. 먼저 폭탄이 터져서 숫자들이 사라졌다는 것을 0으로 표현한다. 숫자는 무조건 1이상 100이하이기 때문에 0이라면 숫자들이 터졌다는 것을 의미한다. 폭탄이 터질 때는 동서남북으로 터지기 때문에..

https://www.codetree.ai/missions/2/problems/conveyor-belt-triangle/description알고리즘시뮬레이션특정한 알고리즘을 요구하지 않는 단순 구현 문제이고 1차원 배열을 한 쪽 방향으로 n칸 만큼 미는 문제이다. 1차원 배열을 한 쪽 방향으로 n칸 만큼 미는 방법은 구현 문제에서 자주 등장하기 때문에 정리해두려고 한다. 문제 해결 과정한 칸씩만 미는 경우를 생각해보자. 크게 두 가지 방법이 있는데 기존 배열을 활용하는 방법과 새로운 배열을 생성하는 방법이다. 기존 배열을 활용할 때는 다음 두 가지를 기억하자.방향을 반대로 생각한다.첫 값을 기억해둔다.n을 최소화 한다.오른쪽으로 한 칸씩 미는 경우는 다음과 같다. 만약 진행 방향과 동일하게 진행한다면 이..