대학생 쩡딱구리

1-2. 시간 복잡도 분석 1. 알고리즘 분석 0. 알고리즘과 자료 구조 1. 알고리즘이란? "유튜브 알고리즘이 나를 꽤 괜찮은 곳으로 데리고 왔다." 2PM의 '우리 집' 유튜브 영상에 달린 베스트 댓글 중 하나다. 이 예시와 같 jjeongttakgoori.tistory.com 삽입 정렬을 처음 다룬 게시글이다. 안 봐도 무방. 1. 포지션 리스트로 삽입 정렬 문제 풀어보기 워크(walk): 마커부터 첫 번째 노드 방향으로 이동한 것. 워크 앞 노드와 피봇을 비교한다. 피봇(pivot): 마커의 다음 노드로, 정렬해야 할 대상 마커(marker): 정렬된 리스트의 가장 오른쪽 노드 2. insertion_sort def insertion_sort(L): """Sort PositionalList of ..

2-2. 동적 배열 2-1. 배열 1. 배열이란? 2020년 수능 시험에 548,734명이 지원했다고 한다. 이런 상황에서 54만명의 성적을 처리하려면 데이터를 어떻게 관리하는 것이 좋을까? 학생 개개인마다 변수를 선언해 자료� jjeongttakgoori.tistory.com 동적 배열에서 이어진다. 1. 분할 분석 분할 분석(Amortization Analysis)이란 연산이 연속적으로 일어날 때 각 시점별로 연산을 따로 분석하지 않고 전체 연산을 함께 분석해 비용을 계산하는 방식이다. 위 그래프를 보도록 하자. 특정 시점의 연산량은 많지만 대부분의 시점에서 연산량이나 시간이 적다는 것을 알 수 있다. 이때 분할 분석을 사용하는 것이 효과적이다. 분할 분석은 단순히 분석방식이기보다 알고리즘의 설계 방..

1. 시간 복잡도 분석 1. 알고리즘 분석 0. 알고리즘과 자료 구조 1. 알고리즘이란? "유튜브 알고리즘이 나를 꽤 괜찮은 곳으로 데리고 왔다." 2PM의 '우리 집' 유튜브 영상에 달린 베스트 댓글 중 하나다. 이 예시와 같 jjeongttakgoori.tistory.com 시간 복잡도의 개념에 대한 이해가 있어야 이번 게시글을 보기 편하다. 1. Big-O 표기법 Big-O 표기법(Big-O Notation)은 시간 복잡도와 공간 복잡도의 점근적 상한이다. Big-O 표기법에 대해서는 아래의 공식이 성립한다. 아래의 공식에서 n은 입력의 크기, f(n)은 알고리즘에서 실행되는 기본 연산의 횟수, g(n)은 기준 함수이다. O(g(n)) = {f(n): there is positive constant..

1. 알고리즘 분석 0. 알고리즘과 자료 구조 1. 알고리즘이란? "유튜브 알고리즘이 나를 꽤 괜찮은 곳으로 데리고 왔다." 2PM의 '우리 집' 유튜브 영상에 달린 베스트 댓글 중 하나다. 이 예시와 같이 우리는 알게 �� jjeongttakgoori.tistory.com 이번 게시글도 저번 게시글에서 이어진다. 1. 시간 복잡도 시간 복잡도(Time Complexity)란 연산의 실행 횟수를 입력 크기 n에 대한 함수로 표기한 것을 말한다. 알고리즘 내에서 실행되는 기본 연산의 횟수라고도 볼 수 있는 시간 복잡도는 T(n)(n은 입력의 크기)으로 표시한다. 알고리즘에서 시간 복잡도를 분석하기 위해서는 몇 가지 가정을 해야 한다. 1. 알고리즘은 가상 컴퓨터에서 가상 언어로 작성되어야 한다. - 가상 ..