알고리즘 기초

정의

- 수학과 컴퓨터 과학, 언어학 또는 관련 분야에서 어떠한 문제를 해결하기 위해 정해진 일련의 절차나 방법을 공식화한 형태로 표현한 것을 말한다.

 

효율성

중요도: 수행 시간 > 사용한 메모리 > 코드의 길이

1. 시간이 30분 걸린다면 정말로 30분 실행시켜야 하지만, 메모리가 64G 필요하다면 램을 구매하면 된다.

2. 하지만 상황에 따라 무엇이 중요한지는 다르다.

 

문제의 크기

10명이 접속하는 사이트를 만드는 것과 10만명이 동시 접속하는 사이트를 만드는 법은 다르다.

문제를 해결할 때도 문제의 크기에 따라 알맞은 방법을 선택하는 것이 좋다.

 

시간복잡도

입력의 크기 N에 대해 최악의 경우에 걸리는 시간을 O(Big O Notation)으로 표기한다.

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

 

시간복잡도가 1억 안팎으로 1초 내에 수행 가능하다.

 

Big O Notation에서 상수는 버린다.

두 가지 항이 있을 때, 변수가 같으면 큰 것만 빼고 다 버린다.

두가지 항이 있는데 변수가 다르면 놔둔다.

 

메모리

메모리 제한은 보통 넉넉하기 때문에 걱정할 필요 없지만,

배열의 크기가 크면 시간 초과를 받는 경우가 많다.

 

입/출력

Java  입력은 Scanner, 출력은 System.out 을 이용한다.

입력이 많은 경우에는 BufferedReader을 사용한다

출력이 많은 경우에는 StringBuilder를 사용해 한 문자열로 만들어 출력을 한 번에 한다

 

입출력에 대해 보다 자세히 알고 싶을 때 참고하면 좋을 글

https://st-lab.tistory.com/41

JAVA [자바] - 입력 뜯어보기 [Scanner, InputStream, BufferedReader]