블로그

[재귀] 재귀 vs 꼬리 재귀 재귀와 꼬리 재귀의 차이 함수를 호출하면 함수가 호출된 위치를 가리키는 주소 값이 저장되어야 한다. 함수가 재귀적으로 호출될 경우 함수 안에서 함수가 계속해서 호출되고 차례로 리턴된다. 그래서 호출 횟수가 많아지면 돌아갈 곳의 주소 값을 저장하고 있는 스택이 넘치거나 프로그램의 실행 속도가 느려지는 단점이 있다. 위의 문제는 함수가 호출된 위치를 기억하기 때문에 발생한다. 일반 재귀 함수의 경우 리턴되는 함수 값을 받아 연산을 하고 다시 그 값을 리턴하는 방식을 취한다. 그렇다면 함수가 호출된 위치로 돌아갔을 때 실행할 작업이 없다면 어떨까? 함수 호출 위치를 기억할 필요도 없고 스택이 넘치는 경우도 발생하지 않게 되지 않을까?꼬리 재귀로 구현하게 되면 위 문제가 해결된다...

[탐색 알고리즘] 순차 탐색 알고리즘 vs 이진 탐색 알고리즘 알고리즘 비교알고리즘의 시간 복잡도만 비교하게 되면, 순차 탐색 알고리즘은 $O(n)$이고 이진 탐색 알고리즘은 $O(logn)$이므로 이진 탐색 알고리즘이 훨씬 좋아 보인다. 하지만 이진 탐색 알고리즘은 데이터가 정렬되어 있어야 한다는 전제 조건이 있다. 보통 정렬 알고리즘의 경우 $O(nlogn)$의 시간 복잡도를 가진다. 어떤 알고리즘이 좋다고 분명하게 말할 수는 없다. 상황에 맞춰서 적합한 알고리즘을 선택해야 한다.아래 코드는 배열의 길이가 500, 5000, 50000일 때, 각 알고리즘의 최대 연산횟수를 나타낸 것이다.(Worst Case)$O(n)$과 $O(logn)$의 차이가 어느정도인지 알 수 있을 것이다. Code123456..

[탐색 알고리즘] 이진 탐색 알고리즘(Binary Search) 이진 탐색 알고리즘 이진 탐색 알고리즘을 위해서는 데이터가 정렬되어 있어야 한다. 이진 탐색 알고리즘은 정렬된 데이터가 아니면 적용이 불가능하다. 배열 { 1, 2, 3, 7, 9, 12, 21, 23, 27 }에서 3을 찾는 경우 알고리즘 진행 방식은 아래와 같다. 첫번째 시도배열 시작 인덱스와 마지막 인덱스 값을 합하여 2로 나눈다. 그 인덱스에 해당하는 값이 3인지 확인한다. 두번째 시도arr[4]의 값 9와 찾는 값 3의 대소를 비교한다.3이 9보다 작으므로 인덱스 4~8은 탐색의 범위에서 제외한다.(정렬된 데이터여서 가능)0과 3을 더하고 2로 나눈다.(나머지는 버린다.)결과가 1이므로 arr[1]의 값 2와 찾는 값 3이 일치하는..

[탐색 알고리즘] 순차 탐색 알고리즘(Linear Search) 순차 탐색 알고리즘 맨앞에서 부터 맨끝까지 순서대로 탐색을 진행하는 알고리즘. 시간 복잡도 O(n)을 가진다.(Worst Case) 종료 조건배열의 길이 내에서 숫자 발견시 종료. 탐색 실패시 배열의 길이만큼 탐색 후 종료된다. Code1234567891011121314151617181920212223242526272829303132#include // 순차 탐색 알고리즘 함수// 찾는 숫자가 있으면 찾는 숫자의 인덱스 리턴// 없으면 -1 리턴int LSearch(int ar[], int len, int target){ int i = 0; for (; i

[컴퓨터 알고리즘 성능분석] 시간 복잡도 vs 공간 복잡도 시간 복잡도와 공간 복잡도 알고리즘 트레이닝 사이트에서 문제를 풀다보면 아래 그림과 같이 시간 복잡도와 공간 복잡도가 조건으로 주어진다.알고리즘을 평가하는데 있어 수행시간과 메모리 사용량을 평가기준으로 두는데 수행시간에 해당하는 것이 시간 복잡도, 메모리 사용량에 해당하는 것이 공간 복잡도이다.정의는 아래와 같다.- 시간 복잡도(Time Complexity) : 알고리즘의 수행시간 분석결과- 공간 복잡도(Space Complexity) : 알고리즘의 메모리 사용량에 대한 분석결과 간단하게 말하면 알고리즘 성능평가는 시간 복잡도와 공간 복잡도를 계산하고 점근적 표기법으로 나타내면 된다.(점근적 표기법 포스팅 : http://ledgku.tistor..

[컴퓨터 알고리즘 성능분석] 점근적 표기법 (Asymptotic Notation) 점근적 분석주어진 문제를 푸는 알고리즘은 딱 하나만 있는 것이 아니라 여러 개가 존재한다.하드웨어, 운영체제, 프로그래밍 언어 등 특징에 따라서 최적화된 여러가지 알고리즘이 존재한다.어떤 문제를 해결하는 데에는 항상 다수 개의 알고리즘이 존재할 수 있으므로 알고리즘의 성능을 비교할 필요가 있다. 점근적 분석의 필요성어떠한 문제 해결을 위한 알고리즘의 성능분석을 할 때, 주어지는 데이터의 형태나 실험을 수행하는 환경, 또는 실험에 사용한 시스템의 성능등 다양한 요소에 의해 공평한 결과가 나오기 힘들고 비교 결과가 항상 일정하지 않을 수 있다. 이를 효과적으로 해결하는 방법이 점근적 분석법이다. 점근적 분석법은 각 알고리즘이 ..

[컴퓨터 알고리즘의 정의] 컴퓨터 알고리즘의 정의와 표현 컴퓨터 알고리즘이란? 컴퓨터를 이용하여 문제를 풀기위한 방법을 과정이나 절차를 이용해 만들어 놓은 것. 컴퓨터가 이해할 수 있는 언어(C, Java...)를 이용해 실행할 내용을 컴퓨터가 할 수 있는 가장 작은 기본 작업의 형태로 만들고 순차적으로 나열한다. 컴퓨터는 지시 사항을 차례대로 하나씩 수행하면서 최종 결과를 얻게 되고 그 결과는 해결하고자 했던 문제의 해답이 된다. 컴퓨터 알고리즘의 정의와 표현컴퓨터 알고리즘을 정의하고 표현하기 위해서는 크게 4가지 단계를 거친다. - 문제 정의 (Problem Definition) : 해결하고자 하는 문제. 입력과 출력의 형태로 정의될 수 있어야 하고 컴퓨터가 수행할 수 있는 형태로 전환이 가능해야한다..