프로그램을 배웠으나 알고리즘 시험을 봐야 한다면. #14

1차원이라고 하면 문자열이나 숫자를 이용한 문제가 많이 있습니다.

(스토리를 입히면 더 실제 문제 같지만 시간이 없어서 그냥 씁니다.)

 

1. 문자열에 포함된 가장 긴 회문 (앞에서 읽어도 뒤에서 읽어도 같은 글자)의 길이는

 

2. 여러 문자열 중 최장 공통 문장의 길이는?

 

3. 문자열을 앞뒤를 붙였을때 최장 연속된 글자열의 길이는?

   (원형 문자열이죠)

 

4. 문자열 중에 특정 문자열의 갯수는?

 

2번 같은 문제는 대표적인 문제로 유명한 풀이 방법이 있지만

길이가 길지 않으면 CPU의 힘으로 완전탐색으로 풀수 있습니다.

 

4번 문제도 찾아보면 KMP등 유명한 알고리즘들이 있습니다.

상용 프로그램의 성능을 좌우하는 알고리즘이지요.

그런데 경우마다 모두 유명한 최고의 성능의 알고리즘을 공부해서는

끝이 없습니다.

다 외울 수 도 없고 인터넷 세상에 외워서 하는 것도 시대에 뒤떨어진것이고요.

 

나머지도 기본은 완전탐색으로 풀수 있는 연습이 필요합니다.

 

자료구조중 스텍과 큐도 1차원 배열을 이용한다고 해야 할까요?

 

1차원 배열을 완전 탐색으로 푸는 방법은

1. 점으로 보고 순열/조합 등으로 경우의 수를 뽑아 내서 풀 수도 있고

2. 간단히 for 문으로 풀리는 경우도 많이 있습니다.

 

오늘 하고 싶은 말은

1. 어떤 경우에 최적화된 알고리즘이 무엇이 있는지는 알아아 햔다.

    (이름이나 원리만, 외우지 말고)

   나중 면접용이라던가, 실제 업무를 할때 유명한 알고리즘이 있는데

   그걸 본인이 구현하는 우를 범하지 말자. 아무리 해도 최적 알고리즘

   보다는 못한다.

 

2. 유명 알고리즘을 쓰지 않고 짧은 경우를 만들어 완전탐색으로 풀어본다.

 

#삼성_소프트웨어_역량_테스트