알고리즘 문제집 (Java)

🧩

한 줄 소개 — 직접 풀었던 알고리즘 문제들을 유형별로 분류 해 문제집 형식으로 묶었다. 큰 줄기는 자료구조 활용 → 완전탐색 → 구현·시뮬레이션 → DFS·백트래킹 → BFS·최단거리 → DP → 그리디. 출처는 백준 · 프로그래머스 · Softeer · CodeTree · 삼성 SW Expert · Codility 등이며, 언어는 주로 Java(일부 Python). 전체 풀이 코드(270+ 문제)는 GitHub 에 모아 두었다 → github.com/taehyuklee/Algorithm.

온라인 저지	문제 수*	특징
백준 (BOJ)	~70	삼성형 시뮬레이션 · 자료구조 전반
삼성 SW 역량 / SW Expert	~44	격자 시뮬레이션 (Java · Python 양쪽 풀이)
프로그래머스	~42	고득점 키트 · Lv1~3
Codility	~26	정확성 + 성능(시간복잡도) 채점
Softeer (현대차)	~22	구현 · DP · 그리디
CodeTree · 재현 · Warm-up	~50	코드트리 시뮬레이션 · 기본기

* 대략치 — 전체 풀이 코드는 github.com/taehyuklee/Algorithm 에 270+ 파일로 정리돼 있다.

0 · 들어가며 — Java 로 알고리즘 풀기

Java 로 알고리즘을 풀려면 먼저 Collection 프레임워크 의 자료구조가 내부적으로 어떻게 동작하는지 알아야 한다. 어떤 자료구조를 고르냐가 곧 시간복잡도를 결정한다.

자료구조	Java	주 용도
가변 배열	`ArrayList`	인덱스 접근 O(1), 동적 크기
스택 / 큐 / 덱	`Deque` (ArrayDeque)	DFS·괄호·BFS·슬라이딩 윈도우
우선순위 큐	`PriorityQueue`	다익스트라·최소/최대 추출 O(log n)
해시	`HashMap` / `HashSet`	존재 확인·카운팅 O(1)
정렬	`Collections.sort` + `Comparator`	기준 정렬·2차원 정렬

⚠️

자주 밟는 함정 (직접 겪은 것들)

for 루프 돌며 remove → IndexOutOfBoundsException. 리스트 크기가 줄어 인덱스가 어긋난다. → 역순 순회 하거나 while(!list.isEmpty() && 조건) 로 앞에서 빼낸다.
== vs .equals() — Integer(127 초과)·String 비교는 반드시 .equals(). 참조 비교(==)는 값이 같아도 false 가 날 수 있다.
int[] → List 변환: Arrays.stream(arr).boxed().collect(Collectors.toList()).
unreachable statement — break; 뒤의 코드는 도달 불가라 컴파일 에러.

1 · 자료구조 활용 — 큐 · 스택

문제의 동작을 자료구조의 성질 로 그대로 흉내 내는 유형. 앞에서 빼고 뒤에 넣는 흐름이면 큐, LIFO 면 스택이다.

문제	출처	핵심 아이디어
기능개발	프로그래머스	배포 순서대로 처리 → 큐. 앞에서부터 100% 도달한 작업을 한꺼번에 빼며 카운트
표 편집	프로그래머스 214288	잦은 삭제·복구 → 이중 연결 리스트 + 삭제 스택(undo)

기능개발 — 처음엔 리스트 인덱스를 돌며 제거하다 IndexOutOfBounds 에 걸렸다. "앞에서부터 빼낸다"는 큐의 성질에 맞춰 다시 작성했다.

class Solution {
    public int[] solution(int[] progresses, int[] speeds) {
        List prog  = Arrays.stream(progresses).boxed().collect(Collectors.toList());
        List speed = Arrays.stream(speeds).boxed().collect(Collectors.toList());
        List answer = new ArrayList<>();

        while (!prog.isEmpty()) {
            for (int i = 0; i < prog.size(); i++)        // 하루 진행
                prog.set(i, prog.get(i) + speed.get(i));

            int count = 0;                                // 앞에서부터 완료된 것 한꺼번에 배포
            while (!prog.isEmpty() && prog.get(0) >= 100) {
                prog.remove(0); speed.remove(0); count++;
            }
            if (count != 0) answer.add(count);
        }
        return answer.stream().mapToInt(i -> i).toArray();
    }
}

2 · 완전탐색 (Brute Force)

경우의 수가 충분히 작을 때, 모든 경우를 다 따져 보는 유형. 반복문·재귀·순열/조합으로 모든 후보를 만든다.

문제	출처	핵심 아이디어
모의고사	프로그래머스	3명의 찍는 패턴을 정답과 비교. 값 비교는 `.equals()` 로 (함정)
주사위 윷놀이	백준 17825	4개 말 × 매 턴 이동 선택 → 모든 경우 완전탐색(DFS), 점수 최대화
최소 직사각형	프로그래머스	각 명함을 (긴 변·짧은 변)으로 정규화 후 max 끼리 곱 — 구현

3 · 구현 · 시뮬레이션 (삼성 SW 핵심)

삼성 SW 역량테스트의 주력 유형. 격자(보드) 위에서 규칙대로 한 턴씩 진행 시키는 문제다. 정해진 절차를 버그 없이 그대로 옮기는 구현력이 핵심이다. 거의 모든 격자 문제는 방향 배열 dx/dy + 시간(턴) 루프 골격을 공유한다.

