코딩테스트 학습법 및 빈출유형 문제풀이

코딩테스트 학습법

1. 수학공부하듯이 공식을 이해와 암기를 병행해야한다.

2. 유형을 암기해야한다

코딩테스트 풀이법

0. 문제를 완전히 이해한 후에 풀이를 시작할 것

1. 주어진 예시를 귀납적으로 접근해서 일반화할 것

2. 풀이의 시간복잡도를 따져볼것

3. 손코드딩이 완료된 후에 실제로 코드를 작성에 들어갈 것

 

코딩테스트 제출전

1. 제출전 로그를 남겨서 코드의 흐름을 확인할 것

2. 주어진 케이스 외에도 엣지 케이스를 3개정도 만들어서 생각해볼것

 

문제접근방식

 

1. 연역적 탐구방식 : 수학적 논리관계를 통해서 답을 도출해낼 수 있을때

2. case by case 분석 : 어떤 solution으로 도달할 수 있는 방법들을 MECE하게 나열하고, 하나씩 고려해서 불가능하면 소거하는 방식

3. 시행착오법(trial and error) : 하나씩 test case를 대입해서 패턴을 찾고 일반화하는 방법

4. divide and conquer : 부분의 패턴을 확인하고 이를 전체로 확장해나가 전체 문제를 푸는 방법

 

백준인수받기

 

String input = "2\n" +
        "6 2 5 3\n" +
        "5 2 7 3 8 9\n" +
        "15 3 10 3\n" +
        "4 15 8 16 6 6 17 3 10 11 18 7 14 7 15";

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int t = sc.nextInt(); // 2

        for (int i = 0; i < t; i++) {
            // 예제처럼 이어서 숫자들을 계속 읽기
            int a = sc.nextInt();
            int b = sc.nextInt();
            int c = sc.nextInt();
            int d = sc.nextInt();
            // ...
        }
    }
}

 

 

문제접근스킬

String 조작

• String -> CharArray -> StringBuilder
  • String의 특정문자를  조회하고 싶을때는 chararray로 변환하여 For문으로 순회한다.
    • char[] charArray = str.toCharArray();
  • String을 특정 문자를 기준으로 나누고 싶을는 Split을 사용한다.
    • String[] words = input.replaceAll("[.!?]", " ").split("\\s+");
  • String의 특정문자를 수정하고 싶을때는 StringBuilder을 사용한다.
    • String 문자를 역순으로 정렬하고 싶을때 
      • new StringBuilder(word).reverse().toString();
    • String의 특정문자를 바꾸고 싶을때 
      • StringBuilder sb = new StringBuilder(str); sb.setCharAt(i, 'W');
  • String을 다른 타입의 데이터(int)로 나누고 싶을때는 Integer.parseInt()를 사용한다.
    • int number = Integer.parseInt(string)

Character 조작

• ASCII 값을 구하고 싶을 때 ; 바로 Int로 변환 -  char은 parseint가 불가하므로 ASC code를 활용하여 int로 변환해야한다 
  • int asciiValue = (int) ch;
• '1'과 같은 숫자를 ASCII 값이 아니라 표면적입 값을 구하고 싶을때 ; String으로 변환후에 partInt 필요
  
  • Integer.parseInt(String.valueOf(numChar))
• d

 

숫자 자리수 조작

• 문자열 변환 (String.valueOf())
• 나눗셈 (while 반복문)
  • 자리수 확인을 위해서는 10으로 나누기를 반복해서 cnt한다.
  •  숫자의 자릿수 분리를 위해서는 %와 /연산을 활용한다

 

대수론 개념활용

• 소수 구하기
  • 에라토스테네스의 체 사용
• 최대공약수 구하기
  • 유클리드 호제법 활용;  public static int gcd(int a, int b) { if (b == 0) return a; return gcd(b, a % b); }
•   피보나치구하기

 

ArrayList <-> Array 변환하기

