1.알고리즘
-알고리즘의 정의:
입력값을 출력값의 형태로 바꾸기 위해,
어떤 명령들이 수행되어야 하는지에 대한 규칙들의 순서적 나열.
???
출력 값(문제의 답)을 내기 위한 도구(컴퓨터가 따르는 일련의 절차)들의 모임.
-알고리즘 공부의 목적:
효율적으로(효율적이다, 합리적이다 = 답(출력 값)을 내기까지 걸리는 시간, 노력(수행 시간)이 최소이다.)도구들을 활용하기 위해.
합리적인 사람이 되기 위해.
알고리즘에 대해 좀 더 자세히 정리된 블로그
출처:https://m.blog.naver.com/pst8627/221658169228]
2.의사 코드
-의사 코드(pseudo code)의 정의와 사용 이유:
정해진 문법이 없으며 목적에 따라 자유롭게 짜는 코드.
들여쓰기를 활용하면 의사코드가 좀 더 정교해 보일 수 있다.
의사코드는 알고리즘 단계별 표현에 유용하고, 프로그램 논리이해에 효과적이다.
본격적으로 코드를 짜기 전에 의사 코드로 모든 가능성을 빠르게 정리해본다면, 예상치 못한 컴퓨터 문제들을 방지하는 정교한 알고리즘 코드를 짜는데 도움이 된다.
3.선형 탐색
-선형 탐색의 정의:
찾고자 하는 값을 맨 처음부터 순차적으로 비교하면서 찾아내는 탐색.
linear search(xxxx...---------------->발견!)
-선형 탐색 알고리즘의 사용 이유:
찾고자 하는 자료를 찾을 때까지 모든 자료를 확인해야 하므로 정확하지만 효율적이지 못한 알고리즘이다.
ex)cs50 강의 2-3 강의 내용 중 숫자 7찾기. 그러나 우린 이런 경우에 특히 자료의 수가 적은 경우에,
선형탐색을 하기보단 뽑고 싶은 것을 랜덤하게 뽑는다. O(n)이 아닌, O(1)의 시간복잡도를 기대하면서.
ex2)실생활 사례 중 가장 선형탐색에 가까운 걸 생각해 보던 중, 방을 효율적으로 치우는 방법을 떠올렸다.
우리가 원하는 출력 값(답)은 방을 빨리 치우기이다. 방에 짐이 어질러져 있다면, 내가 서있는 위치 기준으로 가장 가까운 짐부터 차례대로 정리하는 것이 가장 효율적이라는 생각이 들었다.
나 ---짐1----짐2---짐3--->정리끝
그러나 자료가 정렬 되어 있지 않다면, 자료에 대한 어떤 정보도 없다면
선형 탐색 알고리즘은 유용하다.
cs50 강의 중, 선형 탐색 알고리즘과 비교되는 것으로
이진 탐색 알고리즘이 등장하는데, 방대한 양의 자료가 정렬되어 있다면, 이진 탐색이 매우 유리하다.
++이전에 헷갈렸던 시간 복잡도 정리
-시간 복잡도의 정의:
알고리즘을 수행할 때 걸리는 시간을 기준으로 효율성을 분석하는 것.
시간의 효율성은 알고리즘에서 비교와 교환 등이 일어날 때 연산자의 처리횟수가 적다는 의미.
그래서 아래의 그래프 처럼 데이터수(입력 갯수 n), 연산횟수를 x, y축으로 그래프를 그려볼 수 있다.
관련 링크 ref:
https://joshuajangblog.wordpress.com/2016/09/21/time_complexity_big_o_in_easy_explanation/
그래프 관련 ref:
그래프를 그려보았다.
