[Do it! 알고리즘 코딩 테스트 자바] 시간복잡도/디버깅/오답 유형(1~2일차)

알고리즘 선택의 기준 = 시간 복잡도

수행 시간 -> 1억 번의 연산 = 1초의 시간

최악일 때를 대비해야 함! -> 빅-오 O(n)

 

빅-오 표기법의 시간 복잡도 (데이터 크기 순)

O(n!)-O(2^n)-O(n^2)-O(nlogn)-O(n)-O(logn)

이때 상수는 간주하지 않음 n = 3n

따라서, 같은 차수의 반복문이 여러 개인 것은 의미 없음

하지만, 다른 차수의 반복문은 주의! ex) n과 n^2 -> 가장 많이 중첩된 반복문의 수행 횟수 = 시간복잡도의 기준

 

---

 

디버깅의 중요성

시간 제한, 변수 초기화 오류, 메모리 누수 방지를 위해 디버깅은 필수적임!

디버깅 대표사례

1. 반복문에서 변수 초기화 오류

반복문에서 다른 테스트 케이스로 결과 변수를 출력하는 경우, 테스트 케이스별로 결과 변수를 초기화하지 않음

-> 이전 반복문의 결과가 중첩되거나 변수가 음수로 출력되는 문제 발생!

2. 반복문에서 인덱스 범위 지정 오류

- 범위의 부등호 실수

- 시작값 설정을 잘못한 경우 -> 특히 인덱스는 0으로 시작한다는 점 주의! 

3. 잘못된 변수 사용 오류

- 출력이나 로직 안에서 사용해야 하는 변수를 다른 변수와 혼동함

 

코딩테스트 자주 하는 오답

자료형 설정

- int는 약 21억이 최댓값이라 계산 시 범위를 초과할 수 있음 

- 범위 초과 시 예상치 못한 음수 결과 출력

- 따라서, int보다 long형을 권장함

 

시간 초과

해결 방법

1. 풀이 로직의 시간복잡도가 제한 시간에 해결할 수 있는 검토

2. 입력과 출력 방식부터 최적화

Scanner와 System.out.print() 대신 BufferedReader와 BufferedWriter 사용

성능 차이의 이유

- 입력할 때마다 자료형 변환 과정 거치고, 출력이 발생할 때마다 버퍼를 비움 -> 비효율

- 입력을 버퍼에 저장한 후 데이터를 한 번에 읽어 옴, 출력할 데이터를 버퍼에 저장 후 한 번에 출력함 -> 효율적

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamReader(System.out));
int b - Integer.parseInt(br.readLine());
br.close();
bw.write(String.valueOf(b)); // 정수는 String형으로 변환 후 출력
bw.flush();
bw.close();

 

인덱스에 의미 부여

문제) 수 정렬 시 1000보다 작은 자연수 10,000,000개를 1초 안에 정렬

해결) 10,000,000의 갯수보다 1000범위에 초점! -> 계수 정렬

- 1001크기의 배열에 인덱스를 1~1000의 숫자 범위로 지정

- 1~1000중 숫자 입력 시 해당 인덱스의 값을 +1함

- 배열 값에 따라 반복하며 1000범위 안의 숫자들을 순서대로 저장 후 마지막에 한번에 출력함

따라서, 인덱스 = 단순한 순서가 아닌 의미를 부여하는 해싱 기법 사용!

 

나머지 연산의 중요성

자료형의 표현 범위를 초과하지 않고, 나머지 연산의 원리 이해가 필요함!

ex) 1부터 50까지 곱한 값을 10007로 나눈 나머지를 구하시오.

문제: 1부터 50까지 곱한 값은 long 자료형의 표현 범위 초과

해결: 나머지 연산의 분배 법칙 적용!

나머지 연산은 덧셈, 뺄셈, 곱셈의 분배 법칙이 성립함(나눗셈 제외) 

- (A + B) % C = ((A % C) + (B % C)) % C

- (A -  B) % C = ((A % C) - (B % C) % C)

- (A * B) % C = ((A % C) * (B %C) % C)

정답을 구한 후 마지막에 나머지 연산을 한 번만 적용하는 건 위험! 

따라서, 수행하는 과정마다 나머지 연산을 적용 후 마지막 결과에도 나머지 연산 적용!

(범위 초과 오류 예방 가능함)

 

정렬의 기초

1. 오름차순 

Arrays.sort(배열명)

- 시간 복잡도: O(n)

2. 내림차순

Arrays.sort(배열명, Collections.reverseOrder())

- 시간 복잡도: O(n)

음수로 활용

- negate(배열명)으로 배열의 값을 음수로 변환 후 

- Arrays.sort(배열명) -> 음수 기준으로 오름차순을 하니 결론은 내림차순 정렬이 가능함

 

다중 정렬

정렬 시 값을 비교하면 여러 조건에 맞게 정렬 가능함!

예를 들어, 영어 성적으로 정렬하면서 영어 성적이 동점인 경우엔 수학 성적으로 정렬함

1. Comparable 인터페이스

- 성적 클래스 정의, 성적 클래스에 인터페이스 상속

- 성적 클래스에 compareTo함수 override함

- 현재 성적과 비교할 성적을 비교 후 음수 또는 양수 반환

- 영어 성적이 같은 경우, 수학 성적 비교 후  음수 또는 양수 반환

Collections.sort(리스트명); -> 여러 조건에 맞게 정렬

 

2. Comparator 인터페이스

- 외부에 ScoreComparator 클래스 정의 후 Comparator<타입> 상속

- ScoreComparator 클래스 내에 compare 함수 override

Collections.sort(리스트명, new ScoreComparator()); -> 여러 조건에 맞게 정렬

 

Comparable은 한 클래스에 한 비교 함수만 구현 가능하지만,

Comparator은 외부에 선언해 여러 클래스에 비교 함수 구현 가능함.

 

이차원 ArrayList 사용

그래프 구조를 표현하는데 많이사용함 -> 그래프 관련 알고리즘에 사용

 

그래프의 구조

- 노드=원형, 에지 = 화살표

2차원 ArrayList를 이용한 그래프 구현

1. 2차원 ArrayList 선언과 초기화

-그래프의 Edge 클래스 생성(endNode, value로 구성)

- ArrayList<Edge> 리스트명[] = new ArrayList[리스트 크기];

- 리스트 크기만큼 반복하며 리스트의 값에 각각의 새 ArrayList를 할당

2. 그래프 데이터 저장

- 리스트의 인덱스 = 시작 노드로 의미 부여

- s(시작노드), e(끝 노드), v(가중치)의 3개의 값을 입력 받음(저장할 edge 개수만큼 반복)

ex) list[s].add(new Edge(e, v))

3. 그래프 데이터 가져오기

ex) 1번 노드인 경우 

- Edge tmp = list[1].get(i) 여기서 i는 0부터 list[1].size()범위까지 가져옴