24.01.16 피보나치수열, 퀵정렬, Python, 백준, 완전탐색 알고리즘, 이진탐색 알고리즘

피보나치 수열

• 피보나치 수열의 각 항에 있는 수들을 ‘피보나치 수(Fibonacci number)’ 라고 한다
• Fn+2 =Fn+1 + Fn

퀵 정렬(QuickSort)

def quick_sort(a = list):
	if len(a) <= 1:
		return a
	pivot = a[len(a)//2]
	less_arr,equal_arr,greater_arr = [],[],[]
	for i in a:
		if i < pivot:
			less_arr.append(i)
		elif i > pivot:
			greater_arr.append(i)
		else:
			equal_arr.append(i)
	return quick_sort(less_arr) + equal_arr + quick_sort(greater_arr)

• 여기서 피벗을 더 좋게 바꾸는 것도 도전해보자.
• 내일 화이트보드에 코드 구현 해보기 🎆

Python

sys.stdin.readline() 쓰는 이유

input()이 느린 이유

1. input()은 매개변수로 prompt message를 받는다. (입력을 받기 전에 prompt message를 출력해야 한다.)
2. 입력받은 값의 개행 문자를 삭제시키고 반환한다.

• 이러한 단계를 거치기 때문에 input()은 비교적 속도가 느리다.

sys.stdin.readline() 의 특징

• 문자열로 입력을 받는다.
• 개행 문자 ‘\n’을 같이 입력받는다.
• strip()을 이용해 개행 문자 없이 문자열을 입력받을 수 있다.

집합(Set)

• Python 집합은 고유한 요소의 모음이다. 집합의 목적은 단일 변수에 여러 항목을 저장하는 것이다.
• 특징
  • 순서가 없다(인덱스로 접근하지 못한다.)
  • 중복은 허용되지 않는다.
  • 요소는 변경 불가능한 자료형만 사용할 수 있다.
• 집합은 순서가 없기 때문에 인덱스로 접근할 수 없다. 인덱스로 요소에 접근하려고 하면 TypeError가 발생한다.
• 합집합 - union()
• 교집합 - Intersection()
• 차집합 - difference()

람다(Lambda) 함수

• 함수형 프로그래밍에서 중요한 개념 중 하나로, 익명 함수(anonymous function)라고도 부른다. 람다 함수는 이름이 없는 함수로, 일반적으로 함수를 한 번만 사용하거나 함수를 인자로 전달해야 하는 경우 매우 유용하게 사용된다.

lambda 인자 : 표현식

• map, filter,sorted, reduce 함수와 자주 사용한다.

파이썬 join 함수

• ‘’.join(리스트) , ‘구분자’.join(리스트) 형태
• join 함수는 매개변수로 들어온 리스트에 있는 요소 하나하나를 합쳐서 하나의 문자열로 바꾸어 반환하는 함수이다.
• for문에 비해서 시간복잡도를 줄일 수 있다.

백준

18258 큐2

• 리스트로 구현을 했다.
• pop()시 맨 앞의 원소를 remove()로 제거했는데, 그럴 경우 원소가 한칸씩 앞으로 이동 해야해서 시간초과 오류가 발생했다.
• 파이썬 내장함수 collections에서 덱(double-ended queue을 사용해서 해결했다.

from collections import deque #덱

2309 일곱 난쟁이

• 완전탐색
• 9명의 합을 구하고 2명을 뺏을 때 100이 되는 경우를 찾아서 문제를 해결했다.
• 내일 다시 풀어보자

1920 수 찾기, 2805 나무자르기

• 이분탐색
• 내일 다시 풀어보자 222

Algorithm

완전탐색(ExhaustiveSearch)

• 간단히 가능한 모든 경우의 수를 다 체크해서 정답을 찾는 방법.
• 무식하게 한다는 의미로 ‘BruteFroce’ 라고도 부르며, 직관적이여서 이해하기 쉽고 문제의 정확한 결과값을 얻어낼 수 있는 가장 확실하며 기초적인 방법이다.

완전탐색 기법을 활용하는 방법

1. 해결하고자 하는 문제의 가능한 경우의 수를 대략적으로 계산한다.
2. 가능한 모든 방법을 다 고려한다.
   1. BruteForce기법 - 반복/조건문을 활용해 모두 테스트 하는 방법
   2. 순열(Permutation) - n개의 원소 중 r개의 원소를 중복 허용 없이 나열하는 방법
   3. 재귀호출
   4. 비트마스크 - 2진수 표현 기법을 활용하는 방법
   5. BFS,DFS를 활용하는 방법
3. 실제 값을 구할 수 있는지 적용한다.

이진탐색(BinarySearch)

• 이진탐색(이분 탐색) 알고리즘은 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법이다.
• 이진탐색은 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘이다.
• 변수 3개(start,end,mid)를 사용하여 탐색한다. 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는 것이 이진탐색의 과정이다.

def binary_search(target,start,end):
	if start >= end:
		return 0
	mid = (start + end) // 2
	
	if target == mid:
		return 1
	elif target > mid:
		start = mid + 1
	else:
		end = mid -1
	return binary_search(target,start,end

• 시간 복잡도는 O(logN) 이다.