알고리즘 4

[C++] 문자열 뒤집기(Reverse String) 알고리즘

이 문제는 규모가 큰 IT회사에서 단골 문제로 나온다. 간단히 풀 수 있는 문제여서 면접 중에 화이트보드로 풀라고 하는 경우가 많다. 이 문제의 핵심은 결과만 나오는 것이 아니라 복잡도를 최소한으로 해서 결과가 나오게 하는 것이다. 1. 문제 char arr[6] = { 'S', 'T', 'R', 'I', 'N', 'G' }; char result[6] = {0,}; 주어진 arr 문자 배열의 내용을 역순으로 result 배열에 담아야 한다. 결과 배열 char result[6]에는 'G', 'N', 'I', 'R', 'T', 'S' 순으로 들어있도록 만들면 된다. 2. 어떻게 풀까? (알고리즘) 직관적인 방법으로는 result 배열의 끝 인덱스부터 하나씩 역순으로 접근해서 result 배열에 차례대로 ..

[C++] 소수 구하기 최적의 알고리즘 (2) - 에라토스테네스의 체

소수 구하기 최적의 알고리즘 1편에서 (http://marobiana.tistory.com/89) 주어진 수보다 작은 수의 소수들로 나누는게 성능이 좋다고 했었는데, 그것보다 더 좋은 알고리즘을 찾아냈다.ㅋㅋ 이것보다 더 좋은 방법은 아마도 없을 것이라 자신함 !! 만약 있다면 댓글 달아주시기 바람. 요번에는 c++로 구현해보았음. 1. 알고리즘 에라토스테네스의 체 (Sieve of Eratosthenes)라는 알고리즘이다. 아래 그림을 보면 무엇인지 알 수 있다. 120까지의 모든 소수를 구한다고 해보자. 2부터 120까지 배열에 모두 넣은 후 소수가 아닌 것들을 모두 체크해버리는 것이다. 2를 제외한 모든 2의 배수를 체크한다. 3을 제외한 모든 3의 배수를 체크한다. 4는 아까 체크당했으므로 소수 ..

[C++] 두 정수 사이의 모든 합 구하기

어제 올린 글에는 최적화를 생활화하자는 글을 썼었는데, 오늘은 반대로 최적화를 잘못하면 화를 부를 수 있다는 것을 정리해보고자 한다ㅋㅋㅋㅋ 1. 문제 두 정수 사이의 모든 합을 구하는 것이다. 3, 5를 입력받으면 3 + 4 + 5 를 한 결과를 출력하면 됨. 작은 수부터 입력 받는다고 가정하자. 2. 알고리즘 가장 먼저 생각할 수 있는 알고리즘은 입력 받은 수부터 두번째 입력 받은 수 까지 반복문 돌리면서 더하는 것이다. 반복문을 좀 줄여본다면??? 1 + 2 + 3 + 4 + 5 + 6 를 보면 규칙을 찾을 수 있다. 1 + 6 = 7 2 + 5 = 7 3 + 4 = 7 이것을 이용하면, 포문을 반으로 줄일 수 있다! 여기서 잠깐, 더할 수의 개수가 홀수이면 이렇게 된다. 1 + 2 + 3 + 4 +..

[JAVA] 소수 구하기 최적의 알고리즘 (1)

한달 전에 면접에서 소수를 손코딩하라는 명을 받았다. (인성면접이라는 훼이크에 당해버렸음 @_@) 소수에 대해서는 깊이 생각해본적이 없었는데..이번일을 계기로 더더욱 최적의 방법을 생각하는 버릇을 들이겠다는 다짐을 하게되었다. 1. 소수(Prime Number)란 무엇인가? 2, 3, 5, 7, 11, 13, 17.... 약수가 1과 자기 자신 뿐인 수이다. 2. 소수를 어떻게 구할까? (알고리즘) 약수가 1과 자신뿐인 것을 확인해야한다. 그러려면??? 즉, 자기 자신보다 작은 수들을 나누어봐서, 하나라도 나누어지면 소수가 아닌 것이다.(어떤 수의 배수이면 안된다는 것) 보통은 여기까지만 생각하고 코딩을 시작할 것이다.그런데 조금만 더 생각해보면 더 좋은 방법이 있다. 일단은 이대로 코딩을 시작해봄 ㄱㄱ..