Algorithm (기초)

김정욱·2020년 10월 6일

Algorithm - 문제

목록 보기

2/249

(본 글은 바킹독님의 https://www.youtube.com/watch?v=mBeyFsHqzHg&list=PLtqbFd2VIQv4O6D6l9HcD732hdrnYb6CY&index=4 를 참조)

이론적인 부분

[ 시간/공간 복잡도 ]

컴퓨터가 1초에 할 수 있는 연산은 3-5억 (주먹구구)

문제에서 요구하는 시간은 1~5초 정도

시간복잡도
: 입력의 크기와 문제를 해결하는데 걸리는 시간의 상관 관계

빅오 표기법
: 주어진 식을 값이 가장 큰 대표항만 남겨서 나타내는 방법
(시간복잡도를 표현하는 방법)

대략적인 시간복잡도와 N의 관계(절대적이지 않음)
: 1초 기준이며, 연산의 복잡도에 따라 많이 바뀌므로 느낌만 가져가면 된다.

공간복잡도
: 입력의 크기와 문제를 해결하는데 필요한 공간의 상관관계
크게 알고리즘 문제에서 신경쓰지 않아도 된다.
512MB = 1.2억개의 int변수 만 알아두자.

[ 정수 자료형 ]

short / int / long / long long 이 있다
: short형 -> 3만개 / int형 -> 21억개 (메이플 풀메소의 크기였다..!)

자료형이 커질 때 사용 할 순서
int(4byte)-> long long(8byte) -> unsigned long long -> string(이렇게 클일 가끔)

[ 실수 자료형 ]

: float(4byte)과 double(8byte)이 있다
  double을 쓰는것이 오차범위와 여러 측면에서 나으니 실수 = double이라고 생각하자.

[기억할 3가지]

1) 실수의 저장/연산 과정에서 반드시 오차는 발생
(그래서 꼭 상대오차가 큰 double을 사용!!)

    float은 유효숫자가 6자리 = 상대 오차가 10^-6 까지 안전
    double은 유효숫자가 15자리 = 상대 오차가 10^-15까지 안전
      ex) 답이 N일 때 double이면 N-10^-15 ~ N+10^-15까지!!

2) double은 long long 범위의 값을 전부 담지 못할 수 있다
   (double은 유효숫자 15자리 / longlong은 19자리)

3) 실수를 비교할 때는 등호를 사용하면 안됨
double a = 0.1+0.1+0.1;
double b = 0.3;
if(abs(a-b) < 1e-12) cout << "same" ;
: 1e-12 = 10^-12의미!

기능적인 부분(C++)

[ 참조자 ]

: 참조에 의한 연산을 할 때 포인터 처럼 쓰지 않을 수 있음
      : 오른쪽이 참조자를 이용한 연산

[ STL (Standard Template Library) ]

vector : 가변 배열
1) STL을 함수 인자로 넘길 때(값의 복사)
: vector를 함수의 인자로 넘겼을 때 값이 복사되기 때문에 원본은 그대로!
즉, 이럴 때에는 '참조자'를 사용하면 된다.

2) STL을 함수 인자로 넘길 때(시간 복잡도)
: 참조자를 사용하지 않으면 vector를 복사하는데 O(N)!
  참조자를 사용하면 주소만 넘어가기 때문에 O(1)!

[ 표준 입출력 ]

C에서 문자열은 char배열로 / C++에서는 String으로 사용

공백을 포함한 입력 받을 때
: getline() 사용하면 됨

scanf/printf 와 cin/cout
: 기능상 차이는 없지만 cin/cout을 쓸 때 주의할 점이 있다.
1) ios::sync_with_stdio(0) 작성
: C++에서는 C의 표준 입출력과 동기화를 위해 stream을 사용
그래서 입/출력 양이 많으면 시간초과가 날 수 있기 때문에
해당 명령어로 동기화를 끊어주고! 대신 cin/cout만 사용해야함!!

2) cin.tie(0) 작성
: cin과 cout의 stream을 untie 해주는 것!
default는 항상 cin을 하기 전에 cout의 버퍼를 비워줘서
  입력 -> 출력 -> 입력 -> 출력 이 반복되는 상황에 순서를 맞춰준다.
  하지만!! 코테에서는 출력만 보기 때문에 이러한 불필요한 연결을 끊어서 성능을 향상시키는 것

endl은 개행 + 출력버퍼 비우기 기능인데 성능이 떨어지기 때문에 '\n'을 사용

[ 코테는 개발과 다르다 ]

개발은 클린코드가 중요하지만 / 개발은 내가 빠르게 짜는게 중요
: 전역변수도 사용 / 반복문 줄바꿈 / 종합 헤더 등등!

출력 맨 마지막 공백 or 줄바꿈이 있어도 괜찮다.

디버거는 사용하지 말자
: 끽해야 코테는 100줄 내외이기 때문에 오히려 꼬일 수 있다.
  (cout을 통해 중간중간 값 확인이 좋다)

<bits/stdc++.h> 라는 종합헤더
: 여러가지 헤더를 모두 종합 --> 실제 코테에서 막는 경우도 존재함