CS
[Algorithm] STL vector
STL vector -정의: vector 자료구조는 배열과 거의 동일한 기능을 수행하는 자료구조로, 배열과 마찬가지로 원소가 메모리에 연속하게 저장되어 있기 때문에 배열과 마찬가지로 인덱스로 원소에 O(1)에 접근할 수 있음 -특징: 원소가 연속하게 저장되므로 [] 연산자 또는 at 으로 읽기에는 빠르지만 insert(), erase(), push_back() 등은 비효율적으로 동작한다. -함수: http://www.cplusplus.com/reference/vector/vector/ -주의할 점 (1) size()의 반환 값은 unsigned int vector v1 = {1,2,3}; for(int i=0; i
[Algorithm] 배열
배열(Array) - 정의: 메모리 상에 원소를 연속하게 배치한 자료구조. - 특징 (1) 다른 자료구조와 달리 원소를 저장하는 것 이외에 추가적으로 소모되는 메모리의 양(=오버헤드)이 거의 없는 것이 장점 (2) 메모리 상에 원소가 연속해서 있어야 한다는 성질로 인해 cache hit rate(https://parksb.github.io/article/29.html)가 높다는 장점이 있으나 할당에 제약이 걸린다는 단점도 있음 (3) 배열의 길이: 따로 변수를 하나 두어 배열의 길이 저장. 따라서 배열의 길이를 알고 있다고 가정 - 시간 복잡도 (1) 임의의 위치에 있는 원소를 확인/변경: 원소는 연속하므로 O(1) (2) 원소를 끝에 추가: 배열의 길이를 알고 있으니 마지막 위치에 원소를 두기만 하면 ..
[Algorithm] 가장 큰 수 찾기
#include int main(void) { int arr[5] = { 3, 5, 4, 6, 1 }; max = arr[0]; for(i = 1; i < 5; i++) if(max < arr[i]) max = arr[i]; printf("max: %d", max); return 0; }
[Algorithm] bits/stdc++.h 헤더
#include 해당 헤더안에 모든 표준 라이브러리가 들어가 있음 단 MSVC에는 해당 헤더가 존재하지 않는데 직접 경로에 헤더파일을 추가해놓으면 됨. 참고 https://blog.encrypted.gg/724?category=773649
[Algorithm] cin/cout 시간초과 방지
int main(void){ ios::sync_with_stdio(0); cin.tie(0); } scanf/printf와는 다르게 cin/cout에서는 입출력으로 인한 시간초과를 방지하기 위해 반드시 ios::sync_with_stdio(0), cin.tie(0)이라는 두 명령을 실행시켜야 합니다. 두 명령을 실행시키지 않으면 입/출력의 양이 많을 때 시간초과가 발생할 수 있습니다. -ios::sync_with_stdio(0) : C++ stream과 C stream의 sync를 끄는 명령. 따라서 해당 명령어를 입력할 경우 printf와 cout을 함께 쓰면 안됨. cout만 써야함. -cin.tie(0) : cin과 cout이 번갈아 나올 때 마다 flush를 하지 않도록 하는 명령. 채점 환경에서..
[SW Expert Academy] 2072. 홀수만 더하기
문제 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5QSEhaA5sDFAUq 코드 내가 푼것 #include using namespace std; int main(void) { int n = 0; //number of test cases cin >> n; for (int i = 0; i > tmp; if (tmp % 2 !=0) result += tmp; } cout
[SW Expert Academy] 2071. 평균값 구하기
문제 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5QRnJqA5cDFAUq 코드 #include #include using namespace std; int main(void) { int result = 0; //result of calculation int n = 0; //number of test cases cin >> n; float* test = new float[n]; //store result for (int i = 0; i > tmp; result += tmp; } ..
[Algorithm] 공간 / 시간 복잡도 분석
복잡도는 크게 공간 복잡도와 시간 복잡도로 나뉜다. 복잡도를 분석하는 것은 한 문제에 대해서 해결방법으로 나올수 있는 알고리즘이 여러개가 있기 때문이다. 그 다수의 알고리즘의 성능을 비교해야 할 필요가 있으므로 공간 / 시간 복잡도를 분석하여 표기한다. 이때 표기 방법에는 주로 점근적 표기법 (Asymptotic Notation)이 쓰인다. 시간 복잡도(Time Complexity) -시간복잡도: 프로그램의 수행시간을 분석하는 것, 반복문에 크게 영향을 받음 -계산 방법 1) 연산 횟수의 함수가 주어진 경우 최고차항의 계수와 그보다 낮은 차수의 항을 제외시키면 된다. 예를 들어 7n^5+5n^3+3n^2+3 라는 식이 주어졌을때 최고차항인 7n^5 의 계수인 7과 나머지 5n^3+3n^2+3 를 제외 시..