Acanel Blog

[코딩테스트] 준비

코딩테스트를 위한 Java 기본 API

기본적으로 시작할 때 아래 Import하고 하자.

import java.util.*;

Stack API

Stack<Integer> stack = new Stack<>();

stack.push(item);   //최상단에 삽입
stack.pop();        //최상단 아이템 꺼내오기 (없으면 Exception)
stack.peek();       //최상단 아이템 확인(안꺼내옴. 없으면 Exception)
stack.empty();      //비어있나 확인. (pop/peek할 때 필수)
stack.search(item); //아이템 인덱스 리턴. 없으면 -1.

Queue API

Queue<Integer> queue = new LinkedList<>();     //일반 Queue
Queue<Integer> queue = new PriorityQueue<>();  //우선순위 Queue

queue.offer(item); //최상단에 삽입
queue.poll();      //최하단 아이템 꺼내오기 (없으면 null)
queue.peek();      //최하단 아이템 확인 (없으면 null)

//우선순위 큐 순위 정하기 (Custom Compartor)
Queue<String> queue = new PriorityQueue<String>((str1, str2) -> {
    return str1.length() - str2.length();
});

Map API

Map<String, Integer> map = new HashMap<>();

map.containsKey(ky);       //Key에 대한 Value가 있는지 확인
map.containsValue(value);  //Value를 가진 Key가 있는지 확인
map.get(key)               //키에 대한 값 리턴
map.put(key, value);       //키에 대한 갑 삽입 또는 기존 값 없데이트
map.keySet();              //키값 집합을 리턴 (for문에 적합)

Set API

Set<Integer> set = new HashSet<>();

set.add(item);        //집합에 item 추가
set.contains(item);   //집합에 item이 있는지 확인
set.remove(item);     //집합에서 item 제거

일반 배열 정렬 API

//오름차순 정렬
Arrays.sort(배열);
//사용자 정의 정렬 (Comparator 추가)
Arrays.sort(배열, (a, b) -> { return 정수; });

//List 객체의 정렬 (안에 Comparator 필수)
List.sort((a, b) -> { return 정수; });

ArrayList -> Array 전환 방법

//String ArrayList
ArrayList<String> arrayList = new ArrayList<>();
arrayList.add("Test1");
arrayList.add("Test2");
arrayList.add("Test3");
String[] array = arrayList.toArray(new String[arrayList.size()]);

//Integer ArrayList -> int Array
ArrayList<Integer> arrayList = new ArrayList<>();
arrayList.add(1);
arrayList.add(2);
arrayList.add(3);
int[] arrayList.stream().mapToInt(i -> i).toArray();
//

LinkedList Iterator 사용 방법 (필요 시 remove도..)

LinkedList<String> list = new LinkedList<>();

for (Iterator<String> iter = list.iterator(); iter.hasNext();) {
    String val = iter.next();
    if (condition) iter.remove();
}

Note :
일반 Iterator를 통해서 remove는 가능한데 add는 안된다.
LinkedList 등에서 Iterator을 사용해서 중간에 삽입하려면 Iterator<>가 아닌 ListIterator<>를 사용하자.
Iterator<> 는 Vector, Map, Set 등에서도 사용되는 포맷이어서 안되고 ListIterator<>만 중간 삽입이 가능하다.
ListIterator<>의 추가 메소드 :
- set(Value) : 현재 요소를 변경
- add(Value) : 현재 위치의 next Index에 새 요소 추가

List에서 조건에 따라 삭제하는 방법

list.removeIf(item -> 조건);

문자열 API
1) String -> Integer

Integer.valueOf("100");

2) Integer -> String

String.valueOf(123);

3) SubString : 문자열.substring(시작, 끝) : 시작index 부터 시작, 끝 index 직전까지 문자열

String subString = "abcdef".substring(1, 3); //"bc"

4) Split : 문자열을 분리함. 단, 인자는 regex여야 함.

String [] strArray = "1,2,3".split(","); //{"1", "2", "3"}

수식 API
1) 반올림하기 (인자 및 리턴값은 모두 Double)

double val = Math.round(9.4);   //9.0
double val = Math.round(9.6);   //10.0

2) 올림하기 (인자 및 리턴값은 모두 Double)

double val = Math.ceil(9.4);   //10.0

