TIL을 쓰는 걸 잊고 있었다. 굉장히 아쉬운 일이지만 이미 지난걸 다시 쓰긴 싫다. 오늘은 set, map 컨테이너 공부 후 set, map, 우선순위 큐와 관련된 문제를 하나씩 풀었다. 정렬 문제도 하나 풀었다. 정렬 문제가 제일 어려웠던 것 같다. 확통을 오랜만에 다뤄서 기억이 잘 안 났다. 정렬 문제들은 꽤 많이 풀어서 이제 다른 주제로 넘어가 볼까 한다. 정렬과 해시테이블, 기본 자료구조 문제는 꽤 다뤘으니 마지막 복습 겸 블로그에 정리하고 C++ 관련 컨테이너도 복습하는 식으로 마무리한다. 그리고 검색트리와 문자열로 넘어가야겠다. 문자열이 정말 취약한데 코테에서 여기저기 많이 나와서 이번 기회에 진짜 꼭 잡는다.

int 자료형으로 표현 가능한 숫자는 210,000,000(21억) 언저리까지이다. 그 이상의 숫자는 오버플로우가 발생하므로 long long 자료형을 사용해야 한다. 내가 코딩하다가 숫자가 21억이 넘어갈지 안 갈지 어떻게 알아??라는 의문이 들 수 있다. 1. 먼저 알고리즘을 생각해본다. 사람마다 다르지만 나는 퍼수도코드로 짜고 시작한다. 2. 시간복잡도를 생각해본다. O(N*M) 이런 식으로 나온다면 N과 M의 최댓값을 기준으로 곱해서 생각하면 된다. 얼추 21억이 넘겠다 싶으면 안전하게 long long으로 짜는 편이 좋다. 3. long long으로 코드를 바꿀 때 콤팩트하게 확실하게 안 바꿔도 되는 자료형을 제외하고는 다 바꾸는 편이 좋다. 연산 중 자동 형변환이 일어날 수 있다. 시간초과도 ..

힙 최대 힙은 완전 이진트리이고, 부모가 항상 자식보다 큰 자료구조이다. 완전 이진트리란, 마지막 레벨을 제외하고 모든 레벨의 노드가 다 채워져 있고 마지막 레벨은 왼쪽부터 채워지는 트리이다. 최소 힙은 반대로 부모가 항상 자식보다 작다. 힙은 완전 이진트리의 특성상 부모와 자식의 index가 명확해서 배열을 사용한다. A[i]의 부모는 A [i/2]이고 왼쪽 자식은 A [2*i] 오른쪽 자식은 A [2*i + 1]이다. 힙은 힙 특성 유지하기(heapify), 힙 만들기(buildHeap), 삽입(insert), 삭제(delete)만 알면 된다. 힙 구현 힙 특성 유지하기(heapify) 배열 A에 대해 i번째 원소를 최대힙의 루트가 되게 한다. 아래는 퍼수도 코드이다. heapify(A, i){ l ..

교재 Introduction To Algorithms 3rd Edition를 바탕으로 수업시간에 다룬 내용 위주로 정리하였다. ​ 알고리즘 기본 용어 정리 매개변수((parameter))는 문제에서 언급된 할당되지 않은 변수들이다. 문제 : 오름차순으로 n개의 정수 리스트 S를 정렬하시오. → 매개변수 : n, S ​ 실체((instance))는 매개변수에 실제로 할당된 값이다. → 문제 : 오름차순으로 n개의 정수 리스트 S를 정렬하시오. → 실체 : n = 6, S = [10, 7, 11, 5, 13] ​ 알고리즘이란 어떤 수학적으로 엄밀히 정의된 문제를 풀기 위한 유한한 절차와 방법이다. 알고리즘의 실험적 분석 주어진 알고리즘을 소스코드로 구현한 다음, 실제 환경에서 동작시켜 실제 실행 시간을 측정..