programmers8 [코딩테스트 연습] 정수 삼각형 문제: https://programmers.co.kr/learn/courses/30/lessons/43105 DP 문제입니다. 점화식은 아래와 같습니다. dp[h][w] 정의: 꼭대기부터 triangle[h][w] 칸까지 이어지는 경로의 합 중 최댓값. //점화식 dp[h][w] = triangle[h][w] + max(dp[h-1][w-1], dp[h-1][w]) N제한이 크지않으므로 위와 같이 점화식을 세운 후 TOP-DOWN이나 BOTTOM-UP 방식 중 편한 걸로 풀면됩니다. 코드: https://github.com/cottory/algorithm/blob/master/PROGRAMMERS/PG43105.cc 2020. 7. 21. [코딩테스트 연습] 베스트 앨범 문제: https://programmers.co.kr/learn/courses/30/lessons/42579 주어진 자료를 어떻게 (장르, 재생횟수, 고유번호)로 파싱해서 정렬하냐의 문제입니다. 문제를 해결한 순서는 아래와 같습니다. 1. 장르별 총 재생횟수 카운팅 후 장르를 내림차순 정렬 2. 1번 과정을 통해 장르의 우선순위를 알았으니 vector plays의 players[idx]값과 idx를 활용하여 (장르, 재생횟수, 고유번호)로 소팅 3. 장르마다 최대 2회까지만 재생해야하므로 streamingCnt라는 배열을 선언해 장르별 재생횟수 관리 코드: https://github.com/cottory/algorithm/blob/master/PROGRAMMERS/PG42579.cc 2020. 7. 14. [코딩테스트 연습]예산 문제: https://programmers.co.kr/learn/courses/30/lessons/43237 이분 탐색 문제입니다. 지방의 갯수를 M개라 한다면, 정해진 예산으로 할당이 가능한지 판단하는데 O(M)이 걸립니다. 그러므로 예산을 정하는 로직을 로그시간에 처리해야합니다. 그래서 이분탐색이 필요합니다. 한 가지 주의해야 할 것은 오버플로우 입니다. 예산의 총액 상한액이 10억이지만, mid = (lower + upper ) / 2 를 구하는 과정에서 lower + upper는 INT 범위를 초과할 수 있습니다. 코드: https://github.com/cottory/algorithm/blob/master/PROGRAMMERS/PG43237.cc 2020. 7. 10. [코딩테스트 연습] 디스크 컨트롤러 문제: https://programmers.co.kr/learn/courses/30/lessons/42627 문제 조건 중 아래의 조건 때문에 그리디로 해결할 수 없는 문제입니다. 하드디스크가 작업을 수행하고 있지 않을 때에는 먼저 요청이 들어온 작업부터 처리합니다. 디스크 컨트롤러가 처리해야 할 상황은 두 가지로 나눌 수 있습니다. 1. 현재 디스크 컨트롤러가 위치하는 시간 = 가장 우선처리 해야 할 작업의 시작시간 1번 케이스의 경우 작업을 수행하고 있지 않은 경우이니 그냥 가장 시작시점이 빠른 작업을 수행합니다. 2번의 경우 흔히 말하는 SJF(Shortest Job First)로 해결하면 됩니다. 즉, 현재 디.. 2020. 6. 30. 이전 1 2 다음
