Do it! 알고리즘 코딩 테스트 - 자바 편

01-1 시간 복잡도 표기법 알아보기

 

02-2 디버깅 활용 사례 살펴보기

코딩 테스트에서 실수하기 쉬운 4가지 오류

1. 변수 초기화 오류

2. 반복문에서 인덱스 범위 지정 오류 찾아보기

3. 잘못된 변수 사용 오류 찾아보기

4. 자료형 범위 오류 찾아보기

int형의 범위: -2147483648 ~ 2147483647

long형의 범위: -9223372036854775808 ~ 9223372036854775807

👉 자료형은 처음부터 long형으로 선언!

 

 

03-1 배열과 리스트

배열

• 인덱스를 사용하여 값에 바로 접근 가능
• 값을 삽입하거나 삭제하려면 해당 인덱스 주변에 있는 값을 이동시키는 과정 필요
• 배열의 크기는 선언할 때 지정할 수 있으며, 한 번 선언하면 크기를 늘리거나 줄일 수 없음
• 구조가 간단하므로 코딩 테스트에서 많이 사용

리스트

• 인덱스가 없으므로 값에 접근하려면 Head포인터부터 순서대로 접근해야 함 => 접근 속도 느림
• 포인터로 연결되어 있으므로 데이터를 삽입하거나 삭제하는 연산 속도가 빠름
• 크기가 정해져 있지 않으며, 크기가 변하기 쉬운 데이터를 다룰 때 적절
• 포인터를 저장할 공간이 필요하므로 배열보다 구조가 복잡함

 

03-2 구간 합

 

합 배열

• 기존의 배열을 전처리한 배열
• 기존 배열의 일정 범위의 합을 구하는 시간 복잡도가 O(N)에서 O(1)로 감소함
• 합 배열 S 만드는 공식 : S[i] = S[i - 1] + A[i]

 

구간 합

• 합 배열을 이용하여 시간 복잡도를 더 줄이기 위해 사용하는 특수한 목적의 알고리즘
• 합 배열만 미리 구해 두면 구간 합은 한 번의 계산으로 구할 수 있음
• S[j] - S[i - 1]  //i에서 j까지 구간 합

 

백준 11660 번 같이 표(2차원 배열)에서 (x1, y1) ~ (x2, y2) 구간 합을 구하는 방법

: (0, 0) 부터 구간 합 표 만들기

1	2	3	4
2	3	4	5
3	4	5	6
4	5	6	7

1	3	6	10
3	8	15	24
6	11	18	27
10	15	22	31

첫 번째 표는 아래의 표와 같이 구간 합을 만들 수 있다. ( D[2][2] = D[1][2] + D[2][1] - D[1][1] + A[2][2] )

(x1, y1)부터 (x2, y2) 까지의 구간 합: D[x2][y2] - D[x1-1][y2] - D[x2][y1-1] + D[x1-1][y1-1]

 

 

 백준 10986 번과 같은 문제 팁

💡 나머지 합 문제 풀이의 핵심 아이디어

• (A + B) % C 은 ((A % C) + (B % C)) % C와 같다. 다시 말해 특정 구간 수들의 나머지 연산을 더해 나머지 연산을 한 값과 이 구간 합의 나머지 연산을 한 값은 동일하다.
• 구간 합 배열을 이용한 식 S[i] - S[j] 는 원본 배열의 j + 1 부터 i까지의 구간 합이다.
• ⭐ S[i] % M의 값과 S[j] % M의 값이 같다면 (S[i] - S[j]) % M은 0이다. 즉, 구간 합 배열의 원소를 M으로 나눈 나머지로 업데이트하고 S[i]와 S[j]가 같은 (i, j)쌍을 찾으면 원본 배열에서 j + 1부터 i까지의 구간 합이 M으로 나누어 떨어진다는 것을 알 수 있다.

 

03-3 투 포인터

• 2개의 포인터로 알고리즘의 시간 복잡도를 최적화하는 것
• 2018번: 수들의 합 5 (acmicpc.net)

제한시간은 2초인데 N의 최댓값이 10,000,000으로 매우 크다.

이런 상황에서는 O(nlogn)의 시간 복잡도 알고리즘을 사용하면 제한 시간을 초과하므로 O(n)의 시간 복잡도 알고리즘을 사용해야 한다!

 

이런 경우 자주 사용하는 방법이 바로 투 포인터

 

↓start_index
1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
↑end_index

초기화: sum = 1, count = 1

 

* count 를 1으로 초기화하는 이유는 N이 15일때 숫자 15만 뽑는 경우의 수를 미리 넣고 초기화했기 때문

 

start_index가 오른쪽으로 한 칸 이동하는 것의 의미: 연속된 자연수에서 왼쪽 값을 삭제하는 것

end_index가 왼쪽으로 한 칸 이동하는 것의 의미: 연속된 자연수의 범위를 한 칸 더 확장하는 것

같을 때는 경우의 수를 1 증가시키고, end_index를 오른쪽으로 이동시킴

 

💡 투 포인터 이동 원칙 ⭐

• sum > N : sum = sum - start_index; start_index++;
• sum < N : end_index++; sum = sum + end_index;
• sum == N: end_index++; sum = sum + end_index; count++;

 

 

• 1940번: 주몽 (acmicpc.net)

두 재료의 합, 즉, 크기를 비교하므로 값을 정렬하면 문제를 좀 더 쉽게 풀 수 있음

   > 일반적으로 정렬 알고리즘의 시간 복잡도는 O(nlogn)

 

계획: N개의 재룟값을 정렬한 다음 양쪽 끝의 위치를 투 포인터로 지정해 문제에 접근

 

이 문제도 정렬을 하면 위의 문제와 매우 유사하게 풀이됨!!