3) 내림하기 (인자 및 리턴값은 모두 Double)

double val = Math.floor(9.6);   //9.0

4) 절대값 구하기 (인자 및 리턴값은 모두 Double)

double val = Math.abs(-5.1);   //5.1
double val = Math.abs(5.1);    //5.1

5) 제곱근 구하기 (인자 및 리턴값은 모두 Double)

double val = Math.sqrt(36.0);   //6.0
double val = Math.sqrt(16.0);   //4.0

기타 API
1) Integer의 1 bit를 세는 API

int bitCount = Integer.bitCount(83); //83은 1010011이므로 4가 리턴된다.

2) Integer를 2, 8, 16진수 문자열로 표현하는 API

String binaryStr = Integer.toBinaryString(83);  //"1010011" 문자열로 변환된다.
String octalStr  = Integer.toOctalString(83);   //"123" 문자열로 변환된다.
String hexStr    = Integer.toHexString(83);     //"53" 문자열로 변환된다.

3) 2, 8, 16진수 문자열을 Integer로 변환하는 API

int num1 = Integer.parseInt("1010011", 2);  //83으로 변환된다.
int num2 = Integer.parseInt("123", 8);      //83으로 변환된다.
int num3 = Integer.parseInt("53", 16);      //83으로 변환된다.

4) 특정 문자열이 숫자로 이루어졌는지 확인하는 방법 (정규식과 matches 활용)

boolean isNumber1 = "123".matches("[0-9]"); //true
boolean isNumber2 = "1a3".matches("[0-9]"); //false

대표적인 문제 유형 익히기

프로그래머스 : https://programmers.co.kr/learn/challenges
백준 : https://www.acmicpc.net/problem/tags
많이 나오는 문제 카테고리 및 고민해야 할 부분을 아래에 정리하였다. 각 카테고리 별로 문제를 풀어보는 것을 추천한다.

해시

- 해시는 보통 Map, Set 자료구조로 사용한다.
- 중복 제거, 중복 카운팅, 어떤 데이터가 집합 내에 있는지 여부, 리버스 인덱싱 등을 할 때 O(1) 성능으로 결과를 리턴해 준다.
- 문제에서 어떤 배열이나 리스트에서 조건에 만족하는 요소 집합을 리턴하라고 했을 때 많이 사용되는 것으로 보인다.
- Map을 사용하는 경우 : 어떤 값을 Key로, 어떤 값을 Value로 할 것인지 고려해야 함
- Set을 사용하는 경우 : 각 Set이 어떤 데이터들을 포함해야 하는지, 각 데이터의 hashCode는 어떻게 처리할 것인지 고려해야 함

스택/큐
- 스택/큐는 당연한 이야기지만, 언제 push하고 언제 pop하는지 조건을 고려하는 것이 매우 중요하다.
- 1차원 배열에서 특정 조건에 맞는 최대 최소를 구하거나 할 때, 스택/큐를 활용해서 O(n) 성능으로 결과를 리턴하는 경우가 꽤 있다.
(Sort를 활용하면 O(nlogn)이 나와서 Timeout발생하기도 함)
- 2개의 스택이나 큐를 사용해서 푸는 경우도 있다.

힙
- 알고리즘 문제에서 힙이 사용되는 경우는 "우선순위 큐"를 사용하는 경우가 거의 대부분이다. (다른 케이스는 못 봄)
즉, 큐에 집어넣고 나서 pop할 때 특정 조건에 따라서 가장 우선순위가 높은 아이템을 꺼내서 처리해야 하는 경우에 힙을 사용한다.
- 보통 문제는 여러 조건들과 여러 데이터들을 주고, 종합적으로 우선순위를 계산해서 결과를 리턴하도록 하는 유형이다.

정렬
- 정렬은 보통 O(nlogn) 의 Time Complexity를 가지므로 사용할 때 이를 고려해서 써야 한다.
보통 데이터를 초반에 정렬하거나 결과를 마지막에 정렬할 때 쓰인다.
- 정렬하는 목적과, 정렬 후에 각 데이터의 값과 index간 상관 관계 등을 고려해야 한다.

완전탐색 (Brutal Force)
- 사실 모든 알고리즘 문제는 Brutal Force로 해결할 수 있다. 다만.. Time Complexity가 커질 수 있다.
따라서 가급적이면 최대한 마지막으로 생각해 봐야 하는 방법이다.
- 다만, 조건에 따라서 pruning되는 케이스가 많다면 시도해 보아도 되는 방법이다.

