우리가 보이고 싶은 명제는"전체 배열의 maximum subarray는위 세 가지 중 하나이다."전체 배열의 최적해 Ai...j를 하나 잡았다고 하자.최적해의 원소들이 전부 mid보다 왼쪽 구간에 있으면 Ai...j는 왼쪽 부분배열 안에서의 maximum subarra

왜 갑자기 재귀?Divide and Conquer 알고리즘의 수행 시간을 분석하는 데 가장 자연스러운 접근법.Brute-force methodSubstitution methodRecursion tree methodMaster method만약 T(n) = 2 \* T(n

We can predict how an algorithm will perform for large input sets, based on its performance for moderate input sets.Θ(g(n)) = { f(n): there exist posi

Merge Sort Divide and Conquer > 핵심 성질 Divide : 더 작은 동일 문제로 나눈다. Conquer : 재귀로 해결한다. Combine : 부분해를 combine하여 전체해로 만든다. merge sort에서의 Divide and conqu

Insertion sort, merge sort, quick sort 등의 다양한 정렬 알고리즘들이 있다.Incremental algorithm이다.앞의 원소부터 차례대로 증가하며 체크한다.그렇다면, 이 알고리즘 방식이 정말로 내가 원하는대로 정렬해주는가?어떤 알고리즘

sol : 67' 43''수행 시간 : 0ms메모리 : 2024KBDFS시 매번 독립된 분기 데이터들을 직접 다뤄야 하므로 & 잊지말자.

평균 : 180'sol : 235' 27''수행 시간 : 13ms메모리 : 0MB두 번째 푸는데도 4시간 걸리는 미친 문제주 병목은 부채꼴 진행

평균 : 180'sol : 90' 18''수행 시간 : 8ms메모리 : 0MB// 1-baseint n, k, l;int dustGridMAX_N;int robotGridMAX_N;// 우, 하, 좌, 상const int ds4 = { {0, 1}, {1, 0}, {0

sol : 101' 09''회전한 채로 그리드를 계속 생각하는 방식이 흥미로웠다.

평균 : 180'sol : 165' 24''수행 시간 : 149ms메모리 : 0MB직사각형이어서 좌표를 전부 가지고 다닐 필요가 없었다.

sol : 81' 40''수행 시간 : 4ms -> 0ms메모리 : 2032KB다음엔 1시간 이내로 풀어보자.

sol : 138' 33''깔끔하게 전부 정리하고 풀면 1시간 이내도 가능했을 것.암산 절대금지

평균 : 180'sol : 108' 5''수행 시간 : 7ms메모리 : 0MB처음 풀었을 때는 9ms였는데 이번에 7ms가 나왔다.상태관리를 적재적소에서 잘한 것 같다.재귀가 약점이었는데 상태 관리를 위한 분기를 명확하게 처리했다.

sol : 38' 28''수행 시간 : 8ms메모리 : 2028KB전처리를 하면 좋은 문제였다.실전에서도 이렇게 전처리 생각이 먼저 떠오르려나.미지의 영역 탈출도 같은 논리였다.전처리를 하고 수행하니까 8ms에서 0ms로 줄었다.

평균 : 180'sol : 72' 47''수행 시간 : 9ms메모리 : 2MB

sol : 67' 20''수행 시간 : 28ms메모리 : 2812KB비트마스크를 연습해보자.\-> mask:1 ... 전부 짝수, mask:2 ... 전부 홀수, mask:3 ... 섞임꼭 가지고 있어야 할 정보가 무엇인지 고민하는 습관을 실천해봤다.Fireball은

sol : 63' 40''그리드 밖을 벗어나는 경우의 로직 처리에 대해서 더 깔끔하게 할 수도 있다.

n행 m열 벡터로 초기화배열 초기화

평균 : 180'sol : 187' 24''수행 시간 : 14ms메모리 : 0MB상태 관리를 좀 더 명확하게 하자. 로직은 전부 맞게 짰는데, 상태 관리를 동기화해서 업데이트 해주지 않은 실수로 디버깅에 1시간 넘게 잡아먹혔다.

sol : 104' 10''수행 시간 : 88ms -> 32ms메모리 : 2996KB하드코딩말고 뭔가 더 멋있게 할 수 있는데 당장 생각이 안났다.cin.tie(0)->sync_with_stdio(0) 이거 꼭 쓰자.