Do it - 알고리즘 코딩테스트 1일차

코딩 테스트 준비하기

• 코딩 테스트와 관련된 학습을 시작하기 전 반드시 알아야 할 두 가지 스킬인 시간 복잡도와 디버깅을 알아보자.

 

어떤 알고리즘으로 풀어야 할까?
알고리즘 선택의 기준이 되는 시간 복잡도

• 코딩 테스트의 핵심 중 하나는 문제마다 주어진 시간 복잡도를 고려해 적절한 알고리즘을 선택하는 것이다.

 

• 시간 복잡도 표기법 알아보기
  • 알고리즘에서 시간 복잡도는 주어진 문제를 해결하기 위한 연산 횟수를 말한다.
  • 일반적으로 수행 시간은 1억 번의 연산을 1초의 시간으로 간주하여 예측한다.
• 시간 복잡도 정의하기
  • 실제 시간 복잡도를 정의하는 세 가지 유형은 다음과 같다.

빅-오메가 : 최선일 때( best case )의 연산 횟수를 나타낸 표기법

빅-세타 : 보통일 때( average case )의 연산 횟수를 나타낸 표기법

빅-오 : 최악일 때( worst case )의 연산 횟수를 나타낸 표기법

• 코딩 테스트에서는 어떤 시간 복잡도 유형을 사용해야 할까?
  • 코딩 테스트에서는 빅-오 표기법을 기준으로 수행 시간을 계산하는 것이 좋다.
  • 실제 테스트에서는 1개의 테스트 케이스로 합격, 불합격을 결정하지 않는다. 응시자가 작성한 프로그램으로 다양한 테스트 케이스를 수행해 모든 케이스를 통과해야만 합격으로 판단하므로 시간 복잡도를 판단할 때는 최악일 때를 염두에 둬야 한다.
  • 빅-오 표기법으로 수행할 경우 각각의 시간 복잡도는 데이터 크기의 증가에 따라 성능( 수행 시간 )이 다르다.

 

코드의 논리 오류를 어떻게 잡을까?
가장 뛰어난 오류 탐색 방법, 디버깅

• 코딩 테스트에 떨어진 응시자 중 코드에서 논리 오류를 찾아내지 못해 코딩 테스트를 통과하지 못하는 안타까운 경우가 종종 발생한다. 이러한 상황에서 논리 오류를 찾을 수 있는 가장 최선의 방법은 '디버깅'이다.

 

• 디버깅은 왜 중요할까?
  • 프로그램에서 발생하는 문법 오류나 논리 오류를 찾아 바로잡는 과정을 디버깅이라고 한다.
  • 문법 오류는 컴파일러가 자동으로 찾아 주므로 테스트할 때 문제가 되지 않는다.
  • 논리 오류는 코드가 사용자의 의도와 다르게 동작하는 것이며 다양한 형태로 발생한다.
• 디버깅하는 법
  • 코드에서 디버깅하고자 하는 줄에 중단점을 설정한다. 이때 중단점은 여러 개 설정할 수 있다.
  • IDE의 디버깅 기능을 실행하면 코드를 1줄씩 실행하거나 다음 중단점까지 실행할 수 있으며, 이 과정에서 추적할 변숫값도 지정할 수 있다. 이 방버븡로 변숫값이 자신이 의도한 대로 바뀌는지 파악한다.
  • 변숫값 이외에도 원하는 수식을 입력해 논리 오류를 파악할 수도 있다.
    • 변숫값 추적은 이클립스의 Expressions 기능을 활용하면 된다.

 

• 대부분의 코딩 테스트에서 계산되는 값들은 long형 안에서 표현할 수 있으니 변수를 선언할 때는 처음부터 long형으로 선언하는 것도 나쁘지 않다.
•