02/05(금) 알고리즘 이론 - > 표준 입출력 - 자바의 기본 스트림 : System.in, System.out, System.err - 데이터 타입에 따른 스트림 결정 | | byte | char | | -------- | -------- | -------- | | 입력 스트림|InputStream|Reader| | 출력 스트림| OutputStream|Writer | > Scanner - 스트림에서 데이터를 읽어 구분자로 토큰화하여 다양한 타입으로 리턴해주는 클래스 - 입력 스트림 다루는 방법을 몰라도 손쉽게 사용 가능 - 하지만, 대량의 데이터 처리 시 비효율적 - 주요 메소드 : nextInt(), nextDouble(), next(), nextLine() > BufferedReader - 필터 스트림 유형 중 하나 - line 단위의 문자열 처리 기능을 제공 - 대량의 데이터 처리 시 효율적 - Reader타입이기 때문에 System.in을 InputStreamReader로 변경해주어야 함. >StringBuilder - 문자열의 조작을 지원하는 클래스 - String과 다르게 문자열 조작 시 새로운 문자열 생성을 방지 - 주요 메소드 : append(), toString() >빅-오 표기법 - 시간 복잡도를 표현해주는 표기법 - 시간 복잡도 함수 중 가장 큰 영향력을 주는 n에 대한 항만 표시(계수는 생략) - 실행 횟수는 1억번당 1초로 계산 - O(N), O(logN) > 알고리즘 문제 해결 과정 - 문제를 읽고 이해. - 문제를 익숙한 용어로 재정의. - 문제 해결 계획 수릭 - 계획 검증 - 프로그램으로 구현 - 어떻게 풀었는지 돌아보고, 개선할 방법 탐색 > 좋은 알고리즘의 조건 - 정확성 : 얼마나 정확하게 동작하는가. - 작업량 : 얼마나 적은 연산으로 원하는 결과를 얻어내는가. - 메모리 사용량 : 얼마나 적은 메모리를 사용하는가 - 단순성 : 얼마나 단순한가 - 최적성 : 더 이상 개선할 여지가 없이 최적화 되어 있는가 > 재귀함수 - 자기 자신을 호출하는 함수 - **FLAT** 하게 생각하기 > 순열 - 서로 다른 것들 중 몇 개를 뽑아서 한 줄로 나열하는 것. - 재귀를 이용하여 구현 가능. > 조합 - 서로 다른 것들 중 순서에 상관 없이 몇 개를 뽑는 것. - 재귀를 이용하여 구현 가능 > 부분집합 - 재귀함수로 구현 가능. > 스택(collection클래스) - 주요 메서드 : push pop peek size isEmpty clear - empty stack exeption : 스택이 빈 상태에서 pop 시도할 때 발생 - 예 : 브라우저 뒤로가기/앞으로가기, 스택계산기 > 큐(collection 인터페이스 - linkedlist로 구현) - 주요 메서드 : offer peek poll isEmpty size - front / rear - deQueue / enQueue - 빈 상태에서 poll 해도 예외 발생X, null을 반환 - 예 : 마이쮸 나눠주기 - 주의 : linkedlist는 다른 인터페이스도 구현하고 있으므로 linkedlist로 참조변수 선언 시 quque 성질과 관련 없는 메서드 사용에 유의 문제 풀이 - - 동일 매개변수로 메서드 호출 반복시 오버헤드가 크므로 리턴값을 변수에 저장하는 것이 좋다. - 배열 크기에 패딩 주는 경우 인덱스에 유의 - 배열 탐색 시 방향 배열 활용가능함 (int[] dr, int[] dc) - 상수(static final) 선언하여 방향 인덱스에 활용가능함 - char형 문자를 정수형으로 바꾸고 싶은 경우 -'0' 한다. - 메서드 분리하면 디버깅이 쉬워진다. - static 변수 활용하여 재귀호출 시 매개변수를 대체할 수 있다. - BufferedReader를 활용하여 입력 최적화를 할 수 있다. - StringBuilder 를 활용하여 출력 최적화를 할 수 있다.