알고리즘(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분 안에 집을 가야한다고 가정했을 때는 택시를 타야한다.
  • 문제의 상황이나 조건이 중요하다.
  • 이러한 조건을 배우기 위해서 문제를 계속 풀어보는 것이 가장 중요하다!
  • 읽어보면 좋은 알고리즘 문제 해결 전략 책의 서문

알고리즘을 공부하는 방법

  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()을 사용하면 한 줄을 쉽게 입력받을 수 있다.