코딩 테스트에서는 빅-오표기법 (O(n))을기준으로 수행 시간을 계산
시간 복잡도를 알고리즘 선택의 기준으로 사용할 수 있다.
프로그램에서 발생하는 문법 오류나 논리 오류를 찾아 바로잡는 과정
Tip) 자료형은 처음부터 long형으로 선언하자
메모리의 연속공간에 값이 채워져 있는 형태의 자료구조
배열의 특징
값과 포인터를 묶은 노드라는 것을 포인터로 연결한 자료구조
리스트의 특징
String -> 숫자
String sNum = "1234"; // string형 변수
int il = Integer.parselnt(sNum);
int i2 = Integer.valueOf(sNum);
double dl = Double.parseDouble(sNum);
double d2 = Double.valueOf(sNum);
float fl = Float.parseFloat(sNum);
float f2 = Float.valueOf(sNum);
long 11 = Long.parseLong(sNum);
long 12 = Long.valueOf(sNum);
short si = Short.parseShort(sNum);
short s2 = Short.valueOf(sNum);
숫자 -> String
int i = 1234;
String i1 = String.valueOf(i);
String i2 = Integer.toString(i);
double d = 1.23;
String d1 = String.valueOf(d);
String d2 = Double.toString(d);
float f = (float) 1.23;
String f1 = String.valueOf(f);
String f2 = Float.toString(f);
long l = 1234;
String l1 = String.valueOf(l);
String l2 = Long.toString(l);
short s = 1234;
String s1 = String.valueOf(s);
String s2 = Short.toString(s);
구간합은 합 배열을 이용하여 시간 복잡도를 더 줄이기 위해 사용하는 특수한목적의 알고리즘이다.
합 배열 S
S[i] = A[0] + A[1] + A[2] + ... + A[i-1] + A[i] // A[0]부터 A[i]까지의 합
합 배열 S를 만드는 공식
S[i] = S[i-1] + A[i]
구간 합을 구하는 공식
S[j] - S[i-1] //i에서 j까지 구간합
2차원 구간 합 배열 D[X][Y]
D[X][Y] = 원본 배열의 (0, 0)부터 (X, Y)까지의 사각형 영역 안에 있는 수의 합
D[i][j]의 값을 채우는 구간 합 공식
D[i][j] = D[i][j-1] + D[i-1][j] - D[i-1][j-1] + A[i][j] //A[i][j]는 원본 배열
도서_알고리즘 코딩테스트 참고