1-1 클래스 기본(객체 정의 및 선언)

0. 객체지향 프로그래밍

프로그래밍에서 필요한 데이터를 추상화시켜 상태와 행위를 가진 객체를 만들고 그 객체들 간의 유기적인 상호작용을 통해 로직을 구성하는 프로그래밍 방법

1. 클래스

• 파이썬에서 사용자 객체를 정의하기 위해 사용하는 문법(class를 과자와 과자틀로 비유했을 때)

  • class: 객체를 만들기 위한 틀(과자틀)
  • 객체: class로 정의된 틀에 따라 만들어진 각 결과물(틀로 만들어진 과자)
    • 자신만의 속성과 행위를 가질 수 있음

• 메소드 정의: 객체에 필요한 메소드들은 class 코드 내에서 def로 정의

  • 메소드 내 self 매개변수: 객체 자신을 의미하는 매개변수
  • 특수 메소드: 객체와 관련한 특수한 역할을 맡는 메소드
    • 생성 메소드 init, str, repr 등

1-2 클래스 심화

1. 상속

• 상속: 기존에 있는 클래스의 기능들을 그대로 물려받는 것
• 다중 상속: 두 개 이상의 클래스로부터 상속 받는 것
  • 문제점: 상속하는 클래스끼리 메소드가 겹칠 경우 몇 개가 무시되는 오류 발생

1.1 오버로딩

• 오버로딩: 같은 함수 이름이지만 매개변수에 따라 다른 함수를 실행하는 것
  • 연산자 오버로딩
• 오버라이딩: 부모 클래스의 기존 메소드를 자식 클래스에서 재정의하는 것
• super 함수: 부모 클래스의 메소드를 자식 클래스에서 실행하는 함수

2. 캡슐화

• 캡슐화: 객체의 속성과 행위를 하나로 묶고 외부로부터 정보를 은닉하는 것
• 파이썬에서의 속성 변수 은닉
• 비공개된 속성 변수 열람
  • 열람용 메소드 생성
  • @property
    • 프로퍼티 장식자를 활용해 변수 접근의 통일성 유지 가능

2 자료구조

1 자료구조의 의미와 필요성

• 자료구조
  • 컴퓨터로 자료를 효율적으로 관리하기 위해 만든 구조
• 자료구조의 필요성
  • 전산화
  • 효율성
• 자료구조의 종류
  • 선형 자료구조: 자료들간의 앞뒤 관계가 1:1
  • 비선형 자료구조: 자료들 간의 앞뒤 관계가 1:N, N:N

2 선형 자료구조

• 배열: 파이썬의 리스트와 유사한데 제약이 더 많은 선형 자료구조
  • 같은 자료형만 담을 수 있음
  • 길이가 정해져있음
• 연결 리스트
  • 자료+링크로 이루어진 선형자료구조
  • 링크: 다음(이전)자료의 주소
  • 종류: 단순, 이중, 환형 등
• 스택(stack)
  • 가장 나중에 넣은 자료가 가장 먼저 나오는(LIFO)구조
  • 접시 빼기
• 큐(queue)
  • 가장 먼저 넣은 자료가 가장 먼저 나오는(FIFO)구조
  • 매표소
• 덱(deque)
  • double-ended queue의 줄임말, 양쪽에서 삽입/삭제가 가능한 큐

3 비선형 자료구조

• 그래프
  • 정점과 간선으로 구성
  • 여러 요소들의 다대다 관계
  • 종류: 무방향, 유방향, 가중치 등
  • 표현: 인접행렬, 인접리스트
• 트리
  • 노드와 간선으로 구성된 자료구조
  • 종류: 이진트리, 이진탐색트리 등
  • 그래프의 일종 -> 그래프의 표현 방법을 활용 가능
  • 배열로 표현 가능
  • class로 구현 가능
• 힙
  • 자료 내 우선순위가 가장 높은 값을 빠르게 찾는 트리의 일종
  • 부모 노드는 자식 노드보다 우선순위 높은 값을 보유
    • 루트 노드는 항상 최고 우선순위 값
  • 완전 이진 트리 형태로 구성
  • 힙의 자료 삽입
    • 배열 마지막에 값을 넣은 후, unheap 과정을 통해 제자리 찾기
  • 힙의 자료 삭제
    • 루트 노드에 있는 값을 마지막 단말 노드와 교체한 후 pop
  • 우선 순위 큐: 우선 순위가 가장 높은 원소가 가장 먼저 나오는 자료구조

3 정렬 알고리즘

3-1 정렬 알고리즘

• 여러 자료들을 기준에 맞게 순서를 재배치하는 알고리즘
• 자료를 정렬하면 -> 자료 탐색을 더 편리/빠르게 가능
• 정렬 알고리즘 평가 기준: 시간 복잡도, 공간 복잡도

3-2 버블정렬(기본)

• 인접한 두 값을 비교하여 큰 값을 뒤로 보내는 정렬
• 구현이 쉽지만, 시간복잡도가 높다는 단점을 가짐

3-3 선택정렬(기본)

