공부 순서

자바 문법 > 자료구조 > 알고리즘 > 문제 풀이

문자열, 컬렉션 공부 포함

단계별 공부 방법

[ 1단계 ] 비전공자 혹은 자료구조/알고리즘을 공부한 적이 없습니다. (백준 🥉브론즈)

[ 2단계 ] 자료구조/알고리즘을 학습해 봤고, 기초 문제는 풀 수 있습니다. (백준 🥈실버4 ~ 🥈실버2)

[ 3단계 ] 자료구조/알고리즘에 대한 이해도가 있고, 중급 문제를 풀 수 있습니다. (백준 🥈실버1~🥇골드4)

[4단계 ] 대부분의 문제를 풀 수 있지만, 고난도 문제에서 막힙니다. (백준 🥇골드3 ~ 🥇골드1)

[1~2단계] 공부 방법

이 단계에서는 많은 문제를 풀기보다는 각 유형별 개념을 정확하게 익혀야합니다.

유형별 대표 문제를 반복적으로 풀어보면서 본인만의 템플릿을 만들어놓고 필수 자료구조와 알고리즘을 체득시켜야합니다.

오답노트를 작성해보면서 문제 접근 사고방식을 훈련해야 합니다.

알고리즘은 논리적인 사고방식만 가지고 있으면 쉽게 풀 수 있습니다.

알고리즘은 IQ테스트가 아닙니다. 전략적이고 반복적인 훈련으로 문제풀이 접근 사고방식을 충분히 훈련할 수 있습니다.

[2~4단계] 공부 방법

이 단계에서는 부족한 지식을 메꾸면서 다양한 유형을 풀어보아야합니다.

대표 유형 풀이법을 기본으로 다양한 문제를 풀어보면서 실전 감각을 익히는게 중요합니다.

1. 코딩 테스트 풀이 과정

1) 문제 이해 = 로직을 파악하면 알고리즘을 좁힐 수 있음
2) 입력값(=N)에 따라 시간복잡도를 고려 (모수의 범위 확인)
3) 가장 적합한 알고리즘과 그에 맞는 시간 복잡도를 찾기
4) 시도한 알고리즘이 안되면 다른 후보의 알고리즘을 적용하거나 여러 알고리즘을 같이 적용해본다.

ex) 그래프가 나오면 후보에 DFS/그리디/백트래킹/브루트포스/최단경로 등이 좁혀질 것. 시간복잡도를 보며 브루트포스는 안되겟다, 배열을 다 만들기 힘드니까 하나씩 왓다갓다하는 BFS는 힘들겟다..)

2. 시간 복잡도

알고리즘이 실행될 때 필요한 ‘입력 값’과 ‘연산 수행 시간’에 따라 ‘효율적인 알고리즘’을 나타내는 척도를 의미합니다.

• 시간 복잡도 : 입력되는 n의 크기에 따라 실행되는 조작의 수
• 공간 복잡도 : 알고리즘이 실행될 때 사용하는 메모리 양

2.1. 빅오(Big-O) 표기법

알고리즘의 입력 크기에 대해 수행 시간이 어떤 방식으로 증가하는지를 표기하는 것으로 최악의 경우의 시간 복잡도를 의미합니다.

2.2. 빅오(Big-O) 복잡성 차트

빅오 표기법을 이용하여 알고리즘의 시간 복잡도를 분석하면, 입력 크기가 커질 때 어떤 알고리즘이 더 효율적인지 비교할 수 있습니다.

표기법	이름	시간 복잡도	설명	예시
O(1)	상수	상수 시간	입력 크기와 상관없이 일정한 실행 시간을 가집니다.	배열에서 원소 하나 찾기, Map에서 특정 Key값에 대한 Value 찾기
O(logn)	로그	로그 시간	입력 크기가 증가함에 따라 실행 시간이 로그함수의 형태로 증가합니다.	이진 탐색 알고리즘
O(n)	선형	선형 시간	입력 크기와 비례하는 실행 시간을 가집니다.	선형 탐색 알고리즘, 1차 for문
O(nlogn)	로그 선형	선형 로그 시간	입력 크기가 증가함에 따라 실행 시간이 로그함수와 선형 함수의 곱의 형태로 증가합니다.	병합 정렬, 힙 정렬 알고리즘
O(n^2)	이차	이차 시간	입력 크기의 제곱에 비례하는 실행 시간을 가집니다.	선택 정렬, 버블 정렬, 퀵 정렬 알고리즘, 2차 for문
O(2^n)	지수	지수 시간	입력 크기의 지수에 비례하는 실행 시간을 가집니다.	부분집합
O(n!)	계승	팩토리얼 시간	입력 크기의 팩토리얼에 비례하는 실행 시간을 가집니다.	외판원 문제

