Algorithm/바킹독의 알고리즘 강의11 배열의 정의와 성질 배열 - 메모리 상에 원소를 연속하게 배치한 자료구조. 배열의 성질 1 . O(1)에 k번째 원소를 확인/변경 가능. 2. 추가적으로 소모되는 메모리의 양(overhead)가 거의 없음 3. Cache hit rate가 높음 4. 메모리 상에 연속하 구간을 잡아햐 해서 할당에 제약이 걸림 임의의 위치에 원소를 추가 ,O(N) - 중간에 뭔가를 넣으려면 그 위치 이외에 것들도 다 밀어야 하니 O(N) 임의의 위치에 있는 원소를 제거 , O(N) - 이거도 중간에 뭘 지우면 그 위치 이외에 것들도 다 땡겨야 하니 O(N) 2021. 4. 8. 표준 입출력 C++ 에서 cin과 cout 의 속도를 올리는 방법 cin/cout 은 입출력의 시간초과를 막기 위해서 ios::sync_with_stdio(0), cin.tie(0)을 사용하자. ios::sync_with_stdio(0)은 C++ stream 과 C stream을 원래 동기화 하고 있는 것을 C++ 용만 사용하려고 동기화를 끊는 코드이다. 단, 사용할 경우 printf와 같이 사용하면 안된다. cin.tie(0)의 경우 버퍼의 개념이다. 우리가 화면에 글자를 입력하면 바로 화면에 출력 되는것 같지만, 사실은 버퍼에 저장이 임시로 되었다가 출력으로 나오는 형식으로 구성되어있다. 그리고 순서가 꼬이는걸 막기위해서, 원래 cin에서 꼬이는 것을 막아준다. 근데 백준에서는 굳이 순서 꼬이는 것을 막고 순서대.. 2021. 4. 7. STL과 함수 인자 STL을 함수 인자로 넘길 때 O(N) bool cmp1(vector v1, vector v2, int idx) { return v1[idx] > v2[idx] } 원본으로부터 복사를 하기때문에 생기는 값 때문에 N이 발생한다. O(1) bool cmp1(vector& v1, vector& v2, int idx) { return v1[idx] > v2[idx] } 참조를 하면 참조 대상의 주소만 넘어가기 때문에 O(1)이 된다. 2021. 4. 7. 자료형 정수 자료형 char 자료형은 1byte = 8bit 이다. -2^7 2^6 2^5 2^4 2^3 2^2 2^1 2^0 0 0 0 0 1 0 0 1 제일 왼쪽이 자연스럽게 2^7이지만 char에서는 제일 왼쪽이 독특하게 -2^7이다. unsigned char 최솟값 최댓값 : 0 ~ 255 cahr 최솟값 최댓값 : -128 ~ 127 short(2) = 32767 int(4) = 2.1*10^9 long long(8) = 9.2*10^18 Integet Overflow 컴퓨터는 그냥 시킨대로 계산을 하기 때문. -2^7 2^6 2^5 2^4 2^3 2^2 2^1 2^0 0 1 1 1 1 1 1 1 위 수는 127. 127에서 1을 더하면 어떻게 될까? -2^7 2^6 2^5 2^4 2^3 2^2 2^1.. 2021. 4. 7. 대략 허용가능한 N의 크기 N의 크기 허용 시간복잡도 N 2021. 4. 7. 이전 1 2 다음 IT_learning's Commit