본문 바로가기

취업과 기본기 튼튼

 (76)
재귀적으로 문제 해결하기 (1) 재귀적으로 문제 해결하기(1) 재귀적으로 문제 해결하기.재귀적으로 문제를 푼다는 것은 무엇일까? 가장 대표적인 예인 피보나치 문제를 떠올려보자.피보나치 수열f(n+2) = f(n) + f(n+1) 를 만족하는 수열을 피보나치 수열이라고 한다. 수로 표현하면1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ... 과 같다.n을 입력받아 n번째 피보나치 수를 구하여라.이 문제를 아래와 같이 푼다면 재귀적으로 푼 것이다.long long fibo(int n){ if ( n == 1 || n == 2 ) return 1; else return fibo(n - 1) + fibo(n - 2); }쉽게말해, 함수 내에서 호출된 함수를 또 호출하는 것이 재귀이다.탈출조건이 있어야 한다.( 여기에선 n == ..
큐 구현하기 만약에, 면접장에서 큐를 구현해보라는 말을 들으면 어떻게 해야할까? 이런 기본적인 자료구조를 바로 짜보라는 질문에 대비하여, 지금 다시 한번 복습해보자. 1. 배열로 구현하기 기본 자료구조를 먼저 정의해보자. 배열을 이용하여 queue의 사이즈를 정하여 선언한다. head, tail 그리고 queue의 현재사이즈를 담는 선언한다. #define QUEUE_CAPACITY 8 int queue[QUEUE_CAPACITY]; int head = 0; int tail = -1; int queue_size = 0; 이제 큐에 원소를 삽입, 삭제하는 함수를 짜보자. void enqueue(int n){ if ( queue_size == QUEUE_CAPACITY ){ printf("queue is full! \n..
연결리스트 구현하기 자료구조를 공부해본 사람은 누구나 연결리스트가 뭔지 알 것이다. 이를 복습차, 코드로 다시 구현해보자.1. 노드 정의먼저 연결리스트의 각 노드의 구조체를 정의해보자. 이는 교과서 처럼 다음과 같다.struct _node{ int key; struct _node *next; } note_t; typedef struct _node node_t;여기서는 int 라고 했는데, int 가 아니여도 좋다. 저 구조체 안에 추가적으로 넣고 싶은 변수를 더 넣어도 된다.next 라는 포인터를 통해 다음 노드와 연결된다.2. 노드 삽입연결리스트에 노드를 삽입한다는 것은 일반적으로 리스트 끝 노드에 노드를 추가하는 것이다.연결리스트는 또한 일반적으로 리스트 앞부분을 가리키는 포인터인 head와 끝을 가리키는 포인터인 ta..
팩토리얼 계산하기 1 * 2 * .. * n 과 같은 꼴을 팩토리얼이라 하고, 기호로 n! 이라고 한다. 예를 들면, 1 * 2 * 3 = 3! 이다. 일반적으로 팩토리얼을 구하는 방법은 다음 두 가지 방법이 있다. 1. 반복문으로 구하기 int factorial(int n){ int r, i; r = 1; for (i = 2 ; i

티스토리툴바