컴퓨터는 1초당 1억 번의 계산을 할 수 있다. 아래의 표는 1초당 허용할 수 있는 가용범위를 시간복잡도 별로 나타낸다.

시간 복잡도	N의 가용 범위
O(logn)	10억
O(n)	1,000~2,000만
O(nlogn)	100만
O(n^2)	3,000~5,000
O(n^3)	200~300
O(2^n)	20~25
O(n!)	10

3. 자료 구조란 ?

💡 자료 구조

자료 구조는 효율적인 접근 및 수정을 가능하게 하는 자료의 조직, 관리, 저장을 의미합니다.

더 정확히 말해, 데이터 값의 모임, 또 데이터 간의 관계, 그리고 데이터에 적용할 수 있는 함수나 명령을 의미합니다.

자료 구조는 데이터 값의 모임, 또 데이터 간의 관계, 그리고 데이터에 적용할 수 있는 함수나 명령을 의미합니다.

어떤 자료 구조를 선택하느냐에 따라 효율적인 알고리즘 사용이 가능합니다.

3.1. 자료구조의 필요성

• 개발적 관점
  • 효율적인 데이터 관리: 데이터의 효율적인 저장과 검색을 가능하게 하여 처리 시간을 줄이고 성능을 향상시킵니다.
  • 데이터 조직: 데이터를 논리적으로 구성하여 이해하고 접근하기 쉽게 만듭니다.
  • 재사용성: 일반적인 데이터 구조는 여러 응용 프로그램에서 재사용할 수 있어 개발 시간과 노력을 절약합니다.
  • 알고리즘 최적화: 적절한 데이터 구조의 선택은 데이터를 처리하는 알고리즘의 효율성에 상당한 영향을 미칠 수 있습니다.
• 취업 준비생의 관점
  • 알고리즘 풀이에 많이 사용됩니다. 입력 받은 데이터를 어느 형태로 처리할지 고민하게 되는데, 이 때 자료 구조를 알고 있다면 고민이 빨리 해소되겠죠?

3.2. 자료 구조의 종류

- 배열 (Array)

• 배열은 동일한 자료형의 원소들을 연속적인 메모리 공간에 저장하는 자료 구조입니다.

• 배열의 크기는 고정되어 있으며, 선언 시에 크기를 지정해야 합니다.

• 예제 코드

           int[] age; // 배열 선언
           age = new int[5]; // 메모리 할당 == 크기 지정
  
           int[] age = new int[5]; 
  
           // 배열 초기화
           age[0] = 12;
           age[1] = 4;
           age[2] = 5;
           age[3] = 2;
           age[4] = 5;
  
           int[] age = {12, 4, 5, 2, 5};
           
           int number = age[0]; // number = 12
           
           age[1] = 7
           
           System.out.println(number[1]); // 7

- 리스트 (ArrayList)

• 배열과 ArrayList는 인덱스로 원소를 관리한다는 점은 동일하지만, ArrayList는 크기를 동적으로 지정할 수 있습니다.

• 원시 타입(primitive type)이 아닌 Wrapper Class 만 사용 가능합니다.

