Computer/자료구조, 알고리즘(10)
-
파이썬 선형 자료구조(배열/선형 리스트, 연결 리스트)
배열 1) 배열의 성질 배열은 메모리 상에 원소를 연속하게 배치한 자료구조이라서 k번째 원소의 위치를 바로 계산할 수 있다. k번째 원소를 O(1)에 확인하거나 변경할 수 있다. 임의의 위치에 원소를 추가, 제거하는 과정은 O(N)이다. 메모리는 다른 자료구조와 다르게 추가적으로 소모되는 메모리의 양(=overhead)이 거의 없다. 메모리 상에 데이터들이 붙어있어 Cache hit rate가 높다. 메모리 상에 연속한 구간이 필요해서 할당에서 다소 제약이 있다. 2) 파이썬 배열 우선, 기본 파이썬에는 다른 프로그래밍 언어에서 정의되는 배열이라는 것이 없다. 대신 데이터 분석 등에서 수치 해석을 위해 사용하는 넘파이 라이브러리에서 배열을 지원한다. 그래서, 파이썬의 리스트가 동적 배열의 특징을 갖고 있..
2023.04.12 -
탐색 유형 - BFS/DFS
탐색이란? 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정 탐색 유형 문제 푸는 법 - 대표적인 탐색 알고리즘 DFS와 BFS를 이용 DFS와 BFS를 제대로 이해하려면 기존 자료구조인 스택, 큐, 재귀함수를 알아야한다. 그래프는 노드와 간선으로 표현되며 그래프 탐색이란 하나의 노드를 시작으로 다수의 노드를 방문하는 것이다. BFS, 너비 우선 탐색 가까운 노드부터 탐색하는 알고리즘이다. BFS 구현에서는 선입선출 방식인 큐 자료구조를 이용한다.('큐에서 꺼낸 노드'의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 하기때문에 큐 자료구조를 이용해야 한다.) 인접한 노드를 반복적으로 큐에 넣도록 알고리즘을 작성하면 먼저 들어온 것이 먼저 나가게 되어, 가까운 노드부터 탐색을 진..
2022.11.28 -
자료구조1(리스트, 스택, 재귀함수)
자료구조란? 데이터를 표현하고 관리하고 처리하기 위한 구조 자료구조의 필요성 데이터를 메모리에 저장하기 위해 여러 자료 구조를 사용한다. 자료구조를 활용해서 응용 프로그램의 성능 향상, 표준화, 가독성, 유지 보수 등의 관점에서 유리하게 데이터를 관리할 수 있다. 시간 복잡도는 내부에서 데이터를 어떻게 저장하여 사용하는가에 따라 달라진다. (시간 복잡도는 데이터 크기가 변경되면 연산 시간이 어떻게 변하는지 보여준다.) 선형자료구조 1. 연속된 자료 구조 - 정적 배열, 동적 배열 2. 연결된 자료 구조 - 연결 리스트 스택 -삽입(Push) 삭제(Pop), 순차 자료구조 변수 top : 스택에 저장된 마지막 원소에 대한 인덱스 저장 공백 상태 : top = -1 (초기값) , 포화 상태 : top = n..
2022.11.28 -
greedy
그리디 알고리즘 '현재 상황에서 지금 당장 좋은 것만 고르는 방법' 그리디 알고리즘을 이용하면 매 순간 가장 좋아보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다. 그리디 알고리즘 문제 유형은 사전에 외우고 있지 않아도 풀 수 있을 가능성이 높은 문제 유형이다. 다익스트라 알고리즘은 엄밀히 말하면 그리디 알고리즘으로 분류되고 암기가 필요하지만 이런 특이 케이스를 제외하고 문제를 풀기 위한 최소한의 아이디어(현재 상황에서 가장 좋아 보이는 것만을 선택)를 요구한다. 그리디 알고리즘은 기준에 따라 좋은 것을 선택하는 알고리즘이므로 문제에서 '가장 큰 순서대로', '가장 작은 순서대로'와 같은 기준을 알게 모르게 제시하고 이 기준은 정렬 알고리즘을 사용했을 때 만족시킬 수 있으..
2022.10.17