Algorithm Study #1 (Algorithm and IO)

알고리즘(Algorithm)이란 무엇인가?

• In mathematics and computer science, an algorithm is a self-contained step-by-step set of operations to be performed.
• 알고리즘이란 어떤 문제를 해결하기 위한 여러 동작들의 모임이다.
• https://en.wikipedia.org/wiki/Algorithm
• 예제 1
  - 학교에서 집에 간다고 가정했을 때
  - 버스를 타면 30분 1200원
  - 택시를 타면 10분 12000원
  - 대부분의 사람은 버스가 10배정도 가격이 싸기 때문에 버스를 탄다.
  - 조금 더 시간이 걸리지만 싸니까 버스를 탔다는 것이 알고리즘이라고 볼 수 있다.
  - 학교에서 집에 가야하고 버스와 택시중 버스를 탔다. 왜? 싸니까
  - 하지만 모든 알고리즘의 풀이 방식이 같은 것은 아니다.
  - 오늘은 반드시 20분 안에 집을 가야한다고 가정했을 때는 택시를 타야한다.
• 문제의 상황이나 조건이 중요하다.
• 이러한 조건을 배우기 위해서 문제를 계속 풀어보는 것이 가장 중요하다!
• 읽어보면 좋은 알고리즘 문제 해결 전략 책의 서문
  - http://book.algospot.com/hard.html

알고리즘을 공부하는 방법

1. 먼저 알고리즘이나 문제를 푸는 방법을 이해하자!
   • 완벽하지 않거나 일부만 이해해도 성공!
2. 관련된 문제를 풀어보기
   • 한 문제는 길어야 2시간 정도만 고민해본다.
     - 2시간은 매우 중요!
   • 모르겠으면 포기하고 정답 소스를 보거나 풀이를 본다.
3. 1번과 2번에서 이해가 잘 가지 않는다면 질문한다.
   • 설마 이런 것을 질문해도 될까 고민 되는 것도 질문해야 한다.
4. 다시 알고리즘을 이해해보고 문제를 다시 풀어본다.
   • 모르겠으면 포기하고 다시 풀이를 본다.
   • 그래도 모르겠으면 다른 일을 하거나 놀러 나가거나 다른 알고리즘이나 문제를 풀어본다.
5. 프로그래밍을 많이 하는 것보다 문제를 어떻게 풀지에 대한 방법론에 대해 생각하는 것이 더 도움이 많이 된다.

프로그래밍 언어

• 프로그래밍 언어는 크게 상관이 없다.
• 언어의 빈도 순위는 C++ > C > Java이다.
• C언어를 사용하는 경우에는 C++를 사용하는 것이 좋다.
• C++을 사용하는 경우에는 C++11, STL, scanf/printf를 사용하는 것이 좋다.
• Java를 사용하는 경우에는 Scanner를 이용해 입력을 편리하게 받는 것이 좋다.
• 라이브러리 활용
  - Stack을 사용하여 풀어야 한다고 가정하면
  - Stack을 어떻게 구현할 것이냐보다 Stack을 어떻게 사용할 것이냐에 집중

시간 복잡도 (Time Complexity)

• 내가 작성한 코드가 시간이 얼마나 걸릴지 예측하는 작업
• 표기법으로 대문자 O를 사용 (세타나 오메가도 사용)
• 영어로는 Big O Notation
• 입력의 크기에 대해서 시간이 얼마나 걸릴지 나타내는 방법
• 최악의 경우에 시간이 얼마나 걸릴지 나타내야 한다.
  - 예제1. 시간복잡도 O(N)
  - N번 반복되기에 시간복잡도 O(N)으로 표기 가능

    int sum = 0;
    for (int i=1; i<=N; i++) {
      sum += i;
    }

  • 예제2. 시간복잡도 O(1)
    - 1번 반복되기 때문에 시간복잡도 O(1)

    			  int sum = 0;
    			  sum = N * (N+1)/2;
    			```

  • 예제3. 시간복잡도 (N^2)
    - 안쪽 for문이 n이고 바깥쪽 for문이 또 n이라서 O(N^2)

    			int sum = 0;
    			for (int i=1; i<=n; i++) {
      for (int j=1; j<=n; j++) {
        if (i == j) {
          sum += j;
        }
      }
    }
    			```

• 대표적인 시간복잡도
  - O(1)
  • O(lgN)
  • O(N)
  • O(NlgN)
  • O(N^2)
  • O(N^3)
  • O(2^N)
  • O(N!)
• 문제에서 내 답안이 적절한지 검증하는 방법
  - 일반적으로 O(1억)이 1초정도라고 보면 된다.
  - 정확한 건 아니다.
  - 2000년도에도 1억이 1초여서 요즘은 훨씬 빠르다
• 1초가 걸리는 입력의 크기
  - O(1)
  • O(lgN)
  • O(N) : 1억
  • O(NlgN) : 5백만
  • O(N^2) : 1만
  • O(N^3) : 500
  • O(2^N) : 20
  • O(N!) : 10
• 시간 복잡도의 의미
  - O(1) : 단순 계산
  • O(lgN) : N개를 절반으로 계속해서 나눔
    • N = N / 2
      • 트리를 사용했을 때
  • O(N) : 1중 for문
  • O(NlgN) :
  • O(N^2) : 2중 for문
  • O(N^3) : 3중 for문
  • O(2^N) : 크기가 N인 집합의 부분집합
    • 총 N개가 있을 때, 각각을 선택하는 경우와 선택하지 않는 경우
      • 2진수와 비슷하게 간다
  • O(N!) : 크기가 N인 순열
    • 총 N개가 있을 때, 순서가 중요할 때
      • 1 2 3 이란 숫자가 있을 때, 1 2 3 으로 놓냐, 1 3 2로 놓냐...
        - 어떻게 구현할지 생각하고 문제의 시간 제한 안에 나오는지 미리 파악하는 것이 중요하다.
  • 코드를 작성하기 전에 시간복잡도가 얼마나 나올지를 계산하는 것이 중요하다.
• 시간 복잡도의 계산
  - Big O Notation에서 상수는 버린다.
  - ex 1) O(3N^2) = O(N^2)
  - ex 2) O(1/2N^2) = O(N^2)
  - ex 3) O(5) = O(1)
  • 두가지 항이 있을 때, 변수가 같으면 큰 것만 빼고 다 버린다.
    • O(N^2 + N) = O(N^2)
      • O(N^2 + NlgN) = O(N^2)
  • 두가지 항이 있는데 변수가 다르면 놔둔다.
    • O(N^2 + M)

입/출력 패턴

• 이전 정리인 java.io에서 다뤘기 때문에 기본적인 사항들은 따로 다루지 않습니다.
• 한 줄 입력받기
  - scanf("%s", s);
  • cin >> s;
    • 위의 두 방법은 한 줄을 입력받을 수 없다.
      • 줄바꿈까지 입력받기 때문
  • fgets(s, 100, stdin)
  • scanf("%[^\n]\n", s);
  • getline(cin, s);
    • 위의 세 방법은 모두 한 줄을 전체로 입력받을 수 있다.
      • fgets는 줄 바꿈까지 입력받기 때문에 조심해야 한다.
  • 자바는 nextLine()을 사용하면 한 줄을 쉽게 입력받을 수 있다.