알고리즘 기초1/2

1 minute read

1. 알고리즘 시작

중요한것은 응용

1.어떤 알고리즘의 원리와 증명을 이해하는 것은 중요하지만 응용하는 것이 더 중요하다.
스스로 모든것을 해결하려고 하지 말아라

1.어떤 문제를 보고 도움 없이 스스로 방법을 떠올려야 할 필요는 없다.

2.도움을 받는 것과 이해하는 것,검색을 하는 것도 매우 중요한 능력이다.

3.조금 고민해보고 모르겠으면, 답을 보고 이해하자.
효율적인 시간 분배

1.처음 공부할 때는 2-3일 고민해보는 것이 좋다

2.어느 정도 익숙해진 이후에는 2-3시간 고민해보는 것이 좋고, 많이 익숙해진 이후에는 20-30분 고민해보는 것이 좋다.
알고리즘에서 원하는것

1.이 문제를 푸는 알고리즘이 무엇인가?

2.각각의 알고리즘의 특징을 알고,왜 그 알고리즘으로 다른 문제를 풀 수 있었는지를 위주로 기억해서 문제에 적용해봐야 한다.

3.알고리즘 공부에 가장 효과적인 것은 문제풀이이다. 4.먼저 각각의 알고리즘 문제를 풀어보면서, 알고리즘을 익히는 것이 좋다.

문제의 크기

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

2.문제를 해결할 때는 문제의 크기를 먼저 보고 방법을 생각해야 한다.

시간 복잡도

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

2.표기법으로 대문자 O를 사용한다. (다양한 시간 복잡도가 많지만, 보통 Big-O만 사용한다)

3.입력의 크기 N에 대해서 시간이 얼마나 걸릴지 나타내는 방법

4.즉, 최악의 경우에 시간이 얼마나 걸릴지 알 수 있다.

5.시간 복잡도 안에 가장 큰 입력 범위를 넣었을 때, 1억이 1초정도이다.
시간 복잡도 예측

1.시간 복잡도는 소스를 보고 계산할 수도 있고, 소스를 작성하기 전에 먼저 계산해볼 수 있다.

2.문제를 풀기 전에 먼저 생각한 방법의 시간 복잡도를 계산해보고 이게 시간 안에 수행될 것 같은 경우에만 구현하는 것이 좋다.

Java 입출력

1.Java는 입력은 Scanner, 출력은 System.out을 사용한다. Scanner sc = new Scanner(System.in);

2.입력이 많은 경우에는 속도가 느리기 때문에, BufferedReader를 사용한다. BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); 출력이 많은 경우에는 StringBuilder를 사용해서 한 문자열로 만들어서 출력을 한 번만 사용하거나 BufferedWriter를 사용한다.
문제가 테스트 케이스로 주어지는 경우

1.각각의 독립적인 문제로 생각하고 풀면된다.

2.전체 테스트 케이스를 입력받은 다음에, 풀지 않아도 된다.

예를들어

입력 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있으며, 각 줄에 A와 B가 주어진다. (0 < A, B < 10)
```
5
1 1
2 3
3 4
9 8
5 2
```
출력 각 테스트 케이스마다 A+B를 출력한다.
```
2
5
7
17
7
```
일 경우 테스트 케이스가 주어지면 입력을 다 받고 모아서 출력하는 것이 아니라 하나 입력받고 하나 출력 결과를 보여주는것을 반복하는것이 더 효율적이다. 그 이유는 T의 갯수를 모를때 배열의 크기를 정하기 어렵기 때문이다.