알고리즘, 시간복잡도, Eclipse 디버깅, Stack
1. 오늘의 학습 흐름
- 표준 입출력 (Scanner vs BufferedReader), StringBuilder
- 알고리즘이란 무엇인가, 문제 해결 과정
- 좋은 알고리즘의 기준, 시간복잡도, Big-O 표기법
- Eclipse 디버깅 방법
- Stack
2. 표준 입출력
Scanner vs BufferedReader
알고리즘 문제를 풀 때 입력 처리 방법 선택이 중요하다.
// Scanner - 편하지만 대량 데이터에서 느림
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
String s = sc.nextLine();
// BufferedReader - 줄 단위 처리, 대량 데이터에서 빠름
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String line = br.readLine();
// 공백으로 구분된 숫자 두 개 입력받기
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
int i = Integer.parseInt(st.nextToken());
int j = Integer.parseInt(st.nextToken());Scanner 주요 메서드: nextInt(), nextDouble(), next() (공백 전까지), nextLine() (개행 전까지, 공백 포함)
알고리즘 문제에서 입력 데이터가 많으면 Scanner가 시간 초과 원인이 되기도 한다. 습관적으로 BufferedReader를 쓰는 게 좋다.
StringBuilder
String은 불변이라 + 연산마다 새 객체가 생성된다. 문자열을 많이 이어붙여야 하면 StringBuilder를 써야 한다.
StringBuilder sb = new StringBuilder();
sb.append("Hello ");
sb.append("SSAFY").append("!!");
System.out.println(sb.toString()); // Hello SSAFY!!
sb.setLength(sb.length() - 2); // 끝에서 2글자 제거
System.out.println(sb.toString()); // Hello SSAFY출력이 많은 알고리즘 문제에서 System.out.println()을 반복 호출하면 느려진다. 결과를 StringBuilder에 모아서 한 번에 출력하는 게 좋다.
3. 알고리즘이란
유한한 단계를 통해 문제를 해결하기 위한 절차나 방법이다. 어떤 문제를 해결하기 위한 단계적 방법이라고 보면 된다.
알고리즘을 표현하는 방법은 두 가지다. 의사코드(Pseudocode)로 로직을 언어에 가깝게 표현하거나, 순서도(Flowchart)로 흐름을 시각적으로 표현한다.
문제 해결 과정
오늘 강조하신 내용이다. 문제를 보자마자 코드부터 치는 게 아니라 이 순서를 따라야 한다.
- 문제를 읽고 이해한다
- 문제를 익숙한 용어로 재정의한다
- 어떻게 해결할지 계획을 세운다
- 계획을 검증한다
- 프로그램으로 구현한다
- 어떻게 풀었는지 돌아보고, 개선할 방법이 있는지 찾아본다
SW 문제 해결 역량은 알고리즘을 암기한다고 생기지 않는다. 훈련이 필요하고, 언어와 자료구조와 알고리즘을 적재적소에 연결하는 능력이다.
4. 좋은 알고리즘의 기준
같은 문제를 푸는 알고리즘이 여러 개일 수 있다. 어떤 게 더 나은지 판단하는 기준이 있다.
- 정확성: 얼마나 정확하게 동작하는가
- 작업량: 얼마나 적은 연산으로 결과를 얻는가
- 메모리 사용량: 얼마나 적은 메모리를 사용하는가
- 단순성: 얼마나 단순한가
- 최적성: 더 이상 개선할 여지없이 최적화되었는가
이 중에서 작업량(시간복잡도)이 성능 분석의 핵심 기준이다.
5. 시간복잡도와 Big-O 표기법
같은 결과를 내더라도 연산 횟수가 다를 수 있다.
1부터 100까지 합을 구하는 두 가지 방법:
- 알고리즘 1: 1+2+3+...+100 → 100번 연산
- 알고리즘 2: 100×(1+100)/2 = 5050 → 3번 연산
데이터가 많아질수록 이 차이가 엄청나게 벌어진다.
Big-O 표기법
시간복잡도 함수에서 가장 큰 영향을 주는 항만 표시하고, 계수는 생략한다.
O(3n + 2) → O(n) 최고차항만, 계수 제거
O(2n² + 10n + 100) → O(n²) 최고차항만
O(4) → O(1) 상수는 1로복잡도 순서 (빠름 → 느림):
O(1) < O(logN) < O(N) < O(NlogN) < O(N²) < O(2^N) < O(N!)실제 실행 시간으로 보면
N = 10^8(1억)일 때:
- O(N): 약 0.1초
- O(N²): 115.7일
- O(2^N): 사실상 불가
제약조건을 먼저 보는 이유가 여기 있다. N이 10^8이면 O(N²) 알고리즘은 절대 통과 못한다. 시간복잡도를 먼저 계산하고 접근 방법을 결정해야 한다.
시간복잡도 → 공간복잡도로 해결
다음에 배울 내용이지만 미리 언급하셨다. 시간이 오래 걸리는 문제를 자료구조를 잘 활용해서 메모리(공간)를 더 쓰는 대신 시간을 줄이는 방법이 있다. 그래서 자료구조를 잘 알고 써야 한다.
6. Eclipse 디버깅
알고리즘 문제를 풀 때 디버깅 능력이 중요하다. 오늘 Eclipse 디버거 사용법을 배웠다.
Breakpoint 설정
코드를 멈추고 싶은 줄의 왼쪽 여백을 더블클릭하거나, 우클릭 → Toggle Breakpoint (Ctrl+Shift+B)
Debug 모드 실행
F11 또는 상단 벌레 아이콘
디버그 뷰 버튼
| 버튼 | 단축키 | 설명 |
|---|---|---|
| Resume | F8 | 다음 Breakpoint까지 진행 |
| Suspend | - | 현재 Thread 일시 정지 |
| Terminate | - | 프로그램 종료 |
| Step Into | F5 | 다음 줄로 이동, 메서드 호출 시 내부로 진입 |
| Step Over | F6 | 다음 줄로 이동, 메서드는 건너뜀 |
| Step Return | F7 | 현재 메서드에서 즉시 Return |
| Drop to Frame | - | 메서드를 처음부터 다시 실행 |
Step Into와 Step Over 차이가 중요하다. 메서드()를 만났을 때 F5는 그 안으로 들어가고, F6은 실행만 하고 다음 줄로 넘어간다.
Step Filtering
F5로 Step Into 할 때 Java 내부 API까지 들어가버리면 불편하다. 필터 설정으로 건너뛸 수 있다.
Window → Preferences → Java → Debug → Step Filtering → java.*, javax.* 등 체크
Variables 창
Breakpoint에서 멈췄을 때 현재 스코프의 지역변수와 값을 실시간으로 확인할 수 있다. static 변수나 상수도 보려면 추가 메뉴 → Java → Show Constants / Show Static Variables 선택.
Breakpoint 조건 설정 (Conditional Breakpoint)
반복문 안에 Breakpoint를 걸면 매번 멈춰서 불편하다. 특정 조건일 때만 멈추게 설정할 수 있다.
Breakpoint에서 우클릭 → Breakpoint Properties → Conditional 체크 → 조건 입력 (예: i == 50)
Hit Count로 N번째 실행 시에만 멈추게도 설정 가능하다.
7. Stack 자료구조
Stack이란
Last In First Out(LIFO) - 마지막에 넣은 게 먼저 나오는 구조다. 접시를 쌓는 것처럼, 위에서만 넣고 뺄 수 있다.
Stack<String> stack = new Stack<>();
stack.isEmpty() // 비어있는지 확인
stack.push("hello") // 맨 위에 추가
stack.peek() // 맨 위 데이터 확인 (제거 안 함)
stack.pop() // 맨 위 데이터 꺼내기 (제거)
stack.size() // 크기 확인Stack<String> stack = new Stack<>();
stack.push("hello");
stack.push("world");
stack.push("java");
stack.push("ureka");
System.out.println(stack.peek()); // "ureka" (제거 안 함)
System.out.println(stack.pop()); // "ureka" (꺼내서 제거)
System.out.println(stack.size()); // 3실전 활용 - 괄호 검사 (BleketTest)
Stack의 대표적인 활용 문제다. 여는 괄호 (를 push하고, 닫는 괄호 )가 나왔을 때 pop해서 짝이 맞는지 확인한다.
Stack<Character> stack = new Stack<>();
String result = "Ok";
for (int i = 0; i < line.length(); i++) {
char ch = line.charAt(i);
if (ch == '(') {
stack.push(ch); // 여는 괄호는 push
} else if (ch == ')') {
if (stack.isEmpty() || stack.pop() != '(') {
result = "Error"; // 스택이 비었는데 닫는 괄호 → Error
break;
}
}
}
if (!stack.isEmpty()) result = "Error"; // 다 끝났는데 스택에 남아있으면 → Error에러 케이스가 두 가지라는 게 핵심이다.
- 닫는 괄호
)가 나왔는데 스택이 비어있는 경우 → 짝 없는)존재 - 문자열을 다 처리했는데 스택에
(가 남아있는 경우 → 닫히지 않은(존재
8. 키워드 정리
Scanner BufferedReader StringTokenizer StringBuilder append() 알고리즘 문제 해결 과정 시간복잡도 공간복잡도 Big-O 제약조건 Eclipse 디버깅 Breakpoint Step Into Step Over Step Filtering Conditional Breakpoint Variables Stack
9. 내일의 목표
- 정처기 실기 진짜 얼마 안 남음
- 파랭이책 1/3
- 자소서 쓰기
