개발자를 위한 AI 알고리즘 (2일차)

 

1. 데이터 분석을 위한 핵심 도구: Pandas & Numpy

데이터 사이언스의 기초가 되는 라이브러리와 자료형에 대한 정의입니다.

• Pandas 주요 자료구조
  • 시리즈(Series): 1차원 배열 값.
  • 데이터 프레임(DataFrame): 테이블 형태의 데이터를 저장하는 2차원 자료구조.
• 데이터 선택 및 필터링
  • 열 선택: df[['a', 'b']] (이름으로 선택), df.iloc[:3] (인덱스로 선택).
  • 행 선택: df.iloc[1:3, :] 등 위치 기반 인덱싱 활용.
  • 하위 집합 추출: df[df.age > 30]과 같이 조건문 활용, & 연산자를 통한 다중 조건 필터링 가능.
• 행렬과 벡터
  • 행렬(Matrix): 행과 열의 수가 고정된 2차원 구조. 전치 연산(matrix.transpose()) 등이 가능함.
  • 벡터(Vector): 데이터를 저장하는 1차원 구조.
    • 구현 방법: 1) 파이썬 리스트, 2) Numpy 배열.
    • Numpy의 장점: 단일 자료형으로 동작하여 리스트보다 속도가 빠르고 메모리 효율적임.

2. 자료구조의 세계 (추상화에서 구체화로)

추상 자료형(ADT)은 일련의 변수와 연산으로 동작이 정의되는 고수준 추상화 개념입니다.

• 선형 자료구조
  • 스택(Stack): 후입선출(LIFO) 구조.
  • 큐(Queue): 선입선출(FIFO) 구조. 앞에서 제거하는 것을 '디큐', 뒤에서 추가하는 것을 '인큐'라 함.
• 트리(Tree) : 계층적 저장 구조
  • 정트리: 모든 노드의 차수가 동일한 트리.
  • 포화트리: 모든 리프 노드의 레벨이 동일한 특수한 정트리.
  • 순서트리: 특정 기준에 따라 자식 노드들이 일정한 순서로 정렬된 트리.

3. 알고리즘: 정렬과 탐색

데이터를 효율적으로 처리하기 위한 알고리즘의 종류와 선택 기준입니다.

[정렬 알고리즘]

• 버블 정렬: 구현이 단순하나 비효율적. 원소 개수 1,000개 이하일 때 권장.
• 삽입 정렬: 정렬된 부분과 그렇지 않은 부분으로 나누어, 값을 올바른 위치에 '삽입'함.
• 병합 정렬(Merge Sort): 분할 정복 알고리즘. 초기 배열 상태와 무관하게 성능이 일정하게 유지됨.
• 셀 정렬: 인접 요소가 아닌, 일정 간격이 있는 요소를 비교하여 부분 정렬 후 수행.
• 선택 정렬: 매 패스마다 가장 큰(혹은 작은) 값을 찾아 위치를 바꿈.

[탐색 알고리즘]

• 선형 탐색 / 이진 탐색: 기본적인 탐색 기법.
• 보간 탐색: 찾고자 하는 값 자체를 수식에 활용하여 위치를 예측, 효율을 높이는 방식.

4. 알고리즘 설계와 복잡도 (P vs NP)

알고리즘 설계란 목표(정확성, 성능, 확장성)를 달성하기 위한 가장 효율적인 방식을 고안하는 것입니다. 특히 성능 분석에서 중요한 문제의 유형을 다음과 같이 구분합니다.

• P (Polynomial time): 다항 시간 내에 해결 가능한 문제.
• NP (Nondeterministic Polynomial time): 다항 시간 내에 해결할 수는 없지만, 해답이 주어지면 다항 시간 내에 '검증'은 가능한 문제.
• NP-난해 (NP-Hard): NP 문제만큼 어렵거나 그 이상인 문제 (아직 아무도 해법을 찾지 못함).
• NP-완전 (NP-Complete): NP 문제 중 가장 어려운 문제들.
  1. 증명을 생성하는 다항 시간 알고리즘이 알려져 있고,
  2. 제안된 증명이 최적임을 검증하는 다항식 알고리즘이 존재해야 함.