코테 도전기1

 

코테 준비를 위해 이론 공부를 정리해보고자 한다.

스타뜨!!

 

 

오답노트

먼저 잘 틀리는 유형들을 정리해보자

 

1. 자료형

- 흔히 int 형을 주로 사용하는데, 간혹 int 형을 사용했을 때 범위를 초과하는 경우가 있다.

 

1) int 

- > 약 -20억 ~ 20억

 

2) long 

-> -9223372036854775808 ~ 9223372036854775808

 

범위 초과가 우려된다면 long을 사용하자.

 

 

 

 

 

2. 시간 초과

- 시간 초과 문제를 해결하기 위해서는 고려해야할 것들이 많지만 그중에서도 입출력 최적화를 고려해야한다.

 

1) Scanner와 System.out.println

- Scanner는 입력할 때마다 필요한 자료형으로 변환된다 -> 시간 소요

- System.out.println는 출력 발생 시 버퍼를 비운다. -> 시간 소요

 

 

2) BufferedReader 와 BufferedWriter

- BufferedReader는 입력을 버퍼에 저장해두고 한 번에 데이터를 읽어온다.

- BufferedWriter는 출력을 버퍼에 저장해두고 한 번에 데이터를 출력한다. -> write()로 데이터를 버퍼에 추가하고, flush()로 한 번에 출력한다. 

 

 

 

3. 나머지 연산

- 나머지 연산은 나눗셈 제외하고 덧셈, 뺄셈, 곱셈의 분배 법칙이 성립한다.

 

1) 자료형 범위 오버

- 만약 마지막에 나머지 연산을 한 번에 하는 경우에 자료형의 범위가 오버될 수 있다.

-> 그래서 예를 들어 '곱셈을 실행할 때마다 나머지 연산을 함께 수행하도록 코드를 수정'하면 정상으로 출력된다.

 

즉, 로직의 중간 과정마다 나머지 연산을 지속적으로 수행함으로써 자료형의 표현 범위 초과하지 않도록 한다.

 

for(int i=0; i<=50; i++){
	answer = (answer*i) % 10007;
}

 

 

 

 

 

4. 정렬

 

1) 오름차순

- Arrays.sort() 함수 사용해서 오름차순 정렬이 가능하다. 

 

 

2) 내림차순 

 

- 배열을 클래스형으로 선언했을 때 Collections.reverseOrder()를 이용할 수 있다.

Integer[] A = {5,3,2,4,1};
Arrays.sort(A, Collections.reverseOrder());
System.out.println(Arrays.toString(A));

 

 

- 단, 클래스형으로 선언했을 때가 많지 않으므로 다른 방법도 생각해야한다.

- 부호를 바꿔서 오름차순으로 정렬한 뒤 다시 부호를 바꾸는 방법이 있다.

int[] a = {5,3,4,1,2};
negate(a) -> 부호 반전
Arrays.sort(a);
negate(a);

 

 

 

 

5. 다중 정렬

 

 

1) Comparable 인터페이스

 

- implements Comparable<T>

-> 오버라이드해서 사용

 

@Override
public int compareTo(Score o){
	if(this.eng == o.eng) return o.math - this.math;
   	return o.eng - this.eng;
}

 

 

** o는 뭐?

o는 compareTo의 매개변수. 즉 비교하려고 같이 넘어온 ‘다른 Student 객체’.

정렬 알고리즘이 내부에서 이런 비교를 계속한다. :

• a.compareTo(b) 를 호출해서
• a와 b 중 누가 앞에 와야 하는지 물어본다.

그때

• a가 this
• b가 o

 

 

2) Comparator 인터페이스

@Override
public int compare(Score o1, Score o2){
	if(o1.eng == o2.eng) return o2.math - o1.math;
   	return o2.eng - o1.eng;
}

 

 

 

 

3) 둘의 차이는 ?

 

• Student를 정렬하는 기준이 딱 하나로 고정(“우리는 무조건 학번순”) → Comparable
• 정렬 기준이 여러 개 필요(점수순/이름순/나이순 등 상황별) → Comparator

&

 

 

• Collections.sort(list)만 쓰고 싶다(기본정렬) → Comparable
• list.sort(기준)처럼 기준을 넣어서 정렬하고 싶다 → Comparator

 

 

 

 

 

4) compareTo/compare의 규칙

 

정렬에서 비교 함수가 a.compareTo(b)(또는 compare(a,b))를 호출했을 때:

• 음수면 → a가 b보다 앞(a < b)
• 0이면 → 순서 같음
• 양수면 → a가 b보다 뒤(a > b)

즉, 리턴값의 “부호(+, -, 0)”로 앞/뒤를 결정

 

 

 

5) 정리

 

- 내림차순 = o.eng - this.eng

- 오름차순 = this.eng - o.eng

 

만약 오버플로우가 우려된다면 return o.name.compareTo(this.name);  -> 내림차순 , 이렇게 작성할 수 있음.