이쪽은 그냥 내가 풀다가 죽어라 헷갈리는 부분이나 새로 배우면서 흥미롭다 싶은부분 메모하는 글들이기때문에 작성방법이 묘할것이라 생각함. 세그트리 밀다가 만난 문제 유형 정렬은 그냥 무지성 std::sort 박아서 정렬을 한번쯤 정리해두는게 좋을것 같았다. 해당 유형의 문제로는 1517번, 23336번, 10090번 등등이 있다 머지소트 merge sort 머지소트는 정렬에 대해서 분할정복을 적용한 케이스라고 이해하면 되겠다. void mergeSort(int s, int e){ if(s
https://www.acmicpc.net/problem/22963 22963번: 3초 정렬 원래 수열인 A = [6, 7, 10, 8, 20]의 4번째 원소인 8을 15로 바꾸면 A = [6, 7, 10, 15, 20]이 되어 오름차순으로 정렬된 배열이 된다. 3번째 원소인 10을 8로 바꾸어도 A = [6, 7, 8, 8, 20]이 되어 오름차순으로 정 www.acmicpc.net 처음 보고 든 생각은 lis였고, lis에 포함되지 못한 값들을 적당히 변경하면 오름차순으로 만들수 있지 않을까 생각. https://blog.koderpark.dev/191 백준 BOJ 14003 - 가장 긴 증가하는 부분 수열 5 https://www.acmicpc.net/problem/14003 14003번: 가장 긴..
[원석방 산하 폐수방] 1일차 셋 div 2 B번. 뇌절오지게했다. 이놈의다익스트라 구현만 1e9번 했는데 아직도 못외웠다는점에서 코더가 멍청하다는걸 바로알수있다... :blobsob: https://www.acmicpc.net/problem/20160 20160번: 야쿠르트 아줌마 야쿠르트 주세요 첫 줄에는 정점의 개수 V(1 ≤ V ≤ 10,000)와 도로의 개수 E(0 ≤ E ≤ 100,000)가 정수로 주어진다. 그 다음 E 줄에 걸쳐 각 도로를 나타내는 세 개의 정수 (u, v, w)가 순서대로 주어진다. 이는 u 와 v(1 ≤ www.acmicpc.net 보고 다익스트라는 빠르게 떠올랐었다. 야쿠르트 아줌마 경로구하는것도 그냥 다익스트라를 많이 돌려주면 해결된다. 쬐끔 까다로웠던 부분이 야쿠르..
처음 봤을때는 전구를 두번 켜고끄고 할필요가 없다는 내용을 떠올리고 무지성 브루트포싱을 시도했지만 바로 2^100 TLE 나만 모르는 웰논 풀이 윗줄에 대해서 비트마스킹 등으로 브루트포싱을 진행해주면, 그 아랫줄은 윗줄의 상태에 따라서 켜고끄고 여부를 결정할수 있다고 한다. 쭉 순회해가면서 처리하기. 구현자체는 그리 어렵진 않았다. https://www.acmicpc.net/problem/14939 14939번: 불 끄기 전구 100개가 10×10 정사각형 모양으로 늘어서 있다. 전구에 달린 스위치를 누르면 그 전구와 위, 아래, 왼쪽, 오른쪽에 있는 전구의 상태도 바뀐다. 전구 100개의 상태가 주어지면 모든 전구를 끄 www.acmicpc.net #include using namespace std; ..
11066번 파일 합치기 문제와 매우 동일하므로 따로 풀이를 적지는 않도록 하겠다. 간단히하자면 DP[i][j] => i번째부터 j번째까지를 계산할때의 최소 https://www.acmicpc.net/problem/11049 11049번: 행렬 곱셈 순서 첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같 www.acmicpc.net #include #define INF 1234567890 using namespace std; typedef long long int ll; pair arr[567]; ll dp[567][567] = {0}; int f(int s..
DP문제 https://www.acmicpc.net/problem/10942 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net dp[i][j]를 i번째 수부터 j번째 수까지 붙여 만든 문자열이 팰린드롬인가? (1 or 0) 으로 정의해주면 된다 일단 i와 j가 같은 경우에는 항상 팰린드롬일 것이고, 길이가 짝수인 팰린드롬은 i+1 와 j 번째 숫자가 같아야 한다. 이것들을 먼저 처리해 큐에 넣어주고 BFS를 통해 순회해주며 DP배열을 채우면 된다. #include using namespace std; int dp[2345][2345] = {0}; //..