• ArrayList -> Array 
  • String[] array = list.stream().toArray(String[]::new);
•  Array  -> ArrayList 
  • 원시타입을 boxed : Arrays.stream(array).boxed().collect(Collectors.toList()).
  • 원시타입 그대로 list생성 :  collect.stream().mapToInt(Integer::intValue).toArray();

 

정렬 :  Java의 Sorting method

• JavaMethod
  
  • List.sort(Comparator<? super T> c)
  • Arrays.sort(T[] a, Comparator<? super T> c)

Comparator< ? super T>  

• Comparator은 객체만을 대상으로 사용할 수 있기때문에 원시타입을 wrapperclass로 바꾸어 주어야하여 list로 변환한다.
• 오름차순, 내림차순 정렬 :  List.sort(list,Comparator.naturalOrder() / Comparator.reverseOrder())
• 사용자정의 정렬
  
  • 정렬의 대상(object)와 정렬의 기준(compartor interface)이 필요하다.   
  • Comparator : 인터페이스(추상클래스)로써  compare 메서드를 구현하여 두 객체(obj1, obj2)를 비교할 수 있다.
  • compare(obj1, obj2)의 반환값: 0 → 두 객체가 같음, -1 → obj1이 obj2보다 작음, 1 → obj1이 obj2보다 큼

•  

List<Map.Entry<Integer, Integer>> list = new ArrayList<>(map.entrySet());

list.sort(new Comparator<Map.Entry<Integer, Integer>>() {
    @Override
    public int compare(Map.Entry<Integer, Integer> o1, Map.Entry<Integer, Integer> o2) {
        if (o1.getValue() > o2.getValue()) {
            return -1;
        } else if (o1.getValue() == o2.getValue()) {
            if (o1.getKey() <= o2.getKey()) {
                return -1;
            } else {
                return 1;
            }
        } else {
            return 1;
        }
    }
});

 

 

자료구조

큐

• 사용처 : 입력 순서대로 데이터 처리가 필요할 때 사용 
• Java 메소드
  
  • Queue<Integer> Q = new LinkedList<>();
  • 1) offer(item): item 하나를 큐의 뒷 부분에 추가한다.
  • 2) poll(): 큐에 가장 앞에 있는 항목을 제거하고 반환한다.
  • 3) empty(): 스택이 비어 있을 때에 true를 반환한다.
  • 4) contains(item) : Stack에 객체(item)이 있으면 true를 반환한다
• 유형정리
  • 조세퍼스 문제 : 원형으로 모여있때, N번째 순번인 것을 계속 제외함

스택

• 사용처 : 데이터가 입력된 순서의 역순으로 처리되어야 할 때 사용 
• Java 메서드
  • Stack<Integer> stack = new Stack<>();
  • 1) push(item): item 하나를 스택의 가장 윗 부분에 추가한다.
  • 2) pop(): 스택에서 가장 위에 있는 항목을 제거한다.
  • 3) peek(): 스택의 가장 위에 있는 항목을 반환한다.
  • 4) empty(): 스택이 비어 있을 때에 true를 반환한다.
  • 5) contains(item) : Stack에 객체(item)이 있으면 true를 반환한다

• 문제유형정리
  • 특정 조합의 인접한 것들이 서로 만나서 사라진다고 할때 , 짝이 있는 경우
  • 괄호가 있는 경우

• 적용검토 : 배열에서 다른 자료구조로 잠시 옮겨담아서 순서대로 제거하는 경우 Stack을 사용.
  • 사용이유 1. 시간복잡도 상 배열의 중간에서 제거할 수는 없고 tail에서 탐색하여 제거해야 하는 경우
    • 이유1. tail에서 제거해야하는 경우는 방금 삽입한 데이터를 제거할때
    • 이유2 tail에서 제거해야하는 경우는 인접한 데이터를 연속으로 제거할 때 유의미하다.

