TreeSet, 재귀함수
1. 오늘의 학습 흐름
- 오전: SWEA 암호생성기 (D3-1225), 백준 7785 풀이
- 오후: Set 심화 (HashSet vs TreeSet, Comparable), 재귀함수 입문
2. 오전 - 문제 풀이
SWEA D3-1225 암호생성기
Queue의 핵심 패턴인 "앞에서 꺼내서 처리 후 뒤로 넣기"를 실전에서 쓰는 문제다.
8개의 숫자를 1~5씩 반복해서 감소시키고 맨 뒤로 보내다가, 0 이하가 되면 0으로 만들고 종료한다.
LinkedList<Integer> numbers = new LinkedList<>();
// 입력 받기
StringTokenizer st = new StringTokenizer(in.readLine(), " ");
for (int i = 0; i < 8; i++) {
numbers.add(Integer.parseInt(st.nextToken()));
}
boolean isDone = false;
top: // label: 특정 문장에 이름 부여
while (!isDone) {
for (int i = 1; i <= 5; i++) {
int num = numbers.poll() - i; // 앞에서 꺼내서 감소
if (num <= 0) {
num = 0;
isDone = true;
}
numbers.add(num); // 뒤로 보내기
if (isDone) break top; // label로 중첩 루프 한 번에 탈출
}
}여기서 label이 새로 나왔다. 중첩 반복문에서 특정 루프를 한 번에 빠져나올 때 쓴다. break top은 top:이 붙은 while문까지 한 번에 탈출한다. 남용하면 코드가 복잡해지지만, 중첩 루프 탈출 상황에서는 유용하다.
백준 7785 - 회사에 있는 사람 (TreeSet 활용)
출입 기록에서 현재 회사에 있는 사람을 이름 역순으로 출력하는 문제다.
TreeSet에 Comparator를 넘겨서 역순 정렬을 바로 적용했다.
// 역순 정렬 TreeSet
TreeSet<String> workSet = new TreeSet<>(new Comparator<String>() {
public int compare(String o1, String o2) {
return o2.compareTo(o1); // 역순
}
});
for (int i = 0; i < N; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
String name = st.nextToken();
String action = st.nextToken();
if (action.equals("enter")) {
workSet.add(name);
} else {
workSet.remove(name);
}
}
StringBuilder result = new StringBuilder();
for (String name : workSet) {
result.append(name).append("\n");
}
System.out.println(result);HashSet으로 풀면 정렬을 따로 해야 하는데, TreeSet은 자동 정렬이라 반복문 하나로 끝난다.
3. Set 심화 - HashSet vs TreeSet
HashSet vs TreeSet
| HashSet | TreeSet | |
|---|---|---|
| 내부 구조 | Hash 테이블 | 이진 탐색 트리(Red-Black Tree) |
| 정렬 | 없음 | 자동 정렬 |
| 검색 속도 | O(1) | O(logN) |
| 사용 상황 | 순서 필요 없고 빠른 검색 | 정렬된 상태 유지가 필요할 때 |
TreeSet에 객체 넣기 - Comparable 필수
TreeSet은 요소를 넣을 때마다 정렬해야 하므로, 비교 기준이 반드시 필요하다.
TreeSet<Employee> set3 = new TreeSet<>();
set3.add(new Employee("1", "홍길동", 3000000));
set3.add(new Employee("4", "김철수", 4000000));
set3.add(new Employee("3", "이영희", 2000000));
// Employee가 Comparable을 구현하지 않으면 ClassCastException 발생Employee에 Comparable<Employee>를 구현해서 정렬 기준을 정해줘야 한다.
public class Employee implements Comparable<Employee> {
@Override
public int compareTo(Employee o) {
// 오름차순: 현재 - 인자
return this.salary - o.salary;
// return Integer.compare(this.salary, o.salary); // 더 안전한 방법
// 내림차순: 인자 - 현재
// return o.salary - this.salary;
// return Integer.compare(o.salary, this.salary);
}
}compareTo 반환값 규칙:
- 양수 → 현재 객체가 더 크다 → 뒤로
- 0 → 같다
- 음수 → 현재 객체가 더 작다 → 앞으로
오름차순은 현재 - 인자, 내림차순은 인자 - 현재로 기억하면 된다.
Integer.compare(a, b)를 쓰면 int 오버플로우 걱정 없이 안전하게 비교할 수 있다. a - b는 값이 극단적으로 크거나 작을 때 오버플로우가 날 수 있어서 실무에서는 Integer.compare()를 쓰는 게 낫다.
4. 재귀함수
재귀함수란
함수 내에서 자기 자신을 다시 호출하는 구조다.
public static void print1(int i) {
if (i > N) return; // 기저 조건 (Base Case): 재귀를 중단하는 조건
System.out.print(i + " ");
print1(i + 1); // 유도 파트: 재귀 진행
}재귀함수는 반드시 두 부분으로 나뉜다.
- 기저 조건(Base Case): 재귀를 멈추는 조건. 없으면 스택 오버플로우가 난다.
- 유도 파트: 재귀를 진행하는 부분.
재귀함수 vs 반복문
| 반복문 | 재귀함수 | |
|---|---|---|
| 종료 방식 | break | return |
| 반복 깊이 | 고정 (Fixed depth) | 유동적 (랜덤 depth 가능) |
| 중첩 깊이 | 깊어질수록 코드 복잡 | 깊이가 달라도 코드 구조 동일 |
| 성능 | 빠름 | 함수 호출 오버헤드 있음 |
반복문으로 풀 수 있는 건 재귀로 모두 풀 수 있다. 반대는 성립하지 않는다.
재귀가 반복문보다 유리한 상황: 반복의 깊이가 고정되지 않거나, 반복 중첩 깊이가 깊어서 for문으로 표현하기 어려울 때. DFS, 백트래킹, 트리 탐색이 대표적이다.
Bottom-Up vs Top-Down
// Bottom-Up: 작은 수에서 큰 수로 (1 → 10)
public static void print1(int i) {
if (i > N) return;
System.out.print(i + " ");
print1(i + 1);
}
// Top-Down: 큰 수에서 작은 수로 (10 → 1)
public static void print2(int i) {
if (i == 0) return;
System.out.print(i + " ");
print2(i - 1);
}재귀 호출 전에 출력하면 순방향, 재귀 호출 후에 출력하면 역방향이 된다. 이 차이가 나중에 트리 탐색(전위/후위 순회)에서 그대로 활용된다.
// 재귀 호출 전 출력 → 1 2 3 4 5
public static void printBefore(int i) {
if (i > N) return;
System.out.print(i + " "); // 먼저 출력
printBefore(i + 1);
}
// 재귀 호출 후 출력 → 5 4 3 2 1 (역순)
public static void printAfter(int i) {
if (i > N) return;
printAfter(i + 1);
System.out.print(i + " "); // 나중에 출력 (콜 스택이 쌓인 후 역순으로 풀림)
}5. 재귀의 필요성
재귀를 배우면서 반복문으로 다 풀 수 있는데 왜 재귀를 쓰냐..
재귀가 빛나는 순간은 "탐색 깊이가 달라질 때"다. NxN 배열에서 상하좌우로 이동하는 문제를 for문으로 짜려면 깊이마다 for문을 중첩해야 한다. 근데 깊이가 고정이 아니라 조건에 따라 달라진다면 for문으로는 표현이 불가능하다.
DFS, 백트래킹 같은 알고리즘이 재귀로 구현되는 이유가 바로 이것이다.
6. 키워드 정리
TreeSet 자동 정렬 재귀함수 기저 조건 유도 파트 Base Case Bottom-Up Top-Down 재귀 호출 전후 출력 차이 Stack Overflow
7. 내일의 목표
- 백준 1문제
- 파랭이 진짜마무리
- linux 세팅 및 claude code 세팅 마치기
- 정처기 실기 시험
