newhaneul

본 포스팅은 Do it! 알고리즘 코딩테스트: C++편을 토대로 공부한 내용을 정리하기 위한 포스팅입니다.  1. 병합 정렬(Merge Sort) 병합 정렬(Merge Sort)은 분할 정복(Divide and Conquer) 알고리즘을 사용하는 정렬 방법이다. 배열을 반으로 나누고, 각각을 정렬한 후, 다시 병합하면서 정렬을 완료한다. 알고리즘 과정분할(Divide)정렬할 배열을 중간 기준으로 두 개의 하위 배열로 나눈다.정복(Conquer)각 하위 배열을 재귀적으로 병합 정렬하여 정렬된 상태로 만든다.병합(Merge)정렬된 두 개의 하위 배열을 하나의 정렬된 배열로 합친다시간 복잡도최선, 평균, 최악의 경우: O(nlogn) 모든 경우에서 같은 시간 복잡도를 가진다.공간 복잡도: 추가적인 배열을 사용..

본 포스팅은 Do it! 알고리즘 코딩테스트: C++편을 토대로 공부한 내용을 정리하기 위한 포스팅입니다.  1. 삽입 정렬(Insertion Sort) 삽입 정렬(Insertion Sort)은 배열을 정렬하는 간단한 알고리즘 중 하나다. 이 알고리즘은 두 번째 요소부터 시작하여 현재 요소를 정렬된 부분과 비교하면서 적절한 위치에 삽입하는 방식으로 동작한다. 삽입 정렬의 과정현재 index에 있는 데이터 값을 선택한다.현재 선택한 데이터가 정렬된 데이터 범위에 삽입될 위치를 탐색한다.삽입 위치부터 index에 있는 위치까지 shift 연산을 수행한다.삽입 위치에 현재 선택한 데이터를 삽입하고 index++ 연산을 수행한다.전체 데이터의 크기만큼 index가 커질 때까지, 즉 선택할 데이터가 없을 때까지 ..

본 포스팅은 Do it! 알고리즘 코딩테스트: C++편을 토대로 공부한 내용을 정리하기 위한 포스팅입니다.1. 버블 정렬 (Bubble Sort)인접한 두 원소를 비교하여 교환하는 방식으로 정렬하는 알고리즘이다.큰 값이 점점 뒤로 이동하는 모습이 거품이 떠오르는 것과 비슷해서 "버블 정렬"이라고 한다. 동작 방식첫 번째 원소부터 인접한 원소끼리 비교하여 큰 값을 뒤로 이동한다.한 바퀴 돌면 가장 큰 값이 맨 뒤로 정렬된다.다음 라운드에서 마지막 정렬된 원소를 제외하고 반복한다.배열이 정렬될 때까지 반복한다.시간 복잡도최선: O(n) (이미 정렬된 경우)평균: O(n^2)최악: O(n^2)특징구현이 쉽지만, 효율이 낮아 실제로는 잘 사용되지 않는다.안정 정렬(Stable Sort)이다. // Baekjoo..

본 포스팅은 Do it! 알고리즘 코딩테스트: C++편을 토대로 공부한 내용을 정리하기 위한 포스팅입니다.  1. 스택(Stack)  스택(stack)은 삽입과 삭제 연산이 후입선출(LIFO: Last-in First-out)로 이뤄지는 자료구조이다. 후입선출은 삽입과 삭제가 한 쪽에서만 일어나는 특징이 있다. 스택의 동작push : top 위치에 새로운 데이터를 삽입pop : 스택에서 가장 위에 있는 데이터를 삭제(확인도 동시에 하는 경우가 있음)peek(top) : 스택의 가장 위에 있는 데이터를 확인isEmpty : 스택이 비어있는지 검사  스택은 깊이 우선 탐색(DFS: Depth First Search), BackTracking 종류의 코딩 테스트에 효과적인 자료구조이다.  2. 큐(Queue)..

본 포스팅은 Do it! 알고리즘 코딩테스트: C++편을 토대로 공부한 내용을 정리하기 위한 포스팅입니다.  누적 합(Prefix Sum)브루트 포스를 개선하기 위해 미리 누적된 합을 저장해놓고 활용하는 기법이다.즉, S[i]는 1번부터 i번까지의 합을 의미이다. 위 공식을 사용하면 O(1) 시간에 구간 합을 구할 수 있다. #include #include using namespace std;int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int N, M, A; cin >> N >> M; vector> arr(N+1, vector(N+1, 0)); for (int j = 1; j > A; arr[j][i] = A..