해시테이블이란? - 해시테이블은 키를 활용하여 값에 직접 접근이 가능한 구조 - 해싱의 장점 : 데이터 양에 영향을 덜 받으면 성능이 빠름 ( 키를 통해 값을 검색함 ) - 파이썬의 딕셔너리는 내부적으로 해시테이블 구조로 구현되어있음 - 해시테이블은 검색을 위한 역할도 하고, 딕셔너리를 위한 자료구조의 역할도 함 - 해시테이블은 키를 빠르게 저장 및 검색할 수 있는 테이블형태의 자료구조 - 해시함수는 여러 키를 분할하기 위해 키를 해시값 ( 정수값 ) 으로 매칭시키는 역할 - 해싱 ( Hashing ) 은 쉽게 말해서 다 흩뜨려놓고, 키와 매칭되는 값을 검색하는 과정 class hash_table: def __init__(self): self.table = [None for _ in range(256)]..

분할정복을 활용한 알고리즘 ▶ 분할 정복 ( Divide and Conquer ) - 복잡하거나 큰 문제를 여러 개로 나눠서 푸는 방법 - 재귀호출은 같은 함수코드를 재호출하는 것 ( 같은 함수코드 사용 ) - 분할정복은 비슷한 작업을 재진행하는 것 ( 같은 함수코드는 아닐 수 있음 ) ■ 분할정복의 과정 본 문제를 서브문제로 분할 ( Divide ) 서브문제의 답을 구한 경우, 해당 답을 본 문제에 대한 답이 되도록 병합함 ( Merge ) 문제를 분할할 수 없거나, 할 필요없는 경우에 대한 답을 구함 ( Base case, 기본 케이스 ) ■ 분할정복의 조건 본 문제를 서브문제로 분할할 수 있는가? ( Divide ) 서브문제의 답을 병합 ( 또는 조합 ) 하여 본 문제의 답을 구하는 것이 효율적인가..

선형 및 이진검색 ▶ Linear Search ( 선형 검색 ) - 선형 검색은 기본적인 검색 알고리즘으로 한 번에 하나씩 모두 검색하는 것 ▶ Binary Search ( 이진 검색 ) - 반복을 통해 숫자를 반으로 줄이면서 검색을 진행하기 때문에 속도가 더 빠름 - 이진 검색 방법은 데이터가 이미 정렬된 경우에만 작동 반복 정렬 ( Iteratibe Sorting ) ▶ 선택 정렬 ( Selection Sort ) - 최소노드 선택 -> 왼쪽부터 비교 -> 교환 - 선택정렬은 가장 작은 노드 ( 최소값 ) 를 선택하고 왼쪽부터 정렬을 하기 위해 알맞은 위치와 교환하는 작업을 반복하는 것 - 시간 복잡도 : O(n^2) def selection_sort(li): for i in range(len(li)..

검색과 재귀 ( Searching and Recursion ) ▶ 검색 ( Searching ) - 특정 노드를 추가하거나 삭제를 위해서는 검색이 우선되어야 함 - 다양한 알고리즘을 활용하는 경우, 최적 알고리즘 경로를 측정하는데 쓰임 - 검색하는 컬렉션이 무작위이고 정렬되지 않는 경우, 선형검색이 기본적인 검색방법 # 선형 검색 알고리즘 def linear_search(arr, target): for idx in range(len(arr)): if arr[idx] == target: return idx return -1 ▶ 재귀 ( Recursion ) - 재귀 호출은 스택의 개념이 적용되며, 함수의 내부는 스택처럼 관리됨 ( LIFO, 후입선출 ) - 하위 문제를 쉽게 해결할 수 있을 때 까지 문제를..

추상자료형 ( Abstract Data Type, ADT ) 이란? 연결리스트 ( Linked - List ) 이란? - 연결리스트는 말 그대로 리스트들을 "연결" 해줌 - 연결은 프로그래밍에서 참조의 기능으로 구현되고, 리스트의 길이를 별도로 지정해줄 필요없음 class Node: def __init__(self,value,next=None): self.value = value self.next = next class linked_list: def __init__(self, value): self.head = Node(value) def add_node(self, value): if self.head == None: self.head = Node(value) else: node = self.head w..

https://programmers.co.kr/learn/courses/30/lessons/12928?language=python3 코딩테스트 연습 - 약수의 합 정수 n을 입력받아 n의 약수를 모두 더한 값을 리턴하는 함수, solution을 완성해주세요. 제한 사항 n은 0 이상 3000이하인 정수입니다. 입출력 예 n return 12 28 5 6 입출력 예 설명 입출력 예 #1 12의 약수 programmers.co.kr 문제 설명 더보기 정수 n을 입력받아 n의 약수를 모두 더한 값을 리턴하는 함수, solution을 완성해주세요. 제한 사항 n은 0 이상 3000이하인 정수입니다. 입출력 예 n return 12 28 5 6 입출력 예 설명 입출력 예 #1 12의 약수는 1, 2, 3, 4, ..