[코딩 테스트 합격자 되기 : 자바 편] 2. 프로그래머스 채점 기준 + 3. 알고리즘의 효율 분석

---

2. 프로그래머스 채점 기준 알아보기

정확성 테스트란?

• 제출한 코드가 정답을 제대로 출력하는지 확인
• 각 테스트 케이스 전부 10초 이내로 수행

효율성 테스트란?

• 알고리즘의 성능 확인

---

3. 알고리즘의 효율 분석

시간 복잡도란?

• 시간복잡도(time complexity)란, 알고리즘의 성능을 나타내는 지표로, 입력 크기에 대한 연산 횟수의 상한을 의미
• 시간 복잡도는 낮으면 낮을수록 좋음

1차원 배열 검색하기

• 값을 가장 빨리 찾는 경우 : 시작 위치에 있는 경우 ⇒ 1
• 값을 가장 늦게 찾는 경우 : 값이 없거나 마지막에 위치 ⇒ 연산횟수가 최대 n

 

알고리즘 수행 시간을 측정하는 방법

절대 시간을 측정하는 방법

• 진짜 시간 측정

시간 복잡도를 측정하는 방법

• 연산 횟수를 나타냄
• 시간 복잡도 측정 결과
  • 최선 best
  • 보통 normal
  • 최악 worst
• 입력 크기를 N으로 일반화 하여 연산 횟수의 추이 나타내기
• 입력 크기에 따른 연산 횟수의 추이를 활용해서 식나 복잡도를 표현하는 방법은 점근적 표기법이라고 함
• 코테는 모든 경우의 수에서 알고리즘 처리 ⇒ 시간 복잡도 최악 가정

 

최악의 경우 시간 복잡도를 표현하는 빅오 표기법

• 상한선을 활용하는 점근적 표기법 = 빅오 표기법
• (상한선은 빅오 표기법, 하한선은 빅오메가 표기법)
• 최고차항으로 표기 O(N^2)

빅오 표기법을 쉽게 쓸 때는 왜 최고차항만 남기고 계수를 지울까?

• 로그함수는 다항함수보다 느리게 증가하고, 지수함수는 다항함수보다 빠르게 증가
• 그러므로 최고차항만 남기는 작업에서 우선순위는 지수 > 다항 > 로그

 

시간 복잡도를 코딩 테스트에 활용하는 방법

• 코딩 테스트 문제 시간 제한 ⇒ 문제 분석 후 빅오 표기법으로 시간 내에 출력값 나올지 확인
• 보통은 “컴퓨터가 초당 연산할 수 있는 최대 횟수는 1억 번이다”를 기준으로 알고리즘 선택
• 연산 횟수는 1,000~3,00만 정도로 고려해서 시간 복잡도 생각

시간 복잡도 계산해보기

1. 문제 정의
2. 연산 횟수 측정
3. 시간 복잡도 분석

별 찍기 문제 O(N^2)

박테리아 수명 문제 O(logN)

• 특정값을 계속 반으로 줄이는 동작을 한다면 시간 복잡도를 O(logN)이라 생각하면 됩니다.
• 시간 복잡도가 O(logN)인 문제 ⇒ 정렬, 이진 트리 등

기억하기

1. 입력 크기에 따른 연산 횟수의 추이를 활용해서 시간 복잡도를 표현하는 방법을 점근적 표기법이라고 합니다.
2. 시간 복잡도를 빅오 표기법으로 나타내려면 데이터 개수 N에 대해 연산 횟수를 일반화한 후 최고차항을 남기고 계수를 제거하면 됩니다.

---

해당 글은 다음 책을 참고하여 공부하며 정리한 글입니다. 

https://ebook-product.kyobobook.co.kr/dig/epd/ebook/E000006973689

코딩 테스트 합격자 되기: 자바 편 | 김희성 | 골든래빗(주)- 교보ebook