알고리즘(Algorithm)

여러 개의 지시사항의 집합으로 이를 통해 문제를 해결하는 것을 의미

• 국소적으로 문제 해겨 순서라는 의미로 사용할 수도 있다

지시사항 : 문제를 해결하기 위해 순서가 있는 유한 개의 규칙을 명확하게 정의한 것

생성단계

설계 => 표현/기술 => 정확성 검증 => 효율성 분석

우선 정확도를 목표로 문제를 해결하려 노력하며 문제가 해결된 이 후에 효율성을 분석(리펙토링 혹은 코드 개선)하는 과정 필요

알고리즘 특성

• 명확성 : 알고리즘을 구성하는 각 명령의 의미는 모호하지 않고 명확해야 한다
• 유한성 : 알고리즘은 일정한 시간 내에 종료되어야 함
• 유효성 : 컴퓨터에서 실행 가능해야한다
• 효율성 : 효율적인(성능이 우수한) 알고리즘일수록 가치가 높다

지시사항 프로세스 구조

순차적(concatenation) 구조

• 여러 문장(프로세스)이 순차적으로 실행되는 구조

선택(selection) 구조

• if문처럼 평가 결과에 따라 실행 흐름을 변경하는 구조

반복(repetition) 구조

• 어떤 조건이 성립하는 동안 처리를 반복하여 실행하는 것
• 일반적으로 loop라고 부름
  • loop limit : 반복되는 구간을 칭함

반복문 판단 반복 구조

• 사전
  • 실행 전에 반복을 계속할지 판단
  • ex) while(제어식), for
    • 제어식 평가값이 0이 아니면 명령문 반복
    • 처음에 제어식 평가값 0 인 경우 본문 한번도 실행 X
• 사후
  • 한번 실행 후에 반복을 계속할지 판단
  • ex) do-while(제어식)
  • while문과 마찬가지로 제어식을 평가한 값이 0이 아니면 루프 본문의 명령문 반복
  • while문과의 차이점은 반드시 한번은 실행된다는 것

다중 루프

• 반복문의 중첩

복잡도

• 알고리즘의 성능을 객관적으로 평가하는 기준
  • 보통 최악의 경우(worst - case)의 시간 복잡도를 사용
  • O(f(n)) + O(g(n)) = O(max(f(n), g(n))) : f와 g의 차원 중 더 높은 쪽의 복잡도를 우선

종류

시간 복잡도 - time complexity

• 특정한 크기의 입력에 대하여 알고리즘 실행에 필요한 시간을 평가

공간 복잡도 - space complexity

• 기억 영역과 파일 공간이 얼마나 필요한가를 평가

• 보통 공간보다는 시간 복잡도의 영향이 더 컸던 것 같다

• Memoization 기법

  • 메모리를 더 많이 사용해서 시간을 비약적으로 줄이는 방법
  • ex) 처음 프로그램 실행 시에 변수 초기화처럼 한번만 실행되는 경우의 복잡도는 O(1)
    • 데이터 갯수와 무관

• BIG-O 표기법

  • 함수의 상한만을 나타냄 -> 가장 빠르게 증가하는 항만 고려
  • 복잡도는 연산 종류, 상황에 따라 상대적이며 빅오 표기법이 항상 절대적이지는 않다
  • ex) n^2 + n인 경우 복잡도는 n^2
    
    

• 결국 시간 복잡도와 공간 복잡도 사이를 저울질하며 문제를 해결하는 것이 최종 목표

• 프로그램 실행 시간 체크

• 시간 복잡도 계산

  import time
   start_time = time.time()
   end_time = time.time()
   print(end_time - start_time)

---

자료 구조(data structure)

자료구조

• 컴퓨터에 정보를 효율적으로 저장하고 관리하는 방법

  • 기억공간 내에 자료를 표현하고 조직화한다고 생각하면 된다

• 데이터 단위와 데이터 자체 사이의 물리적 또는 논리적인 관계

  • 데이터 단위 : 데이터를 구성하는 한 덩어리

• 자료를 효율적으로 이용할 수 있도록 컴퓨터에 저장하는 방법

종류

선형 자료구조 : 데이터에 순서 존재

• 배열, 연결리스트, 스택, 큐

비선형 자료구조 : 데이터에 순서 X

• 그래프, 트리
  • 트리는 그래프의 특수한 케이스로 두 개의 노드 사이에 반드시 1개의 경로만을 가짐
    
    
• 알고리즘과 자료구조는 상호보완적 관계
  • 알고리즘으로 순서화되어 자료구조가 만들어지고 다시 이 자료구조를 가지고 효율적인 알고리즘을 구현
  • 프로그램 = 알고리즘 + 자료구조

자료구조 특성

배열과 연결 리스트

• 빠른 접근을 원한다면 배열
• 데이터의 삽입, 제거 등 많은 index들의 수정을 요하다면 연결 리스트
  • 하지만 연결리스트를 이용한다면 검색 시에 처음부터 검색해야된다는 단점

스택과 큐

• 스택 : 막혀있는 둑
  • 후입선출
• 큐 : 뚫려있는 터널
  • 선입선출
• python의 경우 두 개 모두 기본 자료형 list 사용 가능

---

참고

순서도, 흐름도(flowchart)

• 이해하기 쉬운 장점
• 알고리즘이 복잡해질 수록 흐름도가 지나치게 복잡해짐
• 여러 가지 기호 이용해 반복문, 조건문 등을 표시
• 종류
  • 데이터
  • 처리
  • 미리 정의한 처리
  • 판단
  • 루프 범위
  • 선
  • 단말

변수

• actual argument - 실인수
  • 메서드를 호출할 때 사용하는 변수
• formal parameter - 가인수
  • 값 저장 위해 사용하는 변수
  • parameter라고 부름

분기

• 알고리즘에 의해 쪼개지는 흐름
• 프로그램의 순서도를 그렸을 때 프로그램이 진행되며 분리되는 모습

구조적 프로그래밍 - structured programming

• 하나의 입구와 하나의 출구를 가진 구성 요소만을 계층적으로 배치하여 프로그램 구성
• 제어 흐름
  • 순차
  • 선택
  • 반복