[Java] 코딩 테스트에서 잘 쓰이는 java 자료구조와 알고리즘

자주 쓰이는 자료구조

배열

import java.util.*;

public class ListExample {
    public static void main(String[] args) {
		// int형 배열
        int[] intArray = new int[100]; // 크기가 100인 int형 배열 생성 (초기값 0)
        int[] intArrayInit = {1, 2, 3, 4, 5};	// 생성과 함께 값을 할당한 배열

        // 요소 접근 (인덱스 사용)
        System.out.println(intArray[0)); 	// 출력: 0
        System.out.println(intArrayInit[0)); // 출력: 1

		// 문자열 배열
        String[] stringArray = new String[100];	// 크기가 100인 문자열 배열
        
        // 논리형 배열
        boolean[] boolArray = new boolean[100];	// 크기가 100인 논리형 배열(초기 값 false)
        
		// ArrayList 생성
        List<Integer> list = new ArrayList<>();

        // 요소 추가
        list.add(10);
        list.add(20);
        list.add(30);

        // 요소 접근 (인덱스 사용)
        System.out.println(list.get(0)); // 출력: 10

        // 크기 확인
        System.out.println(list.size()); // 출력: 3

        // 요소 삭제
        list.remove(1); // 인덱스 1의 요소 (20) 삭제
        System.out.println(list); // 출력: [10, 30]
    }
}

배열의 경우, 정수형(int or long 타입), 문자형(String 타입), 논리형(boolean 타입)의 배열을 주로 사용한다.

값을 계속 삽입, 제거하는 경우 ArrayList를 사용하기도 한다.

하지만 최대 크기가 정해진 배열 안에서 조작을 한다면, 성능적으로 ArrayList보다 int, String, boolean 타입의 배열을 생성해서 사용하는 것이 좋다.

배열 - ArrayList  배열

import java.util.ArrayList;
import java.util.List;

public class ArrayListArrayExample {

    public static void main(String[] args) {

        // 1. ArrayList<Integer>를 담을 수 있는 크기 5짜리 배열 선언 및 생성
        ArrayList<Integer>[] arrayOfLists = new ArrayList[5];
        // 또는 List<Integer>[] arrayOfLists = new List[5]; (List 인터페이스로 선언하는게 더 유연)

        // 2. 배열의 각 칸에 실제 ArrayList 객체를 생성해서 넣어주기
        for (int i = 0; i < arrayOfLists.length; i++) {
            arrayOfLists[i] = new ArrayList<>();
        }

        // 3. 각 ArrayList에 데이터 추가하기
        arrayOfLists[0].add(1);
        arrayOfLists[0].add(2);

        arrayOfLists[1].add(11);

        arrayOfLists[2].add(100);
        arrayOfLists[2].add(200);
        arrayOfLists[2].add(300);

        // 4. 데이터 확인
        for (int i = 0; i < arrayOfLists.length; i++) {
            System.out.println("arrayOfLists[" + i + "]의 내용: " + arrayOfLists[i]);
        }

        // 5. 특정 요소 접근
        System.out.println("\narrayOfLists[2]의 첫 번째 요소: " + arrayOfLists[2].get(0));
    }
}

리스트 배열

import java.util.ArrayList;
import java.util.List;

public class NestedArrayListExample {

    public static void main(String[] args) {

        // ArrayList<ArrayList<Integer>> 선언 및 생성
        ArrayList<ArrayList<Integer>> listOfLists = new ArrayList<>();
        // 또는 List<List<Integer>> listOfLists = new ArrayList<>();

        // 안쪽 ArrayList (행) 추가 및 데이터 삽입
        ArrayList<Integer> row1 = new ArrayList<>();
        row1.add(1);
        row1.add(2);
        listOfLists.add(row1); // 첫 번째 행 추가

        ArrayList<Integer> row2 = new ArrayList<>();
        row2.add(10);
        row2.add(20);
        row2.add(30);
        listOfLists.add(row2); // 두 번째 행 추가

        // 세 번째 행은 만들면서 바로 데이터 추가
        listOfLists.add(new ArrayList<>()); // 세 번째 행 추가
        listOfLists.get(2).add(100);
        listOfLists.get(2).add(200);


        // 내용 출력
        System.out.println("전체 리스트 내용:");
        for (int i = 0; i < listOfLists.size(); i++) {
            System.out.println("  행 " + i + ": " + listOfLists.get(i));
        }

        // 특정 요소 접근
        System.out.println("\n두 번째 행 (인덱스 1)의 세 번째 요소 (인덱스 2): " + listOfLists.get(1).get(2)); // 출력: 30

        // 새로운 행 추가
        listOfLists.add(new ArrayList<>()); // 네 번째 행 추가
        listOfLists.get(3).add(999);

        System.out.println("\n네 번째 행 추가 후 전체 리스트 내용:");
        for (int i = 0; i < listOfLists.size(); i++) {
            System.out.println("  행 " + i + ": " + listOfLists.get(i));
        }
    }
}

