알고리즘 공부를 시작하기 전 메모했던 것들

1. 학습 사이트

  1) 백준(https://www.acmicpc.net) : 추천

  2) 알고스팟 (https://algospot.com)

알고리즘 문제 해결 전략 세트

작가

구종만

출판

인사이트

발매

2012.11.01.

리뷰보기

    ※ 위 책의 저자가 운영자로 있는 곳.

  3) 코드포스 (http://codeforces.com)

  4) 탑코더 (http://topcoder.com)

    ※ 코드포스와 탑코더는 rating 제도가 있음.

 

2. 공부 방법

  1) 완벽하게 이해할 필요는 없다.

  2) 한 문제는 최대 2시간까지만 시도하자. 모르겠으면 정답이나 풀이를 보고 분석한다.

  3) 모르는 부분은 반드시 해결하고 넘어간다.

  4) 어떻게 문제를 풀 것인지 생각을 많이 하는 것이 중요하다.

 

3. 언어

  1) 사용하는 언어의 비중 : C++ > C > Java

  2) C++을 사용할 땐 STL, scanf, printf를 이용하면 빠르다.

    - ios_base::Sync_with_stdio(false)을 이용하여 cin, cout의 속도를 향상시킬 수 있다.

      참고) http://untheshade.blogspot.kr/2015/06/cin-cout.html

  3) Java는 Scanner를 이용하여 입력하는 편이 좋다.

 

4. 시간 복잡도

  1) 시간이 얼마나 걸릴지 예측하는 방법

  2) Big O(대문자 O) 표기법을 사용한다.

  3) 최악의 경우에 시간이 얼마나 소요되는가를 따지기 위함.

  4) for(int i = 0, i <= n; i++) sum += i; 의 경우 for문이 n번 돌기 때문에 O(n)

    - 등차수열 공식(sum = n * (n + 1) / 2)을 이용하면 O(1)으로 단축할 수 있다.

  5) 이중 반복문 구조

    for(int i = 0; i < n; I++) {

      for(int j = 0; j < n; j++)

    }    의 경우 O * O(N) = O(N^2)

  6) 가장 큰 입력 범위에서, 1억이 1초정도 소요된다고 생각하면 된다.

  7) 1초정도 소요하는 입력의 크기

Big O	입력의 크기	의미
1		단순 계산
logN		N개를 절반으로 계속 나눔(이진탐색)
N	100,000,000	1중 반복문
NlogN	5,000,000
N^2	10,000	2중 반복문
N^3	500	3중 반복문
2^N	20	크기가 N인 집합의 부분집합
N!	10	크기가 N인 순열

  8) 상수는 버리고 항이 2가지 이상인 경우 큰 것만을 취한다.

    - 2N2 + 3N인 경우 N2만 취함.

    - N2 + M에서 N2 = 100, M = 1,000,000 이면 둘다 취함.

 

6. 테스트 케이스가 여러 개인 경우 하나씩 입력받고 하나씩 출력한다.

  1) 온라인 채점 사이트에서 코드 제출할 때를 말함. 어짜피 표준 출력만을 검사한다.

  2) 테스트 케이스의 개수를 모르면 배열의 크기를 정하기 어렵다.

7. TC의 개수를 따로 입력받지 않는다면 EOF까지 받는다.

  1) C의 경우

    - while(scanf("%d %d", &a, &b) == 2)

    - scanf는 정상적으로 입력받은 인자의 개수를 리턴한다.

  2) C++ 의 경우

    - while(cin >> a >> b)

  3) Java의 경우

    - while(sc.hasNextInt())

 

8. 줄 단위 문자열 입력 예시

  1) scanf("%s", s);

    - 공백 단위로 끊어서 받는다. 공백에는 개행문자도 포함된다.

  2) fgets(s, 100, stdin);

    - 문자열에 개행문자(\n)까지 입력된다. 

  3) scanf("%[^\n]\n", s);

    - %[ ]는 대괄호 안 문자만 받는다는 의미. 개행문자는 입력받지 않는다.

  4) getline(cin, s);

  5) sc.nextLine()

  ※ C++는 cstdio 라이브러리를 이용하는 것이 가장 빠르다.

 

9. 12345를 받았을 때, 1 2 3 4 5 따로 저장하는 방법

  1) string으로 입력받고 문자열 가장 뒤 아스키 코드 0을 제거함

  2) for(int I = 0; I < n; I++) { scanf("%1d", &a); sum += a; }

    - 앞에서부터 숫자 1개씩 입력받음