Algorithm/Programmers93 [코딩테스트 연습] 소수 만들기 문제: 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. [코딩테스트 연습] 쿠키 구입 문제: https://programmers.co.kr/learn/courses/30/lessons/49995 1. N^2 탐색을 통해 모든 구간합 DP[L][R]을 구해줍니다. 2. 그리고 난 후 DP[L][M] == DP[M+1][R]인 구간의 갯수을 찾습니다. 이 때 M의 범위는 [L,R) 입니다. 이 범위 탐색을 이분 탐색을 통해 logN에 처리하면 N^2 logN으로 통과할 수 있습니다. O(N^2)이 정해인 것 같은데, 문제를 해결한 아이디어만 얻어가시면 될 것 같습니다. 코드: https://github.com/cottory/algorithm/blob/master/PROGRAMMERS/summer_winter07.cc 2020. 5. 12. [코딩테스트 연습] 배달 문제: https://programmers.co.kr/learn/courses/30/lessons/12978 기본적인 다익스트라 문제입니다. 1. N제한이 크지 않고 2. "두 마을 a, b를 연결하는 도로는 여러 개가 있을 수 있습니다." 위 두 가지 이유 때문에 인접리스트보다 인접행렬로 최소 비용의 간선만 저장하도록 그래프를 구현하였습니다. 1번 마을은 무조건 배달이 되므로, 2번 부터 N번 마을까지 다익스트라를 돌려서 dist[N] 2020. 5. 11. 이전 1 ··· 16 17 18 19 20 21 22 ··· 24 다음
