1강 - 알고리즘 시작

떠먹여주는 밍구 ㅋ_ㅋ

강의를 들을까 말까 고민하고 있는데 밍구가 선뜻 자기 아이디를 알려주었다! 뭔가 미안한데 고맙고 음... 그래서 그냥 강의 살 돈으로 밍구 맛있는거 많이 사줘서 갚기로 했다ㅋㅋㅋ 사룽해 밍구<3<3

암튼!! 이제부터 강의를 들으면서 중요하다고 생각한 내용을 정리해보려고 한다.

----------------------------------------------------------------------------------------------------------------------------------

 

<알고리즘>

이번 강의에서는 정말 말그대로 알고리즘의 시작이었다. 전체적으로 알고리즘이 무엇인지, 알고리즘을 고민하기 전에 알아야 할 것들에 대해 배웠다. 우선 알고리즘이란 문제를 해결하기 위한 절차나 방법을 공식화한 형태로 표현한 것이다. 사실 학교 전공시간에 다양한 자료구조와 알고리즘을 배우고 과제로 구현도 해보았지만 제출하기 위해서 시간에 쫓기며 했을 뿐이지 정확하게 이 알고리즘이 뭐고 경우마다 어떤 알고리즘을 사용하는 것이 효율적인지를 판단하기엔 제대로 알고있지 않다ㅠㅅㅠ

이 강의자료에서는 알고리즘의 원리와 증명을 이해하는 것도 중요하지만 그보다 중요한건 응용하는 것이 더 중요하다고 한다. 이 강의를 통해서 어떠한 문제를 보면 이 문제를 푸는 알고리즘이 무엇인지를 알아내는 것이 나의 목표이다! 이를 이루기 위해서는 각각의 알고리즘 문제를 풀어보면서 알고리즘을 익히는 것이 좋다고 한다!

 

<효율성>

알고리즘 문제를 해결할 때 해당 프로그램이 효율성을 판단하는 방법으로는 3가지 방법이 존재한다

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

그 중에서도 수행 시간이 가장 중요하다!!

 

<문제의 크기>

문제의 크기는 보통 N이라 하고, 문제의 크기 N에 따라 걸리는 시간이 달라지게 된다. 따라서 문제를 해결할 때 문제의 크기에 따라 알맞은 방법을 선택하는 것이 좋다. 그러기 위해서는 문제의 크기를 먼저 보고 문제 해결 방법을 생각해야 한다.

 

<시간 복잡도>

시간 복잡도를 통해서 작성한 코드의 시간이 대략 얼마나 걸릴지 예상이 가능하다. 표기법으로는 대문자 O를 사용한다. 그래서 보통 '빅오'라고도 불린다. 이는 입력의 크기 N에 대하여 Worst case(최악의 경우)의 시간이 기준이 된다. 예를 들어 코드가 최상의 경우에는 1초가 걸리고 최악의 경우에는 10초가 걸린다면 시간 복잡도는 10초가 된다는 것이다.

대표적인 시간 복잡도로는 O(1), O(logN), O(N), O(N^2), O(NlogN), O(N^3), O(2^N), O(N!) 등이 있다. 

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

강의자료 내 시간 복잡도 예시 

Big O Notation에서는 상수는 버린다. 예를 들어 O(3N)이면 O(N)으로, O(5)면 O(1)로 표기한다.

또한 두 가지 항이 있을 때, 변수가 같으면 큰 것만 빼고 다 버린다. 예시로 O(N^2+N)은 O(N^2)로, O(N^2+NlogN)은 O(N^2)로 표기한다. 

하지만 두가지 항이 있는데 항의 변수가 다르면 생략하지 않는다. 예를 들어 O(N^2+M)이면 M을 생략하지 않는다. 왜냐하면 M의 범위가 N^2의 범위보다 훨씬 큰 경우에는 N^2보다 M이 시간 복잡도에 더욱 큰 영향을 끼치기 때문에 두 개의 변수 중에 어떤 것이 영향을 크게 줄지 모른다. 따라서 이와 같은 경우에는 생략하지 않고 작성한다. 

 

<메모리>

메모리 제한은 보통 넉넉해서 걱정할 필요가 없고 대충 얼마나 공간을 사용할지 예상이 가능하다. 보통 가장 많은 공간을 사용하는 것은 배열이다. 배열이 사용한 공간은 '배열의 크기 * 자료형의 크기 B'로 계산한다. 보통 1초에 512MB정도 계산이 가능하다고 한다. 그래서 배열의 크기가 크면 시간 초과를 받는 경우가 많다. 또한 불필요한 공간이 없다면 대부분의 메모리 제한은 지킬 수 있다고 한다. 

 

<입/출력>

1. C 입출력 

- scanf와 printf를 사용할 수 있다.

 

2. C++ 입출력

- scanf, printf, cin, cout을 사용할 수 있다.

- cin/cout은 scanf/printf 보다 느리기 때문에 입출력이 많은 경우에는 scanf/printf를 사용하는 것이 좋다.

- cin/cout의 경우 아래 세 줄을 추가하면 scanf/printf 만큼 속도가 빨라진다.

     -> ios_base::sync_with_stdio(false);

     -> cin.tie(NULL);

     -> cout.tie(NULL);

보통 위의 두 줄만 추가해도 충분히 속도가 빨라지고 아래의 두 줄은 cin.tie(nullptr)/cout.tie(nullptr)로도 많이 쓰인다고 한다. 위의 경우를 사용할 경우에는 scanf/printf를 사용하면 안되고 오직 cin/cout만 써야 하므로 주의하자!

- cout을 사용할 때 개행문자로 endl을 사용하는데 이를 사용하는 것보다 '\n'을 사용하는 것이 훨씬 속도가 빠르다.

 

3. Java 입출력

- 입력은 Scanner, 출력은 System.out을 사용한다.

   -> Scanner sc = new Scanner(System.in);

- 입력이 많은 경우에는 속도가 느리기 때문에, BufferReader를 사용한다.

   -> BufferReader br = new BufferReader (new InputStreamReader (System.in));

- 출력이 많은 경우에는 StringBuilder를 사용해서 한 문자열로 만들어 출력을 한번만 사용하거나 BufferWriter를 사용한다.

 

 

*A+B 입출력 문제를 풀 때 입력받은 숫자를 저장하고 한번에 출력하는 것보다 하나 하나 입력받고 바로 출력하는 것이 메모리 낭비도 하지 않고 좋다. 그리고 테스트 케이스가 주어지지 않는 경우에는 입력을 EOF까지 받으면 된다.

 

<언어별 EOF 받는 방법>

- C : while (scanf("%d %d", &a, &b) == 2) -> 성공적으로 입력받은 변수의 숫자로 판단

- C++ : while (cin >> a >> b)

- Java : while (sc.hasNextInt())

 

 

 

1강 내용정리 끝~~><