알고리즘 기초

알고리즘이란

알고리즘(라틴어, 독일어: Algorithmus, 영어: algorithm 알고리듬[*], IPA: [ǽlɡərìðm])은 수학과 컴퓨터 과학, 언어학 또는 관련 분야에서 어떠한 문제를 해결하기 위해 정해진 일련의 절차나 방법을 공식화한 형태로 표현한 것, 계산을 실행하기 위한 단계적 절차를 의미한다.

 

알고리즘은 음식의 레시피와 비슷하다. (같은 것은 아니다)
'요리의 재료를 이용해 레시피의 방법으로 요리한 다음, 요리를 완성한다. '
이는
'입력을 이용해 알고리즘으로 문제를 해결하고, 정답을 출력한다.'

와 비슷하다.

 

 

알고리즘

어떤 문제를 해결하는 방법을 모두 알고리즘이라고 할 수 있다.

많은 개발은 어떠한 문제를 해결해야 하는 것이 목적인 경우가 많다.

 

나는 BFS도 알고, 브루트 포스도 알고, 다이내믹 프로그래밍도 안다.

그런데 문제는 못 풀겠다.
그러니까 이 문제를 푸는 알고리즘이 무엇인지는 어떻게 알아내는 것인가?
이것이 요구하는 능력이다.
따로 법칙은 없기 때문에 각각의 알고리즘의 특징을 알고 왜 그 알고리즘으로 다른 문제를 풀 수 있었는지를 위주로 기억해서 문제에 적용해봐야 한다.

 

 

문제의 크기

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

 

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

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

웹 사이트를 만드는 경우에 10명이 동시 접속하는 사이트를 만드는 것과 10만명이 동시 접속하는 사이트를 만드는 방법은 매우 큰 차이가 있다.

또, 10만명이 동시 접속하는 사이트를 만드는 방법이 더 어렵다.

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

대부분의 문제는 가장 빠른 방법이 정해져 있지만, 가장 빠른 방법이 너무 어려운 경우일 수도 있어, 그 방법보다는 상대적으로 느린 (하지만 문제는 해결할 수 있음) 방법을 이용하기도 한다.

 

 

시간 복잡도란

어떤 코드를 작성했을 때 시간이 얼마나 걸리는지를 예측해보는 방법이다.

시간 복잡도를 통해 최악의 경우 시간이 얼마나 걸리는지 알 수 있다.

예를 들어 어떤 코드를 작성했을 때 99%의 확률로 0.1초가 걸리지만 1%의 확률로 100초가 걸린다면 이 알고리즘은 100초의 알고리즘이라고 한다.

시간 복잡도는 Big O만 사용하고, 이 Big O가 의미하는것은 최악의 경우에 시간이 어느 정도 걸릴지를 예상하는 방법인 것이다.

다만 컴퓨터의 상황에 따라 변하기 때문에 절대적인 시간은 알 수 없고 대략적인 시간만 예상 가능하다.

 

• 문제의 크기를 알파벳 N으로 나타내는데 이 N에 따라서 시간이 얼마나 걸릴지를 시계 형태로 나타낸다
• 표기법으로 대문자 O를 사용한다. (다양한 시간 복잡도가 많지만, 보통 Big-O만 사용한다. 영어로는 Big O Notation)
• 시간 복잡도 안에 가장 큰 입력 범위를 넣었을 때, 1억이 1초정도이다.
• 이 값은 대략적인 값으로, 실제로 구현해보면 1억을 조금 넘어도 1초 이내에 수행이 가능하다

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

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

 

 

시간 복잡도 계산

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

O(3N^2) = O(N^2)

O(1/2 N^2) = O(N^2)

O(5) = O(1)

 

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

O(N^2 + N) = O(N^2)

O(N^2 + NlgN) = O(N^2)

 

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

O(N^2 + M)

 

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

 

 

Java 입출력

☞Java의 입력은 Scanner, 출력은 System.out을 사용한다.

Scanner sc= new Scanner(System.in);

 

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

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

 

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

 

 

BufferedReader 란

Java에서 주로 받는 입력방식은 Scanner이다.

Scanner를 통해 입력을 받을 경우 Space Enter를 모두 경계로 인식하기에 입력받은 데이터를 가공하기 매우 편리하다.

하지만 그에 비해 BufferedReader는 Enter만 경계로 인식하고 받은 데이터가 String으로 고정되기 때문에 입력받은 데이터를 가공하는 작업이 필요할 경우가 많다.

Scanner에 비해 다소 사용하기 불편하지만, 많은 양의 데이터를 입력받을 경우 BufferedReader를 통해 입력받는 것이 효율면에서 훨씬 낫다.

입력 시 Buffer 메모리 줌으로써 작업 속도 차이가 많이 난다.