Algorithm48 배열의 정의와 성질 배열 - 메모리 상에 원소를 연속하게 배치한 자료구조. 배열의 성질 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. 자주 접할 수 있는 시간 복잡도 알고리즘의 시간 복잡도 중에서 자주 접할 수 있는 형태로는 다음과 같은 것들이 있다. O(1) 상수 시간 알고리즘(Constant-time algorithm)의 수행시간은 입력의 크기에 영향을 받지 않는다. 상수 시간 알고리즘의 예로는 공식을 이용하여 답을 바로 계산해내는 알고리즘이 있다. O(log n) 로그 시간 알고리즘(Logarithmic algorithm)은 대체로 단계마다 입력의 크기를 절반씩 줄여나간다. n을 계속 2로 나눠가면서 1이 되도록 하는 데에 필요한 단계 수는 log2 n 이고, 따라서 이러한 알고리즘의 수행시간은 로그 시간이다. 로그의 밑수가 시간 복잡도에 나타나 있지 않음에 유의하라. O(√n) 제곱근 시간 알고리즘(Square root algorithm)은 O(log n) 보.. 2021. 3. 13. 이전 1 ··· 5 6 7 8 다음 IT_learning's Commit