알고리즘 보관

안녕하세요.

오늘은 알고리즘에 대해서 알아보도록 하겠습니다!

알고리즘(Algorithm)이란 무엇인가?

알고리즘은 문제 해결 방법을 정의한 일련의 단계적 절차이자 어떠한 문제를 해결하기 위한 동작들의 모임이다. (from. wiki…)

음.. 무슨 소리인지 모르겠는데요?
쉽게 말해보면 어떠한 문제가 있습니다.
이 문제를 해결하기 위해 미리 정해 놓은 프로세스를 통해 풀어나가려 할텐데요..
이때! 미리 정해놓은 프로세스를 알고리즘이라 생각하시면 편합니다!

위 그림을 보시면 Input과 Output 사이에 알고리즘이 있습니다.
내가 입력할 값(Input)으로 원하는 값(Output)을 도출해내는 과정을 알고리즘이라고 표현합니다.

예를 들어보겠습니다.
라면을 아주아주 먹고 싶어하는 사람이 있습니다.
그 사람은 라면을 먹기 위해서 라면을 끓이는 과정이 필요합니다.
이때, 라면을 끓이는 과정이 알고리즘에 해당하는 과정입니다.
– Input : 라면 먹고 싶은 사람
– 알고리즘 : 라면 끓이는 과정
– Output : 라면을 맛있게 먹어보자

일상생활에서도 알고리즘과 같은 일련의 과정을 볼 수 있습니다.
IT를 하는 사람으로써 이런 과정을 “알고리즘“ 이라 불러요~

왜 알고리즘 공부를 해야하는가?

알고리즘 공부를 왜 해야하나요?
세상에는 우리보다 훨씬 똑똑한 사람들이 많이 있죠.
그런 사람들을 우리는 천재라고 부릅니다.
천재들이 많이 쓰이는 알고리즘을 구현해놓고, 우리는 그것을 토대로 실전에서 써먹기 위해 분석하고 공부하는 것이죠!

이를테면, 숫자 10으로 100을 만들어야 한다고 문제가 주어졌을때
누군가는 10+10+10….+10 = 100 과 같이 10을 열번 더하는 사람이 있고
10×10 = 100 과 같이 곱셈으로 간단하게 해결하는 사람이 있을 수 있죠.

즉, 덧셈 뺄셈만 아는 사람보다 곱셈 나눗셈까지 알게 된다면 더 효율적으로, 더 빠르게 계산을 할 수 있듯이!
프로그램에서도 알고리즘 공부를 통해 프로그램을 더 효율적으로, 빠르게 만들기 위함이라고 생각합니다.

알고리즘의 종류는 무엇이 있나?

위에서 말씀드렸듯이, 알고리즘의 종류는 아주 많습니다.
그 중에서 오늘은 널리 쓰이는 알고리즘들을 간단하게 알아보도록 하겠습니다.

검색(Search) 알고리즘
– 데이터 집합에서 특정 값을 검색하는 알고리즘
– 선형 검색, 이진 검색 등 다양한 방식으로 사용 가능
정렬(Sorting) 알고리즘
– 데이터를 정렬하는데 사용하는 알고리즘
– 버블 정렬, 선택 정렬 등 다양한 방식으로 사용 가능
동적(Dynamic) 계획법
– 하나의 문제를 작은 문제로 나눠 해결하는 알고리즘
그래프(Graph) 알고리즘
– 정점과 간선으로 이루어진 알고리즘
– DFS, BFS 등 다양한 알고리즘이 있음
탐욕(Greedy) 알고리즘
– 매 순간에 최적이라고 생각되는 것을 선택하는 알고리즘
– 최적이라고 생각해서 선택했지만 최적이 아닐 수 있음

이처럼 다양한 알고리즘이 있습니다.
이후 포스팅을 통해 차근차근 알아보도록 하고 오늘은 큰 틀만 알아보도록 하겠습니다.

좋은 알고리즘이란?

알고리즘이라고 해서 모두 다 좋은 알고리즘일까요?
아닙니다!
그러면 어떤 알고리즘이 좋다고 말할 수 있을까요?
알고리즘이 소모하는 소요 시간을 시간 복잡도, 메모리 공간을 얼마나 잡아 먹는가를 공간 복잡도라 합니다.

이러한 복잡도를 측정하는 방법에 대해서 사람들은 “빅오(Big O) 표기법” 이란 표기법을 만들어 놨습니다.
빅오 표기법은 가장 널리 쓰이는 표기법이에요.

위 그림에서 O(1) 을 좋다고 표현하며, O(n!) 으로 갈 수록 좋지 않다고 표현 합니다.
결과적으로 알고리즘 내부에서 코드를 실행하기 위한 횟수가 시간과 관련되어서 효율이 좋고, 좋지 않고를 판단하는 지표가 됩니다.

