Take Action

소수 구하기 최적의 알고리즘 1편에서 (http://marobiana.tistory.com/89) 주어진 수보다 작은 수의 소수들로 나누는게 성능이 좋다고 했었는데,그것보다 더 좋은 알고리즘을 찾아냈다.ㅋㅋ이것보다 더 좋은 방법은 아마도 없을 것이라 자신함 !! 만약 있다면 댓글 달아주시기 바람.요번에는 c++로 구현해보았음.1. 알고리즘에라토스테네스의 체 (Sieve of Eratosthenes)라는 알고리즘이다..

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

한달 전에 면접에서 소수를 손코딩하라는 명을 받았다. (인성면접이라는 훼이크에 당해버렸음 @_@)소수에 대해서는 깊이 생각해본적이 없었는데..이번일을 계기로 더더욱 최적의 방법을 생각하는 버릇을 들이겠다는 다짐을 하게되었다.1. 소수(Prime Number)란 무엇인가?2, 3, 5, 7, 11, 13, 17....약수가 1과 자기 자신 뿐인 수이다.2. 소수를 어떻게 구할까? (알고리즘)약수가 1과 자신뿐인 것을 확인해야한다.그러려면??? ..

1. Insertion Sort 개념아래와 같은 순서로 카드가 놓여져 있다고 생각해보자. 4 5  3  2  (1)4  5  3  2  2번째부터 기준이 되어 시작한다. (왼쪽과 비교해야 하므로 2번째부터 시작한다)기준인 5와 그 왼쪽인 4를 비교하니 5가 더 크므로 냅둔다.4  5  3  2  이 알고리즘은 특성상, 기..

앞에 글에서 이진탐색트리의 삽입을 구현했었다.이진탐색트리 삽입 (1) -  http://marobiana.tistory.com/81이진탐색트리 삽입 (2) -  http://marobiana.tistory.com/82이번에는 순회에 대해 짜볼 것이다.사실 이걸 정리하고 싶었을 뿐인데, 이진탐색트리 삽입이 더 복잡해서 거기서 시간 다보냄 ㅎㅎ요번건 소스가 아주 간단함.1. 이진트리 순회 방법컴공 2학년 때 자료구조에서 배우는..

앞에 글에 이어서.. 앞 글  - http://marobiana.tistory.com/81문제 : 트리에 넣을 숫자들을 입력 받아 이진탐색트리를 만들어라.3. 예제C++로 하면 포인터 써서 눈에 보기 더 좋을 것을ㅠㅠ Java로 포인터처럼 짜봤음 ㅋㅋ아래와 같이 3개의 클래스로 구성할 수 있음.트리 삽입참고로, Tree에 넣는 숫자 순서가 트리모양을 결정한다public class Bina..

1. 이진트리, 이진탐색트리란?각 노드의 자식노드 수가 최대 2개까지만 존재하는 트리이다.글로만 쓰면 이해가 안가므로, 그림 투척!위의 트리는 맨 밑 노드(리프노드 - Leaf Node)를 제외한 모든 각 노드가 자식노드를 2개씩 갖고있는데, 이런 트리를 완전트리 라고 한다.완전트리가 아니더라도 자식노드가 2개 이하이면 이진트리이다. 아래 트리처럼!!요런 모양을 편향트리? 왼쪽 경사 트리? 변질 트리? 등으로 부른다.어쨌든..

재귀에 대한 이해도가 전혀 없다면 http://marobiana.tistory.com/79   <- 팩토리얼을 먼저 보면 이해가 쉬울 것이다.그것보다 조금 더 응용된게 피보나치.피보나치는 팩토리얼보다 조금 어렵지만, 원리를 이해하면 어렵지 않다.근데 재귀는 워낙 복잡해서 처음 접하는 사람에게는 설명하기도, 이해하기도 어렵다ㅠ_ㅠ (복잡한 재귀문제 풀다보면 아무리 이해도 높은 사람도 ..

오랜만에 재귀 문제를 풀다보니 헷갈려져서 정리한번 해보겠음.재귀 중에 가장 쉬운 팩토리얼부터..1. 재귀함수란?함수 내에서 자기 자신을(함수)를 계속적으로 콜 하면서 풀어가는 방식이다.스택(Stack)이라고 생각할 수 있다.함수가 콜 되면서 최근에 자신을 부른 원래 함수가 스택에 차곡차곡 쌓이게 됨.중요한건 처음 불려진 함수에서(스택 맨 밑에있는 메소드) return 되는 값이 최종 return 값이 된다2. 팩토..