자료구조 기초 + 코테
1. int vs long
조합, dp, 경우의 수, 순열, 큰 수 계산 등의 문제에서 30억 이상의 길이가 생길 수 있음으로 int가 안먹힐 수 있음
long을 써주는 것이 더 정확.
2. scanner vs stringBuilder
3. ++i vs i++ (전위 연산자 vs 후위 연산자)
i = 0
A[++i] = 10; => i가 먼저 올라가서 A[1] 에 10 이 저장.
A[i++] = 10; => i가 나중에 올라가기 때문에 A[0]에 10이 저장된 후 A[1]로 증가.
4. 오름차순 vs 내림차순
- 오름차순정렬
Int A[] = {5,4,3,2,4,1};
Arrays.sort(A);
System.out.println(Arrays.toString(A)); => {1,2,3,4,5}
- 내림차순 정렬.
1) Integer로 객체형식을 만들어 collection의 reverseOrder를 사용.(이건 객체만 먹힘.)
Integer A[] = {5,4,3,2,4,1};
Arrays.sort(A, Collections.reverseOrder());
System.out.println(Arrays.toString(A));
2) collection의 reverseOrder를 사용해서 int로 출력하기
int A[] = {5,3,2,4,1};
Integer[] tmp = Arrays.stream(A).boxed().toArray(Integer[]::new);
Arrays.sort(tmp, Collection.reverseOrder());
System.out.println(Arrays.toString(tmp)); = > {5,4,3,2,1}
3) -1을 곱해 sort를 사용하기.
// 오름차순처럼 같은 메서드로 사용해 내림차순을 만들고 싶어.
int A[] = {-5,-4,-3,-2,-1};
Arrays.sort(A);
System.out.println(Arrays.toString(A)); => {-5,-4,-3,-2,-1}
5. Comparable
*정렬
- sort : 단일기준일 경우.
- comparable : 정렬기준이 여러 개
* 영어 점수가 높은 학생 순으로 정렬하되 영어점수가 같으면 수학점수가 높은 학생을 선순위로 정렬하기.
1. class 정의 (get,set, tostring)
2. comparable implements 해서 compareTo 재정의하기.
Class Socre implements Comparable<Score>{
01-1 시간 복잡도 표기법
1. 빅오메가 : 최선
2. 빅세타 : 보통
3. 빅오 : 최악
코테는 빅오를 염두해두고 문제를 풀어야함.
최악만 아니면 문제 통과가능.
n = 데이터의 크기
O(n!) : n의 수가 커질수록 처리속도가 엄청 오래걸림.
O(logn) : logn 은 2의 제곱으로 따짐. log 100 => 2^6 = 64 2^7 = 128이므로 7번안에 데이터가 처리되는 것을 의미.
*시간계산
연산횟수계산 = 알고리즘 시간 복잡도 x 데이터 크기
ex) N = 100만건.(제한시간 2초에 2억번 이하의 연산횟수로 문제풀기 )
- 버블정렬 = N^2(n제곱) = (100만)^2 = 10억 > 2억 = 부적합한 알고리즘
- 병합정렬 = nlogn = 100만log(100만) = 100만 x 20
= 2000만 < 2억 (1억건에 1초 / 10분의 1정도 걸리니까 약 0.2초만에 해결가능) = 적합한 알고리즘.
* 문제를 볼때 계산을 해서 어떤 알고리즘을 사용해야겠다는 판단을 먼저 내려야함.
- for 문 3개 = 3N
- 이중 for문 = N ^ 2(N제곱)
* 코테에서 중요한 점.
1) 알맞은 알고리즘 선택기준
2) 비효율적인 로직 찾아서 효율적으로 바꿀것. ( 알고리즘을 잘 선택한것 같은데 안될때)
01-2 디버깅. (논리 오류잡기)
코테에선 로그보단 디버깅을 하는게 더 효율적
로그는 지협적이고 매번 다시 실행해야하지만, 디버깅은 전체를 한번 실행하면 모든 부분들을 확인할 수 있음.
코테에서 자주 실수하는 부분
1) 변수 초기화 위치 오류.
2) for문의 index 범위 설정 실수.
3) 자료형 타입 실수.
int를 long으로 선언하기.
int의 공간이 부족해서 음수가 나와버리는 경우가 있음.
ex, 팩토리얼, 순열, 경우의 수, dp 등에서 계산했을 때 숫자가 굉장히 커질경우.
자료구조.
1. Stack
- 후입선출(LAFO)
- top : 삽입,삭제가 일어나는 위치
- push : 삽입 / pop : 삭제 & 확인 / peek : 단순 확인
- 깊이우선탐색, 백트래킹 문제에 효과적 / 재귀함수 원리와 비슷.
2. Queue
- 너비우선탐색에 자주 사용.
- 선입선출(FIFO)
- 삽입삭제가 양방향. 뒤쪽이 삽입, 앞쪽이 값꺼내고 삭제
- rear : 큐에서 가장 끝 데이터
- front : 큐에서 가장 앞의 데이터를 가르키는 영역
- add : rear 부분에 새로운 데이터를 삽입하는 연산
- poll : front부분에 있는 데이터를 삭제하고 확인
- peek : font에 있는 데이터 확인.
+) 우선순위 큐도 있음!
- 값이 들어간 순서와 상관없이 우선순위가 높은 데이터가 먼저 나오는 자료구조.
- 설정으로 front 에 항상 최댓값 or 최솟값이 존재하게 할 수 있음.
- 힙(트리종류)을 사용해 구현. -> min힙, max 힙.
3. 정렬알고리즘.
1) 버블정렬
- 시간복잡도 O(n²) : 느린편.
- 인접한 데이터의 크기를 비교해 정렬.(loop를 돌면서 인접한 데이터간의 s)
2) 선택정렬
3) 삽입정렬
4) 퀵정렬
5) 병합정렬
6)