자바로 코딩테스트 준비 (1) : 학습법, 효율적인 준비법, 알고리즘 효율 분석

학습법

기본골자: 이론 학습 -> 연습 문제 -> 모의 테스트

 

프로그래머스 활용이 학습에 좋음

• 남의 풀이를 보며 접근방식 개안, 대신 숏코딩은 걸러,
• 내 테스트 케이스를 바로 추가하여 테스트 해볼수 있음 : 테스트 케이스 작성만으로도 이해도 향상

---

아는 것과 모르는 것을 명확히 하라

1. 안풀릴때 그냥 답지를 본다? -> XXX 내가 어디까지 알고 어디까지 모르는지 알 방법이 없어.나만의 답 추적 노트를 작성하고 나서 답지를 본다 -> ㅇㅇ 내가 어디까지 아는건지는 체크가 가능하니까
2. 시험보듯
   긴장감 + 단시간 집중력
3. 꾸준하게
   벼락치기가 의미 없는 문제해결능력, 그저 드립따 외우는게 아니니까
4. 요약정리나만의 언어로 요약하는건 문제해결 과정을 복습하는 최고의 방법

---

효율적인 준비법

 

언어선택: 자신있는 언어, 자신있어 지고 싶은 언어

---

문제 분석 순서 연습 

문제 쪼개기: 쪼개서 분리할 수 있는 연산은 쪼개서 생각

 

제약 사항 파악: 테스트 케이스 생각 -> 예외 사항 생각 -> 문제를 이해하게 됨

 

입력갑 분석: 입력값의 크기와 속도 제한으로 사용할 시간복잡도가 추려짐.

 

그리디한 접근은: 반드시 의사코드 단계에서 근거가 명확해야함.

 

데이터 흐름 파악: 자료구조에대한 이해를 동반

---

의사 코드로 설계 연습

원칙 :  프로그래밍을 하면 안됨, 일반인이 이해가능한 자연어, 일정한 형식은 없음

 

첫째 세부 구현X 동작 중심 ㅇ

ex 국어, 영어, 수학 점수를 입력받는다. -> o

ex 크기가 256바이트인 문자열 배열을 만든뒤에 ~~~ ->XXX 

 

세부 구현은 나중에 고민하는거고 지금은 흐름과 동작을 깔끔하게 정리하는것만 고려해야함.

 

둘째 문제 해결 순서로 작성해야함-> 흐름 파악

의사 코드는 나중에 주석으로 그 의사코드를 이렇게 구현했어요 정리해야하기 때문에 문제 해결 순서대로 잘 정리된 의사코드는 구현이 편해짐.

 

셋째 의사 코드 단계에서 충분히 테스트

실제 프로그래밍을 구현하기 이전에 계산기나 머리와 펜을 이용한 식으로도 충분히 테스트가 가능함. 테스트가 잘 완료된 의사코드여야 구현이 한번에 깔끔하게 떨어짐.

---

알고리즘 효율 분석

빅오 표기법: 속도를 함수로 나타낼때 최고차항만 고려하여 표기하는거
자질구레 이래저레 따지지말고 무한히 x입력이 증가할때 속도의 크기만 비교하고싶어

 

시간 복잡도 계산해보기

순서: 문제 정의 -> 연산 횟수 측정 -> 시간 복잡도 분석

<단순 별찍기>
N번 만큼 반복 돌리는데 N번만큼 찍겠네
-> N^2 

푸는 과정
1번 줄은 1번 연산 N번줄은 N번 연산
그리고 총합이 연산 횟수

f(N) = 1+2+...+N = (N(N+1))/2

수열: 일정한 규칙에따라 수들이 나열된거
수열의 함수화: 첫째항 둘째항 셋째항
f(1)=1 f(2)=2 f(3)=3
수열의 정의역: 자연스럽게 자연수만 생각해도 됨.
일반항 = f(n) = n

f(n)=an

자 되었고 등차수열 합은 뭔데?
1 +2 + ...+ 99 + 100 = A
100+99+...+ 2 + 1 = A
101 + 101 +...+101 = 2A
2A = 101*100
A = (101+100)/2
따라서 등차수열의 합은 (N(N+1))/2

<박테리아 수명 문제>
초기 박테리아 수에서 세포개수는 이전 세포 개수의 반으로 계속 줄어든다면 언제 죽을지 출력

푸는 과정
식세우기: f(n)=16 f(n/2)=8 f(n/4)=4 f(n/8)=2 f(n/16)=1 f(n/32)=0
따라서 5년인데

등비 수열 N의 d=1/2 1보다 작은 값을 만드는 y+1항은 y년뒤잉고 (1/2)^y*N 이때 y를 찾는 식을 도출

1 > ((1/2)^y)*N
1/n > (1/2)^y
1/n > 1/(2^y)
n < 2^y
log2(n) < y

n이 주어지면 log2(N)을 이용해 y년도를 구할 수 있음. 실제 log2(n)은 4 이고 1보다 작게 만들어야하는게 원칙이므로 1년 뒤인 한번 더 5년이 정답이 되는 것 빅오도 log(n) 회이다.

 

---

시간 복잡도와 입력값에따른 1초 제한 : 이건 암기 영역

시간 복잡도	N 범위
O(N!)	10
O(2^N)	20~25
O(N^3)	200~300
O(N^2)	3,000~5,000
O(NlogN)	100만
O(N)	1,000~2,000만
O(logN)	10억