• 남은 원소들 중 가장 작은 값을 찾아서 맨 앞으로 보내는 정렬
• 구현이 쉽지만, 시간복잡도가 높다는 단점을 가짐

3-4 삽입정렬(기본)

• 정렬된 앞쪽 리스트의 적절한 위치에 특정 원소(key)를 삽입하는 정렬
• 구현이 비교적 쉬우며, 정렬된 경우 시간 복잡도가 빠름(최선의 경우 O(n))
• 시간 복잡도가 높으며, 다른 알고리즘에 비해 교체가 빈번함
• 셸 정렬
  • 삽입 정렬이 정렬된 리스트에서 빠르다는 장점을 활용한 정렬
  • 일정한 간격 h마다 떨어져 있는 원소들끼리 삽입 정렬
  • h를 점점 줄이면서 최종적으로 h=1(=삽입 정렬)로 마무리

3-5 합병정렬(심화)

최소 단위(1개)까지 나누고 다시 합치면서 정렬하는 정렬
1. 자료를 균등하게 분할 -> 최소 단위(리스트 길이 =1)까지 반복
2. 분할했던 리스트를 정렬된 순서로 합병 -> 전체 리스트 범위까지 반복

• 시간 복잡도가 낮음
• 구현이 어려우며 추가 공간이 필요함

3-6 빠른정렬(퀵정렬, 심화)

피봇(특정 값)을 기준으로 작은 값과 큰 값들을 나눈 후, 그 값들을 다시 각각 정렬(=퀵 정렬)하는 정렬
1. 피봇을 선정
2. 피봇을 기준으로 작은 값과 큰 값으로 나누기
3. 나눈 값들을 각각 정렬(-> 빠른 정렬)
4. 합치기

• 시간 복잡도가 가장 낮음, 추가 공간 필요X
• 구현이 어려우며, 최악의 경우 시간 복잡도가 높아짐

3-7 힙정렬(심화)

4 알고리즘과 시간 복잡도

• 시간복잡도
  • 알고리즘이 수행되는데 걸리는 시간
  • 시간 복잡도가 높다 = 느리다
  • 알고리즘 성능 평가에 있어 중요한 요소
  • 알고리즘의 단위연산 횟수 바탕으로 계산
    • 단위연산: 해당 알고리즘의 핵심 연산이자 가장 자주 일어나는 연산
• 빅오 표기법
  • 기본적으로 가장 높은 차수에 절대적으로 비례해 수가 상승함
  • 식의 최고 차수가 무엇인지가 중요
  • 단위 연산 횟수 식의 최고 차수만 표기하는 것

5 탐색 알고리즘

5.1 탐색 알고리즘-리스트

• 리스트 탐색
  • 리스트(배열) 내에 특정 값이 있는지 찾는 방법
  • 1. 순차 탐색(선형 탐색)
    • 리스트의 첫 원소부터 시작해서 순차적으로 특정 원소를 찾는 방법
    • 모든 원소를 하나하나 비교해 찾는 원소인지 판단
    • 반환값으로 탐색 결과로 찾은 자료의 인덱스나 -1(못찾았을 때) 반환
    • 파이썬으로 구현

      def linear_search(my_list, find_value):
          for i in range(len(my_list)):
              if my_list[i] == find_value:
                  return i
          return -1

    • 시간 복잡도 O(n)
    • 파이썬의 in, .index() => 자체적으로 리스트 탐색 기능(순차 탐색)을 지원
  • 2. 이진 탐색
    • 정렬된 리스트에서 값이 있을 만한 방향으로 절반씩 좁혀가는 탐색
    • 시간복잡도 O(n)

5.2 탐색 알고리즘-트리&그래프

DFS(깊이우선탐색)

• 한 쪽으로 깊게 파고드는 방식으로 트리와 그래프를 탐색하는 방법
• 구현: 스택 자료구조 활용

BFS(너비우선탐색)

• 레벨이 같은 노드를 탐색하는 방식으로 트리와 그래프를 탐색하는 방법
• 큐 자료구조 활용
  • 큐의 front노드를 dequeue함으로써 해당 노드를 탐색

트리 순회

• 정의: 트리의 모든 노드들을 한 번씩 방문하는 방법
• 종류
  • 전위 순회: 자기 -> 왼쪽 -> 오른쪽
  • 중위: 왼 -> 자기 -> 오
  • 후위: 왼 -> 오 -> 자기
  • 레벨: 상위레벨 우선 탐색(=BFS)

6 해시 알고리즘

특정 계산(규칙)으로 값을 변환하여 자료 접근 속도를 높이는 알고리즘

해시 알고리즘

• 배열에 여러 자료를 저장하고 탐색하는 방법

1. 정렬되지 않은 경우 - 선형 탐색 활용
2. 정렬된 경우 - 이진 탐색 활용

• 해시 함수를 거쳐 특정 값에 대한 '해시 값'을 구할 수 있음

해시 충돌 해결

• 선형조사: 해시 값이 충돌한 경우, 그 다음부터 선형으로 탐색하는 방법
• 이차조사: 군집화 문제 해결 위해, 제곱수만큼 증가하는 방법
• 체이닝: 같은 해시 값을 가진 자료들을 같은 연결 리스트에 삽입

