자료구조 썸네일형 리스트형 [Computer Science] 자료구조 - 그래프 탐색 DFS, BFS DFS(depth-first search) - 깊이우선탐색 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘. LIFO 스택 자료구조(혹은 재귀함수)를 이용 DFS 동작과정 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다. 더이상 2번 과정을 수행할 수 없을 때까지 반복. Backtracking DFS에서 활용되는 방법, 노드가 있을만한 곳을 되돌아가서 모두 살펴본다는 개념 위의 그림처럼 DFS는 깊이우선적으로 탐색을 진행하고, 재귀적으로 아래에서부터 탐색하지 않은 정점이 있는지 확인하는 방법으로 되돌아가는 것에서 backtracki.. 더보기 [Computer Science] 자료구조 - 검색과 재귀(Searching and Recursion) 검색(Searching) 특정 노드를 추가하거나 삭제를 위해서는 검색이 우선되야 한다. 다양한 알고리즘을 활용하는 경우, 최적 알고리즘 경로를 측정하는데 쓰인다. 검색하는 컬렉션이 무작위이고 정렬되지 않은 경우, 선형검색이 기본적인 검색방법이다. linear search (선형 검색, (순차탐색)) 한 번에 하나씩 모두 검색 반복문을 활용해 배열의 변수(코드에서는 반복자 i)만큼 검색을 진행 # 선형 검색 알고리즘 # 하나의 반복문과 리스트의 인덱스, 조건문을 활용하여 특정값을 검색할 때까지 반복한다. def linear_search(arr, target): # 입력 배열 길이의 범위에서 각 idx를 반복 for idx in range(len(arr)): # 현재 idx의 항목이 비교 대상과 같은지 확인.. 더보기 [Computer Science] 자료구조 - ADT(추상자료형) / linked-list/ Stack / Queue !!! ADT(Abstract Data Type) ADT는 추상적으로 필요한 기능을 나열한 일종의 명세서(로직)이다. ADT는 기본자료형(대표적으로 리스트, 숫자, 문자열)을 활용하여 사용자에 의해 구현된다. 파이썬의 리스트와 자료구조의 리스트. 파이썬은 리스트 자료형이 자료구조의 연결리스트로 기능을 지원한다. 리스트는 임의의 메모리(위치)에 자료를 동적으로 처리할 수 있다. 파이썬의 리스트는 자료구조의 배열과 연결리스트의 특징을 모두 갖고 있다. 배열의 특징 : 인덱스 사용하여 노드에 접근가능 연결리스트의 특징 : 인덱스 크기를 자유롭게 확장가능, 서로 다른 자료형을 노드로 갖을 수 있다. 즉, 파이썬이라는 프로그래밍 언어는 기존 프로그래밍에서 발생한 어려운 점을 부분적으로 개선시켰다는 것을 알 수 있다. 파.. 더보기 [Computer Science] 파이썬 with OOP(Object-Oriented Programming) OOP(Object-Oriented Programming) 최소비용으로 최대효율을 지향하며. 세상에 있는 실체가 있는 모든 물체를 클래스와 인스턴스, 함수, 변수라는 object로 변화시켜서 프로그램을 구성. 기본 전제는 기능(함수, 변수) 재사용이 가능한 설계 및 프로그래밍. 기본 개념 설계(사람이 이해하는 방식)와 구현할 소스코드(컴퓨터가 이해하는 방식) 간의 상호이해가 중요하다. HW&SW 성능증가 (CPU성능 증가, 소프트웨어 다중실행) 덕분에 OOP의 모든 기능을 활용할 필요는 없다. OOP의 개념을 무분별하게 활용하면 유지보수가 어려워질 수도 있기때문에 설계방향 및 서비스기능에 따라 사용해야 한다. OOP를 제대로 하는 법은 프로그래밍뿐만 아니라 다양한 도메인에서 재사용 가능한 클래스, 메소드.. 더보기 이전 1 다음
