Advance_Start

01 SW 문제 해결

- 소프트웨어(SW) 문제 해결 역량

: 프로그램 작성을 위한 많은 제약 조건들과 요구사항들을 이해하고 최선의 방법을 찾아내는 능력
프로그래머가 사용하는 언어, 라이브러리, 자료구조, 알고리즘에 대한 지식을 적재적소에 연결하여 큰크림을 만드는 능력

 

- 문제 해결 능력 향상

: 조합 방법 공부
ex) 새로운 언어, 프레임 워크, 개발 방법론
경험을 통해 나아지지 않는다 → 인위적인 상황을 만들어서 훈련해야 한다.

 

- 문제 해결 과정 단계

1. 문제 인지
2. 문제를 익숙한 용어로 재정의
3. 계획 세우기
4. 계획 검증
5. 프로그램 구현
6. 풀이 검토 및 개선 방안

⇒ 능력 향상을 위해 직관적인, 체계적인 접근이 필요하다.

• 비슷한 문제를 풀어본 적 있는가?
• 단순한 방법에서 시작할 수 있는가?
• 문제를 단순화 할 수 있는가? 그림으로 표현가능? 수식으로 표현가능?
• 문제를 분해 할 수 있는가?
• 뒤에서부터 풀 수 있는가?
• 특정 형태의 답만을 고려할 수 있는가?
•  

---

02 알고리즘 복잡도

• 알고리즘
  : 유한한 단계를 통해 문제를 해결하기 위한 절차나 방법
  주로 컴퓨터 용어로 쓰이며, 컴퓨터가 어떤 일을 수행하기 위한 단계적 방법
  어떤 문제를 해결하기 위한 절차

• 효율
  알고리즘 설계 → 필요한 자원 분석 → 효율성 제시
  1. 공간적 효율성
     : 얼마나 많은 메모리 공간을 요하는가?
  2. 시간적 효율성
     : 얼마나 많은 시간을 요하는가?
  • 시간적 복잡도 분석
    • 하드웨어 환경에 따라 처리시간이 달라진다.
      부동소수 처리 프로세서 존재 유무, 나눗셈 가속 기능 유무
      입출력 장비의 성능, 공유 여부
    • 소프트웨어 환경에 따라 처리시간이 달라진다.
      프로그램 언어의 종류
      운영체제, 컴파일러의 종류
    • 환경적 차이로 인해 분석이 어렵다.
• 시간(공간) 복잡도 점근적 표기

1. Big-Oh 표기
2. Bit-Omega 표기
3. Theta 표기

1: 점근적 상한, 2: 점근적 하한, 3: 상한과 하한이 같다. 라는 발상

 

- O-표기

O(1) : 상수 시간
O(logn) : 로그 시간
O(n) : 선형 시간
O(nlogn) : 로그 선형 시간
O($n^2$) : 제곱 시간
O($n^3$) : 세제 시간
O($2^n$) : 지수 시간

⇒ 효율적인 알고리즘이 컴퓨터 기능보다 더 큰 가치가 있다.

---

03 비트 연산

• 1 << n
  : $2^n$
  원소가 n개일 경우 모든 부분집합의 수
  Power set(멱집합)
• i & (i << j)
  : i의 j번째 비트가 1인지 아닌지를 의미

• 특정 위치의 비트값을 확인 예제

def BitPrint(i):
    for j in range(7,-1,-1):
        print('1' if (i &(1<<j)) else '0', end="")
        # print("%d" % ((i>>j)&1), end="")

for i in range(-5,6):
    print("%2d = " %i, end = "") # 십진수 출력
    BitPrint(i) # 이진수 출력
    print()
```  
```python
a = 0x10
x = 0x01020304
print("%d = " % a, end="")
BitPrint(a)
print()
print("%08x = " %x, end="")
for i in range(0,25,8):
  BitPrint(x>>i)
  print(end="")

• 엔디안(Endianness)
  : 컴퓨터의 메모리와 같은 1차원의 공간에 여러 개의 연속된 대상을 배열하는 방법
  • 주의 사항
    속도 향상을 위해 바이트 단위와 워드 단위를 변환, 연산시 올바르게 이해하지 않으면 오류 발생
• Big-endian : 보통 큰 단위가 앞에 나온다, 네트워크
• Little-endian : 작은 단위가 앞에 나온다, 대다수 데스크탑 컴퓨터

# 어떤 엔디안 방식인지 확인하는 코드  
n = 0x00111111

if n & 0x11:
    print("little endian")
else:
    print("big endian")

# XOR 연산자를 두번 사용하면 처음 값과 같다.  
a = 0x86
key = 0xAA

BitPrint(a)
print()

a ^= key
BitPrint(a)
print()

a ^= key
BitPrint(a)
print()

# 출력값 확인하세요.

---

04 진수

진수 변환은 10 → 2,8,16 이 있고, 2,8,16 → 10 이 있다.

 

보수란?
⇒ 두수의 합이 진법의 밑수가 되게 하는
수

• 절대값 표현, 1,2의 보수 표현
  : 제일 앞의 비트는 부호를 의미하고, 나머지는 값의 절대값을 비트로 표현한다.
  1의 보수는 부호 비트를 제외한 나머지 비트를 0→1, 1→0 로 반전시킨 표현
  2의 보수는 1의 보수의 최하위 비트에 1을 더한 표현

---

05 실수

• 부동 소수점(Flaoting-point) 표기법
  : 소수점의 위치를 고정시켜 표현하는 방식 (지수 제곱을 이용한 표기법)
  1001.0011 → 1.0010011 x $2^3$
• 컴퓨터 실수 저장 형식
  단정도 실수(32bit), 배정도 실수(64bit)로 나뉜다.
  python에서 float은 8bit이므로 배정도 실수를 사용한다.
  가수부(Mantissa)
  : 실수의 유효 자릿수들을 부호화된 고정 소수점으로 표현한 것
  지수부(Exponent)
  : 실제 소수점의 위치를 지수 승으로 표현한 것