ssungcohol 개발 성장기

DFS (Depth - First Search) 깊이 우선 탐색으로, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘 스택 (Stack) 을 사용하여 표현 동작과정 탐색 시작 노드를 스택에 push하고 방문 처리 스택의 최상단 노드에 방문하지 않은 인접 노드가 있다면 그 인접 노드를 스택에 넣고 방문 처리 - 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼냄 위의 과정을 더 이상 수행할 수 없을 때까지 반복 코드 구현 graph = { 1: [2, 5, 9], 2: [3], 3: [4], 4: [], 5: [6, 8], 6: [7], 7: [], 8: [], 9: [10], 10: [] } def recursive_dfs(v, visited = []): visited.append(v) #..

해시 (Hash) 키 (key)와 값 (value)를 매핑하여 데이터를 저장하는 자료구조 (python에서는 기본으로 제공되는 딕셔너리 자료형이 해시 테이블의 구조) 해시 테이블은 해시 함수를 사용해 색인 (index)을 버킷 (bucket)이나 슬롯 (slot)의 배열로 계산 데이터를 다루는 기법 중 하나로 데이터 검색과 저장이 빠르게 진행 용어 키 (key) - 고유의 값으로 해시 함수의 input이고, 다양한 길이를 가짐 해시 테이블 (Hash table) 또는 해시 맵 (Hash map) - key 와 value를 매핑하여 데이터를 저장하는 자료구조 해시 함수 (Hash function) - 임의의 값을 고정된 길이의 데이터로 변환하는 함수. 다양한 길이의 키를 고정된 길이의 해시로 변환하여 저장..

큐 (Queue) 자료를 보관할 수 있는 선형 구조 스택 (stack)과는 달리, 한 쪽에서 자료를 넣으면 자료를 넣은 쪽이 아닌 반대 쪽에서 자료를 뽑아야 함 (자료를 넣는 것 : 인큐연산(enqueue), 자료를 빼는 것 : 디큐연산 (dequeue)) 선입선출 형태의 자료구조 (FIFO : First in First out) 구현 방법 배열 : python리스트와 메서드를 사용 연결 리스트 : 양방향 연결 리스트 사용 (Doubly Linked List) 기초 연산 동작 size() - 현재 큐에 들어가 있는 데이터 원소의 수를 구함 isEmpty() - 현재 큐가 비어있는지를 판단 enqueue(x) - 데이터 원소 x를 추가 dequeue() - 큐의 맨 앞에 저장된 데이터 원소를 반환하고 제거..

연결 리스트 (Linked List) 다른 추상 자료형을 구현할 때 기반이 되는 기초 선형 자료구조 선형 배열과 비슷하지만, 링크라고 부르는 고리로 원소리들이 연결되는 점이 다르다 장점 원소를 삽입, 삭제하는 것이 쉬움 (빠름) 단점 데이터 구조 표현에 소요되는 저장 공간(메모리) 소요가 크다 k 번째 원소를 찾는데 배열보다 시간이 오래 걸림 (배열은 데이터 원소들이 번호가 있는 칸에 있지만, 연결 리스트는 연결된 형태) 종류 단방향 연결 리스트 (Singly Linked List) 양방향 연결 리스트 (Doubly Linked Lists) 원형 연결 리스트 (Circular Linked List) 양방향 연결 리스트 (Doubly Linked Lists) 노드들이 앞/뒤로 연결되어 있음 (인접한 두 개..

탐색 (Search) 다수의 원소로 이루어진 데이터에서 특정 원소를 찾아내는 작업 선형 탐색 (linear search) or 순차 탐색 (sequential search) - 순차적으로 모든 요소를 탐색 - 배열의 길이에 비례하여 시간이 소모 (Ex_ 1,000,000,000개의 원소 존재 시 최악의 경우 모든 원소를 탐색...) - 성능 = O(n) 이진 탐색 (binary search) (= 이분탐색) - 배열이 정렬되어 있는 경우에만 사용 가능 - 찾고자 하는 원소를 배열의 가운데 원소와 비교하여 값이 크다면 오른쪽, 작다면 왼쪽 - 위의 과정을 반복하여 원하는 값을 추출 - 예제 코드 def binary_search(a, x): lower = 0 upper = len(a) - 1 while lo..