탐욕법 (Greedy)
- 주어진 데이터에 대해서, 다음에 선택할 데이터의 조건(즉, Greedy 조건)을 선정하는 것이 매우 중요한 방법이다.
- 보통 Greedy 조건이 정해지면 우선순위 큐나 정렬을 통해서 구현한다.

동적계획법 (DP)
- 점화식을 통해서 푸는 방법이므로, "이전에 계산해 둔 값"을 활용해서 다음 값을 구할 수 있는지 찾아보는 것이 중요하다.
- 점화식을 만들어 보다가, 아무리 봐도 이전에 계산해 둔 값 외에, 이후에 계산될 값을 가져와야 한다거나 그 외 요소들이 필요하다 싶으면 과감히 포기하자.

BFS/DFS (너비/깊이 우선 탐색)
- BFS는 일반적으로 큐를 통해 구현하며, DFS는 재귀를 통해 구현함.
- BFS/DFS에서 중요한 것은, 이미 탐색한 정보에 대해서 중복으로 탐색하지 않도록 처리하는 것임. (잘못하면 무한 루프에 빠질 수 있음)
- 어쩃든 BFS, DFS로 탐색 시, 완전 탐색이 되는 문제들도 있다. 따라서 그런 케이스의 경우, Brutal Force와 같이 pruning 케이스를 잘 고려해 보아야 한다.

Binary Search
- 이진탐색 하면 1차원 배열에서 탐색하는 경우를 많이 생각하지만, bit 연산이나 index 연산 시 Binary Search를 통해서 처리해야 하는 경우도 있다.
예를 들어, K번째 요소를 찾으라고 하면 수학적인 부분을 고려해서 K/2 번째 요소를 찾고, (K/2)/2 번째 요소를 찾고.. 머 이런식으로 탐색해야 하는 Index를 줄여가면서 풀어야 하는 문제도 있다는 것이다.
- 만약 정렬되어 있는 1차원 배열이 초기 입력 데이터나 중간 결과물로 주어지고, 그 안에서 뭔가 찾아야 한다면 Binary Search 문제일 가능성이 높다.

그래프
- 보통 그래프 문제는 2차원 배열로 문제가 주어지고, 특정 조건에 맞는 최단/최대 거리 등을 구하도록 나온다.
- 데익스트라/프림/크루스칼 알고리즘 등의 알고리즘 개념을 알고 있으면 보통 도움이 많이 된다.

분할 정복(Divide & Conquer)
- 1/2차원 배열의 영역을 분할해서 해결하도록 나오는 경우도 있고, 어떤 입력 값이 2n 단위로 주어진다고 하면 분할 정복으로 풀 수 있는 가능성이 높다.

재귀
- DFS를 쓸 때 재귀가 많이 사용되며, 그 외에도 Brutal Force나 DP에서도 사용할 수 있다.
- 재귀는 간단하게 구현할 수 있어서 좋은 반면, 스택 오버플로우를 고려해야 하므로 탐색 depth 제한 등을 잘 고려하는 것이 중요하다.

수학
- 수학 요소가 들어간 문제들은 유형이 너무 많고, 보통 다른 요소들과 조합되어 있어서 문제에서 필요한 수식을 잘 찾아내는 것이 중요하다.
- 최소공배수, 최대공약수, bit 연산, 팩토리얼, 소인수분해 구하기, 소수 구하기 등을 미리 알아두면 도움이 될 것 같다.

문제의 유형 파악

알고리즘 문제의 핵심이다.

머리가 매우 좋거나 문제 풀이에 많은 경험을 쌓아 통찰력을 쌓게되면 문제를 보고 어떤 방법으로 풀 것인지 짧은 시간 안에 찾을 수 있겠으나, 개인적으로는 어려웠다. ㅠㅠ 그래서 잘 안될 경우에는 역으로 아래의 방법으로 해 보는 것을 추천한다.