딕셔너리 & 집합

• 파이썬에서 지원하는 해시 테이블 자료형
• 딕셔너리가 해시 테이블인 이유
  • key를 해시 값으로 변환 후 관리
  • 개방 주소 방식 중에서 랜덤 조사 방식을 활용

7 단순하게 문제 풀기(Brute Force)

정의

• 특별한 전략 없이 가능한 모든 경우 탐색
• 시간 효율성 낮음, 정확성 보장
• = 완전탐색
• 예시) 순차 탐색, 선택 정렬, 삽입정렬

8 분할 정복 알고리즘

• 정의
  • 주어진 문제를 최소 단위까지 반복 분할해 문제를 해결
  • 분할한 작은 단위들을 풀면서 -> 마지막으로 전체 문제 해결
• 세 단계: 분할, 정복, 통합
• 예시
  • 이진탐색, 합병정렬, 빠른정렬

8-1 재귀함수

함수 안에 함수 자신을 다시 호출하는 함수

• 정의

  • 호출한 하위 함수가 종료되어야 상위 함수가 다시 진행

• 예시

  • 
  • 반복문을 중첩해서 사용하면 횟수가 N에 비례해서 커지는데 이때 간단하게 사용 가능

8-2 재귀함수와 꼬리 재귀함수

• 재귀함수
  • 사용 조건: 어떤 문제를 동일한 해결 과정의 부분 문제로 나눌 수 있는 경우(문제의 해결 과정에서 다시 그 문제가 반복해서 나타날 수 있는 경우)
  • 조건: 무한 재귀를 막기 위해 재귀 종료 조건이 포함되어야 함
  • 문제 적용하기 -> 두 조건 염두
    • 1. 재귀조건: 어떻게 동일한 과정의 부분 문제로 나눌까?
    • 2. 종료조건: 언제 재귀를 종료해야할까?
• 꼬리 재귀함수
  • 재귀함수의 연산 메모리 낭비 방지를 위해, 등장

9 그리디 알고리즘

• 그리디 알고리즘: 그 순간 가장 좋아보이는 답을 선택해가는 문제 해결 알고리즘

• 정의

  • 문제의 해결을 찾는 단계마다 욕심을 부리며 가장 최고의 답을 선택
  • 현재 선택지 중 가장 좋아보이는 경우를 매번 선택

• 설계

  • 1. 선정 과정 - 지금 가장 좋아보이는 해결책 선택
  • 2. 적정성 검정 - 그 해결책을 채택해도 되는가?
  • 3. 해답 점검 - 그리디의 결과가 실제 최적해랑 같은가?

9-1 배낭 문제

• 무게가 한정된 배낭 안에 최대한 가치의 합이 높게 물건들을 넣는 문제

• 종류

  • 1. 분할 가능 배낭 문제: 물건을 쪼개서 넣을 수 있는 배낭 문제
  • 2. 0-1 배낭 문제: 물건을 쪼개서 넣을 수 없는 배낭 문제

• 배낭 문제를 풀 수 있는 알고리즘

  • 그리디 알고리즘, 동적 계획법, 분기한정기법(백트래킹)

9-2 스터디룸 공유하기(작업 스케줄링 문제)

• 하나의 스터디룸을 최대한 많은 그룹이 사용할 수 있도록 하는 문제

• 기준에 따라 매 순간 가장 기준에 적합한 그룹 선택

9-3 다익스트라 알고리즘

• 한 노드(정점)를 기준으로 다른 노드와의 최단 거리를 구하는 알고리즘

10 DP(동적 프로그래밍, 동적 계획법)

하위 단계의 결과를 저장하고 이후 단계에서 재활용하는 알고리즘

• 정의

  • 이전 단계에서 습득된 정보를 이용해 다음 문제를 해결해 전체 문제를 해결하는 알고리즘
  • 이전 단계에서 계산된 정보를 재사용하여 불필요한 계산을 줄임
  • 각 단계마다 결과값을 저장해서 다음 계산에 재활용
  • 수학의 점화식과 유사한 형태
  • 계산 결과를 저장하고 다음 계산에 재활용하는 알고리즘 기법

• 어디에 쓰일까?

  • 피보나치 수열(재귀)
    • 각 수열 항의 결과값을 리스트에 저장해서 다음 항 계산에 재활용
    • 
    • 미리 이전 항의 값들을 저장해서 활용해 중복 계산이 줄어 효율성이 증가

• 활용하기

  • 10-1 행렬 경로 문제
    • 2차원 배열에서 좌상단에서 우하단으로 가장 많은 이득을 얻으며 가는 방법

11 되추적 기법

문제를 해결하다 특정 단계에서 막히면 전 단계로 되돌아가는 기법

• 정의

  • 적절한 해결안을 찾을 때까지 다양한 선택을 적용하여 문제를 해결
  • 미로 찾기
    • 쭉 가다가 길이 막히면 되돌아가는 백트래킹 예시

• 특징

  • 일반적으로 트리 구조로 접근
  • 유망성 여부를 점검 -> 가지치기

• N-Queens

  • 되추적 기법을 사용하는 대표적인 문제