본문 바로가기

알고리즘

알고리즘/BOJ 2020. 3. 28. [C++] 백준 10825번 - 국영수 0. 문제 1. 아이디어 1) 기존 정렬 문제에서 정렬 기준의 개수만 늘어났을 뿐이다. 2. 소스코드 #include #include #include #include using namespace std; bool compare(tuple t1, tuple t2) { if (get(t1) != get(t2)) return get(t1) > get(t2); else { if (get(t1) != get(t2)) return get(t1) get(t2); else return get(t1) < get(t2); } } } int main() { ios_base::sync_with_stdio(0); cin.t..
알고리즘/BOJ 2020. 3. 28. [C++] 백준 10814번 - 나이순 정렬 0. 문제 1. 아이디어 1) pair 클래스에 이름과 나이를 담아서 벡터에 저장한다! 2) 하지만 기존 sort 함수를 사용하면 '이름'까지도 정렬 기준으로 사용되니까 비교함수를 만들어준다. 2. 소스코드 #include #include #include #include bool NewSort(std::pair p1, std::pair p2) { return p1.first > N; std::vector v; for (int i = 0; i > age >> name; v.push_back(std::make_pair(age, name)); }..
알고리즘/BOJ 2020. 3. 28. [C++] 백준 11651번 - 좌표 정렬하기 2 0. 문제 1. 아이디어 2. 소스코드 #include #include #include int main() { int N; std::cin >> N; std::vector v; for (int i = 0; i > x >> y; v.push_back(std::make_pair(y, x)); } sort(v.begin(), v.end()); for (int i = 0; i < N; i++) std::cout
알고리즘/BOJ 2020. 3. 28. [C++] 백준 11650번 - 좌표 정렬하기 0. 문제 1. 아이디어 1) pair클래스를 저장하는 벡터를 생성하여 정렬한다. (sort 함수 사용) 2. 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 #include #include #include #include int main() { std::vector v; int N; std::cin >> N; for (int i = 0; i > x >> y; v.push_back(std::make_pair(x, y)); } sort(v.begin(), v.end()); for (int i = 0; i
알고리즘/BOJ 2020. 3. 28. [C++] 백준 2751번 - 수 정렬하기 2 0. 문제 1. 아이디어 1) 위는 합병정렬(Merge Sort), 아래는 퀵정렬(Quick Sort)로 구현했다. (퀵소트는 백준에서 시간초과가 뜬다.. pivot값을 잘 설정해주면 될 듯하다) 2. 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 #include #include int arr[1000000]; int tmp[1000000]; void merge(int st, int ed) // Merge Sort! { int mid = (st + ed) / 2; int idx = st;..
알고리즘/BOJ 2020. 3. 27. [C++] 백준 11052번 - 카드 구매하기 0. 문제 1. 아이디어 1) 해당 문제에서 dp는 N개를 사기 위한 최대 금액값! 2) 처음 생각했을 땐 dp[N]은 dp[N-1] + P1이라고 생각했지만 테스트케이스에서 볼 수 있듯이 그러지 않은 경우가 있었다. 예를 들어 카드 4개를 사려고 구매하려고 할 때 2개 포함된 카드팩 2개를 사는게 더 금액의 값이 큰 경우가 있다! 3) 그래서 해당 경우까지 모두 고려해주기 위해서 반복문을 사용했다. (물론 시간을 고려했다) (이때, 순열이 아니라 조합으로 봐야한다!) 2. 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 #include int main() { int N, price[1001], dp[1001]; std::cin >> N; f..
알고리즘/BOJ 2020. 3. 26. [C++] 백준 2011번 - 암호코드 0. 문제 1. 아이디어 일단 이 문제에서는 고려해줘야할 점들이 생각보다 많았다. 우선 문제에서 dp는 숫자의 개수별로 만들 수 있는 경우의 수라고 정했다! 그리고 만약 N-1번째 숫자와 N번째 숫자가 암호의 범위(1~26) 사이에 있다면 dp[N] = dp[N-1] + dp[N-2] 이고 범위 밖이라면 dp[N] = dp[N-1] 이라는 걸 알아냈다. (왜냐면 저번 문제에서 사용한 아이디어처럼, dp[N-1]에서 그냥 N번째 숫자 하나만 독립적으로 뒤에 붙여주는 경우 그리고 dp[N-2]에다가 N-1번째와 N번째 숫자가 이루는 두자리수 암호를 붙여주는 경우로 나눌 수 있기 때문이다.) 하지만 해석할 수 없는 암호의 경우엔 0을 출력하라고 했다. 해석할 수 없는 암호란, 범위의 숫자로써 판단할 수 없는 ..
알고리즘/BOJ 2020. 3. 25. [C++] 백준 2225번 - 합분해 0. 문제 1. 아이디어 예를 들어 (3, 3) 즉 0부터 3까지의 정수 중에서 3개를 더해 3을 만드는 경우의 수는 아래와 같다. 1. 숫자 0을 제일 먼저 더하고, 연속해서 나오는 2개의 숫자들의 합을 3로 하는 경우의 수 2. 숫자 1을 제일 먼저 더하고, 연속해서 나오는 2개의 숫자들의 합을 2로 하는 경우의 수 3. 숫자 2을 제일 먼저 더하고, 연속해서 나오는 2개의 숫자들의 합을 1로 하는 경우의 수 4. 숫자 3을 제일 먼저 더하고, 연속해서 나오는 2개의 숫자들의 합을 0로 하는 경우의 수 top-down 방식으로 이렇게 쭉쭉 내려가다보면 어느 순간 ( ??, 1 ) 이라는 경우를 만난다. 이때 ( ??, 1 )은 1가지 숫자를 더해서 ??을 만들어야 하니 반드시 1이 된다. (또한 같은..

티스토리툴바