100-시작-개념

1. 알고리즘

알고리즘이란? 수학과 컴퓨터 과학, 언어학 또는 관련 분야에서 어떠한 문제를 해결하기 위해 정해진 일련의 절차나 방법을 공식화한 형태로 표현한 것을 말한다.
알고리즘은 음식의 레시피와 비슷하다. (같은 것은 아니다)
- 요리의 재료를 이용해 레시피의 방법으로 요리한 다음, 요리를 완성한다.
- 입력을 이용해 알고리즘으로 문제를 해결하고, 정답을 출력한다.
다익스트라 (Dijkstra), 프림(Prim), 크루스칼(Kruskal)처럼 이름이 붙어있는 것만 알고리즘이 아니다.
- 어떤 문제를 해결하는 방법을 모두 알고리즘이라고 할 수 있다.
- 많은 개발은 어떠한 문제를 해결해야 하는 것이 목적인 경우가 많다.
알고리즘 문제는 상대적으로 대부분의 개발보다 크기가 작다.
- 문제도 다른 분야의 특정 문제를 알고리즘 문제 스타일로 변형하는 경우가 많다.
- 코딩 테스트나 인터뷰에서는 문제를 모델링하고 해결하는 능력을 알아보기 위해서 알고리즘 문제를 푼다.
게임을 잘하고 싶다. 어떻게 해야 할까?
- 게임을 많이 해야 한다. 물론, 게임을 무작정 많이 하면 되는 것은 아니다.
코딩을 잘하고 싶다. 어떻게 해야 할까?
- 코딩을 많이 해야 한다. 물론, 코딩을 무작정 많이 하면 되는 것은 아니다.
어떤 알고리즘의 원리와 증명을 이해하는 것은 중요하지만 응용하는 것이 더 중요하다.
- 어떤 문제를 보고 도움 없이 스스로 방법을 떠올려야 할 필요는 없다.
- e.g. 수학 공부를 할 때 피타고라스의 정리, 미분, 적분을 스스로 떠올리는 것을 요구하지 않는다.
이 문제를 어떻게 푸는지 모르겠으니 어떻게든 스스로 풀어내는 것이 나쁜 생각은 아니다.
- 하지만, 인생을 짧고, 시간을 없고, 할 일은 많다.
- 개발은 모든 것을 스스로 해결하는 것을 요구하지 않는다.
- 도움을 받는 것과 이해하는 것, 검색을 하는 것도 매우 중요한 능력이다.
- 족므 고민해보고 모르겠으면, 답을 보고 이해하자.
고민의 시간은 개인마다 차이가 있지만, 처음 공부할 떄는 2~3일 고민해보는 것이 좋다.
- 어느정도 익숙해진 이후에는 2~3시간 고민해보는 것이 좋고,
- 많이 익숙해진 이후에는 20~30분 고민해보는 것이 좋다.
나는 BFS도 알고, 브루트 포스도 알고, 다이나믹 프로그래밍도 안다. 그런데 문제는 못 풀겠다.
- 그러니까 이 문제를 푸는 알고리즘이 무엇인지는 어떻게 알아내는 것인가?
- 이것이 요구하는 능력이다.
- 따로 법칙은 없기 때문에, 각각의 알고리즘의 특징을 알고, 왜 그 알고리즘으로 다른 문제를 풀 수 있었는지 위주로 기억해서 문제에 적용해야 한다.
알고리즘 공부에 가장 효과적인 것은 문제 풀이이다.

2. 효율성

알고리즘 문제를 해결하는 어떤 코드를 작성했을 때, 이 프로그램이 얼마나 효율적인지 알고 싶다. 다음 중 무엇이 가장 중요할까?

수행 시간
사용한 메모리
코드의 길이

수행 시간이 가장 중요하다

어떤 프로그램을 작성했는데, 시간이 30일이 걸리면 정말로 30일동안 실행시켜야 한다.
어떤 프로그램을 작성했는데, 메모리가 64GB 필요한데, 메모리가 부족하면 램을 구매하면 된다.
이런 이유 때문에 문제를 해결할 떄는 시간이 중요하다.

3. 문제의 크기

개발 상황에서 접하게 되는 상황은 문제를 해결하는 것이고, 항상 문제의 크기가 존재한다.

e.g.1 ) 쇼핑몰 장바구니 물건의 개수
e.g.2 )게임 동시 접속자의 수

이러한 문제의 크기를 보통 N이라고 하고, 문제의 크기 N에 따라 걸리는 시간이 다르다

