Algorithm & Data structure

큐(Queue) 큐는 FIFO(First-In First-Out) 규칙의 순차적 자료구조이다. Stack의 경우 들어온 순에서 역순으로 값이 빠져나가지만 큐는 내가 값을 넣은 순서대로 나간다. 그래서 이런 형태로 값이 들어가고 빠져나가는 것이다. enqueue의 경우 내가 넣은 값이 어디까지 쌓였는지 알아야 하고 dequeue에서는 다음에 나갈 값의 index를 알아야 해당 값을 빼내고 옆으로 옮김으로써 다음 값도 뺄 수 있다. *참고로 각 순차적 자료구조마다 insert와 delete시키는 이름을 암묵적으로 구별한다. 이렇게 insert의 경우 Stack에서는 Push, Queue에서는 enqueue라고 하고 delete의 경우 Stack에서는 pop, queue에서는 dequeue라 한다. 이런 식으..

앞에서 간단히 설명한 Stack의 추가 설명 알고리즘을 만드는데 있어서 기본적으로 제공해야 하는 함수 연산은 - 자료구조의 값을 저장(삽입) - 저장된 값 중 일부를 제거(삭제) - 어떤 값이 자료구조에 저장되어 있는지 알고 싶을 때 (탐색) 등이 있다. Stack의 구조 Stack을 코드로 작성하면 이와 같다. 여기서 꼭 기억해야 하는 점은 __init__(self)는 기본적으로 생성하는 함수이므로 변경하면 안된다. 빈 리스트를 생성하면 여기서 push(삽입),pop(삭제), top(제일 위의 값 리턴), __len__(item 리스트가 가지고 있는 값 찾기) 등의 기능을 수행한다. 참고로 push가 리스트에서는 append, 삭제는 똑같이 pop으로 실행시킨다. 모두 반복하는 수행문은 없으므로 O(1..

순차적 자료 구조의 경우 크게 세 가지가 있다. 하나는 앞에서 설명했던 배열과 리스트 1. 배열과 리스트 설명은 앞에서 했으므로 생략 참고로 insert와 remove 연산의 경우 중간에 값이 삽입/삭제가 된다면 중간의 빈 공백을 만들거나 삭제해야 하기 때문에 기존의 값들을 반복문을 통해 index를 밀어내거나 당겨야 한다. 따라서 O(n)의 시간복잡도를 가진다. 2.Stack, Queue, Dequeue 이 세 개는 비슷하면서도 조금씩 다르다. 공통점으로는 삽입과 삭제만 허용된다. Stack은 LIFO방식으로 Last In First out 가장 마지막에 들어온 값이 가장 먼저 나간다는 의미이다. 프링글스 통에 비유하면 이해가 쉽다. 과자를 넣기 위해서는 아래서부터 위로 차곡차곡 쌓아서 올려야 한다. ..

여러 개의 자료구조 중 가장 기본적인 배열과 리스트 주로 배열보다는 리스트가 더 대중적으로 많이 쓰이는 편 가장 기본적이면서도 중요함 C언어의 배열 C언어로 다음과 같은 리스트를 초기화시키면 네 개의 정수를 저장한다. 그렇다면 자기의 자리에 따라 인덱스를 가지게 되고 해당 자리에 값이 초기화된다. 이러한 인덱스 하나에도 4개의 바이트를 가지고 있다. 여기서 첫 번째 바이트는 첫 번째 원소의 주소가 저장되어 있다. 만약 여기서 A[2]에 A[2]+1을 더해서 다시 넣게 된다면 해당 인덱스의 값을 읽고 더한다음 다시 쓰면 해당 인덱스의 원소가 바뀌게 되는 것이다. 여기서 기본 연산은 읽기 +1, 쓰기 +1, 대입+1, 산술+1로 4번의 연산이 이루어지지만 모두 기본연산이기 때문에 O(1)이라 표현한다. (일..

앞에서 구한 함수들의 시간 복잡도는 이렇게 나왔다. 그래프로 만들어 보면 이런 느낌 그럼 여기서 알 수 있는 사실이 있다. 1. Algorithm2가 Algorithm1보다 2배 느리다 2. Algorithm3은 n5/3이면, 항상 Algorithm2보다 느리다. 이는 n의 값에 따라서 도출한 사실들이다. 따라서 n의 증가율이 함수값을 결정하는 가장 큰 요인임을 알 수 있다. 여기서 T1, T2는 n이 증가함에 따라 선형적으로 증가하고, T3는 제곱이기 때문에 n^2의 값에 따라 더욱 크게 증가한다. 여기서 알 수 있는 사실은, n의 값에 따라 함수값이 결정된다는 것이고, 함수들의 최고차항에 따라 증가율이 결정된다는 것이다. 그래서 우리는 우리가 만든 알고리즘의 최악의 경우의 입력에 대한 기본 연산 횟수..

시간복잡도(Time complexity)는 내 알고리즘의 수행 시간을 지칭한다. 하지만 함수에 어떤 값을 넣느냐에 따라 입력의 수행 시간은 항상 달라진다. 그래서 입력값을 고려하여 시간복잡도를 계산하는 방법중에 가장 정확도가 높은 계산은 모든 입력에 대해서 기본 연산 횟수를 더한 후 평균을 내는 것이다. 하지만 이렇게 평균을 내기에는 고려해볼 입력이 무한히 많기 때문에 현실적으로 불가능한 방법이다. 그렇기에 우리는 다른 방안으로 가장 안 좋은 입력, 즉 worstcase input에 대한 기본 연산 횟수로 측정한다. 이렇게 가장 오래 걸리는 입력에 대한 횟수를 따지면 다른 입력이 있더라도 이보다는 기본 연산 횟수가 낮기 때문이다. 따라서 시간복잡도는 최악의 입력에 대한 기본 연산 횟수를 계산하는 것이고 ..

우리는 자료구조와 알고리즘을 통해 문제를 해결하는 과정을 코드로 기술한다. 자료구조와 알고리즘을 통해 성능을 검사할 때는 가상컴퓨터+가상언어+가상코드를 사용해서 성능을 검사한다. 이유라고 하면은 컴퓨터의 하드웨어/소프트웨어 환경에 따라 성능이 다르게 나타날 수도 있을 뿐더러 다양한 크기의 입력이 들어오기 때문에 컴퓨터마다 통일이 안되기 때문이다. 그래서 우리는 가상 컴퓨터에서 가상 언어를 가지고 가상의 코드를 작성한다. 가상의 컴퓨터를 통해 내 알고리즘의 동작 성능을 측정하게 된다면 HW/SW 환경과는 독립적으로 객관적 비교가 가능하기 때문에 비교하기가 용이하다. 가상컴퓨터는 가장 원시적인 형태의 컴퓨터인 튜링 머신에서 나아가 폰 노이만이 우리가 현재 쓰고 있는 컴퓨터와 매우 유사한 RAM(Random ..

자료구조(Data Structure)는 알고리즘과 긴밀한 관계이다. 자료는 Data로 컴퓨터에 저장된다. 컴퓨터에 저장되기 위해서는 컴퓨터가 저장공간에 연산을 통해서 자료를 저장시킨다. 위와 같이 저장되는 자료구조를 이용해서 우리는 자료를 입력하고, 알고리즘을 통해 입력 데이터를 가지고 문제풀이하여 정답을 출력시킨다. 자료구조는 일련의 과정에서 자료를 효율적으로 사용하기 위해서 자료의 특성에 따라서 분류하여 구성하고 저장 및 처리하는 모든 작업을 의미한다. 가장 기본적인 예시는 변수(variable)이다. 우리는 변수를 할당할 때, 알아서 할당하는 것이 아닌 = 를 통해서 쓰기연산이 실행된다. 이를 읽기연산(print(a))를 통해서 변수 이름에 접근하여 출력시키는 것이다. 다른 기본적인 예로는 배열도 ..