알고리즘 기본

표준 입출력

• System.in, System.out, System.err

표준 입출력 대상 변경

• System.setIn(), System.setOut(), System.setErr()

java.util.Scanner

• 파일, 입력 스트림 등에서 데이터를 읽어와 구분자로 토큰화하고 다양한 타입으로 형변환하여 리턴
• 토큰화: 의미있는 단위로 구분
• 생성자: Scanner(File source), Scanner(InputStream source), Scanner(String source)
• 사용법이 쉽고, 알아서 형변환 해줘서 편리
• 비효율적
• next()와 nextLine() 구분 필요

java.io.BufferedReader

• 필터 스트림 유형
• 라인 단위 문자열 처리 제공하여 쉬운 처리
• 대량의 데이터 처리에 효율적
• 보조 스트림

java.lang.StringBuilder

• 문자열 조작을 지원
• 새로운 문자열 생성(String)을 방지

SW 문제 해결 역량

• 문제는 적어도 3번 읽는다.
  1. 빠르게 문제 파악(유형 파악)
  2. 유형을 생각하며 문제 파악(유형 확신, 복잡도 계산)
  3. 제약사항을 꼼꼼히 파악하고, 계획

알고리즘

• 유한한 단계를 통해 문제를 해결하기 위한 절차나 방법

복잡도의 점근적 표기

• 시간(공간)복잡도는 입력 크기에 대한 함수로 표기
• 단순한 함수로 표현 → 점근적 표기
• 빅 오 표기: 시간 복잡도 함수 중에서 가장 큰 영향력을 주는 n에 대한 항만을 표시, 계수는 생략

배열

• 일정한 자료형의 변수들을 하나의 이름으로 열거하여 사용하는 자료구조

재귀

• 반복과 재귀는 유사한 작업 수행 가능
• 반복은 수행하는 작업이 완료될 때까지 계속 반복
• 재귀는 주어진 문제의 해를 구하기 위해 동일하면서 더 작은 문제의 해를 이용
• 하나의 큰 문제를 해결하기 쉬운 작은 문제로 쪼개고 결과들을 결합(분할 정복)

재귀 함수

• 함수 내부에서 직접 혹은 간접적으로 자기 자신 호출
• 기본 파트와 유도 파트
  • 기본 파트: 재귀를 멈추는 조건(return)
  • 유도 파트: 단위 반복 코드
• 반복 구조에 비해 간결
• 메서드 스택을 이용
• 메모리 및 속도 성능 저하
• 반복 알고리즘보다 더 많은 메모리와 연산을 필요
• 입력값이 커질수록 재귀 알고리즘은 반복에 비해 비효율적

완전 검색

• 생각할 수 있는 모든 경우의 수를 나열
• Brute-force 혹은 generate-and-test 기법