웹 사이트를 만드는 경우에

10명이 동시 접속하는 사이트를 만드는 것과 10만명이 동시 접속하는 사이트를 만드는 방법은 매우 큰 차이가 있다.
또, 10만명이 동시 접속하는 사이트를 만드는 방법이 더 어렵다.
문제를 해결할 때도 문제의 크기에 따라 알맞은 방법을 선택하는 것이 좋다.
대부분의 문제는 가장 빠른 방법이 정해져 있지만, 가장 빠른 방법이 너무 어려운 경우일 수도 있어,
그 방법보다는 상대적으로 느린 (하지만 문제는 해결할 수 있음) 방법을 이용하기도 한다.
이러한 이유 때문에 문제를 해결할 때는 문제의 크기를 먼저 보고 방법을 생각해야 한다.

4. 시간 복잡도 Time Complexity

시간 복잡도를 이용하면 작성한 코드가 시간이 대략 얼마나 걸릴지 예상할 수 있다.

표기법으로 대문자 O를 사용한다. (다양한 시간 복잡도가 많지만, 보통 Big-O만 사용한다)
영어로는 Big O Notation
입력의 크기 N에 대해서 시간이 얼마나 걸릴지 나타내는 방법
즉, 최악의 경우에 시간이 얼마나 걸릴지 알 수 있다.

4.1 대표적인 시간 복잡도

O( 1 )
O(lgN )
O(N)
O(NlgN )
O(N^ 2 )
O(N^ 3 )
O( 2^N)
O(N!)

시간 복잡도 안에 가장 큰 입력 범위를 넣었을 때, 1억이 1초정도이다. 이 값은 대략적인 값으로, 실제로 구현해보면 1억을 조금 넘어도 1초 이내에 수행이 가능하다

4.2 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

5. 메모리

메모리 제한은 보통 넉넉하기 때문에, 걱정할 필요가 없다.
대략적으로 얼마나 공간을 사용할지 예상할 수는 있다.
보통 가장 많은 공간을 사용하는 것은 보통 배열이다.
- 배열이 사용한 공간 : 배열의 크기 × 자료형의 크기 B
- int a[1000000]; → 1000000 × 4B = 4,000,000B
- int a[1000][1000]; → 1000 × 1000 × 4B = 4,000,000B
보통 배열의 크기가 크면 시간 초과를 받는 경우가 많다.
불필요한 공간이 없다면, 대부분 메모리 제한은 알아서 지켜진다.

6. 입출력

6.1 C 입출력

C 의 경우에는 scanf /printf 를 사용할 수 있다

6.2 C++ 입출력

C++의 경우에는 scanf/printf, cin,/cout을 사용할 수 있다.
cin/cout은 scanf/printf보다 느리기 때문에,
- 입/출력이 많은 문제의 경우에는 scanf/printf를 사용하는 것이 좋다.
cin/cout의 경우 아래 세 줄을 추가하면 scanf/printf만큼 빨라진다

1ios_base::sync_with_stdio(false);
2cin.tie(NULL);
3cout.tie(NULL);

이 경우에는 cin/cout와 scanf/printf을 섞어 쓰면 안된다. 즉, cin/cout만 써야 한다

6.3 Java 입출력

Java는 입력은 Scanner, 출력은 System.out을 사용한다.
- Scanner sc = new Scanner(System.in);
입력이 많은 경우에는 속도가 느리기 때문에, BufferedReader를 사용한다
- BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
출력이 많은 경우에는 StringBuilder를 사용해서 한 문자열로 만들어서 출력을 한 번만 사용하거나,
BufferedWriter를 사용한다

6.4 입력 속도 비교

10,000이하의 자연수 10,000,000개가 적힌 파일을 입력받는데 걸리는 시간

C++17 (sync_with_stdio, cin.tie 사용): 0.5938초
Java (BufferedReader): 0.6585초
C11 (scanf): 0.9206초
C++17 (cin): 2.1742초
Java (Scanner): 4.8448초

6.5 출력 속도 비교

1부터 10,000,000까지 자연수를 한 줄에 하나씩 출력하는 시간

C++17 (cout, ‘\n’ 사용): 0.827초
C11 (printf): 0.9118초
Java (BufferedWriter): 0.9581초
Java (StringBuilder 사용): 1.1881초
C++17 (cout, endl 사용): 11.5322초
Java (System.out.println): 30.013초

자료구조&알고리즘-py 100-시작-문제