대학생 쩡딱구리

3-1. 스택 1. 스택이란? 스택(Stack)이란 한 쪽 끝에서만 자료를 넣거나 뺄 수 있는 선형 자료 구조이다. 스택은 LIFO(Last In First Out) 형태의 자료구조로, 가장 최근에 저장된 값 다음에 자료가 저장되고(push), � jjeongttakgoori.tistory.com 스택에 대한 내용은 이 게시물에 있다. 1. 큐 가장 나중에 들어간 자료가 가장 먼저 나오는 스택과 달리 큐(Queue)는 FIFO(First In, First Out) 형태 자료 구조로, 가장 먼저 넣은 것이 가장 먼저 나온다. 달리 말하면 큐는 한쪽 끝에서는 자료를 넣고 한 쪽 끝에서 자료를 꺼내는 선형 자료구조를 말한다. 큐에서는 가장 최근에 저장된 값 다음에 자료가 저장되며(Enqueue), 가장 오래 ..

1. 스택이란? 스택(Stack)이란 한 쪽 끝에서만 자료를 넣거나 뺄 수 있는 선형 자료 구조이다. 스택은 LIFO(Last In First Out) 형태의 자료구조로, 가장 최근에 저장된 값 다음에 자료가 저장되고(push), 가장 최근에 저장된 값이 먼저 나간다(pop). 스택은 데이터를 순서대로 쌓아두었다가 가장 최근 데이터부터 봐야 할 때 쓰이는데 예를 들어 편집기의 되돌리기 기능(undo)이 스택의 예이다. 스택의 기본 연산은 아래와 같다. Operation Comment S.push(e) Top에 새로운 요소 추가 S.pop() - Top 요소를 반환하면서 제거 - 단, 스택이 비어 있으면 error 생성 S.top() - Top 요소 반환 - 스택이 비어 있으면 error 생성 S.is_e..

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

2-1. 배열 1. 배열이란? 2020년 수능 시험에 548,734명이 지원했다고 한다. 이런 상황에서 54만명의 성적을 처리하려면 데이터를 어떻게 관리하는 것이 좋을까? 학생 개개인마다 변수를 선언해 자료를 관리하 jjeongttakgoori.tistory.com 동적 배열을 알기 위해서는 배열을 알아야 한다! 1. 리스트 아래 코드를 살펴보자. 이 코드를 실행했을 때 데이터를 계속 추가할 경우 베열의 길이가 고정되어 있다면 오류가 날 텐데 리스트는 오류가 나지 않는다. 그 이유는 바로 데이터가 추가될수록 크기가 일정 단계마다 커지기 때문이다! import sys# provides getsizeof function data = [] for k in range(n):# NOTE: must fix choi..

1. 배열이란? 2020년 수능 시험에 548,734명이 지원했다고 한다. 이런 상황에서 54만명의 성적을 처리하려면 데이터를 어떻게 관리하는 것이 좋을까? 학생 개개인마다 변수를 선언해 자료를 관리하는 것은 불편할 것이다. 이런 문제점을 해결하는 자료구조 중 배열이 있다. 배열이란 동일한 타입의 데이터를 연속된 메모리 공간에 저장하여 하나의 변수로 표현하는 자료 구조를 말한다. 그렇다면 배열이 갖는 장점은 무엇일까? 배열은 각 요소의 길이가 같기 때문에 어떤 요소라도 바로 접근할 수 있다. 예를 들어, 배열에서 index i의 주소 = [배열의 시작 주소] + [요소의 크기] * i로, O(1)의 시간 복잡도를 가질 것이다. 또한, 배열에선 data[4]와 같은 추상화된 형태로 각 요소를 접근하게 만듦..

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. 알고리즘은 가상 컴퓨터에서 가상 언어로 작성되어야 한다. - 가상 ..

0. 알고리즘과 자료 구조 1. 알고리즘이란? "유튜브 알고리즘이 나를 꽤 괜찮은 곳으로 데리고 왔다." 2PM의 '우리 집' 유튜브 영상에 달린 베스트 댓글 중 하나다. 이 예시와 같이 우리는 알게 모르게 알고리즘이라는 말 jjeongttakgoori.tistory.com 알고리즘이 무엇인지에 대해서는 위 글을 참고하면 좋을 것 같다. 1. 좋은 알고리즘이란? 정의하고자 하는 문제와 자료구조에 따라 알고리즘은 천차만별이다. 그렇다면 좋은 알고리즘이란 어떤 알고리즘일까? 좋은 알고리즘이란 1) 빠르게 실행되면서 2) 적은 공간을 사용하는 알고리즘이다. 두 가지가 알고리즘의 효율성을 결정하는데, 둘 중 우선순위를 고르자면 시간적인 요소가 더 중요하다. 2. 실험 분석 위에서 우리는 같은 내용의 알고리즘일 ..