프로그래머스69 [코딩테스트 연습] 지형 편집 문제: https://programmers.co.kr/learn/courses/30/lessons/12984 문제 풀이법은 아래의 상도님 블로그 포스팅을 보면 잘 나와있습니다. https://sangdo913.tistory.com/140 X값이 증가하는 방향을 기준으로 2차 함수는 1. 미분한 함수의 기울기가 계속 증가한다는 점 2. 기울기가 0인 점에서 최소가 나온다는 점 이 두 가지 성질을 활용해서 x, x+1 좌표에 대해 결과값으로 y, y+1을 구하고 이 둘의 값을 비교해가면서 이차 함수를 탐색하면 됩니다. 코드: https://github.com/cottory/algorithm/blob/master/PROGRAMMERS/summer_winter11.cc 2020. 5. 13. [코딩테스트 연습] 스티커 모으기(2) 문제: https://programmers.co.kr/learn/courses/30/lessons/12971 DP 문제입니다. DP의 의미를 아래와 같이 정의합니다. DP[N] = N번째 칸까지 스티커를 모았을 때 최대 점수 그러면 다음과 같은 점화식이 성립합니다. DP[N] = max(DP[N-1], DP[N-2] + sticker[N]) 단, 원형판이라는 특수한 조건이 있으므로 값을 한 번 더 분기해줘야 합니다. 첫 번째 칸의 스티커를 뗀 경우와 떼지 않은 경우입니다. 첫 번째 칸의 스티커를 뗀 경우라면 마지막 칸의 스티커는 떼면 안됩니다. 첫 번째 칸의 스티커를 떼지 않은 경우라면 마지막 칸의 스티커를 포함시킬 수 있습니다. 이렇게 BOTTOM-UP 형식으로 구해주면 됩니다. 코드: https://.. 2020. 5. 13. [코딩테스트 연습] 소수 만들기 문제: https://programmers.co.kr/learn/courses/30/lessons/12977 조합을 통해 50 combination 3을 구현해준 뒤, 뽑힌 수에 대해서 소수판별을 해주면 됩니다. 소수 판별을 해줄 때 해당 숫자의 제곱근까지만 탐색을 하면 소수 유무를 알 수 있습니다. 왜 그런지 이해가 안가신다면 '에라토스테네스의 체' 관련 포스팅을 찾아보시면 됩니다. 코드: https://github.com/cottory/algorithm/blob/master/PROGRAMMERS/summer_winter09.cc 2020. 5. 12. [코딩테스트 연습] 종이 접기 문제: https://programmers.co.kr/learn/courses/30/lessons/62049 규칙을 찾으면 해결할 수 있습니다. N번 접은 후의 배열을 DP[N]이라고 하면, DP[N-1]과 DP[N]의 관계는 다음과 같습니다, DP[N-1]을 대충 1 2 3 4 5 6 7 이라고 한다면 0 1 1 2 0 3 1 4 0 5 1 6 0 7 1 이렇게 이전 배열에 0 1을 번갈아가며 씌운 것이 다음 배열의 형태가 됩니다. 코드: https://github.com/cottory/algorithm/blob/master/PROGRAMMERS/summer_winter08.cc 2020. 5. 12. 이전 1 ··· 13 14 15 16 17 18 다음
