[면접대비] 알고리즘 문제 풀이

1) 1부터 50까지 짝수만 곱해서 출력하기

-이 문제를 해결하면서 짝수인 i 값을 차례로 더할 때는 정상적으로 출력됐는데,
무심코 넣었던 int 자료형의 크기가 짝수 곱을 담을 수 없자
음수 값이 나온 뒤 0으로 바뀌는 현상 때문에 문제 풀이에 시간이 걸렸다.

오류가 난 장면

-이는 자료형의 크기 때문이였다.
-1차 시도로, int가 안되자 long을 집어넣었는데, long의 자료 크기는 19-20자로, 경 단위 까지밖에 담을 수 없다.
-이 과정에서 long의 데이터 형은 float 값 뒤에 f가 붙는 것 처럼 L이 붙는다는 것을 배웠다.
-그 후 , 구글링으로 무한대 크기의 데이터를 담을 수 있는 BigInteger를 찾았다!
-BigInteger 선언/초기화 : 문자열을 인자 값으로 넘겨주어야 한다

BigInteger big = new BigInteger("1");

-BigInteger 연산법 : BigInteger은 문자열이기에 사칙연산이 안된다. BigIntger 클래스 내부에 있는 메서드를 사용
1. big에 20을 더하는 방법
big = big.add(BigInteger.valueOf(20));
2. big에 2를 빼는 방법
big = big.subtract(BigInteger.valueOf(2));
3. big에 2를 곱하는 방법
big = big.multiply(BigInteger.valueOf(2));
4. big에 3를 나누는 방법
big = big.divide(BigInteger.valueOf(3));
5. big를 5로 나눌 때 나머지를 구하는 방법
big = big.remainder(BigInteger.valueOf(5));

실제 코딩테스트에서는 1부터 100까지 2와 3의 배수이면서, 5의 배수가 아닌 수를 모두 더하는 문제로 출제

2) 특정 정수 이하의 소수 더하기

*소수 : 1과 자기 자신만으로 나누어떨어지는 정수

에라토스테네스의 체 이용하기

1. 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다.
2. 2는 소수이므로 오른쪽에 2를 쓴다.
3. 자기 자신을 제외한 2의 배수를 모두 지운다.
4. 남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다.
5. 자기 자신을 제외한 3의 배수를 모두 지운다.
6. 남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다.
7. 자기 자신을 제외한 5의 배수를 모두 지운다.
8. 남아있는 수 가운데 7은 소수이므로 오른쪽에 7을 쓴다.
9. 자기 자신을 제외한 7의 배수를 모두 지운다.
10. 위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다.

2부터 N까지의 수 중에서 소수를 찾는다고 했을 때,
N의 제곱근(나누어 떨어지지 않는다면 보다 큰 자연수)보다 작은 소수의 배수를 모두 지우고 남는 수는 모두 소수입니다.

-숫자 100을 집어넣었을 때, 100이하의 소수는 100의 제곱근인 10보다 작은 소수(2,3,5,7)의 배수를 모두 지우고 남는 수이다.
-초기에 0과 1은 false로, 나머지는 true로 세팅해둔 뒤
-2부터 100의 제곱근(10)보다 작을 때 까지의 소수를 구한 뒤 배수를 false로 바꾼다.
-i가 2일 때 j는 자신을 제외하기 위해서 2*2=4부터 시작, 다음은 4+2인 6 , 다음은 6+2인 8

실제 코딩테스트에서는 소수를 구하는 알고리즘에서 틀린 점을 디버깅하는 문제로 출제되었다.

3) 대문자 추출하기

대문자 제거

String str = "I Live In South Korea."; str.replaceAll("[A-Z]", ""); // ive n outh orea.

소문자 제거

String str = "I Live In South Korea."; str.replaceAll("[a-z]", ""); //I L I S K.

특정 글자가 대문자인지 소문자인지 확인하는 방법은
Character.isUpperCase(글자);
이렇게 입력하면 대문자일 경우 true 그렇지 않을 경우 false가 뜨는데

-이를 이용해 문자열에서 대문자만 추출 해 출력해 봤다.

