손코딩 면접 준비

재귀를 이용한 피보나치
메모이제이션을 이용한 피보나치
재귀를 이용한 팩토리얼 문제 
10회 1~10까지 랜덤한 숫자를 출력하여 중복된 숫자가 있을 경우 true, false를 반환

1000보다 작은 숫자 중 3과 5의 배수의 총합을 구하는 프로그램

주어진 정수배열에서 0을 가장 왼쪽으로 배치하는 함수 (추가 메모리공간 X, in-place)

배열을 오름차순으로 정렬해서 리턴하는 함수

임의의 string이 주어질 때 reverse

큐로 스택 구현하기

스택으로 큐 구현하기

최대 공약수와 최소 공배수를 구하는 알고리즘

n개의 배열에서 k(k<=n) 번째로 큰수를 찾는 효과적인 방법

 

재귀를 이용한 피보나치

int fibo(int n) {
   if(n == 0)
      return 0;
   else if(n == 1)
      return 1;
   else
      return fibo(n - 1) + fibo(n - 2);
}

n이 int형이기 때문에 n<40인 피보나치까지 구할 수 있던 것으로 기억한다.

 

메모이제이션을 이용한 피보나치

int fibo(int n) {
   if(n == 0)
      return 0;
   else if(n == 1)
      return 1;
   else if(fibo[n] != 0)
      return fibo[n];
   else
      return fibo[n] = fibo(n - 1) + fibo(n - 2);
}

 

재귀를 이용한 팩토리얼 문제 

int factorial(int n) {
   if(n == 1)
      return 1;
   else
      return n * factorial(n - 1);
}

 

10회 1~10까지 랜덤한 숫자를 출력하여 중복된 숫자가 있을 경우 true, false를 반환

int randomQuiz() {
   for(int i = 0; i<10; i++)
   {
      int n = rand() % 10 + 1;
      cout << n << endl;
      if(!Quiz[n]) {
            cout << "false" << endl;
            Quiz[n] = true;
      }
      else
            cout << "true" << endl;
   }
}

 

1000보다 작은 숫자 중 3과 5의 배수의 총합을 구하는 프로그램

int sum() {
   int res = 0;
   for(int i = 1; i<1000; i++)
   {
      if(i % 3 == 0 || i % 5 == 0)
         res += i;
   }
   return res;
}

 

정렬

주어진 정수배열에서 0을 가장 왼쪽으로 배치하는 함수 (추가 메모리공간 X, in-place)

배열을 오름차순으로 정렬해서 리턴하는 함수

 

제자리 정렬 중 어느 것이던 오름차순으로 구현 (삽입, 버블, 퀵, 선택 정렬)

 

버블정렬

void bubbleSort(int n, int *arr) {
   for(int i = 0; i < n; i++)
      for(int j = i + 1; j < n; j++)
         if(arr[i] > arr[j])
         {
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
         }
}

 

임의의 string이 주어질 때 reverse

void stringReverse(int length, string str) {
   for(int i = 0; i < length / 2; i++)
   {
      char temp = str[i];
      str[i] = str[length - 1 - i];
      str[length - 1 - i] = temp;
    }
}

 

큐로 스택 구현하기

class Stack
{
    queue <int> a, b;
    void push (int n)
    {
         if(a.empty())
             a.push(n);
         
         else {
             while(!a.empty())
             {
                  b.push(a.front());
                  a.pop();
             }
             a.push(n);
             while(!b.empty())
             {
                  a.push(b.front());
                  b.pop();
             }
         }
    }

   int pop()
   {
         int front = a.front();
         a.pop();
         return front;
    }
}

 

스택으로 큐 구현하기

class Queue
{
    stack <int> a, b;
    void push (int n)
    {
         a.push(n);
    }

   int pop()
   {
         if(b.empty())
             while(!a.empty())
             {
                  b.push(a.top());
                  a.pop();
             }
         int top = b.top();
         b.pop();
         return top;
    }
}

 

최대 공약수와 최소 공배수를 구하는 알고리즘

int gcd(int a, int b)
{
   if(b == 0) return a;
   return gcd(b, a % b);
}

int lcm(int a, int b)
{
   return a * b / gcd(a, b);
}

 

n개의 배열에서 k(k<=n) 번째로 큰수를 찾는 효과적인 방법

hochulshin.com/algorithm-find-kth-item/