문제의 지문을 읽고 완전히 이해한다.
간단히 테스트 케이스를 추가해서(노트등에 적고) 알고리즘은 일단 배제하고 올바른 답에 대해서도 생각해 본다.
문제의 유형이 직관적으로 떠오르지 않는 경우,
왜인지 해결될 것 같은 유형 후보를 4~5가지 고른다.
각 유형 후보들을 하나씩 선택해서 10분 정도 투자해서 과연 이 알고리즘으로 문제를 풀려면 어떻게 풀 것인가 고민해 본다.
Note : 즉, 문제를 풀 때 문제가 어떤 유형인지를 찾는게 아니라 각 유형을 문제에 대입해서 고민해 보는 방법이다.
예) 하노이의 탑 문제가 주어졌을 때, 솔루션이 생각나지 않으면 스택/큐로 풀게되면 어떻게 해볼 것인가 고민해보고,
답이 안나오면 탐욕법으로, 그래도 안나오면 재귀로.. 짧게 짧게 여러 알고리즘들을 대입해서 고민해 보는 것이다 .

덧붙여서, 보통 문제들을 보면 정말 쉬운 문제가 아니고서는 2~3개 유형의 조합으로 해결해야 하는 경우가 대다수이다.
수학 + 큐 또는 정렬 + 탐색, 해시 + BFS 등등...
그 중에 보통 Main 솔루션이 될 만한 부분을 찾은 후 Main 솔루션을 해결할 Sub 솔루션을 추가로 찾아보는 방식이 될 것이다.

Big-O

어떤 방법으로 해결할 수 있을 것이라는 아이디어가 떠올랐을 때 다음으로 고민해보아야 하는 것은 Big-O이다.

개인적으로는 알고리즘 문제를 풀 때 메모리 사용량은 재귀함수 사용하는 경우를 제외하고는 우선순위에서 크게 고려하지 않는 편이다.
(재귀함수는 스택을 쓰기 때문에 신경을 써야 하고, 자료구조 크기가 엄청나게 크지 않는 이상 크게 신경쓸 일이 없다고 봐야 함)

다만 성능에서는 Time Complexity 때문에 반드시 고려해야 하는 사항이다.

Case 1) O(n³) 알고리즘
→ O(n³) 알고리즘이 나왔다면 다시 한 번 고민을 해보아야 한다.
만약 입력 데이터의 범위나 크기가 어느 정도 제한되어 있거나(1만 이하 수준) 내부적으로 pruning case가 많다면 시도해 볼 만 하지만,
그렇지 않다면 성능 개선을 할 수 있는지 검토해야 한다.

Case 2) O(n²) 알고리즘
→ 어려운 문제들의 경우 O(n²)으로 풀리는 경우도 은근히 있다.
입력 데이터 범위나 크기가 10만 이하 수준으로 되어 있거나, 내부적으로 pruning case가 많다면 시도해 볼 만 하다.
하지만 Time Out 이 발생하는 경우도 있다. Time Out이 발생하면 다느 방법으로 검토하는 것을 추천한다.

Case 3) O(nlogn), O(n) 알고리즘 이하
→ 보통 이 정도 수준으로 줄이게 되면 Time Out은 거의 발생하지 않는다고 봐야 한다.
따라서 Time Out은 크게 신경쓸 필요가 없고, 알고리즘이 정말 맞는지 + 정확하게 동작하는지 집중하면 된다.

테스트 케이스

보통 알고리즘 문제를 풀고 나서 일부 테스트케이스 통과 후 제출하면 여러 개 중 2~3개 케이스에서 Fail 발생하거나 Timeout 발생하는 경우가 있다.

이런 경우를 잘 찾아내기 위해서는, 테스트케이스를 잘 찾아보는 것이 중요하다.

입력 범위 Case 찾기
→ 보통 입력 값 또는 개수의 범위가 주어지는 경우가 많다.
그럴 때 해당 범위의 양 끝에 해당하는 테스트 케이스를 작성하면 도움이 된다.

복잡한 Case 찾기
→ 이 부분에서 Fail 발생하는 경우가 많다. 복잡하게 꼬아서 테스트케이스를 만들어내야 한다.
문제 출제자의 입장에서 생각해 보면 도움이 많이 되고, 기존 테스트 케이스를 뒤집어 본다던지, 순서를 바꾼다던지, 중복 데이터를 넣는다던지 해봐야 한다.
참고로, 문제에서 입력 조건 범위를 넘어서는 Edge Case 등은 굳이 할 필요는 없다.