정규 표현식
정규 표현식을 사용하기 위해
import re
regex의 약자
re.compile(r"^[\w\.-}+@([\w-] 어쩌구
이런거 외우지 말고 정규표현식 코드 짜는거 어려우니 어디서 가져다가 사용해라
정규표현식 사이트를 들어가 보면 알려준다.
언어마다 정규식을 사용하는 방법이 달름, python password validait
나눗셈을 조금 다른 방법으로 하기
int.__floordiv__
int 클래스에 내장된 매서드
divmod 몫과 나머지를 구함
알고리즘 강의 - 강민철 튜터님
스택/ 큐 정렬
지난 시간에 한것 linked list
import random은 진짜 랜덤값이 아니다.
스택 큐 정렬 에 대해서 알아보다.
스택 한쪽 끝이 막혀있는 통 같은 자료구조
스택에 저장한다 스택에 푸시한다.
스택에서 팝 한다. 스택에서 나간다.
스택에서 데이터를 뺄 경우 위부터 빠져나감
나중에 삽입된 데이터가 먼저 나오는 자료구조
큐 개념
양쪽 끝이 뚫려 있는 통과 같은 자료구조
먼저 삽입된 데이터가 먼저 나오는 자료구조
인큐-> 데이터 들어감 디큐=> 데이터 나옴
큐 , 스택 활용
그래서 이 알고리즘이 어디에 / 어떻게 쓰이는데?
스택의 활용
데이터를 임시저장하고 싶을 때
최근에 임시저장한 데이터를 가장먼저 활용
쌍을 맞추어 데이터를 임시저장하고 싶을때
뒤로가기기능
괄호 ((( )))
여는괄호 푸시 닫는괄호 팝
매개변수 , 지역변수
큐의 활용
데이터를 임시 저장하고 싶을 때
버퍼로서 활용하고 싶을 때
줄을 세우고 싶을때
임시 저장된 데이터를 차례차례 내보내야/꺼내와야 할때
실습
스택선언: 파이썬에서는 주로 리스트 활용
큐 변형
원형큐
front rear
front와 rear가 동적으로 움직이면서 데이터를 저장하고 삭제함
덱
더블 엔디드 큐
양쪽에서 데이터 삽입, 삭제
우선순위 큐
먼저 저장된 데이터가 먼저 나가는 구조가 아닌
저장된 순서와 무관하게 '우선순위가 높은' 데이터가 먼저나감
정렬의 개념 -
데이터를 정해진 기준에 따라 재배치하는 것
다양한 정렬 알고리즘이 존재
버블정렬
선택정렬
삽입 정렬
퀵정렬
정렬 알고리즘마다 시간 복잡도가 다르다.
\
sorted 정렬한 대상이 바뀌지는 않는다
sort 정렬한 대상이 바뀐다.
파이썬 내장 정렬 함수
내장 함수만으로 풀 수 있는 문제
정렬 알고리즘의 원리를 묻는 문제
다양한 정렬 알고리즘 = 삽입정렬
시간복잡도 O(n^2)
앞에서부터 차례대로비교하여 , 자신의 위치를 찾음
[5,2,9,1,5,6]
[1,2,5,5,6,9]
배열의 인덱스 조작하기
버블 정렬
요소를 쭉 순회하며
인접한 요소와 비교하며 정렬이 제대로 되었는지 확인하며
정렬이 제대로 될 때까지 인접한 요소와 바꿔치기하는 방법
시간 복잡도 n^2
선택 정렬
최소값을 찾고
맨앞으로 대체 -> 나머지 중에서 다시 최소값을 찾음
다시 맨앞으로 대체
퀵 정렬
분할 정복 알고리즘의 일종
큰 문제를 작은 분리하여 작은 문제들을 해결함으로서 큰 문제를 해결
이름처럼 빠른정렬: 시간 복잡도 nlogn 배열이 정렬되어
1. 기준점 피벗을 하나 고른다.
피벗보다 작은 부분집합, 피벗보다 큰 부분집합을 선정한다.
2. 피벗의 좌, 우를 기준으로 정렬한다. 정렬 뒤 피벗은 더이상 움직이지 않는다.
피벗 앞에는 피벗보다 값이 작은 모든 원소들이 오고,
피벗 뒤에는 피벗보다 값이 큰 모든 원소들이 오도록 피벗을 기준으로 둘로 나눈다.
3. 분할된 두 개의 작은 배열에 대해 재귀적으로 이 과정을 반복한다.