내가 헷갈렸던 지점은분명 DFS 문제 풀이때는 2차원 벡터를 매개변수로 받았을 때, 직접 값을 변경해주기 위해 &를 사용했었는데, 왜 BFS에서는 큐의 원소로 vertex 구조체를 넣으면서 관리하려니 안되는걸까?우선 DFS에서 &가 잘 동작했던 이유는void dfs(v

Dynamic programming is applicable when the subproblems are independent!!Characterize the sutructure of an optimal solutionRecursively define the vaule

재귀식은 아래와 같다.따라서, Worst case는 피봇 기준 어느 한 쪽으로 계속 치우쳐지는 경우로,반면, Best case는 피봇 기준 항상 n/2로 나눠지는 경우로,정리하기보단 직접 풀면서 공부하는 게 훨씬 효율이 좋은 듯 하여 여기까지만 기록하기로.

퀵소트의 코드를 보면재귀 호출이 partition 작업이 끝난 후에야 수행되는 것을 볼 수 있다.partition이 In-place 방식이다.

Build max heap correction proof Loop Invariant 복습) Initialization : It is true prior to the first iteration of the loop. Maintenance : If it is true b

vs Insertion sort,1\. in-place.2\. running time is O(nlgn).vs Merge sort,1\. running time is same as O(nlgn).2\. it does not require O(n) additional s

우리가 보이고 싶은 명제는"전체 배열의 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로 줄었다.