-isUpperCase, isLowerCase를 사용하여 a.charAt의 길이만한 배열을 true/false로 채워준 뒤 , true만 출력한다.
-출력결과 :

 

4) 문자열 아스키 코드 순으로 정렬하기

 

실행결과

-먼저 문자열을 toCharArray를 사용하여 배열에 담아준다. 여기서는 두 개의 for문이 사용된다.
첫 번째는 문자 배열을 반복하는 것이고, 두 번째는 비교에서 반복을 피한다.
두 번째 반복문 안에서 조건 (StringtoChar[j] <StringtoChar[j+1])이 참이면 치환을 통해 배열을 정렬

실제 문제에서는 String 형태로 된 숫자를 int 배열로 만들어 오름차순 정렬하는 문제로 출제되었다.

5) 문자열에서 숫자 제거하기

48은 아스키코드 숫자 0, 57은 아스키코드 숫자 9를 의미하므로, 문자열에서 0-9사이의 숫자만 추출 가능

6) 피보나치 수열에서 N번째 값 뽑아내기

 

7) 숫자 버블정렬 하기

 

이 때, 각 라운드를 진행 할 때마다 뒤에서부터 한 개씩 정렬되기 때문에, 라운드가 진행 될 때마다 한 번씩 줄면서 비교하게 된다.
한마디로 정리하자면 이렇다.
총 라운드는 배열 크기 - 1 번 진행되고,
각 라운드별 비교 횟수는 배열 크기 - 라운드 횟수 만큼 비교한다.

버블정렬 연습해놓길 잘함! 정렬 문제가 출제되었다.

8) STACK 구현하기

interface Stack
{
  boolean isEmpty(); 
  boolean isFull(); 
  void push(char item); 
  char pop(); 
  char peek(); 
  void clear();
} 

public class ArrayStack implements Stack 
{
  private int top; 
  private int stackSize;
  private char stackArr[];
  
  // 스택을 생성하는 생성자
  public ArrayStack(int stackSize) 
  {
    top = -1; // 스택 포인터 초기화 
    this.stackSize = stackSize; // 스택 사이즈 설정
    stackArr = new char[this.stackSize]; // 스택 배열 생성 
  } 
  
  // 스택이 비어있는 상태인지 확인
  public boolean isEmpty() 
  { 
    // 스택 포인터가 -1인 경우 데이터가 없는 상태이므로 true 아닌 경우 false를 return 
    return (top == -1); 
  } 
  
  // 스택이 가득찬 상태인지 확인
  public boolean isFull() 
  { 
    // 스택 포인터가 스택의 마지막 인덱스와 동일한 경우 true 아닌 경우 false를 return 
    return (top == this.stackSize-1); 
  } 
  
  // 스택에 데이터를 추가 
  public void push(char item) 
  {
     if(isFull()) 
    {
      System.out.println("Stack is full!"); 
    } 
    else 
    {
       stackArr[++top] = item; 
    // 다음 스택 포인터가 가리키는 인덱스에 데이터 추가 
    }
  }
  
  // 스택의 최상위(마지막) 데이터 추출 후 삭제 
  public char pop() 
  { 
    if(isEmpty()) 
    {
      System.out.println("Empty");
      return 0; 
    }
    else 
    {
      System.out.println("Deleted Item : " + stackArr[top]); 
      return stackArr[top--]; 
    } 
  } 
  
  // 스택의 최상위(마지막) 데이터 추출 
  public char peek() 
  { 
    if(isEmpty()) 
    { 
      System.out.println("Peeking fail! Stack is empty!"); 
      return 0; 
    } 
    else 
    { 
      System.out.println("Peeked Item : " + stackArr[top]);
      return stackArr[top]; 
    } 
  } 
  
  // 스택 초기화 
  public void clear() 
  {
    if(isEmpty())
    {
   	 System.out.println("Stack is already empty!"); 
    } 
    else 
    {
     top = -1; 
     // 스택 포인터 초기화 
     stackArr = new char[this.stackSize];
   	 // 새로운 스택 배열 생성
   	 System.out.println("Stack is clear!");
    } 
  } 
  
