[이.코.테] 복잡도

 

 

예전에도 잠깐 파이썬을 배운 적 있고 (6주 네이브 부스트캠프 강의 들음)

이번에 방송대에서 파이썬 강의를 들으면서 파이썬의 간단한 문법에 대해 배웠다.

(물론 다시 찾아보면서 공부해야할거다..)

 

정식으로 공부를 시작한 언어는 자바라서 자바에 애정이 깊지만, 

알고리즘 문제를 풀기 시작하면서.. (C에 비하면 간결하지만) 자바의 구구절절함에 비해

짧고 이해하기 쉬운 파이썬 문법이 부럽고 배우고 싶어졌다.

 

그래서 알고리즘 공부는 파이썬으로 해야겠단 마음을 먹고 

그쪽 분야에서 유명한 책을 알라딘에서 구했다!

 

 

 

알고리즘이 뭐길래 나를 이렇게 따라다니나..

개발자라면 벗어날 수 없는 알고리즘 마수를 직접 대면해보기로 했다.

그리고 회사에서 코드를 짤 때, 실행 속도와 용량을 계속 신경쓰시는 팀장님을 보며

대체 어떤 부분이 영향을 미치는지 알아야겠다는 생각이 들기도 했다.

느리더라도, 몰랐던 부분을 학습하고 개념에 익숙해지길 바라며.

시작합니다~~

 

 

1. 실습 환경 설정

 

파이참 깔기 귀찮아서 리플릿이라는 온라인 IDE 를 사용해보려고 한다.

 

https://nadocoding.tistory.com/103

파이썬 개발 환경설정 - Repl.it

 

 

 

2. 복잡도란?

 

복잡도(Complexity)는 알고리즘의 성능을 나타내는 척도로, 낮을수록 좋은 알고리즘이다.

• 시간 복잡도 -- 특정한 크기의 입력에 대하여 알고리즘이 얼마나 오래 걸리는지 (연산 횟수)
• 공간 복잡도 -- 특정한 크기의 입력에 대하여 알고리즘이 얼마나 많은 메모리를 차지하는지 (메모리 양)

보통 알고리즘 테스트에서 복잡도는 시간복잡도를 의미한다.

시간복잡도와 공간복잡도 모두 빅오(Big-O) 표기법을 주로 쓰는데, (다른 표기법에 비해 평가하기 편하다는 이유로)

O(N)

여기서 N은 가장 빠르게 증가하는 항.. 이다. / .. .. 

어렵다. ^^. 

즉, N은 알고리즘을 수행하기 위해 프로그램이 수행해야하는 연산의 횟수라고 이해하면 된다.

 

문제풀이때나 프로젝트 때

for문을.. 뭣도 모르고 이중for문을 썼을 때 실행속도가 느리고 시간초과가 났는지

이제 조금 알 것 같기도 하다.

그리고 개발자가 수학을 배워야 하는 이유에

상수 연산이 속도가 제일 빠르기때문이라는 이유도 알겠다. -- (O(1))

 

C++ 언어는 하드웨어에 더 가까운 언어이고 C보다 간결하고 파이썬보다 속도가 빠르다고 해서

나중에 함 배워보고싶어졌다!

 

실질적인 알고리즘 소요시간을 확인하는 습관을 들여 효율성을 챙기자.

import time
start_time = time.time()	# 측정 시작

# 프로그램 소스 코드 ...

end_time = time.time()		# 측정 종료
print("time: ", end_time - start_time)	# 수행 시간 출력

 

 

알고리즘 문제를 풀 때에는 가독성을 해치지 않는 선에서 최대한 복잡도가 낮게 프로그램을 작성해야 한다.

 

 

https://blog.chulgil.me/algorithm/

알고리즘의 시간 복잡도와 Big-O 쉽게 이해하기

 

 

 

 

3. 꼭 알아야 할 알고리즘

* 가장 출제빈도가 높은 문제

• 그리디
• 구현
• DFS/BFS

* 알고리즘 자체는 어렵지만 상대적으로 쉽게 출제되는 문제

• 다이나믹 프로그래밍
• 그래픽 이론
• 최단경로
• 정수론 ..

 

 

 

0. 마치며

이 다음부터는 알고리즘 설명이라 이번 글은 여기서 마무리하려고 한다.

 

아무래도 이 책은 "취업을 위한" 책이어서 중간에 취업 준비를 할 때 필요한 점을 알려주는 섹션이 있다.

본 전공으로도 취업하기 어려운데, 다른 전공으로 취업해 밥 벌어먹고 사는게 얼마나 힘들겠는가?

배우고 익혀야 할 양이 상당하다.

회사 일 바쁘고 힘들다고 방송대 공부를 소홀히 한 부분이 좀 아쉽게 느껴진다.

 

컴퓨터 공학 지식도 쌓고

• 서버, 네트워크.. 
• 다음 학기는 휴학하려고 했지만.. 그래도 시간을 버는게 중요하니까 두과목 정도만 수강신청해서 들어야겠다.

토이 프로젝트도 해서 포트폴리오 만들고 

• 자바나 노드로 서버 구축하고 파이썬으로 웹 크롤링해서 보여주는거 만들어보고 싶다!! 언제 하지?

알고리즘도 익히고~ 

• 우선 파이썬 문법에 익숙해져야 하니까, 알고리즘을 들어가기 전에 코드업에서 기초100문제를 파이썬으로 풀어보자!

수학 공부도 하고싶긴 하다. 내 수학은 중1에 멈춰있으니까 ㅜㅜ .. 언제 하지?? ㅜㅜ

 

그렇지만 쉬고 싶고 눕고 싶고 놀고 싶다!

뭐든지간에 건강이 최고니까.

차근차근 하다보면 뭐라도 되어있지 않겠는가?