이번 시간엔 시간복잡도의 개념과 다양한 알고리즘 문제를 풀었다. 하 쉽지 않았다. 함께한 페어분도 나처럼 어려워하셔서 둘이 머리를 꽁꽁싸맸다.
매번 느끼는거지만 내가 아는 최대한의 지식을 남에게 설명하는것은 큰 도움이 되는 것 같다. 페어활동을 진행할때 어떤분들은 나에게 질문을 던지고 자꾸 물어봐서 민폐 끼치는 것 같아 죄송하다고 하지만, 나는 내가 답변해줄때 공부도 되는 것 같고 좋은데 가끔 그렇게 느끼시는 분들이 계신다.
시간복잡도를 대학교 전공시간에 배운 기억이 난다 그당시에는 이걸 배워서 뭐에 써먹어? 라고 생각을 했었는데 코딩테스트에서 제한된 시간 내에 반환하는 프로그램을 작성할때 필요했구나 ... 이번에 공부를 하면서 새롭게 알게 됐다.
내가 알고리즘 짜는 실력이 너무 부족한 것 같아 다양한 문제를 풀어볼려고 알고리즘 책을 샀다 근데 기초를 샀어야했나.. 3장을 넘기니까 바로 백준 골드3 레벨 정도의 문제가 바로 나온다.. 잘못 산듯.. 책 제목에 기초가 붙은 걸로 새로 주문 해야겠다 ㅠㅠ
시간 복잡도
알고리즘에서 시간 복잡도는 주어진 문제를 해결하기 위한 연산 횟수
일반적으로 수행 시간은 1억 번의 연산을 1초의 시간으로 간주하여 예측한다.
시간 복잡도를 정의하는 3가지 유형
- Big-Ω(빅-오메가)- 최선일 때의 연산 횟수를 나타낸 표기법
- Big-θ(빅-세타) - 보통일 때의 연산 횟수를 나타낸 표기법
- Big-O(빅-오) - 최악 일때의 연산 횟수를 나타낸 표기법 ★ 코딩 테스트에서 주로 사용되는 시간 복잡도
출처 : http://bigocheatsheet.com/
위 차트에서 보듯 각각의 시간 복잡도는 테스트 크기(N)의 증가에 따라 성능(수행 시간)이 다르다
정규 표현식
정규표현식 - 문자열에서 특정한 규칙에 따른 문자열 집합을 표현하기 위해 사용되는 형식 언어
정규표현식을 익힐 수 있는 웹페이지
https://www.regexplanet.com/
