dlng23

12-1 공간으로 시간을 살 수 있나요?시간과 공간의 효율성은 충돌하는 요소 많은 경우 시간 효율성이 더 중요하게 인식되기 때문에 많은 메모리를 사용하여 처리시간을 줄이려는 다양한 전략들이 개발됨 가능한 모든 입력에 대한 답을 미리 다 구해서 저장→ 대부분은 가능한 모든 입력이 거의 무한하게 많아 미리 계산하기 어렵고, 답을 저장할 공간도 턱없이 부족그러나, 현실적인 수준에서 이 전략을 사용하는 알고리즘도 다수 존재함기수 정렬이 위 전략에 해당, 미리 버킷을 많이 준비해두고, 입력 데이터를 배분하는 방법으로 정렬입력의 제한이 존재하지만 거의 선형(O(n))에 가까운 성능문자열 매칭 문제에서도 사용 가능, 효율적인 탐색을 위한 전처리로 테이블을 만들어 두어 더 효율적으로 문자열 매칭 가능동적 계획법도 부분..

11-1 동적 계획법이란?동적 계획법도 분할 정복과 같이 문제를 더 작은 부분으로 나눈 후 답을 계산하여 답들로부터 원래 문제의 해답을 구하는 구조동적 계획법은 부분 문제들의 답을 어딘가에 저장해 둔 뒤 필요할 때 다시 꺼내서 사용하는 전략을 사용한다는 점에서 차이 존재 피보나치 수열 문제n번째 피보나치 수를 구하는 fib(n)은 위와 같이 순환 관계로 나타낼 수 있음 순환 관계는 분할 정복을 이용하여 해결할 수 있으나, 심각한 계산 중복 문제가 발생하고, 시간 복잡도가 O(2^n) 동적 계획법은 구한 답을 저장하여 재사용 → 다시 풀어야 할 때는 저장된 해답을 이용부분 문제의 해를 저장하는 방법에는 메모이제이션과 테이블화가 있음 메모이제이션을 이용한 피보나치 수열메모이제이션(memoization): 함..

09-1 문제 해결 과정알고리즘 개발 과정 문제의 이해문제를 정확히 이해, 조금이라도 애매한 부분들을 없애야 함올바른 알고리즘 → '대부분의 입력'이 아닌 '모든 유효한 입력'에 대해 정확한 해답을 구할 수 있어야 함 설계 방향 결정알고리즘을 어떤 방향으로 설계할지 결정사용할 컴퓨터의 방식에 따라 순서적(sequential) 알고리즘으로 개발할 수도 있지만, 병렬처리(parallel) 방식을 선택할 수도 있음대부분의 문제는 정확한 해답, 최적해를 요구하지만, 근사해를 구해도 되는 경우도 많음 → 어떤 해를 구할 것인지 결정해야 함 근사해를 고려해야 하는 상황정확한 해 자체를 구할 수 없는 문제ex) 제곱근 문제계산량이 너무 많아져서 현실적인 시간에 해결할 수 없는 문제정확한 해를 구하기 위한 알고리즘의 ..

08-1 그래프란?그래프(graph): 복잡하게 연결된 객체 사이의 관계를 효율적으로 표현할 수 있는 자료구조 그래프의 유래과거 독일의 도시였던 쾨니히스베르크라는 곳에 강이 흐르고 있고 4개의 지역들을 연결하기 위해 7개의 다리 존재도시의 사람들 사이에서 '모든 다리를 한 번씩만 건너서 출발했던 장소로 돌아올 수 있을까?' 라는 문제가 돌았음해당 문제를 수학자 레온하르트 오일러(Leonhard Euler)가 처음으로 해결오일러는 해당 문제를 '위치'라는 객체는 정점(vertex)으로, 위치 간의 관계인 '다리'는 간선(edge)로 표현하여 그래프 문제로 변환하였음오일러는 그래프에 존재하는 모든 간선을 한 번만 통과하면서 처음 정점으로 되돌아오는 경로를 오일러 경로(Eulerian tour)라 정의그래프의..

07-1 탐색이란?탐색: 데이터의 집합에서 원하는 조건을 만족하는 데이터를 찾는 작업레코드(record): 탐색을 위한 대상테이블(table): 레코드의 집합키(key) or 탐색키(search key): 여러 개의 필드로 이루어진 하나의 레코드에서 탐색의 기준이 되는 필드 탐색은 테이블에서 원하는 탐색키를 가진 레코드를 찾는 작업 테이블을 구성하는 방법에 따라 탐색의 효율이 달라짐가장 간단한 방법인 배열을 사용하는 것보다는 탐색 트리나 해싱 같은 더 진보된 방법을 사용하는 것이 성능을 높일 수 있음 탐색 방법을 선택할 때 탐색 연산의 효율이 가장 중요하지만, 삽입, 삭제 연산과 같이 필요한 작업들을 함께 고려하여 알고리즘을 선택해야 함 07-2 순차 탐색순차 탐색(sequential search), 선..