public static String deleteString(String s) {
    Stack<Character> stack = new Stack<>();
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        if (stack.isEmpty()) {
            stack.push(c);
            continue;
        }
        if (stack.peek() == c) {
            stack.pop();
        } else {
            stack.push(c);
        }
    }

    StringBuilder sb = new StringBuilder();
    while (!stack.isEmpty()) {
        sb.append(stack.pop());
        sb.reverse();
    }

    return sb.toString();
}

 

 

해쉬테이블

• 사용처 : 특정한 value의 개수를 셀때 사용함

 

boolean containsKey(Object key)	HashMap에 저장된 키(key)가 존재하는지 알려준다. (존재하면 true)
boolean containsValue(Object value)	HashMap에 저장된 값(Value)이 존재하는지 알려준다. (존재하면 true)
Object get(Object key)	지정된 키(key의 값(객체)을 반환, 못찾으면 null 반환
Object getOrDefault(Object key, Object defaultValue)	지정된 키(key)의 값(객체)을 반환한다. 키를 못찾으면, 기본 값(defaultValue)로 지정된 객체를 반환
boolean isEmpty()	HashMap이 비어있는지 알려준다.
Set keySet()	HashMap에 저장된 모든 키가 저장된 Set을 반환
Object put(Object key, Object value)	지정된 키와 값을 HashMap에 저장
Object remove(Object key)	HashMap에 지정된 키로 저장된 값(객체)를 제거

• for문 순회 : 해쉬를 순회할때는 keyset 혹은 values라는 set구조를 순회할 수 있다. 두가지 모두 순회하고 싶다면 entrySet이라는  튜플에서 getvalue or getkey로 구체적인 값을 순회할 수 있다.
  • for (Map.Entry<Character, Integer> entrymap : map.entrySet())
  • for (char key : sH.keySet())

    HashMap<Character, Integer> sH = new HashMap<>();
    String s = "statistics";
    for (char x : s.toCharArray()) {
        sH.put(x, sH.getOrDefault(x, 0) + 1);
    }
    for (char key : sH.keySet()) {
        System.out.println(key + " " + sH.get(key));
    }
}

• 유형정리
  • 빈도수 세기 
  • 두개의 값을 쌍으로 묶기 : 올바른 괄호2

 

 

이진탐색

코드작성

• 정렬된 상태의 데이터에서 특정 값을 빠르게 탐색하는 방법
  1. 왼쪽 bound를 lt, 오른쪽 bound를 rt 데이터 중앙값을 mid로 하고, 찾고자 하는 target값과  mid 값을 비교
  2. target값이 mid 값보다 더 작으면 오른쪽을 날리고 (rt=mid-1) 데이터 왼쪽 부분에서 이진 탐색
  3. target값이 mid 값보다 더 크면  왼쪽을 날리고 (lt=mid+1)데이터 오른쪽 부분에서 이진 탐색
  4. target값과 mid 값이 일치하면 이를 반환함.
  5. 이를 반복하게되면 최종적으로 lt=rt가 되는 한점으로 수렴하게 됨 {while (lt<=rt)이면 lt=rt}

public static int binarySearch(int[] arr, int target) {
    int left = 0;
    int right = arr.length - 1;

    while (left <= right) {
        int mid = (left + right) / 2;

        if (arr[mid] == target) {
            return mid;  // Element found
        } else if (arr[mid] < target) {
            left = mid + 1;  // Search right half
        } else {
            right = mid - 1;  // Search left half
        }
    }

    return -1;  // Element not found
}

 

응용(Bound Search)

• 이진탐색의 변형으로, target이 범위 내에 존재하지만 f(x) 출력값이 target값과 일치할 수 없는 경우
• Lower Bound Search : target 값보다 작거나 가장 근접한 값을 반환.
  
• Upper Bound Search :  target 값보다 크지만 가장 근접한 값을 반환.

응용(Bound Search) 코드작성

