algorithm/data structure & algorithm6 배열(Array)과 리스트(List) 개념 정리 배열 (Array)배열의 특징- 동일한 자료형을 가지는 데이터들의 집합- 고정된 크기 (정적 할당)- 연속된 메모리 공간에 저장됨- Index 기반으로 빠른 조회 가능 (O(1))- 삽입, 삭제 시 연산이 느림 (O(n)) (중간 요소 변경 시 모든 요소 이동이 필요하기 때문)배열의 장점- 메모리 접근 속도가 빠르다. (연속된 메모리 할당)- Index 기반으로 빠른 조회 가능 (O(1))- CPU 캐시 최적화가 가능배열의 단점- 크기가 고정됨 (Python 예외)- 중간 삽입/삭제 시 비효율적 (뒤 요소들을 이동해야 함)시간 복잡도- 접근 (Access) : O(1)- 삽입 (Insert) & 삭제 (Delete) : O(n) 리스트 (List)리스트의 특징- 크기가 동적으로 변경 가능 (가변 길이).. 2025. 2. 6. 보간 (Interpolation) 공부하면서 정리한 내용이며, 틀린 내용이 있을 수 있으니 양해바랍니다!보간: 주어진 데이터 점들 사이의 값을 추정하는 수학적 기법.두 데이터 점 사이에 값을 알지 못할 때, 그 구간의 값을 예측하는 과정보간을 통해 더 많은 데이터를 생성하거나, 불완전한 데이터를 보완 보간이 사용되는 분야데이터 분석: 누락된 데이터 예측 or 더 높은 해상도의 데이터 생성컴퓨터 그래픽: 이미지나 동영상에서 픽셀 간의 색상 값을 추정할 때과학 실험: 실험 값 사이의 미세한 변화를 분석할 때 보간의 유형 1. 선형 보간 (Linear Interpolation)두 데이터 점 사이를 직선으로 연결하여 그 사이의 값을 추정함두 점 $(x_{1}, y_{1})$과 $(x_{2}, y_{2})$ 사이에서 $x$값이 주어졌을 때, $.. 2024. 10. 2. [algorithm] DFS/BFS (python) DFS, 깊이 우선 탐색 (Depth-First Search)DFS는 스택이나 재귀함수를 이용하며 구체적인 동작 과정은 다음과 같다.탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리하고, 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.더 이상 2번의 과정을 수행할 수 없을 때까지 반복한다.즉, 매번 최상단 원소를 기준으로 해서 방문하지 않은 인접 노드가 있으면 그 인접한 노드로도 방문을 수행하는 것이다.그래프에서 가장 깊은 부분을 우선적으로 탐색하고 가장 깊게 들어갔다가 더 이상 들어갈 수 없다면 다른 방향으로 깊게 들어가는 방식을 반복 하는 것이다. DFS 동작 예시간선은 방향이 없는.. 2024. 8. 22. [algorithm] 재귀 함수(Recursive Function) (Python) 재귀함수재귀함수는 자기 자신을 다시 호출하는 함수를 의미한다.def recursive_func(): print('재귀 함수 호출') recursive_func()recursive_func()파이썬에서는 재귀를 호출하는 과정에서의 깊이 제한이 있기 때문에 별다른 설정을 하지 않고 함수를 재귀적으로 호출하게 되면 오류가 발생한다. def recursive_func(): if i == 100: return print(i, '번째 재귀함수에서', i+1, '번째 재귀함수 호출') recursive_function(i+1) print(i, '번째 재귀함수 종료')recursive_func(1)재귀 함수를 문제 풀이에서 사용할 때는 위처럼 재귀 함수의 종료 조건을 반드시.. 2024. 8. 22. [algorithm] Queue (Python) Queue먼저 들어온 데이터가 먼저 나가는 형식의 자료구조 (선입선출) (FIFO)입구와 출구가 모두 뚫려 있는 터널과 같은 형태ex) 은행 창구, 터널 등 큐 구현 예제파이썬에서는 큐를 구현할 때 deque를 사용하여 구현한다.list자료형으로 기능적으로는 큐를 구현할 수 있지만 시간복잡도가 더 높아서 비효율적으로 동작한다.from collections import dequequeue = deque()# 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제()queue.append(5)queue.append(2)queue.append(3)queue.append(7)queue.popleft()queue.append(1)queue.append(4)queue.. 2024. 8. 22. [algorithm] Stack (python) Stack먼저 들어 온 데이터가 나중에 나가는 형식의 자료구조 (선입후출) (FILO)입구와 출구가 동일한 형태로 스택을 시각화할 수 있다.ex) 쌓아올린 박스 스택 구현 예제파이썬에서는 append()와 pop()의 시간복잡도가 상수. 즉 O(1)이기 때문에 리스트로 스택을 구현하면 된다.stack = []# 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제()stack.append(5)stack.append(2)stack.append(3)stack.append(7)stack.pop()stack.append(1)stack.append(4)stack.pop()print(stack[::-1]) # 최상당 원소부터 출력print(stack) # 최하단 원.. 2024. 8. 22. 이전 1 다음
