공돌이 공룡의 서재

0. 들어가기 전 2020/08/18 - [코딩/자료구조] - [Python] 자료구조: 스택(Stack) / LIFO [Python] 자료구조: 스택(Stack) / LIFO 1. 기본 개념 스택(Stack)이란 쌓아 올린다는 의미가 있다. 차곡차곡 쌓여있는 접시들을 생각해보자. 접시를 쌓을 때 위로 하나씩 올리고 뺄 때도 위에서부터 하나씩 뺀다. 중간에 있는 접시를 빼 mr-waguwagu.tistory.com 이번 포스트에서는 기본적인 개념에 대해서는 설명하지 않고, 간단한 예시를 통해 어떻게 쓰일 수 있는지를 정리하고자 한다. 스택구조가 어떻게 구현됐는지와 O(n)이 나오는지를 유의하며 보자. 1. 클래스 정의 class Stack: def __init__(self): self.box = [] d..

1. 기본 개념 스택(Stack)이란 쌓아 올린다는 의미가 있다. 차곡차곡 쌓여있는 접시들을 생각해보자. 접시를 쌓을 때 위로 하나씩 올리고 뺄 때도 위에서부터 하나씩 뺀다. 중간에 있는 접시를 빼면 무너지고 만다. 여기서 순서로 생각해보면 가장 마지막에 올린 접시가 뺄 때는 가장 먼저 나간다는 것을 알 수 있다. 이것을 LIFO(Last in, First out)이라고 한다. 또 다른 예시로 구멍이 하나인 통이 있다고 생각해보자. 빨강부터 보라색까지 무지개 색으로 7개의 마카롱이 있고 빨간색부터 통에 넣는다 생각하자. 마지막으로 들어가는 마카롱은 보라색인데, 꺼낼 때는 마지막으로 들어간 보라색 마카롱을 마카롱을 제일 먼저 꺼내고 제일 먼저 들어간 빨간 마카롱이 제일 마지막에 나온다. 이처럼 새로운 개체..

같은 작업을 하는 코드여도 어떤 알고리즘을 사용했는지에 따라 실행 시간과 사용하는 메모리 공간이 달라진다. 실행 시간이 짧고 메모리 공간을 절약하는 코드가 효율적인 코드라 볼 수 있을 것이다. 1부터 n까지 더한 값을 return하는 코드들의 비교로 감을 잡아보자. def sum1(n): sum = 0 for i in range(n): sum += (i+1) return sum 위의 코드는 for문을 함수인자 n의 값만큼 실행한다. 1부터 100까지 더한다고 치면 100번 덧셈 연산을 수행한다. def sum2(n): return (n+1)*n/2 위의 코드는 등차급수의 합(점화식) 공식을 이용한 코드인데 곱셈과 나누기를 한번씩 하고 바로 값을 return한다. n이 작다면 실행시간이 거의 차이나지 않는..