본문 바로가기

분류 전체보기

[Computer Science] 자료구조 - 탐욕알고리즘 Greedy 탐욕알고리즘은 발견법(heuristic method)의 방법중 하나. 발견법(heuristic method) 최선, 최적의 답을 찾기보다도 주어진 상황을 한단계씩 빠른 시간 내에 해결하기 위해 사용하는 방법론 backtracking(역추적)과 같이 알고리즘 수행시간이 많이 걸릴 때 사용하는 방법 (역추적과 구조는 비슷하지만 방법이 다름) 탐욕법은 이전의 선택으로 돌아가는 역추적과는 반대개념으로, 다른 문제들과 독립적이다 탐욕법이 쓰이는 실제상황예시 1) 여행짐싸기(물건담기) : 여행 배낭에 물건을 정해진 시간 내에 담으려는 경우, 우선순위가 높은 순서대로 물건을 담을 때 한번 배낭에 담은 물건은 다시 빼지 않는다. 2) 여행경로 짜기(도시방문) : 도시가 많아질 수록, 도시를 방문(배열)할 수 있는 가짓.. 더보기
[Computer Science] 자료구조 다이나믹프로그래밍(Dynamic Programming) - 메모이제이션(Memoization) 다이나믹 프로그래밍 Dynamic Programming '문제의 일부분을 풀고 그 결과를 재활용하는 방법으로 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상 시키는 패러다임. 하나의 문제는 단 한번만 풀도록 하는 알고리즘 -탑다운과 보텀업으로 구성되어있다. DP를 사용하게 되는 상황 : 이진 검색, 최단경로 알고리즘, 최적화 문제, 외판원 문제 !!! 분할 정복과의 차이점? 분할정복(Divide and Conquer)과 유사한 개념. 분할정복 기법은 동일한 문제를 다시 푼다는 단점이 있다.(=부분 문제, 서브문의 중복) ('정렬'과 같은 문제는 다시 풀게 되는 단점 없다, 그 예시로 퀵정렬과 병합 정렬이 있고 이 또한 매우 빠름) 다이나믹 프로그래밍 방식 다이나믹 프로그래밍의 구현은 일반적으.. 더보기
[Computer Science] Divide and Conquer(분할 정복) - 퀵정렬과 병합정렬(Quick Sort and Merge Sort) Divide and Conquer(분할 정복) 복잡하거나 큰 문제를 여러 개로 나눠서 푸는 방법. 비슷한 크기로 문제를 분할하고, 해결된 문제를 제외하고 동일한 크기로 문제를 다시 분할한다. 병렬적으로 문제를 해결할 수 있다. 단점: 동일한 문제를 다시 푼다. 문제해결함수가 재귀적으로 호출될 수 있으므로 메모리가 추가적으로 사용된다. !!! 재귀호출과 분할정복의 차이 !!! 재귀호출은 같은 함수코드를 재호출하는 것(같은 함수코드 사용) 분할정복은 비슷한 작업을 재진행하는 것(같은 함수코드는 아닐 수 있음) ''' 1부터 10까지의 합 구하기 ''' #재귀 함수 사용 def r_func(num): if num < 1: return 0 else: return num + r_func(num-1) print('.. 더보기
[Computer Science] Iterative Sorting(반복 정렬) - Selection Sort(선택정렬), Insertion Sort(삽입정렬), Bubble Sort(버블정렬), Count Sort (계수 정렬) / 시간 측정 비교 모든 알고리즘의 기본 원리는 숫자와 조건을 활용하면서 발전시킨다고 생각하면, 어려운 알고리즘에 대해 배우는 관점이 달라질 수 있다. Selection Sort(선택정렬) 선택정렬은 가장 작은 노드(최소값)를 선택하고 왼쪽부터 정렬을 하기 위해 알맞은 위치와 교환하는 작업을 반복하는 것. 선택정렬 정리 : 최소노드 선택 -> 왼쪽부터 비교 -> 교환 단점 : 버블정렬과 달리 서로 이웃하지 않은 노드를 교환하므로, 안정적이지 않다. '''선택 정렬 소스 코드 ''' array = [7, 5, 9, 0, 3, 1, 6, 2, 8, 4] for i in range(len(array)): min_index = i #가장 작은 원소의 인덱스로 지정 for j in range(i+1, len(array)): #j는 .. 더보기
파이썬에서 시간 측정하기 알고리즘의 성능 측정은 공간/시간복잡도로 이루어지고 시간 측정은 Notation Big O와 아래의 모듈과 같이 측정할 수 있다. 많은 양의 입력이 들어오면 차이는 점진적 또는 지수적으로 커지게 된다. 문제를 해결하는데 있어서 다양한 방법이 존재하지만, 가능하면 빠른 알고리즘을 사용하는 이유는 속도 때문이다. 데코레이터를 활용 자주 사용해야할때 불러오기 편하다. # 파이썬에서 시간을 측정하기 위한 함수생성 import time from functools import wraps def check_time(function): @wraps(function) def measure(*args, **kwargs): start_time = time.time() result = function(*args, **kwar.. 더보기
[Computer Science] 자료구조 - Hash Table 해시 테이블 해싱 = 해시 맵 =해시 테이블 데이터 관리/유지 하는테이블 형태의 자료구조, 리소스를 이용하여 속도를 취함. 즉, key를 활용하여 value에 직접 접근이 가능한 구조로 정렬보다는 검색이 더 유용함. 구조 딕셔너리는 내부적으로 해시테이블 구조로 구현되여 있다. key-value형태로 저장 하나의 key는 하나의 value에 맵핑, key는 uniqueness를 보장함 # case 1 - 딕셔너리로 활용되는 해시테이블을 확인할 수 있다. test_code = {2.5: 'A' ,'2.0': 'B', '1.0': 'C'} print(test_code[2.5]) print(test_code['1.0']) print(test_code['2.0']) # case 2 - 리스트와 튜플을 활용해서 해시테이블을 확.. 더보기
[Computer Science] 자료구조 - 검색과 재귀(Searching and Recursion) 검색(Searching) 특정 노드를 추가하거나 삭제를 위해서는 검색이 우선되야 한다. 다양한 알고리즘을 활용하는 경우, 최적 알고리즘 경로를 측정하는데 쓰인다. 검색하는 컬렉션이 무작위이고 정렬되지 않은 경우, 선형검색이 기본적인 검색방법이다. linear search (선형 검색, (순차탐색)) 한 번에 하나씩 모두 검색 반복문을 활용해 배열의 변수(코드에서는 반복자 i)만큼 검색을 진행 # 선형 검색 알고리즘 # 하나의 반복문과 리스트의 인덱스, 조건문을 활용하여 특정값을 검색할 때까지 반복한다. def linear_search(arr, target): # 입력 배열 길이의 범위에서 각 idx를 반복 for idx in range(len(arr)): # 현재 idx의 항목이 비교 대상과 같은지 확인.. 더보기
[Computer Science] 자료구조 - 트리 tree, 순회 traversal 알고리즘 리스트나 스택 또는 큐로 가계도나 조직도를 구현할 수 있을까요? 선형 자료구조로 계층형 구조를 표현하기 어렵습니다. 이처럼 가계도와 같은 계층형 구조를 가진 문제를 해결하기 위한 자료구조 형태가 트리입니다. 트리 관련 용어 루트 노드(Root node) 부모가 없는 최상위 노드 단말 노드 (leaf node) 자식이 없는 최말단 노드 형제 노드 (sibling node) 부모가 같은 두 개의 노드 서브 트리 (sub tree) 자식노드이면서 부모노드역할을 하는 노드가 있는 트리 레벨 (level) 루트노드에서 얼마나 멀리 떨어져 있는지 각각 나타낸다. 루트노드의 레벨은 0이며, 아래로 내려갈때마다 1씩증가한다 크기(size) 트리에 포함된 모든 노드의 개수 깊이 (depth) 루트 노드부터의 거리 높이(.. 더보기

티스토리툴바