↓start_index
1	2	3	4	5	7
				↑end_index

 

위의 투 포인터 원칙 이용!

 

🔥🔥🔥 이거는 두 수의 합이기 때문에 포인터가 양쪽 끝에 있고 A[i] + A[j] == M일때, i++; j--;를 해서 두 포인터를 다 움직일 수 있다!!

그리고, i와 j의 크기가 역전될 때까지 반복하면 됨!!

 

 

• 1253번: 좋다 (acmicpc.net)

- 예외 사항을 파악하는게 중요

    * 음수인 경우

    * 0 0 0 => 3

    * 0 0 1 => 0

등 ...

 

 

03 - 4 슬라이딩 윈도우

 

* 2개의 포인터로 범위를 지정한 다음 범위를 유지한 채로 이동하여 문제를 해결

 

• 12891번: DNA 비밀번호 (acmicpc.net)

1) S 배열과 비밀번호 체크 배열을 저장

2) 윈도우에 포함된 문자로 현재 상태 배열을 만든다. 그런 다음 현재 상태 배열과 비밀번호 체크 배열을 비교하여 유효 비밀번호인지 판단한다.

    * A개수, C개수, G개수, T개수 배열 만들기 -> 비교하기

3) 윈도우를 한 칸씩 이동하며 현재 상태 배열을 업데이트한다.

3-1) 현재 상태 배열을 업데이트 한 이후에는 비밀번호 체크 배열과 비교하며 비밀번호 유효성을 판단한다.

3-2) 현재 상태 배열을 업데이트 할 때는 빠지는 문자열, 신규 문자열만 보고 업데이트하는 방식으로 진행

 

• 11003번: 최솟값 찾기 (acmicpc.net)

- 문제 분석하기

1. 일정 범위 안에서 최솟값을 구하는 문제이므로 슬라이딩 윈도우와 정렬을 사용하면 될 듯
2. 윈도우의 크기: i-L+1 ~ i => L로 생각!
3. 최솟값을 찾기 위한 정렬: 일반적으로 정렬은 nlog(n)의 시간 복잡도를 가지므로 N과 L의 최대 범위가 5,000,000인 해당 문제에서는 정렬을 사용할 수 없음
4. 슬라이딩 윈도우를 덱으로 구현하여 정렬 효과를 볼 수 있음

덱 구조

 

* Deque 사용

* 내부에 클래스 선언

 

* 인덱스의 범위를 벗어난 친구는 1차이로 벗어난 인덱스일 것. => 뒤에 있는 노드의 인덱스는 해당 인덱스보다 당연히 크기 때문에, 그 다음 친구를 버퍼라이터에 넣으면 됨.

public class B11003 {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //출력을 버퍼에 넣고 한 번에 출력하기 위해 BufferedWriter 사용
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());  //데이터 개수
        int L = Integer.parseInt(st.nextToken());  //최솟값을 구하는 범위
        st = new StringTokenizer(br.readLine());

        Deque<Node> mydeque = new LinkedList<>();
        for (int i = 0; i < N; i++) {
            int now = Integer.parseInt(st.nextToken());
            //새로운 값이 들어올 때마다 정렬 대신 현재 수보다 큰 값을 덱에서 제거해 시간 복잡도를 줄임

            while (!mydeque.isEmpty() && mydeque.getLast().value > now) {
                mydeque.removeLast();
            }
            mydeque.addLast(new Node(now, i));
            //범위에서 벗어난 값은 덱에서 제거
            if (mydeque.getFirst().index <= i - L) {
                mydeque.removeFirst();
            }
            bw.write(mydeque.getFirst().value + " ");
        }
        bw.flush();
        bw.close();
    }

    static class Node {
        public int value;
        public int index;

        Node(int value, int index) {
            this.value = value;
            this.index = index;
        }
    }
}

 

 

 

03-5 스택과 큐

• 스택
  • 삽입과 삭제 연산이 후입선출로 이뤄지는 자료구조
  • 후입선출: 삽입과 삭제가 한 쪽에서만 일어나는 특징이 있음
  • Last in First Out : 나중에 들어온게 먼저 나감
  • 용어
    • push: top 위치에 새로운 데이터를 삽입하는 연산
    • pop: top 위치에 현재 있는 데이터를 삭제하고 확인하는 연산
    • peek: top 위치에 현재 있는 데이터를 단순 확인하는 연산
  • 깊이 우선 탐색 (DFS: Depth First Search), 백트래킹 종류의 코딩 테스트에 효과적임!!
• 큐
  • 삽입과 삭제 연산이 선입 선출로 이루어지는 자료구조
  • 선입선출: 먼저 들어온 데이터가 먼저 나감
  • First In First Out
  • 삽입과 삭제가 양방향에서 이루어짐
  • 용어
    • rear: 큐에서 가장 끝 데이터를 가리키는 영역
    • front: 큐에서 가장 앞의 데이터를 가리키는 영역
    • add: rear 부분에 새로운 데이터를 삽입하는 연산
    • poll: front 부분에 있는 데이터를 삭제하고 확인하는 연산이다.
    • peek: 큐의 맨 앞(front)에 있는 데이터를 확인할 때 사용하는 연산이다.
  • 너비 우선 탐색(BFS: Breadth First Search)에서 자주 사용함
  • 우선순위 큐
    • priority queue
    • 값이 들어간 순서와 상관 없이 우선순위가 높은 데이터가 먼저 나오는 자료구조
    • 큐 설정에 따라 front에 항상 최댓값 또는 최솟값이 위치한다.
    • 일반적으로 힙(heap)을 이용해 구현하는데, 힙은 트리 종류 중 하나

 

• 1874번: 스택 수열 (acmicpc.net)