리스트 타입을 가지는 리스트

 

Set

Set 자료구조는 중복 값을 제거해서 값들을 저장할 때 유용

import java.util.HashSet;
import java.util.Set;

public class SetExample {
    public static void main(String[] args) {
        // HashSet 생성
        Set<String> set = new HashSet<>();

        // 요소 추가 (중복은 하나만 저장됨)
        set.add("Java");
        set.add("Python");
        set.add("Java"); // 중복
        set.add("C++");

        System.out.println(set); // 출력: [Java, C++, Python] (순서 보장 안됨)

        // 요소 존재 확인
        System.out.println(set.contains("Python")); // 출력: true

        // 요소 삭제
        set.remove("C++");
        System.out.println(set); // 출력: [Java, Python] (순서 보장 안됨)
    }
}

 

Stack

import java.util.*;

class Main {
    public static void main(String[] args) {
        Stack<Integer> s = new Stack<>();
        s.push(1);
        s.push(2);
        s.push(3);
		
        // stack이 비어있지 않다면, 계속해서 pop
        while (!s.empty()) {
            System.out.println("stack pop " + s.pop());    
        }
    }
}

Stack은 First in Last out으로 마지막에 들어간 값(push)이 처음으로 출력된다.(pop)

stack의 경우, 값이 비어있을 때, pop을 시도하면 EmptyStackException이 발생한다.

때문에 사용 시, try-cath로 묶어서 사용하거나 pop 이전에 empty() 함수로 사전 체크해서 오류를 방지해줘야 한다.

Queue

import java.util.*;

class Main {
    public static void main(String[] args) {
        Queue<Integer> q = new LinkedList<>();

        q.offer(1); // 1추가
        q.offer(2); // 2추가
        q.offer(3); // 3추가

        // 큐가 비어있지 않다면 계속 출력
        while(q.peek() != null) {
            System.out.println("다음 값은 " + q.peek());
            q.poll(); // 가장 앞의 값을 리턴 
        }

        System.out.println("마지막 " + q.poll());	// 출력: 마지막은 null
    }
}

Queue 자료구조는 First in First out으로 처음 들어온 값을 처음 출력하는 자료구조이다.

Queue 자료구조는 인터페이스로 존재하며, 인스턴스 생성은 LinkedList로 생성하면 된다.

 

offer(value): value 값을 추가한다.

peek(): 큐의 가장 앞의 값을 확인한다(출력 X). 비어 있다면 null을 출력한다. 비슷하게 isEmpty() 함수로 확인 가능하다.

poll(): 큐의 가장 앞의 값을 출력한다(가장 먼저 들어온 값). 값이 비어 있다면, null을 출력한다.

 

Deque

import java.util.ArrayDeque;
import java.util.Deque;

public class Main {
    public static void main(String[] args) {
        // Deque 생성 (Queue처럼 사용)
        Deque<Integer> queue = new ArrayDeque<>();
        queue.offerLast(1); // 뒤에 추가 (enqueue)
        queue.offerLast(2);
        queue.offerLast(3);
        System.out.println("Queue poll: " + queue.pollFirst()); // 앞에서 제거 (dequeue), 출력: 1
        System.out.println("Queue peek: " + queue.peekFirst()); // 앞에서 확인, 출력: 2

        // Deque 생성 (Stack처럼 사용)
        Deque<String> stack = new ArrayDeque<>();
        stack.offerFirst("A"); // 앞에 추가 (push)
        stack.offerFirst("B");
        stack.offerFirst("C");
        System.out.println("Stack poll: " + stack.pollFirst()); // 앞에서 제거 (pop), 출력: C
        System.out.println("Stack peek: " + stack.peekFirst()); // 앞에서 확인, 출력: B
    }
}

덱은 큐와 스택을 동시에 함께 상용할 수 있는 자료구조이다.

또한, 성능적인 측면에서도 Stack과 Queue 보다 유리한 면이 있어서 실제 테스트에서 Stack과 Queue를 사용해야할 때, 모두 Deque를 사용해도 좋다.

다만, Heap 구조를 위한 우선순위 큐(PriorityQueue)로 사용은 불가능하다.

 

Heap

import java.util.PriorityQueue;
import java.util.Collections; // 내림차순 정렬에 필요

