프로그래머스69 [코딩테스트 연습] 단속카메라 문제: https://programmers.co.kr/learn/courses/30/lessons/42884 ST: 고속도로에 진입한 시점 EN: 고속도로에서 나간시점 차량이 고속도로에서 나간시점을 오름차순으로 우선순위 큐에 넣어줍니다. 그 후 우선순위 큐를 순회하면서 1. 이전 단속카메라가 커버하는 범위(EN)가 현재 탐색하는 자동차의 도로 진입시점(ST)보다 빠르다면, 현재 자동차를 찍어줄 단속카메라를 추가해줍니다 (camera++) 2. 이전 카메라가 커버하는 범위(EN)가 현재 탐색하는 자동차의 도로 진입시점(ST)을 포함한다면, 이전 단속 카메라로 현재 자동차도 찍을 수 있으니, 다음 자동차를 탐색하러 가면 됩니다 (continue) 코드: https://github.com/cottory/alg.. 2020. 6. 18. [코딩테스트 연습] 최고의 집합 문제: https://programmers.co.kr/learn/courses/30/lessons/12938 어떻게 풀지 오래 고민했던 문제입니다. 총합이 1억인 10,000개인 숫자를 모두 곱한 값을 구하는 시도 자체가 파이썬이 아닌 이상 불가능하다고 생각했습니다. 합을 직접 안구해도 알 수 있는 방법이 있나 생각해봤을 때, 곱하는 수의 차가 최소일 때 곱한 값은 최대가 됩니다. (아마 수학적으로 증명이 가능할텐데 그거까진 모르겠네요) 그래서 제곱, 세제곱, N제곱 형태가 되면 가장 베스트 케이스입니다. 코드: https://github.com/cottory/algorithm/blob/master/PROGRAMMERS/PG43163.cc 2020. 6. 17. [코딩테스트 연습] 등굣길 문제: https://programmers.co.kr/learn/courses/30/lessons/42898# DP 문제입니다. dp[i][j] = dp[i-1][j] + dp[i][j-1] 의 관계가 성립함을 알 수 있습니다. 단, 전처리에서 중요한 것이 있는데요. 맨 처음 경로 계산을 위해 가장 자리 값들을 1로 셋팅 할 때 아래와 같이 할 수 있습니다. 집 1 1 1 1 1 1 학교 그런데, 특정 지점에서 웅덩이가 등장했다면, 그 뒷 지점은 전부 방문할 수 없으므로 0으로 놔둬야 합니다. 집 웅덩이 0 0 1 1 1 집 이 부분만 신경써주면 무난히 DP로 해결할 수 있습니다. 코드: https://github.com/cottory/algorithm/blob/master/PROGRAMMERS/PG42.. 2020. 6. 17. [코딩테스트 연습] 멀리 뛰기 문제: https://programmers.co.kr/learn/courses/30/lessons/12914 DP 문제입니다. 푸는 방식은 다양하겠지만 값을 저장함으로써 중복되는 연산은 O(1)에 리턴하는 로직이 중요합니다. 효진이는 한 번에 1칸 또는 2칸을 뛸 수 있으므로, N번째 칸까지 점프하는 방법을 구한다면 1. N-1번째 칸에서 + 1 점프하는 방법 2. N-2번째 칸에서 + 2 점프하는 방법 JUMP[N] = JUMP[N-1] + JUMP[N-2] 의 점화식이 성립하게 됩니다. 문제 조건처럼 1234567로 나눌 때 모듈러 연산자 법칙을 적용하면 답을 얻을 수 있습니다. 코드: https://github.com/cottory/algorithm/blob/master/PROGRAMMERS/PG1.. 2020. 6. 15. 이전 1 ··· 10 11 12 13 14 15 16 ··· 18 다음