격자 시뮬레이션 공통 골격 — 방향 배열로 이동하고, 턴 루프 안에서 규칙을 순서대로 적용한다

문제	번호	핵심 기법
스타트 택시	백준 19238	시뮬레이션 + BFS(승객까지 최단거리)
컨베이어 벨트와 로봇	백준 20055	원형 벨트 회전 시뮬레이션 (인덱스 모듈러)
어른 상어	백준 19237	냄새 격자 + 우선순위 이동 시뮬레이션
모노미노도미노 2	백준 20061	블록 낙하·라인 제거 시뮬레이션
마법사 상어와 블리자드 / 복제	백준 20056 / 23290	격자 회전·이동·합치기 시뮬레이션
온풍기 안녕	백준 23289	BFS 확산(온도) + 벽 처리 시뮬레이션
원판 돌리기	백준 17822	원형 배열 회전 + BFS(인접 제거)
체스판 말 이동	백준 17837	말 객체 + 색(흰/빨/파)별 이동 규칙 시뮬레이션
게리맨더링 2	백준	경계선 완전탐색 + 구역 나누기 시뮬레이션
포탑 부수기 / 메이즈 러너 / 코드트리빵 …	코드트리	격자 시뮬레이션 (+ BFS 경로)

🧱

시뮬레이션은 상태를 객체로 모델링 하면 깔끔하다. 예) 체스판 말 이동(17837)은 말을 Horse{num,x,y,dir} 로 두고, 칸마다 List<Horse> 를 쌓아 색(흰=한 칸 이동, 빨=역순으로 쌓기, 파=방향 반전) 규칙을 그대로 옮겼다.

🗂️

GitHub 삼성 컬렉션 — 위 표 외에도 스타트 택시 · 어른/청소년 상어 · 마법사 상어(블리자드·복제·파이어볼·토네이도) · 컨베이어 벨트 · 모노미노도미노 · 온풍기 · 포탑 부수기 · 메이즈 러너 · 코드트리빵 · 산타 선물공장 · 나무 박멸 · 어항 정리 · 2024 상반기(왕실의 기사 · 루돌프 소싸움) 등 40여 문제를 Java·Python 양쪽으로 풀어 정리했다.

반복되는 패턴은 재사용 "삼성 모듈" 로 빼 두었다 — 좌표 회전(시계/반시계) · 나선(spiral) 순회 · 주기 경계(periodic boundary) 이동 · PriorityQueue + Comparator. 격자 문제는 이 모듈 조합으로 빠르게 조립한다.

4 · DFS · 백트래킹

선택을 깊게 밀고 들어갔다가, 막히면 되돌아오며(backtrack) 모든 경우를 탐색한다. "상태를 바꾸고 → 재귀 → 원복" 패턴이 핵심.

한 가지 선택을 끝까지 시도하고, 막히면 직전 분기로 되돌아가 다른 선택을 한다

문제	번호	핵심 아이디어
청소년 상어	백준 19236	물고기 배치 복사 → 상어가 먹는 모든 경우 DFS 백트래킹, 최대 점수
주사위 윷놀이	백준 17825	말 4개의 이동 선택을 DFS 로 완전탐색

5 · BFS · 최단거리

"몇 번 만에 도달?", "동시에 퍼져 나감" 류는 BFS. 큐로 가까운 칸부터 층(level)별로 방문하면 가중치가 같은 그래프의 최단거리 가 보장된다.

BFS 는 시작점에서 가까운 칸부터 층별로 방문 — 층 번호가 곧 최단거리

문제	출처	핵심 아이디어
숨바꼭질	백준 / 코드트리	±1, ×2 이동을 그래프로 보고 BFS 최단
쉬운 최단거리	백준	격자 BFS 거리 전파
스타트 택시 (승객 탐색)	백준 19238	택시→승객, 승객→목적지 거리를 각각 BFS
온풍기 안녕 / 코드트리빵	백준 23289 / 코드트리	여러 출발점에서 동시에 퍼지는 다중 시작 BFS

6 · DP · 그리디 · 그래프

DP 는 큰 문제를 겹치는 작은 문제로 나눠 메모이제이션한다. 그리디 는 매 순간 최적을 골라도 전체 최적이 보장될 때 쓴다.

문제	출처	유형 · 아이디어
경찰차	백준 2618	DP — 두 경찰차가 처리한 사건 인덱스 `dp[i][j]`, 최소 이동거리
ReserveRoom	Softeer	그리디 — 회의실 예약(구간 스케줄링), 끝나는 시간 기준 정렬
Virus	Softeer	그래프 탐색 — 감염 전파(BFS/DFS) 또는 Union-Find

🗺️

유형 판별 감각 — "모든 경우" & 작은 입력 → 완전탐색/DFS · "한 턴씩 규칙대로" → 시뮬레이션 · "최소 횟수/거리" & 가중치 동일 → BFS · "겹치는 부분 문제" → DP · "매 순간 최선" → 그리디. 삼성형은 대부분 시뮬레이션 + BFS/DFS 의 조합이다.

📓 2022–2023년 제가 코딩테스트를 준비하며 직접 푼 문제들(삼성 SW 역량테스트·프로그래머스·Softeer)을 Java 로 풀고 유형별로 정리한 노트입니다 · 전체 풀이 GitHub · Algorithm ↗ · 정리 Notion ↗