SW 문제 해결

SW 문제 해결

프로그래밍을 하기 위한 많은 제약 조건과 요구 사항을 이해, 최선의 방법을 찾아내는 능력

추상적인 기술, 명확히 정의된 실체가 없다.

문제 해결 과정

1. 문제를 읽고 이해
2. 문제를 익숙한 용어로 재정의
3. 해결 계획 수립
4. 계획 검증
5. 프로그램으로 구현
6. 복기 및 개선 방법 탐색

문제 해결 전략

• 직관과 체계적인 접근

• 비슷한 문제 해결 경험

• 단순한 방법에서 시작

• 문제를 단순화

• 그림 및 수식으로 표현

• 문제 분해

• 뒤에서 접근

• 특정 형태의 정답만을 고려

알고리즘 성능

• 정확성 : 얼마나 정확하게 동작하는가

• 작업량 : 얼마나 적은 연산으로 결과를 만들 수 있는가

• 메모리 사용량 : 얼마나 적은 메모리를 사용하는가

• 단순성 : 얼마나 둔순한가

• 최적성 : 더 이상 개선할 여지없이 최적화되었는가

시간 복잡도 : 연산의 작업량, 수행 시간

• 최선의 경우(Best Case)

  • 빅 오메가 표기법 사용
  • 최선의 시나리오로 최소 이만한 시간이 걸림

• 최악의 경우(Worst Case)

  • 빅 오 표기법 사용
  • 최악의 시나리오로 아무리 오래 걸려도 이 시간보다 덜 걸림

• 평군적인 경우(Average Case)

  • 빅 세타 표기법 사용
  • 평균 시간을 나타냄

공간 복잡도 : 메모리 사용량

복잡도의 점근적 표기

시간(or 공간) 복잡도는 입력 크기에 대한 함수로 표기

단순한 함수로 표현위해 점근적 표기(Asymptotic Notation) 사용

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

빅-오(O) 표기법

시간 복잡도 함수 중에서 가장 큰 영향력을 주는 n에 대한 항만 표시

계수(Coefficient)는 생략하여 표시

Big O 시간 복잡도 그림