Java 코딩 테스트 특강(1)

<시간복잡도>

big O 를 사용하는 이유

최악을 알 수 있어서(최악을 피하기 위해)
-> 왜 최악을 중요하게 생각하는가? = 입력값을 통제할 수 없으니까

대략적인 빅오
O(1)
O(logN)               - 상한 기준 27
O(N)                   - 상한 기준 1억
O(N * logN)          - 상한 기준 10만 ~ 100만
O(N^2)                - 상한 기준 10000
O(N^2 * logN)
O(N^3)                - 상한 기준 500

1억이 상한이다 라고 기억해주세요
로그는 한 번씩 할 때마다 절반으로 나뉜다라고 생각해주세요(업앤다운)


자, 그럼 n을 어떻게 알 수 있냐? n이 미지수일때 어떡하냐?
일단 정답은 N은 미지수일수가 없어요.

<알고리즘의 정의>
1.문제해결절차
2.how to solve

정확하게는!

"A finite set of intructions that solve the given problem"
모든 알고리즘은 시작과 끝이 있음
시작부터 끝까지 '순서대로' 해결하는 게 알고리즘
시작과 끝이 있기 때문에 N은 미지수X
(N을 계산하는법은 많이 풀면서 체화해야함..)


(중요) 코테문제는 모두 프로그래밍 언어 없이 풀 수 있어야 합니다.
->문제를 분석하고 설계하는게 중요한거지 일단 키보드에 손 부터
   올라가면...................................... 놉!!!!!!!!!!!!!!!

 

<코딩테스트 문제 유형 및 학습 순서>

구현(주어진 조건을 빠짐없이 잘 짤 수 있는지) : 문해력테스트에 가까움
완전탐색(순열, 조합, DFS, BFS)
이진탐색(대표적인 로그 알고리즘 1)
최소힙, 최대힙(대표적인 로그 알고리즘 2)
최단거리(다익스트라, 벨만-포드, 플로이드-와샬)
다이나믹 프로그래밍
분할 정복(로그 알고리즘에 속함)
---------------------------------------------
최소 신장 트리(MST)
구간합
---------------------------------------------
탐욕 알고리즘 간단하게 공부하기(정말 쉽게나오거나 정말 어렵게 나옴)


여러분들이 문제 풀 때 생각할 것
N^2 이나 N^3 으로 알고리즘을 생각해보고
N을 대입해봤는데 1억이 넘는다면?
1. N이 잘못설정되지 않았는지 먼저 재검토
2. 1이 아니라면 log 알고리즘 사용하기
->로그 알고리즘 종류가 이진탐색,최소최대힙,다이나믹,분할정복

<학습방법>
1. 1137 - 복습의 주기(1시간, 1일, 3일, 7일)
2. 알고리즘은 낯선 것이지 어려운 게 아니다(복습으로 익숙하게 만들자)
3. 할 수 있다!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

<공간복잡도 가이드>
1GB에 근접하면 다시 생각해보자
-자료구조를 새롭게 생성해서 저장하는 경우


<프로그래머스 1레벨에서 풀 문제들>
2018 KAKAO BLIND RECRUITMENT 
2019 KAKAO BLIND RECRUITMENT 실패율
2019 카카오 개발자 겨울 인턴십 
2020 카카오 인턴십 
2021 카카오 채용연계형 인턴십 
공원 산책 
로또의 최고 순위와 최저 순위 
신고 결과 받기
키패드 누르기

 

 

 

-위의 내용은 코드스테이츠에서 제공하는 '수료 후 특강' 중 'Java 코딩테스트 대비 문제풀이' 의 내용을 요약한 것 입니다.

-내용 출처 : code states