06-1 정렬이란?정렬: 순서가 없는 사물들을 순서대로 나열하는 것무언가를 찾을 때, 효율적인 탐색을 위해 사용됨 정렬을 위해서는 서로 비교 가능해야 함비교할 수 있는 모든 속성은 정렬의 기준이 될 수 있음 정렬 관련 용어레코드(record): 정렬시켜야 할 대상레코드는 여러 개의 필드(field)로 이루어짐ex) 쇼핑몰에서 '상품'이란 레코드는 '이름', '가격', '제조' 등 다양한 필드를 가짐 키(key) or 정렬 키(sort key): 정렬의 기준이 되는 필드정렬: 레코드들을 키(key)의 순서로 재배열하는 것 알고리즘이 단순하면 일반적으로 비효율적ex) 삽입 정렬, 선택 정렬, 버블 정렬효율을 높이기 위해서는 복잡한 알고리즘 사용해야 함ex) 퀵 정렬, 힙 정렬, 병합 정렬, 기수 정렬, 팀 ..

04-1 트리란?트리(tree) 나무를 닮은 자료 구조→ 계층적인 관계를 가진 자료의 표현에 유용하게 사용됨 트리 관련 용어트리에서 각각의 요소들을 노드(node)라고 부름트리는 하나 이상의 노드들로 이루어짐노드와 노드의 연결 관계는 간선 또는 에지(edge)로 나타냄계층적인 구조에서 가장 높은 곳에 있는 노드를 루트(root) 노드라고 부름부모(parent) 노드간선으로 직접 연결된 노드 중에 상위 노드자식(child) 노드간선으로 직접 연결된 노드 중에 하위 노드형제(sibling) 노드같은 부모 노드를 가진 노드조상(ancestor) 노드어떤 노드에서 루트 노드까지의 경로상에 있는 모든 노드자손(descendent) 노드어떤 노드 하위에 연결된 모든 노드단말(terminal, leaf) 노드자식 노..

03-1 리스트란?리스트(list) 또는 선형 리스트(linear list)는 자료들이 차례대로 나열된 선형 자료구조각 자료는 순서 또는 위치(position)를 가짐 리스트에서는 어떤 위치에서도 새로운 요소를 삽입할 수 있음어느 위치에 요소를 삽입 → 이후 모든 자료가 한 칸씩 뒤로 밀림어느 위치의 요소를 삭제 → 이후 모든 자료가 한 칸씩 당겨짐 리스트 - 집합(Set)리스트: 순서 O, 중복 허용집합: 원소 사이에 순서 X, 중복 허용 X집합은 원소 사이에 순서의 개념이 없으므로 선형 자료구조라 볼 수 없음 리스트의 연산insert(pos, e) : pos 위치에 새로운 요소 e를 삽입delete(pos) : pos 위치에 있는 요소를 꺼내서 반환getEntry(pos) : pos 위치에 있는 요소..

02-1 큐란?큐(queue)가장 먼저 들어간 자료가 가장 먼저 나오는 자료구조선입선출(FIFO: First-In First-Out) 큐는 삽입과 삭제 연산이 같은 쪽이 아니라 서로 다른 쪽에서 일어남삽입이 일어나는 곳을 후단(rear)이라 하고 삭제가 일어나는 곳을 전단(front)이라 부름 큐는 빠른 CPU와 속도가 상대적으로 느린 주변장치들 사이의 시간이나 속도 차이를 극복하기 위한 임시 기억 장치(버퍼(buffer))로 사용됨 큐의 연산enqueue(e): 새로운 요소 e를 큐의 맨 뒤에 추가dequeue(): 큐의 맨 앞에 있는 요소를 꺼내서 반환isEmpty(): 큐가 비어 있으면 True를, 아니면 False를 반환isFull(): 큐가 가득 차 있으면 True를, 아니면 False를 반환p..

01-1 스택이란?스택마지막에 들어간 자료가 가장 먼저 나오는 자료구조후입선출 LIFO(Last-In First-Out) 스택은 물건을 넣는 좁고 긴 통으로 생각할 수 있는데, 다른 통로는 막고 한쪽만을 열어둔 구조로열린 곳을 보통 상단(stack top) 이라 부르고, 스택에 저장되는 것을 요소(element) 라 부름 스택은 요소의 삽입과 삭제가 상단에서만 가능 추상 자료형추상화(abstraction): 새로운 자료형을 정의하기 위해 그 자료형의 자세하고 복잡한 내용 대신에 필수적이고 중요한 특징만 골라서 단순화시키는 작업 추상 자료형(ADT: Abstract Data Type): 추상화를 통해 정의한 자료형 스택의 연산push(e): 새로운 요소 e를 스택의 맨 위에 추가 (삽입)pop(): 스택의..