코딩테스트를 준비하자

의사코드

프로그래밍 언어로 코드를 작성하기 전에 일상 언어로 프로그램이 작동하는 논리를 먼저 작성하는 것

 

문제 이해 -> 의사코드 -> 개발 언어

기초적인 부분부터 구체적이고 상세하게 명령

노트북 켜는 것을 수도코드로 작성

 

public void openLaptop() {

//노트북을 연다

//노트북의 전원 버튼을 누른다

//if (이용할 사용자가 여러명이면) 사용자를 고른다
	//if (비밀번호가 있다면) 번호를 입력한다

	//else (비밀번호가 없으면) 이용할 사용자만 클릭한다
//else (사용자가 1명이면) 엔터 || 클릭을 이용한다
	//비밀번호 유.무 if/else문

//엔터 || 클릭을 해서 로그인을 완료한다

 

시간 복잡도

입력값의 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 시간이 얼마만큼 걸리는가?

• Big-O(빅-오): 최악 "이 정도 시간까지 걸릴 수 있다"
• Big-Ω(빅-오메가): 최선
• Big-θ(빅-세타): 중간

 

1. Big-O 표기법

입력값의 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 시간이 얼마만큼 걸리는가?

 

1. O(1)

• 즉시 출력값 얻을 수 있음

1. O(n)

• 입력값이 증가함에 따라 시간 또한 같은 비율로 증가하는 것

1. O(log n)

• 원하는 값을 탐색할 때, 노드를 이동할 때마다 경우의 수가 절반으로 줄어듦
• up&down 게임과 유사

1. O(n^2)

• 입력값이 증가함에 따라 시간이 n의 제곱수의 비율로 증가하는 것

1. O(2^n)

• Big-O 표기법 중 가장 느린 시간 복잡도

 

탐욕 알고리즘(Greedy)

 

선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법

• 선택 절차(Selection Procedure): 현재 상태에서의 최적의 해답을 선택
• 적절성 검사(Feasibility Check): 선택된 해가 문제의 조건을 만족하는지 검사
• 해답 검사(Solution Check): 원래의 문제가 해결되었는지 검사하고, 해결되지 않았다면 선택 절차로 돌아가 위의 과정을 반복

 

완전 탐색 알고리즘(Brute-Force Algorithm)

Brute Force Algorithm 무차별 대입 방법

 

모든 가능성을 시도하여 문제를 해결하는 방법

사용하는 곳 순차검색 알고리즘, 문열 매칭 알고리즘, 선택 정렬 알고리즘 등

 

이진 탐색 알고리즘(Binary Search Algorithm)

데이터가 정렬된 상태에서 절반씩 범위를 나눠 분할 정복기법으로 특정한 값을 찾아내는 알고리즘

1. 정렬된 배열의 가장 중간 인덱스를 지정
2. 찾으려고 하는 값이 지정한 중간 인덱스의 값이라면 탐색을 종료
3. 아니라면 3단계로
4. 찾으려고 하는 값이 중간 인덱스의 값보다 큰 값인지, 작은 값인지 확인
5. 값이 있는 부분과 값이 없는 부분으로 분리
6. 값이 있는 부분에서 다시 1단계부터 반복

 

데이터를 찾을 때 사용하는 방법 ex) 사전검색, 대규모 시스템에 대한 리소스 사항 파악 등