20220203 Algo

표준 입출력

System.in : InputStream (byte 단위 입력)

System.out

System.err

java.util.Scanner : 파일, 입력 스트림등에서 데이털르 일겅 구분자로 토큰화하고 다양한 타입으로 형변환하여 리턴해주는 클래스

• 데이터 형변환으로 인한 편리함
• 대량의 데이터 처리 시 수행시간이 비효율적

BufferedReader : 라인 단위로 입력을 받아 수행시간이 효율적임

next → 공백으로 문자를 split함

• 구분자이전까지 커서를 이용해서 값을 읽어들임.

nextLine → Enter에서 개행문자로 공백인 엔터만 반환하므로 nextLine을 하나 더 추가해서 개행을 flush해줌

• Enter까지 커서를 이용해서 값을 읽어들임.

java.io.BufferedReader : 필터 스트림 유형 → 줄단위로 문자열 처리 기능 제공

• System.in → InputStreamReader → BufferedReader

java.lang.StringBuilder : 자바에서 상수로 취급되는 문자열을 조작 시 마다 새로운 문자열이 생성되는 것을 방지

• append( ) : return value(StringBuilder)
• toString( ) : 저장된 데이터 String 형태로 반환
• setLength( ) : 뒤에서 길이 자르기

빅-오(O) 표기법

시간 복잡도 함수 중에서 가장 큰 영향력을 주는 n에 대한 항만을 표시 (계수는 생략)

배열

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

재귀함수(recursive function) : 자기 자신을 호출하는 함수

• 기본 부분(basis part)와 유도 파트(inductive part)로 구성됨
• 함수 호출은 프로그램 메모리 구조에서 스택을 사용

경우의 수에서는 선택하지 않아도 하나의 case로 간주함

반복 vs 재귀

재귀는 반복 알고리즘보다 더 많은 메모리와 연산을 필요로 함

입력 값 n이 커질수록 재귀 알고리즘은 반복에 비해 비효율적

2차원 배열

Array of Array, 각 차원에 따라 크기를 명시

완전검색(Exhaustive Search)

Brute-force, 문제의 해법으로 생각할 수 있는 모든 경우의 수를 나열해보고 확인하는 기법