알고리즘51 [그리디 #20] BOJ 2212 - 센서 https://www.acmicpc.net/problem/2212 2212번: 센서 첫째 줄에 센서의 개수 N(1 ≤ N ≤ 10,000), 둘째 줄에 집중국의 개수 K(1 ≤ K ≤ 1000)가 주어진다. 셋째 줄에는 N개의 센서의 좌표가 한 개의 정수로 N개 주어진다. 각 좌표 사이에는 빈 칸이 하나 있 www.acmicpc.net 접근방법 저번에 풀었던 행복유치원과 같은 문제이다. 예제 2번을 보면서 한번 살펴보자. 10 5 10 5 20 3 14 6 7 8 18 10 12 15 해당 센서를 오름차순으로 정렬하면 다음과 같다. 3 6 7 8 10 12 14 15 18 20 이 세선들을 몇 개씩 묶어서 총 K개의 묶음으로 만들면 된다. 이때, 문제의 핵심은 센서 사이의 거리가 짧은 것을 위주로 선택해.. 2024. 2. 25. [백트래킹 #1] BOJ 15649 - N과 M (1) https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 접근 방법 예전에 풀어봤던 백트래킹이 가물가물해져서 다시 N과 M 시리즈를 풀어보도록 해야겠다. 브루트포스에서 처음부터 시작하는 것 대신, 이전 단계로 복귀하여 행하는 것이다. 코드를 보면 쉽게 이해가 가능하다. https://www.youtube.com/watch?v=Enz2csssTCs 코드 #include #include #include #include #include #include #d.. 2024. 2. 23. [그리디 #19] BOJ 2812 - 크게 만들기 https://www.acmicpc.net/problem/2812 2812번: 크게 만들기 N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 접근 방법 심플하면서 어려운 문제이다. n자리 수에서 m개의 수를 제거하여 가장 큰 수를 만드는 문제이다. 예제 3번에 이 문제에 힌트가 있다. 4 1 7 7 2 5 2 8 4 1 에서 4개를 제거하여 775841 를 만들어야 한다. 핵심은 4와 1을 제거하여 7을 가장 높은 자릿수로 만들어야 한다는 것! 예전에 스택을 이용하여 괄호가 포함된 중위 표기법을 후위 표기법으로 고치던게 생각이 났다. 스택에 숫자들을 넣고, 현재 숫자보다 작은 숫자들은 제거하는 방식으로 진행하여 .. 2024. 2. 23. [그리디 #18] BOJ 11000 - 강의실 배정 https://www.acmicpc.net/problem/11000 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109) www.acmicpc.net 접근 방법 저번에 풀었던 최소 회의실 개수와 같은 문제이다. https://parvegoongame.tistory.com/126 [그리디 #16] BOJ 19598 - 최소 회의실 개수 https://www.acmicpc.net/problem/19598 19598번: 최소 회의실 개수 2개 회의실로 3개 회의를 모두 진행할 수 있다. 예를 들어, 첫번째 회의실에서 첫번째 회의를 진행하고 두번째 회의실에서 두번째 회의와 meteorfish.blo.. 2024. 2. 22. [그리디 #17] BOJ 21314 - 민겸 수 https://www.acmicpc.net/problem/21314 21314번: 민겸 수 민겸 수 하나가 주어진다. 민겸 수는 대문자 M과 K로만 이루어진 문자열이며, 길이는 3,000을 넘지 않는다. www.acmicpc.net 접근 방법 두를 최종적으로 계산하는 경우는 두가지 이다. 1. K가 왔을때 2. string이 끝날때 이 두 가지 경우는 최소와 최대 공통적으로 적용된다. 이제 세부적으로 최대와 최소를 구하는 알고리즘을 생각해보자. i) 최대 MKKMMK 의 경우, MK + K + MMK = 50 5 500 이다. K는 50을 곱해버리므로 무조건 M과 붙어야한다. 따라서, 알고리즘은 다음과 같다. 1. M이 왔을 경우, mCnt를 +1 한다. 2. K일 경우, mCnt를 이용하여 수를 계산 .. 2024. 2. 22. BOJ 11779 - 최소비용 구하기 2 https://www.acmicpc.net/problem/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 접근 방법 1753 최단경로 문제에 경로까지 출력하는 짬뽕된 문제이다. 다익스트라를 이용하여 문제를 풀어보도록 하자. 기존 priority_queue를 이용한 코드에 경로를 저장하는 것이 이 문제의 핵심이다. 경로를 어떻게 지정할까 생각을 하다 최소신장트리에서 부모를 저장하는 방법을 사용해보기로 했다. 1. 부모를 저장할 parent[] 를 선언 (자기 자신으로 초.. 2024. 2. 21. 이전 1 2 3 4 5 6 7 8 9 다음
