[자료구조&알고리즘] 1주차 - 2

알고리즘의 기술 방법

• 자연어를 이용한 서술적 표현 (영어 or 한국어)
  • 장점 : 대화나 의사소통을 통해서 전달하기 때문에 의사소통만 가능하다면 편하게 전달이 가능함
  • 단점
     말하는 사람과 듣는 사람에 따라 다르게 이해할 수 있어 일관성과 명확성이 떨어짐
     언어, 단어, 표현등에 의존적임
  • ex) 배열에서 최대값 찾기 알고리즘

배열에서 최대값 찾기 알고리즘 - 자연어

• 도식화 : 흐름도 (flowchart)
  • 장점 : 간단하고 명확하게 흐름을 표현 가능
  • 단점 : 복잡한 알고리즘을 표현하기에는 어려울 수 있음
  • ex) 배열에서 최대값 찾기 알고리즘

배열에서 최대값 찾기 알고리즘 - 흐름도

• 가상코드를 이용한 추상화 : 의사 코드 (pseudo-code)
  
  • 장점
     의사코드를 실제코드로 변환하기만 하면 되기 때문에 편하게 구현이 가능
     알고리즘 기술에 가장 많이 사용
     코드지만 프로그래밍 언어에 대한 의존성이 없음
     프로그램을 구현할 때의 여러가지 문제들을 감출 수 있어서 핵심적인 내용에 집중 가능
  • 단점 : 전반적인 프로그래밍 지식이 있어야 함
  • ex) 배열에서 최대값 찾기 알고리즘

배열에서 최대값 찾기 알고리즘 - 의사 코드

• 프로그래밍 언어
  • 장점 : 가장 명확하게 알고리즘을 전달 가능
  • 단점
     상대방이 해당 언어를 알아야 하고 알고리즘을 이해 할 수 있어야 함
     다른 언어에 적용할 때 범용성이 떨어짐
     실제 구현 시, 많은 구체적인 사항들이 구현되어야 하기에 알고리즘의 핵심적인 내용에 대한 이해를 방해
  • ex) 배열에서 최대값 찾기 알고리즘

배열에서 최대값 찾기 알고리즘 - 프로그래밍 언어

 

추상 자료형(ADT)

• 추상 : 세세한 부분을 표현하지 않고 전체적인 이미지를 표현한 것

추상적인 표현의 예시

• 데이터 타입이 추상적?
  • 데이터나 연산이 무엇(what)인가는 정의 되지만 데이터나 연산을 어떻게(how) 컴퓨터 상에서 구현할 것인지는 제공되지 않음
• 추상화(Abstaction)?
  • 사용자에게 중요한 정보는 강조되고 중요하지 않은 구현 세부사항은 제거하는 것
• ADT
  • 세부 사항에서 벗어나 추상적으로 정의한 데이터 타입
  • 즉, 어떤 데이터 타입이 어떤 작업으로 이루어지는지 표현한 것
• ex) 리스트의 추상자료형 표현

리스트의 추상 자료형 표현

알고리즘의 성능 분석

• 알고리즘의 성능 분석 기법
  • 수행 시간 측정
    • 두개의 알고리즘의 실제 수행 시간을 측정 및 비교하는 것
    • 실제로 구현하는 것이 필요
    • 동일한 하드웨어를 사용해야함
    • ex) 수행 시간 측정 기법의 예

수행시간 측정 기법의 예

• 알고리즘의 복잡도 분석
  • 직접 구현하지 않고서도 수행 시간을 분석하는 것
  • 알고리즘이 수행하는 연산의 횟수를 측정하여 비교(시간 복잡도)
  • 구현하지 않고, 하드웨어/소프트웨어 환경 관계없이 평가 가능!
  • 일반적으로 입력의 개수 n에 때라 연산의 횟수가 달라짐
    ex) 양의 정수 n을 n번 더하는 문제를 해결하자.

복잡도 분석 기법의 예

• 왜 알고리즘의 성능 효율성이 중요한가?
  • 입력의 개수가 많아질 수 있기 때문에!
  • ex)

알고리즘의 성능 효율성이 중요한 이유

• 빅오(O) 표기법
  • 자료의 개수가 많은 경우에는 차수가 가장 큰 항이 가장 영향을 크게 미치고 다른항들은 상대적으로 무시될 수 있음
  • 간단하게 말하면 최고차항이 중요함
    (최고 차항에사 계수 뗀거)

빅오 표기법의 예시