algorithm

어떤 코드가 잘 짠 코드이고, 어떤 코드가 못짠 코드일까? 코드의 가독성, 메모리, 시간 등 여러 요소가 있겠지만 그중에서 효율성(시간)에 관련된 빅오 표기법에 대해 쓰려한다. ● Big-O Notation 정의는 다음과 같다. 전공서적에 있는 것을 그대로 옮긴 것인데, 해석한 그대로이다. n이 n0 보다 큰 경우에서 어떠한 양의 정수 c를 g(n)에 곱해도 함숫값이 f(n)보다 크거나 같은 경우 함수f(n)의 시간복잡도를 O(g(n))이라고 한다. 다시말하면, 어떤 알고리즘의 실행시간이 f(n)을 따라간다고 할때 그 알고리즘은 적어도 cg(n)보다는 빠른 시간에 작동된다는 뜻이다. 예를 들어, - f(n) = 5n²+3n+7는 O( n²) - f(n) = 6n+1은 O(n) - f(n) = 8n³+2n..

https://www.acmicpc.net/problem/20500 20500번: Ezreal 여눈부터 가네 ㅈㅈ 문제의 답을 $1\,000\,000\,007$로 나눈 나머지를 출력한다. www.acmicpc.net 우선 1과 5로만 이루어진 숫자가 15의 배수가 되기 위해서는 마지막 숫자가 5로 끝나야 한다. 마지막 숫자가 5로 끝나면 경우의 수는 3가지이다. 15로 나눴을 때 나머지가 5인경우, 10인 경우, 0인 경우. dp[i][0] 을 i자리수면서 나머지가 0인 경우, dp[i][1]을 i자리수면서 나머지가 5인경우, dp[i][2]를 i자리수면서 나머지가 10인 경우로 생각했다. 저렇게 나누고 4자리수까지 나머지가 0,5,10인 경우를 세 보았는데 다음과 같은 규칙이 보였다. dp[i][0] ..

https://www.acmicpc.net/problem/10835 10835번: 카드게임 첫 줄에는 한 더미의 카드의 개수를 나타내는 자연수 N(1 ≤ N ≤ 2,000)이 주어진다. 다음 줄에는 왼쪽 더미의 카드에 적힌 정수 A(1 ≤ A ≤ 2,000)가 카드 순서대로 N개 주어진다. 그 다음 줄에는 오 www.acmicpc.net 1. 왼쪽 카드만 버리는 경우 2. 왼쪽 카드와 오른쪽 카드를 버리는 경우 3. "왼쪽 카드 < 오른쪽 카드" 를 만족하여 오른쪽 카드만 버리는 경우 이 세가지 경우를 모두 고려해주어야 한다. dp[left][right] 는 왼쪽 카드와 오른쪽 카드를 left장, right장 버렸을 때 점수의 최댓값이다. 코드는 다음과 같다. #include #include using ..

https://www.acmicpc.net/problem/14728 14728번: 벼락치기 ChAOS(Chung-ang Algorithm Organization and Study) 회장이 되어 일이 많아진 준석이는 시험기간에도 일 때문에 공부를 하지 못하다가 시험 전 날이 되어버리고 말았다. 다행히도 친절하신 교수님께서 아래와 www.acmicpc.net 배낭 문제랑 똑같은 문제이다. 배낭문제는 2차원 Dp를 이용해서 Buttom-up으로 풀었었는데 배낭문제는 1차원 Dp를 이용하면서 Top-down으로 풀어주는게 더 효율적이다. 배낭문제를 풀어본 사람이라면 알다시피 2차원 배열에서 굳이 값을 채우지 않아도 되는 배열까지 값을 채우기 때문에 메모리와 시간이 Top-down에 비해 오래걸린다. 주어진 시간..

https://www.acmicpc.net/problem/9764 9764번: 서로 다른 자연수의 합 첫째 줄에, 테스트 케이스의 개수 T (1 ≤ T ≤ 20)이 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, N이 주어진다. www.acmicpc.net 중복된 자연수를 사용할 수 없기 때문에 우리가 흔히 아는 동전 문제와 비슷하게 생각할 수 있지만 살짝 다르다. 동전 문제는 button up으로 간단하게 해결 할 수 있다. 하지만 이 문제는 buttom up 보다는 top down이 더 효율적이고 풀이도 간단한 문제이다. 두 풀이를 모두 올리니 공부할 때 참고 하면 되겠다. 먼저 Dp 이므로 큰 문제(우리의 목표)를 작은 문제로 나눠야 한다. 동전 문제에서는 2000원이 되는 경우를 1원이 되..

https://www.acmicpc.net/problem/3067 3067번: Coins 우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 모든 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어 30원을 만들기 위해 www.acmicpc.net DP문제로 아주 유명한 문제이다. DP가 큰 문제를 작은 문제로 나눠 생각해서 작은 문제를 통해 큰 문제를 해결하는 방식이므로 문제를 쪼개야한다. 예를 들어 1000원을 만드는 방법의 수를 구해야 한다면, 주어진 동전으로 1원을 만드는 경우의 수, 2원을 만드는 경우의 수, 3원을 만드는 경우의 수... 계속 나아가서 1000원까지 도달하는 방식으로 DP를 구성해 주면 된다...