매일 많은 글이 올라올 예정.
-----------------------------------
알고리즘의 카테고리는 2가지가 있다. 교육용과 상업용.
교육용
Online judge 사이트(topcoder 等)에서 정형화된 문제를 푸는 것이다.
문제의 발견 → 문제의 정의 → 수식으로 변환 → 코드로 변환
문제는 알고리즘 사이트에 있고, 정의도 알고리즘 사이트에 있다. 수식은 공개되어 있어서 외우고 해당 코드로 만드는 법도 외우면 된다.
엘리베이터 사고
는 해결하지 못한다.
상업용
알고리즘은 상품을 만드는 것이 대표적인 예이다.
목표 설정 → 정보수집 → 대안 설정 → 수식으로 변환 → 코드로 구현 → 성능 테스트 → 최적안 선정
여러 대안이 있을 수 있고, 교육용에서 하는 것처럼 시/공간 복잡도를 평가할 수도 있겠지만 고려할 사항은 매우 많다. TRIZ와 비슷하다.
Teoriya(이론) Resheniya(해결책) Izobretatelskikh(발명의) Zatach(작업의)
TRIZ는 구 소련 겐리히 알츠슐러(Genrich Altshuller)에 의해 제창된 창의문제 해결을 위한 체계적 방법론
명백, 개선, 혁신, 발명, 발견 과정에서 고려해야할 해법 수는 10가지에서 1,000,000(백만)가지로 늘어남.
아무리 잘 만들어도 선점형 운영체제가 아닌 경우 문제가 될 수 있다. RTOS를 쓴다고 해도 Cortex-R과 같이 해당 운영체제를 지원하는 프로세서 라야 문제를 일으키지 않을 수도 있다.
디자인 패턴
교육용
알고리즘과 디자인 패턴은 같은 의미로 보면 된다. 둘 다 상업용 알고리즘을 만들기 위한 [기초]가 된다. 디자인 패턴 안에는
우리가 일반적으로 아는 [자료구조], [알고리즘]이 들어간다. 알고리즘은 수학과 결합되어 있고, 나에게 대표적으로 중요한 과목을
꼽으라면 고등학교 수학, 공업수학, 선형대수 정도이다.
수학, 물리학과, 산업공학과가 알고리즘을 잘 짜는 이유
On-Line Encyclopedia of Integer Sequences
여기 들어가면 정수열이 많다.
0,
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597,
2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418,
317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465,
14930352, 24157817, 39088169
이 숫자에서
Fibonacci numbers: F(n) = F(n-1) + F(n-2) with F(0) = 0 and F(1) = 1
이 수식을 뽑을 수 있다면,
#include <iostream>
using namespace std;
int fibonacci(int number) {
if (number <= 1) { return number;
} else { return fibonacci(number - 1) + fibonacci(number - 2);
} }
int main() {
int fib_number = fibonacci(8);
cout << "The 8th Fibonacci number is: " << fib_number << endl;
return 0;
}
C/C++이던
public class Fibonacci {
public static void main(String[] args) {
int fibNumber = fibonacci(8);
System.out.println("The 8th Fibonacci number is: " + fibNumber);
}
public static int fibonacci(int number) {
if (number <= 1) {
return number;
} else {
return fibonacci(number - 1) + fibonacci(number - 2);
} } }
JAVA 던
function fibonacci(number) {
if (number <= 1) {
return number;
} else {
return fibonacci(number - 1) + fibonacci(number - 2);
} }
var fibNumber = fibonacci(8);
console.log("The 8th Fibonacci number is: " + fibNumber);
JAVA SCRIPT 던
func fibonacci(number: Int) -> (Int) {
if number <= 1 {
return number
} else {
return fibonacci(number - 1) + fibonacci(number - 2)
}
}
var fibNumber = fibonacci(8)
println("The 8th Fibonacci number is: \(fibNumber)")
SWIFT 던
#!/usr/bin/env ruby
def fibonacci(number)
if number <= 1
return number
else
return fibonacci(number - 1) + fibonacci(number - 2)
end
end
fib_number = fibonacci(8)
puts "The 8th Fibonacci number is: #{fib_number}"
RUBY 던
def fibonacci(number):
if number <= 1:
return number
else:
return fibonacci(number - 1) + fibonacci(number - 2)
if __name__ == "__main__":
fib_number = fibonacci(8)
print 'The 8th Fibonacci number is:', fib_number
PYTHON이던
중요하지 않다.(중요하지만 이 글에서는 중요하지 않다로 하겠다.)
수학,
물리학과 학생들이 수식을 잘 뽑아 낸다. 이들을 프로그래머로 만들려면 코드로 변환하는 것만 가르쳐 주면 된다. 내가
산공출신이라(시스템경영으로 바뀌었지만) 억지로 산업공학과도 넣었다. 사실, 따지고 보면 통계, 기계 等 수식을 배우는 모든 학과가
해당된다.
기초 알고리즘만 예를 들었을 때
if문
for문, 배열, 링크드 리스트, 큐, 트리, 문자 처리, 함수 쓰는 방법, 소트, 최단거리 알고리즘, 그리디 알고리즘 정도의
키워드를 알면 뽑아낸 수식에서 코드로 변환하기 위한 공부들을 인터넷을 통해 찾을 수 있다. if/for, 배열, 함수 쓰는 방법은
해당 키워드가 전부이지만 나머지는 응용한 것들이 많고 또 응용한 것이 새로운 학문이 되기도 한다.
고급으로
넘어가면 논문을 검색하는 영역으로 들어가는데 논문은 전체를 이해하기에는 시간이 너무 걸린다. 보통 해당 수식을 단순히 코드로만
구현해서 상품을 만든다. 상품이 성공하면 해당 부분에 대해서 깊게 공부하는 것이 상업용 알고리즘의 사이클이다. 결국 상업적으로
성공해야 깊게 팔 수 있다는 뜻이다.
경험적이고 현실적으로 말해 보았다.
대학생의 경우 원하는 기업 입사를 위해서 교육용 알고리즘 공부만 하는 것이 최근 기조이다. 전체적인 흐름은 알고 공부를 하면 왜 공부해야 하는지 알기에 좀 더 고무적이게 된다.
이렇게 생각한다.
P.S
끝으로
여담을 하나 말해 봅니다. IT 비전공자를 가르칠 기회가 많아서 기업은 왜 다들 알고리즘 시험을 보는가? 에 대한 답을 자주
하게 됩니다. 프로그래밍은 문제를 푸는 것이고 알고리즘이라는 단어 자체가 문제가 있고, 그것을 해결해 가는 과정의 뜻을 내포하고
있습니다. 그래서 데이터 구조도 그 안에 있는 것입니다. 객체는 상태와 행동인데 상태를 효율적으로 표현하기 위해 데이터 구조가
있고, 행동을 효율적으로 표현하기 위해 알고리즘이 있습니다. 데이터 구조가 알고리즘에 포함되어 있기 때문에 알고리즘이 중요한
것입니다. 물론, 교과 과목은 따로 되어 있지만요 ^^
알고리즘이 어렵다는 사람은
카테고리를 잘 알고 자주 쓰는 알고리즘을 공부하면 됩니다. 현재 진행하고 있는 교육 운영 프로그램 운영하는 자산이라 제가 정리한 목록 공개는 어렵지만 관련 책이 많으니 참고하시기 바랍니다.
저의 경우 구종만씨 책과 다음 책을 샀습니다. 사실 구종만씨 책은 선물용으로 계속사서 주고 있습니다.
저의
경우 실무에서 가장 많이 쓰이는 것은 array, list, hashtable, map, heap 으로 보입니다. heap 을
알려면 tree를 알아야 합니다. 소팅을 하다보면 heap 정렬도 있고, list search를 하다보면 quick
sort(binary)랑 array(linear)를 씁니다. 그래프 서치에 tree가 또 들어갑니다.
전,
여러 교육 알고리즘 문제를 잘 풀지 못합니다. 다만 저명 인사를 만나보니 리누스 토발즈나 존 카멕도 구글 코드 잼에서 예선 탈락
할 수 있다는 것을 알지요. 게다가 항공기에도 쓸 수 있는 RTOS 소프트웨어의 스케쥴러도 간단한 array 와 sort,
search 등을 기반하여 짜여 진다는 것도 알고 있습니다.
간단한
OLPP를 실생활에 완벽하게 적용하여 생각 회로를 바꾸고 싶다면, 모든 자잘한 것 세부적인 것들도 알고 있는 상태여야 합니다. 제
이야기도 해 드렸으니 기본 공부는 얼핏이라고 해서 언제든 찾을 수 있는 keyword를 머릿속에 넣었으면 합니다.
