[알고리즘] Array

<APS 기본>

1. 입출력 처리

• 표준 입출력
  • 스트림(데이터의 흐름-단방향)<빨대>
  • 읽어들이는 스트림(InputStream/Reader)과 내보내는 스트림(OutputStream/Writer) 2개가 있어야 함
  • System.in: InputStream - byte단위의 입력
  • System.out/err
  • 대상변경: System.setOut(),setErr(),setIn()
• Java.util.Scanner
  • 파일, 입력 스트림등에서 데이터를 읽어 구분자로 토큰화하고 다양한 타입으로 형변환하여 리턴해주는 클래스
  • 데이터 형변환으로 인한 편리함
  • 대량의 데이터 처리 시 수행시간이 비효율적
  • 최적화를 위해 다른애를 쓰는게 나음 → BufferedReader
  • 출력도 하나씩 쌓아서 한번에 출력 → StringBuilder
  • <Scanner 주요 메소드>
    • nextInt(): 유효 문자열 후 공백을 만나면 처리
    • nextLint(): 개행 문자를 만나면 처리 → next()와 달리 문자열 안에 띄어쓰기 가능
• Java.io.BufferedReader
  • 필터 스트림 유형
  • 줄 단위로 문자열 처리 기능 제공 → readLine()
  • 대량의 데이터 처리 시 수행시간 효율적
• Java.lang.StringBuilder
  • 문자열의 조작을 지원
  • 문자열 조작할 때마다 새로운 문자열 생기는거 방지
  • append() - StringBuilder 자기 자신 ⇒ sb.append(”dd”) 하고 sb.toString() 하면 dd출력

2. SW 문제 해결

• SW 문제 해결 역량?
  • 언어, 라이브러리, 자료구조, 알고리즘 적재적소에 사용
• 복잡도의 점근적 표기
  • 시간 복잡도는 입력 크기에 대한 함수로 표기. 함수는 주로 여러 개의 항을 가지는 다항식 → 점근적 표기 사용
• 빅-오 표기법
  • 시간 복잡도 함수 중에서 가장 큰 영향력을 주는 n에 대한 항만을 표시
  • 계수는 생략하여 표시
  • O(3n+2) = O(3n) = O(n)

3. 1차원 배열

• 1차원 배열의 접근
  • 배열 원소 오른쪽 shift
    • arr[i+1]=arr[i]
  • 배열 원소 왼쪽 shift

4. 재귀 호출

• 반복과 재귀
  • 반복은 수행하는 작업이 완료될 때까지 계속 반복
• 재귀 함수
  • 함수 내부에서 직접 혹은 간접적으로 자기 자신을 호출하는 함수
  • 일반적으로 재귀적 정의를 이용해서 재귀 함수를 구현함
  • 재귀의 끝: 조건 판별 후 재귀호출 x → return값
  • 재귀= 기본부분(basis part)<재귀호출 끊어주는 부분-return 필수!!!!!> + 유도파트(inductive part)<단위 반복 코드>
  • 끝이 결정되어 있는 반복인가!!!! 중요중요
  • 함수 호출은 프로그램 메모리 구조에서 스택을 사용
  • 재귀 호출: 반복적인 스택의 사용 → 메모리 및 속도에서 성능 저하가 발생 → 반복문이 조금 유리
• 팩토리얼 재귀 함수

  int fact(int n){
  	if (n <=1 )  //Basis part
  		return 1;
  	else         //Inductive part
  		retrun n*fact(n-1);}