• 예제 코드

         int, long, double, float, char
         Integer, Long, Double, Float, String, Character
         
         ArrayList<Integer> integerList = new ArrayList<>(); // Integer 리스트 생성
         
         ArrayList<String> stringList = new ArrayList<>(); // String 리스트 생성
         
         integerList.add(1);
         integerList.add(3);
         integerList.add(2);
         integerList.add(4);
         integerList.add(4);
         
         integerList.size(); 5
         
         int element = integerList.get(3); // ?
         
         integerList.remove(integer.size()-1);	// 삭제
        

  	int[] arr = {1, 2, 4, 5, 3};
     
     System.out.println(arr.length);
     
     Arrays.sort(arr);  // 정렬 [1, 2, 3, 4, 5]
     
     System.out.println(Arrays.toString(arr));
     
     // Arrays.sort(arr, Collections.reverseOrder());  // 에러 : 프리미티브 타입은 내림차순 안됨 래퍼타입 배열만 가능
     
     Integer[] arr2 = {1, 2, 4, 5, 3};
     
     Arrays.sort(arr2, Collections.reverseOrder()); // 정렬 [5, 4, 3, 2, 1]
  
  
  	ArrayList<Integer> list = new ArrayList<>(Arrays.asList(1,2,4,5,3));
     
     System.out.println(list.size());   // 5
     
     System.out.println(list.isEmpty());   // false
     
     Collections.sort(list);  // 정렬 [1, 2, 3, 4, 5]
     
     System.out.println(list);   // 출력 [1, 2, 3, 4, 5]
     
     Collections.sort(list, Collections.reverseOrder());  // 정렬 [5, 4, 3, 2, 1]
     
     System.out.println(list);   // 출력 [5, 4, 3, 2, 1]
  

- 세트 (HashSet)

• 중복된 원소를 저장할 수 없습니다.
• 원소들의 순서가 존재하지 않습니다.
• 예제 코드

        
         HashSet<Integer> numberSet = new HashSet<>(); // Integer Set 생성
         
         numberSet.add(2);
         numberSet.add(4);
         numberSet.add(6);
         numberSet.add(2);
         
         numberSet.size() // ?

- 맵 (HashMap)

• HashMap은 데이터를 저장할 때 키(Key)와 밸류(Value)가 짝을 이루어 저장됩니다.
• HashMap의 키(Key) 값은 중복될 수 없고, 밸류(Value) 값은 중복이 가능합니다.
• 원소들의 순서가 존재하지 않습니다.
• 예제 코드
  

        // Key: String, Value: Integer 타입 HashMap 생성
        HashMap<String, Integer> languageMap = new HashMap<>();
        
        languageMap.put("Java", 8);
        languageMap.put("JavaScript", 1);
        languageMap.put("Python", 3);
        
        languageMap.get("JavaScript") // ?

- 스택(Stack)

• 마지막으로 입력한 값이 제일 먼저 출력되는 자료 구조입니다.
• 이것을 LIFO(Last In First Out), 또는 반대로 FILO(First In Last Out)이라고 부릅니다.
• 데이터를 입력하는 push와 데이터를 출력하는 pop 기능이 있습니다.
• 예제 코드
  

        
        Stack<Integer> stacks = new Stack<>(); // Integer Stack 생성
        
        Stack<String> animals = new Stack<>(); // String Stack 생성
        
        Stack<String> animals = new Stack<>();
        
        animals.push("Dog");
        animals.push("Horse");
        animals.push("Cat");
        
        animals.peek(); // Cat
        animals.size(); // 3
        
        animals.pop(); // Cat
        animals.size(); // 2
        
        animal.isFull(); // false
        
        animal.isEmpty(); // false

- 큐(Queue)

출처 - https://www.geeksforgeeks.org/introduction-to-queue-data-structure-and-algorithm-tutorials/)

제일 먼저 입력한 값이 가장 먼저 출력되는 자료 구조입니다.
FIFO(First In First Out)이라고 부릅니다.

데이터를 입력하는 enqueue<인큐>와 데이터를 출력하는 dequeue<디큐> 기능이 있습니다.

• 예제 코드
  

        Queue<String> languages = new LinkedList<>();
        
        // 원소 추가
        languages.add("Python");
        languages.add("Java");
        languages.add("C");
        System.out.println("LinkedList: " + languages); // [ Python, Java, C ]
        
        // 첫번째 원소 출력
        String str1 = languages.peek(); // ?
        
        // 첫번째 원소 출력 및 삭제
        String str2 = languages.poll(); // ?
        System.out.println("LinkedList after poll(): " + languages); // ?
        
        // 원소 추가
        boolean result = languages.offer("Swift");
        System.out.println("LinkedList after offer(): " + languages); // ?
        
        add() : 큐가 꽉 찬 경우 IllegalStateException 에러 발생
        offer() : 큐가 꽉 찬 경우 false 반환

✏️ 코딩테스트 문제 유형 정리

코딩테스트에는 시간 제한(효율성)이 존재하기 때문에 시간복잡도가 매우 중요하다.
만약 문제에서 주어진 N이 10,000 이라면 O(N^3) 풀이 방법으로는 시간 초과가 날 것이다. (대부분의 테스트 환경에서)