올바른 알고리즘을 사용하기 위해서 해당하는 표기법을 통해 미리 계산해보고, 판단해서 프로그램에 적용한다면 보다 효율적으로 만들 수 있게 됩니다.

사실.. 프로그램을 실제로 만들어보면 해당 방법을 고려하지는 않지만, 고려하는 훈련도 필요하다고 생각이 드네요.

이상! 알고리즘에 대해 알아보았습니다.

오늘도 읽어주셔서 감사합니다.

안녕하세요~

오늘은 재귀 알고리즘에 대해서 알아보겠습니다!

재귀 알고리즘이란?

재귀 : 어떠한 것을 정의할 때 자기 자신을 참조하는 것. [from 위키..]
즉, IT 관점에서 본다면 자기 자신을 계속해서 호출하는 알고리즘입니다.

Working of C recursion

위 그림과 같이
1. main() 메소드 안에서 최초 recurse() 메소드 호출
2. 호출된 recurse()에서 자기자신인 recurse() 호출
3. 종료되기까지 계속해서 자기자신 호출 반복
이 처럼 계속해서 자기자신을 호출하는 방식의 알고리즘입니다.

해당 알고리즘을 적용한 재귀함수를 많이 쓴다고 해요~

왜 재귀 함수를 쓰는가?

어? 반복문과 비슷한데 왜 재귀 알고리즘을 쓰나요?

재귀 함수의 장점은 “가독성” 이 가장 크다고 생각해요.
인터넷 찾아보면 변수 사용을 줄인다는 장점도 있는데,
결국에는 그것도 가독성이죠… 하하..

저 같은 경우 폴더-파일 구조를 for문이나 while문 등의 반복문을 통해 구현하기 어렵다고 느꼈어요.
반복문을 사용하게 되면 그 만큼의 가독성도 떨어지고 변수도 많이 사용하더라구요..
그래서 재귀 함수를 통해 구현을 한번 해본 적이 있는데 이때 엄청 간단하게 구현을 해냈습니다..!!

하지만 재귀함수는 메모리 사용량이 많고, 단순 반복문보다 성능이 더 떨어질 수 있는 단점이 있어요.

그리고 종료 조건을 잘못 했을때에는 Stack Overflow 발생..

그래서 특히 재귀 함수의 경우에는 주의해서 사용해야합니다!

재귀 알고리즘 예시 (팩토리얼)

재귀 알고리즘 검색 시에 가장 많이 나오는 팩토리얼 구하기입니다.

팩토리얼은 특정 정수에서 1까지의 수를 모두 곱하는 것이에요.
예를 들어서 4! = 4 x 3 x 2 x 1 = 24. [즉 4! = 24]

자. 그러면 팩토리얼을 구현한 코드를 보시죠!

public static void main(String[] args) {
  System.out.println(factorial(4));
}

public static int factorial(int n) {
  int result = 1;
  for (int i=n ; i>=1 ; i--) {
    result *= i;
  }
  return result;
}

main()메소드 실행
factorial(4) 실행
n = 4, n * factorial(n-1) 실행
n = 3, n * factorial(n-1) 실행
n = 2, n * factorial(n-1) 실행
n = 1, if문안의 return 1 실행

결과는 4 * 3 * 2 * 1 = 24 가 나옵니다!

그냥 for문을 통한 반복문으로 실행한다면?

public static void main(String[] args) {
  System.out.println(factorial(4));
}

public static int factorial(int n) {
  int result = 1;
  for (int i=n ; i>=1 ; i--) {
    result *= i;
  }
  return result;
}

반복문을 통해 구현한 팩토리얼도 똑같이 24의 결과값이 나옵니다.
그런데 사실 반복문으로 구현하나, 재귀함수를 통해 구현하나 비슷해보입니다.
하지만… 팩토리얼이 아닌 더 복잡한 프로그램을 구현하려 한다면 어떻게 될까요?
더욱 더 복잡하고, 가독성도 그 만큼 떨어지게 될거에요.. (제 생각 ㅎ)

마치며.. 결론은?

항상 재귀 함수가 좋지는 않습니다!
고려해봐야 할 부분도 일반 반복문보다 훨씬 많고,
많이 쓰지 않는다면 그 만큼 어려운 알고리즘이라고 생각해요..
하지만? 적용할 수 있는 상황에서 적용을 한번 해본다면
아!! 왜 써야하겠구나..! 라는 거를 깨달을테니 한번 도전해봅시다!

상황에 맞게 적절히 골라 사용을 해보며 공부해봅시다!

오늘도 제 글을 봐주셔서 감사합니다 ^__^

DevlyJ

태그 보관물: 알고리즘

알고리즘(Algorithm)이란?