1. 왼쪽 bound를 lt, 오른쪽 bound를 rt 데이터 중앙값을 mid로 하고, 찾고자 하는 target값과  mid 값을 비교
2. target값이 mid 값보다 더 작으면 오른쪽을 날리고 (rt=mid-1) 데이터 왼쪽 부분에서 이진 탐색
   • LowerBoundSearch면 res = mid라고 임시저장하는 과정을 추가한다
3. target값이 mid 값보다 더 크면  왼쪽을 날리고 (lt=mid+1)데이터 오른쪽 부분에서 이진 탐색
   • UpperBoundSearch이면 res = mid라고 임시저장하는 과정을 추가한다
4. target값과 mid 값이 일치하면 이를 반환함.
   • bound search이므로 해당 케이스는 존재하지 않음
5. 이를 반복하게되면 최종적으로 lt=rt가 되는 한점으로 수렴하게 됨 {while (lt<=rt)이면 lt=rt}

public static int binarySearch_LowerBound(int[] arr, int target) {
    int left = 0;
    int right = arr.length - 1;
    int res = -1;  // Initialize to -1 to indicate "not found"

    while (left <= right) {
        int mid = left + (right - left) / 2;  // Avoid overflow

        if (arr[mid] < target) {
            left = mid + 1;  // Move to the right half
        } else {
            // Potential lower bound is mid, but continue searching left
            res = mid;
            right = mid - 1;
        }
    }

    return res;  // Returns the index of the first element >= target, or -1 if not found
}

 

코드에 대한 고찰과 검증

 

1. 어째서 left<= right 조건인가? 이진탐색이 완료되는 시점을 생각해보면 총 두가지 경우를 생각할 수 있다.

• 첫번째, 범위가 완전히 다 좁혀지기전에 mid = target이 일치하여 while문을 빠져나가는 경우.
• 두번째, 범위가 충분히 좁혀서저 lt와 rt가 한칸차이로 인접할때까지 mid = traget이 일치하지 않은 경우.
  • lt와 rt가 한칸차이로 인접하는 경우에는 Mid 값은 lt 혹은 rt 중 하나로 수렴하게 된다.
  • 이 경우에도 mid = target이 일치하지 않으면 다음번 루프에 의해서 lt와 rt는 같아지며, 자연적으로 mid값도 같아지게 된다.
  • 이경우에도 mid=target이 일치하지 않으면 범위 내에서 target값이 존재하지 않음으로 판별되고 -1 혹은 임시저장 값인 res 값이 반환된다. 

때문에 left<= right 조건은 left = right = mid 인 시점까지는 유지되며 left가 right +1이 되거나 right가 Left -1 이 되기 전까지는 유지되기 위한 조건이 유지된다.

 

2. boundSearch에서는 어째서 조건이 이항인가?

• boundSearch는 우선 하나의 값을 찾는 것이 아니라 하나의 값에 근접하는  근사치를 찾는 것이다. 즉, 'arr[mid]=target'을 만족하는 mid 값이 단 하나 존재하지 않을 수 있다는 것이다. 그래서 즉시 mid를 반환하는 것이 아니라 arr[mid-1]=target인지 지속 탐색이 필요하기 때문이다. 

 

유형정리

• Array가 주어지고 index를 대입해서 target값의 index를 찾는 경우
• Array가 주어지고 index를 대입해서 target값의 근사치를 찾는 경우 (bound search)
• bound가 주어지고 함수와 타겟값이 주어지면 인수를 대입해서 타겟 값과 일치하는 인수 혹은 근사치를 찾는 경우(결정알고리즘)

 

이진탐색 적용검토의 근거

• 정렬된 상태인 경우 한번쯤은 의심해봐야한다.
• 어떤 문제에서 답이 확실히 주어진 범위 내에 있겟다는 확신이 든다면
• 하나씩 대입해서 정답과 근사한 값을 찾아내는 부정방정식 형태의 문제가 주어질때
• 함수의 출력값 f(x)이 입력값x과 일관된 양의 상관관계이거나 음의 상관관계를 유지할 경우