lee-soo 님의 블로그

[분할정복]1780번 종이의 개수 (C++)

https://www.acmicpc.net/problem/1780창자가 끊어지는 뇌의 고통을 받음 하.. 나는 재귀가 너무 약한거같다 문제는 대충 3의 거듭제곱 단위로,1*1 3*3 9*9 81*81.. 이렇게점점 쪼개가며 내부의 값들을 확인하는건데 솔직히 처음에아무 생각 없이 풀었을때는 너무 어려웠다 재귀를 통한 머릿속에서 상상이 잘 안된다 해야하나?그래서 그림을 그려가면서 풀어도재귀 , 변수 이런걸 어떻게 넘겨야될지 감이안왔따... 예를들어9*9 가 다 같지 않으면3*3 으로 쪼개지는데 0,0에서 시작하는 3*3이 만약 다 맞으면? 0,4로 가야되는데 여기서 그 조건이 새로시작하는 인덱스 = n+기존에 새로시작하는 인덱스여야 되는데 그 값이 배열범위를 벗어나지 않게 하려면 또 조건문을 써야되고만약 ..

[분할정복]11728 배열합치기(C++)

https://www.acmicpc.net/problem/11728 에뭐지 그냥 두개 다 입력받아서 SORT해볼가...#include #include #include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin >> n >> m; int n_arr[n + m]; for (int i = 0; i { cin >> n_arr[i]; } sort(n_arr, n_arr + n + m); for (int i = 0; i { cout } }응..?ㅋㅋㅋㅋㅋ..

[분할정복]백준 10815,10816번 숫자카드 1,2(C++)

https://www.acmicpc.net/problem/10815 최근 너무 바빠서 1주일만에 찾아오게 되었다.. 무능하고 게으른 나 반성중 쨋든 문제 쉽다 실버 5 문제니까 그렇기도한데 입력 출력을 보고, 두번째입력되는 수열들이 앞선 수열에 있는 값이면 1 없는값이면 0을 출력하는 간단한 문제이다 근데 숫자 카드의 갯수가 뜨헉 500,000개 그리고 숫자는 -10,000,000 ~ 10,000,000 wow; 당연히 중첩문 두개 사용해서 하나하나 비교해보는 for 힘들거고 그렇다고 미리 int arr [ 숫자 ]= true 로하는 비트 마스크 방식도천만개가 넘어가니 따로 정의해주긴 힘들거고 그래서 걍 분할정복 1. 앞서 입력된 값을 sort 2. 이후 입력된 값을 앞서 sort된 arr에서 분할정..

https://www.acmicpc.net/problem/1201 내 인생의 첫 플래티넘 문제이다 뇌 척수가 뽑힐정도의 고통을 받고 결국 풀이를 봤다. 참고한 블로그이다https://hongjw1938.tistory.com/191 알고리즘 풀이 - 백준 1201(NMK, 그리디(Greedy))관련글 그리디 알고리즘 관련 포스팅은 여기를 참조 1. 개요 문제의 링크는 여기를 참조 문제의 내용은 아래의 더보기를 클릭하여 참조 더보기 1~N 수를 한 번씩 이용해서 LIS와 길이가 M이고, LDShongjw1938.tistory.com너무 예쁘게 설명을 잘 해놓았는데나의 개판같은 설명이 이해가 안되면,, 여기서 보면서 이해해라 그림도 그려주신 아주 멋진분이시다 먼저 -1이 나오는 조건문부터 해결해주어야 한다. ..

https://www.acmicpc.net/problem/1744 읽어보면쉽다 단순히오름차순 정렬해주고 제일 작은 음수 들끼리 곱해주고, 제일 큰 양수들끼리 곱해주고 그 중에서 다 묶고 난 후, 남은 음수가 1개일때, 남은 양수가 1개일때 등조건만 나눠주면 된다 #include #include using namespace std;int main(){ int n; cin >> n; int arr[n]; for (int i = 0; i { cin >> arr[i]; } sort(arr, arr + n); int result = 0; for (int i = n - 1; i >= 0; i--) { if (arr[i] >= 0 &&..

