재귀함수6 백준알고리즘_10870_재귀함수_피보나치수열 (C언어) 자바 공부하다가 머리가 아파서 잠시 머리도 식힐겸 알고리즘으로 돌아와서 C를.. 자바의 객체 개념은 정말 어렵네요. 외울 것도 많고.. 재귀함수 버전 피보나치 수열은 재귀함수 입문용인데 의외로 인터넷 보면 어마어마한 성능을 요구하는 재귀함수를 정답이라고 올려두신 분들이 많은 듯 합니다.. 기본적으로 피보나치 수열 공식이 "f(n) = f(n-1) + f(n-2)" 이라고 아래와 같이 그대로 재귀함수 코드를 짰다가는 컴퓨터한테 혼납니다. 컴퓨터 성능에 따라 다르겠지만 대략 제 컴퓨터에서는 35이상 넘어가면 연산 시간이 1초를 넘어가네요. #include int pivo(int num); int main() { int num; scanf("%d", &num); printf("%d", pivo(num + .. ▸알고리즘 문제 풀이 2019. 12. 9. 백준알고리즘_11729_재귀함수_하노이탑 이동 (C언어) 처음 풀어본 알고리즘 문제인데 이틀이 꼬박 걸렸습니다. 그런데 모범답안보니 너무 간단하네요. ㅠ 하노이탑 이동 원리를 아는 것 자체는 사실 무의미하지만 이 문제를 푸는 사고 과정 자체가 확립 되는 것이 중요할 것 같습니다. 머리 좋은 사람 참 많네요. 전 모범답안 보고도 한참 헤맸는데.. 재귀함수가 모두 그렇듯, 키 포인트는 함수 자체가 계속 부분집합으로 발생했다 없어지는 방식이라는 것입니다. 일반적인 사고 방식과 같이(저처럼..) 전체를 보면서 풀어나가면 답이 없습니다. 제가 이틀 걸려 짠 코드는 가장 아랫쪽에 남겨둡니다. 흑역사네요. 간단히 3개짜리 원판 옮기기 구조만 보면 나머지는 로직만 주고 컴퓨터에게 맡길 수 있습니다. 실제로 원판이 7개쯤 되면 손으로 그리기도 힘듭니다. 세 개짜리 원판에서 가.. ▸알고리즘 문제 풀이 2019. 12. 9. 이분탐색(재귀함수 사용법)_값 찾기 [1/1] [ 이분탐색이란? ] 정렬된 데이터에서 특정 값을 찾을 때, 하나하나 찾는것이 아니라 범위를 좁혀나가며 찾는 방법 O(logN)의 시간 복잡도가 소요되어 정렬되어 있는 데이터를 보다 빠르게 검색 가능 이미 정렬이 되어 있다는 것은 처음부터 찾아나가는 것 보다 더 효율적인 탐색 방법이 항상 존재합니다. 그 중 가장 간단한 방법인 이분 탐색을 해도 해도 항상 헷갈리는 재귀함수 사용법과 함께 정리해봅니다. 먼저 정렬된 데이터가 있습니다. size를 구하고 찾을 데이터를 입력합니다. 배열에서 범위를 지정할 때는 대부분 size를 사용하는 것이 편합니다. 예를 들어 10개가 있으면 배열의 마지막 인덱스는 9이지만 총 10개라 size는 10이 됩니다. int arr[] = { 1,2,5,7,11,15,22,38,.. ▸C언어/알고리즘 및 자료구조 2019. 12. 9. 다이나믹 알고리즘_타일 채우기 [2/2] 이번에는 타일이 늘었습니다. 이전글은 1*2 / 2*1 두 개의 타일이 있었는데 이번에는 2*2 타일로 추가해보라고 하네요. 과제는 유투브 '동빈나'님의 알고리즘 강의를 참고했습니다. 별로 달라지는 건 없는 것 같습니다. 수열의 규칙이 바꼈을 뿐.. 규칙을 달리해서 수열을 전개해보라는 걸까요. 일단 이전글처럼 일반 반복문, 재귀함수 버전으로 한 번 작성해보겠습니다. 제가 뭔가를 잘 못 생각하고 있는걸까요.. 아무리 고민해봐도 수식에서 숫자 1개 추가하고 1개 바꿔주는 것 외에는 달라지는게 안보이는데 흠.. 일단 미심쩍으므로 재귀함수 버전만 짜보고 강의를 들어보겠습니다. 굳이 값을 리턴해야하는 경우가 아니라면 재귀함수에서는 그냥 void함수로 사용하고 포인터를 써서 특정 변수들을 바꿔주는 방식이 더 편.. ▸C언어/알고리즘 및 자료구조 2019. 12. 9. 다이나믹 알고리즘_타일 채우기 [1/2] [ 다이나믹 알고리즘이란? ] 반복되는 작업 없이 알고리즘 수행 이미 한 번 계산한 경우 그 값을 어딘가에 저장해뒀다가 재활용하는 구조 의미만 보면 간단합니다. 재귀함수같이 동일 알고리즘을 arguments만 바꿔가면서 계속 수행할 때, 이전 값의 결과를 가져와서 수행할 수 있도록 만들어준다는 것이죠. 사실 뭔가 거창한 이름이지만 이제까지 해왔던 로직들과 그리 다를 건 없는 것 같습니다. 최대한 효율적으로 수행한다 정도로 이해하면 될 것 같습니다. 그럼 타일채우기 문제를 한 번 풀어보도록 하겠습니다. 과제는 유투브 '동빈나'님의 알고리즘 강의를 참고하였습니다. 그려보니 [1,2] 로 시작하는 피보나치 수열이 나옵니다. 간단한건데 한참을 고민했네요.. 오른쪽으로 한칸 늘어나면 (n -1) 경우의 수와.. ▸C언어/알고리즘 및 자료구조 2019. 12. 9. 재귀함수_팩토리얼 예제 [1/1] 저는 개인적으로 시작할 때 들었던 악명 높은 포인터도 어렵다고 느껴본적이 없는데.. 오히려 재귀함수가 제일 어려웠던 것 같습니다. 물론 원리를 알고 나니 그리 어렵지만은 않지만요. 재귀함수는 잘못하면 무한루프가 돌기 쉬우니 조심하셔야 합니다. [ 재귀함수란? ] 말 그대로 함수 안에 자기 자신의 함수가 다시 있는 것을 뜻 함 (Recursion) 특정 조건을 만족시킬때까지 함수실행-함수실행-함수실행 형태로 같은 함수 반복 수행 아래는 재귀함수에서 제일 흔한 예제인 팩토리얼 구현입니다. 5! = 5 * 4 * 3 * 2 * 1 == 120 3! = 3 * 2 * 1 == 6 아래 예제만 보면 굳이 재귀함수를 사용할 필요 없이 일반 반복문을 사용하면 충분해 보입니다만.. 같은 기능을 다른 범위나 다른 .. ▸C언어/알고리즘 및 자료구조 2019. 12. 9. 이전 1 다음 💲 추천 글 반응형
