Algorithm/Programmers93 [코딩테스트 연습] 정수 삼각형 문제: 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/42583 시뮬레이션 문제이므로 문제의 제약 조건만 잘 구현하면 됩니다. 1. 총 루프횟수: 다리를 통과한 트럭의 갯수 == 총 트럭의 갯수 2. 매 초마다 다리를 빠져나가는 트럭이 있는지, 대기열에 있는 트럭이 다리에 올라갈 수 있는지 체크해줍니다. 중요한 건 트럭이 여러 대 다리에 올라갈 수 있을 때 어떻게 처리하는지가 중요합니다. 코드: https://github.com/cottory/algorithm/blob/master/PROGRAMMERS/PG42583.cc 2020. 7. 7. 이전 1 ··· 11 12 13 14 15 16 17 ··· 24 다음