  // 스택에 저장된 모든 데이터를 출력 
  public void printStack() 
  { 
    if(isEmpty())
    { 
    	System.out.println("Empty"); 
    } 
    else 
    { 
      System.out.print("Stack elements : "); 
      for(int i=0; i<=top; i++) 
    {
    	System.out.print(stackArr[i] + " "); 
    } 
    System.out.println(); 
    }
} 


public static void main(String args[]) { 
  int stackSize = 5; 
  ArrayStack arrStack = new ArrayStack(stackSize);
  arrStack.push('A'); 
  arrStack.printStack();
  arrStack.push('B'); 
  arrStack.printStack(); 
  arrStack.push('C'); 
  arrStack.printStack(); 
  arrStack.pop(); 
  arrStack.printStack();
} 
}

9) 팩토리얼

public class Factorial {

public static void main(String[] args) {
int input = 4; // 4!

System.out.println(fact(input));
}

public static int fact(int n) {
if (n <= 1)
return n;
else
return fact(n-1) * n;
}
}
4. 원리

1) 처음 fact 메소드가 불린 것은 main 함수에서이다.
fact(4) 가 실행될 것이다.

2) fact(4)
n은 현재 4이다.
n은 1보다 크므로 else를 타고,
fact(3)이 호출된다.

3) 여기서 처음 호출된 fact(4)는 종료되지 않고 Stack에 쌓인상태로,
fact(4)가 호출한 fact(3)이 실행된다.

Stack

fact(4)

4) fact(3)
n은 현재 3이다.
n은 1보다 크므로 else를 타고,
fact(2)이 호출된다.

5) 여기서 두번째로 호출된 fact(3)은 종료되지 않은 상태로 Stack에 쌓이고,
fact(3)이 호출한 fact(2)이 실행된다.

Stack

fact(3)

fact(4)

6) fact(2)
n은 현재 2이다.
n은 1보다 크므로 else를 타고,
fact(1)이 호출된다.

7) 세번째로 호출된 fact(2)는 종료되지 않은 상태로 Stack에 쌓이고
fact(2)가 호출한 fact(1)이 실행된다.

Stack

fact(2)

fact(3)

fact(4)

8) fact(1)
n은 현재 1이다.
n이 1과 같으므로 if문을 타고, n 즉, 1을 return 한다.

9) fact(1)이 종료되면서, Stack의 가장 위에 있는 fact(2)가 실행된다.
8번에서 리턴 받은 값과 n을 곱하며 return 하고 fact(2)가 종료될 것이다.

fact(2) 에서는 n이 2이다.
8번에서 fact(1)은 1을 리턴했었다.

fact(2-1) * n 즉, 1 * 2

그래서 fact(2)에서는 1*2 한 값을 return 한다.

Stack은 이제 아래와 같은 상태가 된다.

fact(3)

fact(4)

10) 스택에 있던 fact(3)이 실행된다.
9번에서 리턴 받은 1*2 = 2 와 n을 곱하며 리턴하고 종료한다.

fact(3-1) * n 즉, 2 * 3

fact(3)은 1*2*3 한 값 6을 리턴한다.

11) 마지막으로, 처음 불리워졌었던 fact(4)가 리턴할 차례가 왔다.
10번에서 리턴받은 6과 n을 곱하고 리턴하고 종료될 것이다.

fact(4-1) * n 즉, 6 * 4 = 24

이렇게 4! 을 구했고, 리턴 받은 값은 main 함수에서 출력된다.

결론적으로 따져보면
1*2*3*4 를 하게 된 것이다.

실제 문제에서는 주어진 알고리즘을 디버깅하는 문제로 출제되었으며, return 부분에 n * fact(n--); 비슷하게 나와있어서 숫자를 감소시킨 후 재귀되어야 하기 때문에 n-1로 수정했다. 또한 if문의 구조적 문제도 수정했음!

• 실제 손코딩을 해보니, public class 부터 모든 클래스를 직접 작성하는 문제보다는 내부에 매서드를 작성하여 비워진 부분을 완성시키는 형태가 많았다.
• SQL문제는 거의 조인으로 나왔는데, 그부분이 많이 약하다는 것을 느낄 수 있었다. 조인에서 점수를 다 까먹음