반대로 생각하면, 이것은 문제의 힌트와 같다! 시간복잡도를 고려하여 제한 시간내 성공 가능한 알고리즘이 문제의 정답이기 때문이다.
따라서 자료구조, 알고리즘의 시간복잡도는 반드시 알아야 한다.

✨ 해시 테이블

key-value 쌍으로 저장되는 특성에 따라 자주 사용된다.
유형이라기보다는 자주 사용되는 자료구조 정도가 맞는 것 같다.

예) 2020 KAKAO BLIND RECRUITMENT - 주차 요금 계산

차량 번호를 key로, 입차 시간을 value로 저장한 뒤 출차할 때 해시 테이블에서 꺼내 계산

✨ 스택 & 큐

많이 사용되긴 하지만 단독으로 사용되는 경우보다 구현하는데 필요한 자료구조 정도로 사용되는 경우가 많다. 예) 스택 : DFS, 큐 : BFS
문제에서 선입선출, 후입선출의 단서가 보이면 사용하자!

예) 프로그래머스 - 다리를 지나는 트럭

다리는 먼저 들어간 차량이 먼저 나옴 -> 선입선출 -> 큐
반목문을 돌면서 다리가 버티는 무게를 계산하여 큐에 넣어주고 다 건넜으면 빼줌

✨ 힙

우선순위를 고려하는 문제에서 사용된다. 예) 작은 수부터, 큰 수부터
보통 Java의 경우 PriorityQueue로 사용한다. (그렇다고 힙 == PQ는 아님)
PriorityQueue의 경우 개선된 다익스트라의 구현에 사용된다.

예) 프로그래머스 - 더 맵게

스코빌 지수가 K이상이 될 때까지 반복문을 돌며 우선순위 큐에서 2개를 빼고 섞은 뒤 다시 넣음

✨ 구현

주어진 문제를 알고리즘을 통하여 코드로 바꾸는 것이다.
머리로 구상한 과정을 코드로 옮기는 능력이 중요하다.
주로 어렵지는 않지만, 복잡한 구현이 나올 때가 많다.
문제를 많이 풀어보는 것이 실력 향상에 도움이 되는 것 같다.

2020 KAKAO BLIND RECRUITMENT - 기둥과 보 설치 문제를 풀이해보길 추천한다.

✨브루트 포스(완전탐색)

코딩테스트 필수 of 필수일 만큼 자주 출제되는 유형으로 완탐이라고 줄여 부르기도 한다.
DFS, BFS, 백트래킹(완탐은 아니긴 하다)을 공부하자.
이름 그대로 모든 경우를 탐색해야 할 경우에 사용된다. (미로찾기 등)
무작정 모든 경우를 탐색하면 효율이 낮으므로, 시간 제한에서 실패하면 다른 풀이를 생각해보거나 문제 조건에 따라 탐색을 최소한으로 만들어야 한다.

예) 2020 KAKAO BLIND RECRUITMENT - 양궁대회

라이언이 쏠 수 있는 모든 경우의 수를 구하기 위해 DFS 사용하면 시간 초과가 뜸
어피치가 쏜 과녁 횟수의 + 1 이상이어야 라이언이 득점하므로 이 조건을 DFS에 추가하면 성공

✨ 다이나믹 프로그래밍

복잡한 문제를 한 번에 해결하는 것이 아닌, 조금씩 점차적으로 풀이하는 유형이다. (점화식을 떠올리면 이해하기 쉬움)
개인적으로 어려운 유형이라고 생각한다.
다른 유형도 그렇겠지만, 특히 DP는 여러 문제를 풀어보면서 감을 익혀보자.
bottom-up, top-down 을 모두 공부하자. (필자는 bottom-up 접근이 편하다고 생각)
한 문제를 bottom-up, top-down 두 방법으로 각각 풀이해보는 것도 좋다.

예) 프로그래머스 - 정수 삼각형

산보다 나무를 본다는 마음으로 가장 작은 삼각형 부터 시작
가장 위부터 0번째 인덱스라고 하면 1번째 인덱스의 solution은 10, 15
마찬가지로 2번째 인덱스의 solution은 18, 16, 15
그 다음으로 3번째 인덱스는... 반복하다보면 점화식이 보임

✨ 그리디