public class Main {
    public static void main(String[] args) {
        // 기본 PriorityQueue (최소 힙 - 오름차순)
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();

        minHeap.offer(30);
        minHeap.offer(10);
        minHeap.offer(20);
        System.out.println("Min Heap: " + minHeap); // 내부 저장 순서는 다를 수 있지만, poll/peek은 우선순위대로!

        System.out.println("Poll from Min Heap: " + minHeap.poll()); // 출력: 10 (가장 작은 값)
        System.out.println("Poll from Min Heap: " + minHeap.poll()); // 출력: 20
        System.out.println("Poll from Min Heap: " + minHeap.poll()); // 출력: 30

        System.out.println("--------------------");

        // PriorityQueue (최대 힙 - 내림차순)
        // Collections.reverseOrder() 사용해서 내림차순으로 정렬 기준 변경
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());

        maxHeap.offer(30);
        maxHeap.offer(10);
        maxHeap.offer(20);
        System.out.println("Max Heap: " + maxHeap); // 내부 저장 순서는 다를 수 있지만, poll/peek은 우선순위대로!

        System.out.println("Poll from Max Heap: " + maxHeap.poll()); // 출력: 30 (가장 큰 값)
        System.out.println("Poll from Max Heap: " + maxHeap.poll()); // 출력: 20
        System.out.println("Poll from Max Heap: " + maxHeap.poll()); // 출력: 10
    }
}

 

자주 쓰이는 알고리즘

정렬

import java.util.*;

public class SortingExample {
    public static void main(String[] args) {
        // 배열 정렬 (기본 오름차순)
        int[] arr = {5, 2, 8, 1, 4};
        Arrays.sort(arr);
        System.out.println("Sorted Array: " + Arrays.toString(arr)); // 출력: [1, 2, 4, 5, 8]

        // 배열 정렬 (람다식을 이용한 내림차순)
        Integer[] arrDesc = {5, 2, 8, 1, 4}; // 기본형 int는 람다식 쓰려면 Wrapper 클래스(Integer) 사용 필요
        Arrays.sort(arrDesc, (a, b) -> b - a);
        System.out.println("Sorted Array (Desc): " + Arrays.toString(arrDesc)); // 출력: [8, 5, 4, 2, 1]

        // List 정렬
        List<String> list = new ArrayList<>(Arrays.asList("Cherry", "Apple", "Banana"));
        Collections.sort(list); // 기본 오름차순
        System.out.println("Sorted List: " + list); // 출력: [Apple, Banana, Cherry]

        // List 정렬 (람다식을 이용한 내림차순)
        Collections.sort(list, (a, b) -> b.compareTo(a));
        System.out.println("Sorted List (Desc): " + list); // 출력: [Cherry, Banana, Apple]
    }
}

오름차순 정렬을 위해서는 Wrapper 클래스로 람다식을 사용하는 것이 편리하다.

다만 int 배열의 경우, Integer 배열을 사용해야하는데 Integer 배열을 사용하지 않으려면 약간의 기교로 이용해서 쉽게 사용 가능하다.

 

1. 오름차순으로 정렬 후 필요시 검색을 반대로 수행

2. 모든 값에 -1을 곱해서 오름차순 후 실제 필요한 값을 -1을 곱해서 사용

import java.util.*;

public class SortingExample {
    public static void main(String[] args) {
        // 배열 정렬 (기본 오름차순)
        int[] arr = {5, 2, 8, 1, 4};
        Arrays.sort(arr);
        System.out.println("Sorted Array: " + Arrays.toString(arr)); // 출력: [1, 2, 4, 5, 8]
		
        // 내림차순 기교
        int[] arr2 = {-5, -2, -8, -1, -4};	// 원래 값에 -1을 곱한 값을 사용
        Arrays.sort(arr2);	// 오름차순 정렬
        System.out.println("Sorted Array: " + Arrays.toString(arr2)); // 출력: [-8, -5, -4, -1] -> 값을 사용할 때, -1을 곱해서 사용
    }
}

 

 

이진탐색

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        // 이진 탐색은 반드시 정렬된 배열에서 사용
        int[] sortedArr = {1, 2, 4, 5, 8, 10, 12};

        // 값 5 찾기
        int index = Arrays.binarySearch(sortedArr, 5);
        System.out.println("Index of 5: " + index); // 출력: 3 (0부터 시작)

        // 값 7 찾기 (없는 값)
        int indexNotFound = Arrays.binarySearch(sortedArr, 7);
        System.out.println("Index of 7: " + indexNotFound); // 출력: 음수 값 (찾지 못했음을 의미)
    }
}

이진탐색은 정렬된 배열에서 특정 값을 찾는데 유용하다. 정렬이 안되어있는 배열이 주어진다면 sort로 직접 정렬 수행.

Java에서는 이진탐색 알고리즘을 메서드로 제공하여 쉽게 사용 가능하다.

 

