SW 문제 해결 응용

SW 문제 해결

문제 해결 역량

• 프로그램을 하기 위한 많은 제약 조건과 요구사항을 이해하고 최선의 방법을 찾아내는 능력
• 프로그래머가 사용하는 언어나 라이브러리, 자료구조, 알고리즘에 대한 지식을 적재적소에 퍼즐을 배치하듯 이들을 연결하여 큰 그림을 만드는 능력
• 훈련이 필요하다

문제 해결 과정

1. 문제를 읽고 이해

2. 문제를 익숙한 용어로 재정의한다

3. 어떻게 해결할지 계획을 세운다

4. 계획을 검증한다

5. 프로그램으로 구현한다.

복잡도 분석

알고리즘?

• 유한한 단계를 통해 문제를 해결하기 위한 절차나 방법이다.
• 주로 컴퓨터 용어로 사용되며, 컴퓨터가 어떤 일을 수행하기 위한 단계적 방법

알고리즘의 효율

• 공간적 효율성과 시간적 효율성

  • 공간적 효율성은 연산량 대비 얼마나 적은 메모리 공간을 요하는 가를 말한다
  • 시간적 효율성은 연산량 대비 얼마나 적은 시간을 요하는 가를 말한다.
  • 효율성을 뒤집어 표현하면 복잡도가 된다.

• 시간 복잡도 분석

  • 하드웨어 환경에 따라 처리시간이 달라진다.
    • 부동소수 처리 프로세서 존재유무, 나눗셈 가속기능 유무
    • 입출력 장비의 성능, 공유여부
  • 소프트웨어 환경에 따라 처리시간이 달라진다.
    • 프로그램 언어의 종류
    • 운영체제, 컴파일러의 종류

• 복잡도의 점근적 표기

  • 시간 복잡도는 입력크기에 대한 함수로 표기
  • O(Big-Oh) 표기
  • Ω(Big-Omega) 표기
  • Θ(Big-Theta) 표기

• O(Big-Oh) 표기

  • 복잡도의 점근적 상한을 나타낸다.
  • f(n) = 2n^2 - 7n + 4이라면 O-표기 : O(n^2)

• Ω(Big-Omega) 표기

  • 복잡도의 점근적 하한을 의미
  • f(n) = 2n^2 - 7n + 4이라면 Ω표기는 Ω(n^2)이다.
    • 의미 : n이 증가함에 따라 2n^2 - 7n + 4 이 cn^2보다 작을 수 없다.
  • 최소 시간을 의미

• Θ(Big-Theta) 표기

  • O표기와 Ω표기가 같은 경우 사용
  • f(n) = 2n^2 + 8n + 3 = O(n^2) = Ω(n^2)이므로 f(n) = Θ(n^2)이다.

• 자주 사용하는 O-표기

  O표기	Time
  O(1)	상수시간 (Constant time
  O(logn)	로그 시간 (Logarithmic time)
  O(n)	선형시간 (Linear time)
  O(nlogn)	로그 선형 시간 (Log-linear time)
  O(n^2)	제곱 시간 (Quadratic time)
  O(n^3)	세제곱 시간 (Cubic time)
  O(2^2)	지수 시간 (Exponetial time)

비트 연산

연산자	연산자의 기능
&	비트 단위로 And 연산을 한다. Ex) num1&num2
\	비트 단위로 OR 연산을 한다. Ex) num1\num2
^	비트 단위로 XOR 연산을 한다. Ex) num1^num2
~	단항연산자로서 피연산자의 모든 비트를 반전시킨다. Ex) ~num
<<	피연산자의 비트 열을 왼쪽으로 이동시킨다. Ex) num <<2
>>	피연산자의 비트열을 오른쪽으로 이동시킨다. Ex) num >> 2

• 1 << n
  • 2^n의 값을 갖는다
  • 원소가 n개일 경우의 모든 부분집합의 수를 의미
  • Power set(모든 부분집합)
    • 공집합과 자기 자신을 포함한 모든 부분집합
    • 각 원소가 포함되거나 포함되지 않는 2가지 경우의 수를 계산하면 모든 부분집합의 수가 계산
• i&(1<<j)
  • 계산 결과는 i의 j번째 비트가 1인지 아닌지를 의미
• 엔디안(Endianness)
  • 컴퓨터의 메모리와 같은 1차원의 공간에 여러 개의 연속된 대상을 배열하는 방법을 의미하며 Hw 아키텍처마다 다르다
  • 빅 엔디안
    • 보통 큰 단위가 앞에 나옴
  • 리틀 엔디안
    • 작은 단위가 앞에 나옴