부분적인 최적해가 전체적인 최적해가 되는 문제에서 사용한다.
어렵게 출제되면 풀이를 쉽게 떠올리기 힘드니, 문제를 많이 풀어보면서 풀이 방법을 기억하자.
정렬, 우선순위 큐를 활용하는 경우가 많다.

예) 프로그래머스 - 큰 수 만들기

숫자가 증가할 때 까지 제거하다 숫자가 내려가면 가장 큰 수 keep 을 k 개 제거할 때 까지 반복

✨ 이분 탐색

순차적인 배열 탐색으로는 시간 초과가 나는 문제에서 사용한다.
시간 복잡도 : O(logN)로 그냥 순회하는 O(N)보다 빠르다.
이분 탐색 + 다익스트라 등 다른 유형과 연계되는 문제가 출제될 수 있다.

예) 2019 카카오 개발자 겨울 인턴십 - 징검다리 건너기

건널 수 있는 친구의 수를 1부터 최대 200000까지 구하면 비 효율적
따라서 1~ 200000 중앙 값부터 모두 건널 수 있는지 이분 탐색 시작
건널 수 없으면 중앙 값에서 좌측 절반, 건널 수 있으면 중앙 값에서 우측 절반 이동

✨ 트리

트리의 경우 DFS를 활용한 전/중/후위 순회, 루트노드, 서브트리, 높이, 너비, 그래프에서 트리의 수 찾기 등 다양하게 출제할 수 있다.
따라서 트리를 활용한 다양한 문제의 유형을 풀어보는 것이 좋다.

바킹독 트리 문제집의 문제들을 풀어보는 것을 추천한다.

✨ 그래프

최단 경로를 구하는 문제가 많이 출제된다.
최단 경로를 구할 때는 다익스트라, 벨만-포드, BFS, 플로이드-워셜 알고리즘들을 사용하자.
그래프 순회에는 DFS / BFS를 사용하자.
추가로 학습하면 좋은 알고리즘으로는 위상정렬이 있다.

예) 2021 KAKAO BLIND RECRUITMENT - 합승 택시 요금

문제가 너무 길어서 사진만...
S에서 함께 출발하거나 따로 택시 타서 A, B에 각각 내리면 됨
즉, 어떤 정점(자신 포함)으로 까지의 최단 거리 + 해당 정점에서 A 최단 거리 + 해당 정점에서 B 최단 거리 3가지를 합친 것의 최소를 구하면 됨

✨ 투 포인터, 슬라이딩 윈도우

배열에서 인덱스 2개를 사용해야 할때 평범하게 for 문 2번으로 풀이하면 시간 초과가 발생하는 경우 생각해볼 수 있다.
인덱스 2개를 while 문 한번으로 사용하면서 문제를 해결할 수 있다.
구간 합도 공부하자.

예) 백준 - 2230번 수 고르기
투 포인터를 사용해서 두 수의 차이가 주어진 값보다 작으면 포인터 이동
주어진 값보다 크거나 같으면 최소 값 갱신

✨ 유니온 파인드

최근 자주 기출되는 유형이다.
노드를 집합에 속하게 하는 Union 연산과 노드의 루트 노드를 찾는 Find 연산으로 이루어진다.
노드들을 루트 노드를 기준으로 하는 어떠한 집합으로 묶는다고 생각하면 이해하기 편하다.

예) 백준 - 1717번 집합의 표현
입력 값이 0인 경우 Union, 1일 경우 Find하여 루트 노드를 확인

✨ 최소 신장 트리

최소 신장 트리를 만드는데 필요한 비용을 구하는 유형이다.
자주 기출되지는 않지만, 사용되는 알고리즘이 어렵지 않으니 익혀두자.
크루스칼, 프림 알고리즘을 공부하자.

예) 백준 - 1368 물대기
우물을 하나의 노드라고 생각하고 MST 만드는 비용을 계산

✨ 비트마스킹

문제에서 0, 1로 표현할 수 있는 경우 비트마스크를 사용하여 효율적으로 풀이할 수 있다.
비트마스크를 사용하면 수행시간, 메모리에서 이점을 가진다.
비트 연산자를 사용하므로 AND, OR, XOR, NOT, Shift 를 공부하자.

예) 백준 - 11723 집합
비트를 해당 값의 유무(있으면 1, 없으면 0)로 사용하여 풀이
집합에 x를 추가하거나 있으면 무시하기 위해선 bitmask |= 0b1 << x