https://www.acmicpc.net/problem/1541 문제는 간단하다 최소가 되면 됨 잘 생각해봐라-가 나온 이후에+가 나온다면?-앞에 괄호를 쳐줘서 모든 + 들을 다 더한 후 음수로 바꿀 것이다 그렇다면 -가 나온 이후에+가 나오고 또 -가 나오면? 그냥 또 빼주면 된다 그니까 -가 1개라도 나오면 그 이후의 수는 모두 -로 바꿔주는 것이 최소이다.#include #include using namespace std;int main(){ string s; cin >> s; string temp; int result = 0; char trigger = '+'; int first = 0; for (int i = 0; i { if (s[i]..

.https://www.acmicpc.net/problem/1931 그리디 알고리즘을 배운다면무조건 나오는 문제 중 하나이다. 이건 그냥 외우다 시피 해라!~! https://source-sc.tistory.com/59 [탐욕 알고리즘][2] - 회의실 배정 문제유명한 Greedy 알고리즘 - 회의실 배정 문제 회의실 배정 문제는 그리디 알고리즘에서 빠지지 않고 등장하는 문제이다. 이문제는 각 회의마다 시작시간과 종료시간이 정해져있고 하나의 회의실에source-sc.tistory.com이 블로그에서 회의실 배정 문제에 대해 굉장히 자세히 알려주고 있다! 그리디 알고리즘을 사용하는 건 알겠는데 어떻게 사용하냐! 끝나는 시간을 기준으로 생각하면 된다 예를들어 q에 들어가는 회의 시간은"종료 시간이 가장 빠른..

https://www.acmicpc.net/problem/11047흠.. 너무쉽다 이거 딱봐도 그리디 문제 조건에 Ai 가 Ai-1의 배수라 했으니까 그냥 간단하게 가장 큰 수부터 작은 수 까지 반복적으로 더해주고, 커지면 다음으로 넘어가면 된다#include using namespace std;int main(){ int n, k; cin >> n >> k; int arr[n]; for (int i = 0; i { cin >> arr[i]; } int money = 0, count = 0; int temp = n - 1; while (money != k) { if (money + arr[temp] > k) { ..

https://www.acmicpc.net/problem/1167 이 문제에 대해 간단히 설명하자면 여러개의 노드가 있을때, 한 노드와 또 다른 노드 사이의 거리가 제일 멀 때의 거리를 구하라그게 지름이고 이것이다. 예를들어 이렇게 노드가 있으면? 가장 긴 거리는3+2+6 =11이다 그래서 내가 먼저 처음에 생각한건 "무조건 거리를 잴 때는, 연결된 노드가 1개밖에 없는 경우이다"라고 생각해서 조건문으로 자식이 한개인 경우를 걸러낸 후,그 노드들에 대해 dfs를 통해 distance들을 알아내고max를 지정해줬었다 #include #include #include #include using namespace std;bool visited[100001];bool visited_2[100001];vector..

https://www.acmicpc.net/problem/11725 해당 문제는 루트를 1이라고 할 때, 노드 2번부터 n번까지 그의 부모 노드를 출력하면 되는 문제다 예를들어 입력된 예제를 보면 이런 형식으로 되어있고 2번노드의 부모는 43번은 64번은 15번은 36번은 17번은 4이므로461314가 나오게되는데 문제는 노드가 주어질 때, 그저 간선간의 정보만을 입력으로 줄 뿐 누가 부모노드인지 알려주지 않았다 하지만!우리는 1이 루트노드인걸 알았으니, 1로부터 시작한 탐색을 하면 되는데bfs로 하든 dfs로 하든 이건 상관없다 #include #include #include using namespace std;vectorint> v[100001];bool visited1[100001];int par..