SW 문제해결 역량

• 프로그램을 하기 위한 많은 제약 조건과 요구 사항을 이해하고 최선의 방법을 찾아내는 능력
• 프로그래머가 사용하는 언어나 라이브러리, 자료구조, 알고리즘에 대한 지식을 적재적소에 퍼즐을 배치하듯 이들을 연결하여 큰 그림을 만드는 능력이라 할 수 있음
• 문제해결 역량은 추상적인 기술임
  • 프로그래밍 언어, 알고리즘처럼 명확히 정의된 실체가 없음
  • 무작정 알고리즘을 암기하고 문제를 풀어본다고 향상되지 않음
• 문제해결 역량을 향상시키기 위해서는 훈련이 필요함
• 문제해결 과정
  1. 문제를 읽고 이해한다.
  2. 문제를 익숙한 용어로 재정의한다.
  3. 어떻게 해결할지 계획을 세운다.
  4. 계획을 검증한다.
  5. 프로그램으로 구현한다.
  6. 어떻게 풀었는지 돌아보고, 개선할 방법이 있는지 찾아본다.

복잡도 분석

알고리즘의 효율

• 공간적 효율성

  • 알고리즘이 필요로 하는 메모리 공간

• 시간적 효율성

  • 알고리즘이 작업을 완료하는 데 걸리는 시간

• 효율성을 뒤집어 표현하면 복잡도가 됨. 복잡도가 높을수록 효율성은 저하됨

  ⇒ 시간적 효율성은 주로 입력 크기 n에 대한 연산 횟수로 나타낸다.

• 복잡도의 점근적 표기

  • 시간 또는 공간 복잡도는 입력 크기에 대한 함수로 표기

    → 이 함수는 주로 여러 개의 항을 가지는 다항식임. 이를 단순한 함수로 표현하기 위해 점근적 표기 (Asymptotic Notation)를 사용

표기법

• 입력 크기 n이 무한대로 커질 때의 복잡도를 간단히 표현하기 위해 사용하는 표기법

O(Big-Oh) 표기

• O-표기는 복잡도의 점근적 상한을 나타냄

• 복잡도가 f(n) = 2n² - 7n + 4 이라면, f(n)의 O-표기는 O(n²)

• 먼저 f(n)의 단순화된 표현은 n²

• 단순화된 함수 n²에 임의의 상수 c를 곱한 cn²이 n이 증가함에 따라 f(n)의 상한이 된다.

  (단, c > 0)