BFS

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class BFSExample {
    static List<List<Integer>> graph;
    static boolean[] visited;

    public static void bfs(int startNode) {
        Queue<Integer> q = new LinkedList<>();
        q.offer(startNode);
        visited[startNode] = true;

        while (!q.isEmpty()) {
            int currentNode = q.poll();
            System.out.print(currentNode + " "); // 방문 노드 출력

            // 현재 노드와 연결된 노드들 확인
            for (int nextNode : graph.get(currentNode)) {
                if (!visited[nextNode]) {
                    visited[nextNode] = true;
                    q.offer(nextNode);
                }
            }
        }
    }

    public static void main(String[] args) {
        // 그래프 생성 (예시)
        int numNodes = 5;
        graph = new ArrayList<>();
        for (int i = 0; i <= numNodes; i++) {
            graph.add(new ArrayList<>());
        }
        graph.get(1).add(2);
        graph.get(1).add(3);
        graph.get(2).add(4);
        graph.get(3).add(4);
        graph.get(3).add(5);
        graph.get(4).add(5);

        visited = new boolean[numNodes + 1]; // 방문 기록 배열

        System.out.print("BFS 탐색 결과 (1부터): ");
        bfs(1); // 1번 노드부터 BFS 시작
        System.out.println();
    }
}

 

BFS(너비 우선탐색)은 시작 노드를 주변으로 가까운 노드들을 먼저 탐색하면서 범위를 확장하는 탐색 방법이다.

그래프나 트리구조의 탐색에 사용하며, 최단거리, 네트워크 찾기 등 이동의 가중치가 동일한 경우 사용한다.

 

DFS

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Main {
    static int[] numbers = {1, 2, 3};
    static int n = numbers.length; // 총 숫자의 개수
    static int r = 3; // 선택할 숫자의 개수 (3자리 순열)
    static boolean[] visited = new boolean[n]; // 숫자를 사용했는지 체크
    static int[] result = new int[r]; // 현재 만들어지고 있는 순열

    // DFS (Backtracking) 함수
    // depth: 현재 몇 번째 숫자를 선택하고 있는지 (0부터 시작)
    public static void dfs(int depth) {
        // 기저 조건 (Base Case): r개의 숫자를 모두 선택했을 때
        if (depth == r) {
            // 완성된 순열 출력
            System.out.println(Arrays.toString(result));
            return; // 되돌아가기
        }

        // 재귀 호출 부분: 현재 depth 위치에 어떤 숫자를 넣을지 선택
        for (int i = 0; i < n; i++) {
            // i번째 숫자를 아직 사용하지 않았다면
            if (!visited[i]) {
                // 1. 선택 (상태 변경)
                visited[i] = true;      // i번째 숫자를 사용했다고 표시
                result[depth] = numbers[i]; // 현재 depth 위치에 i번째 숫자 저장

                // 2. 탐색 (더 깊이 들어가서 다음 숫자 선택)
                dfs(depth + 1);

                // 3. 원복 (백트래킹)
                // depth+1 에서 돌아오면 i번째 숫자를 사용했던 것을 취소
                // 그래야 다음 반복(i+1)에서 다른 숫자를 선택해서 새로운 순열
                visited[i] = false;
                // result[depth]는 다음 반복에서 덮어씌워지므로 여기서 따로 원복 안 해도 됨 (새로운 값으로 채워짐)
            }
        }
    }

    public static void main(String[] args) {
        System.out.println("순열 생성 결과:");
        dfs(0); // depth 0부터 시작 (첫 번째 숫자 선택)
        /*
        출력 결과:
        순열 생성 결과:
        [1, 2, 3]
        [1, 3, 2]
        [2, 1, 3]
        [2, 3, 1]
        [3, 1, 2]
        [3, 2, 1]
         */
    }
}

 

DFS(깊이 우선탐색)의 경우, 그래프나 트리구조의 탐색에서 사용하며 현재 노드와 연결된 노드를 모두 먼저 탐색하지 않고

다음 노드와 연결된 다음 노드가 있다면 해당 노드를 우선탐색한다.

1번 노드가 2, 3, 4 노드이고 2번과 연결된 노드가 5, 6(1제외)라면, 1->2->5 순으로 탐색한다.

 

위 코드는 1~3까지의 숫자로 만들 수 있는 배열의 조합을 출력하는 코드

DFS 탐색은 완전탐색으로 모든 경우를 탐색하다보니 시간초과의 이슈가 있을 수 있다.

 

3번의 백트래킹을 통해서 불가능한 경우, 더 이상 탐색하지 않고 종료하거나 모든 경우를 탐색하나 조건에 맞는 경우만 찾아야할 때 사용할 수 있다.