[알고리즘 기초] 08_SW 문제해결 응용_1 / Python

[알고리즘 기초] 08_SW 문제해결 응용_1 / Python

[알고리즘 기초] 08_SW 문제해결 응용_1 / Python

1. SW 문제 해결

문제 해결 역량

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

 

문제 해결 과정

1. 문제를 읽고 이해한다.
2. 문제를 익숙한 용어로 재정의 한다.
3. 어떻게 해결할지 계획을 세운다.
4. 계획을 검증한다.
5. 프로그램으로 구현한다.
6. 어떻게 풀었는지 돌아보고, 개선할 방법을 찾는다.

 

문제 해결 전략

• 직관과 체계적인 접근

 

2. 복잡도 분석

알고리즘

• 유한한 단계를 통해 문제를 해결하기 위한 절차나 방법이다. 주로 컴퓨터용어로 쓰이며, 컴퓨터가 어떤 일을 수행하기 위한 단계적 방법을 말한다.
• 간단하게 다시 말하면 어떠한 문제를 해결하기 위한 절차라고 볼 수 있다.

 

알고리즘의 효율

• 공간적 효율성과 시간적 효율성
  • 공간적 효율성은 연산량 대비 얼마나 적은 메모리 공간을 요하는가
  • 시간적 효율성은 연산량 대비 얼마나 적은 시간을 요하는 가를 말한다.
  • 효율성을 뒤집어 표현하면 복잡도(Complexity)가 된다. 복잡도가 높을수록 효율성은 저하된다.
• 시간적 복잡도 분석
  • 하드웨어 환경에 따라 처리한시간이 달라진다.
    • 부동소수 처리 프로세서 존재유무, 나눗셈 가속기능 유무
    • 입출력 장비의 성능, 공유여부
  • 소프트웨어 환경에 따라 처리시간이 달라진다.
    • 프로그램 언어의 종류
    • 운영체제, 컴파일러의 종류
  • 이러한 환경적 차이로 인해 분석이 어렵다.

 

복잡도의 점근적 표기

• 시간(또는 공간)복잡도는 입력 크기에 대한 함수로 표기하는데, 이 함수는 주로 여러개의 항을 가지는 다항식이다.
• 이를 단순한 함수로 표현하기 위한 점근적 표기를 사용한다.
• 입력 크기 n이 무한대로 커질 때의 복잡도를 간단히 표현하기 위해 사용하는 표기법
  • O(Big-Oh) - 표기 등.

 

O(Big-Oh) - 표기

• 복잡도의 점근적 상한을 나타낸다.
• 가장큰 수 만 나타냄

 

자주 사용하는 O-표기

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

 

효율성

• 효율적인 알고리즘은 슈퍼컴퓨터보다 더 큰 가치가 있다.
• 값 비싼 H/W의 기술 개발보다 효율적인 알고리즘 개발이 훨씬 더 경제적이다.

 

3. 표준 입출력 방법

python3 표준입출력

• 입력
  • Raw값의 입력 : input()
    • 받은 입력값을 문자열 취급
  • Evaluated된 값 입력 : eval(input())
    • 받은 입력값을 평가된 데이터 형으로 취급
• 출력
  • print()
  • print("text", end="")
  • print("%d" % number)

 

4. 비트 연산

비트 연산자

연산자연산자의 기능

'&'	비트 단위로 AND 연산을 한다.
'|'	비트단위로 OR 연산을 한다.
'^'	비트단위로 XOR 연산을 한다.
'~'	단항 연산자로서 피연산자의 모든 비트를 반전 시킨다.
'<<'	피연산자의 비트 열을 왼쪽으로 이동시킨다.
'>>'	피연산자의 비트 열을 오른쪽으로 이동시킨다.

 

연산

• 1<<n
  • 2**n의 값을 갖는다.
  • 원소가 n개일 경우 모든 부분집합의 수를 의미한다.
  • Power set(모든 부분 집합)
    • 공집합과 자기 자신을 포함한 모든 부분집합
    • 각 원소가 포함되거나 포함되지 않는 2가지 경우의 수를 계산하면 모든 부분집합의 수가 계산된다.
• i&(1<<j)
  • 계산 결과는 i의 j번째 비트가 1인지 아닌지 의미한다.

 

엔디안(Endianness)

• 컴퓨터 메모리와 같은 1차원 공간에 여러 개의 연속된 대상을 배열하는 방법을 의미하며 HW아키텍처 마다 다르다.
• 주의: 속도 향상을 위해 바이트 단위와 워드 단위를 변환하여 연산 할 때 올바로 이해하지 않으면 오류를 발생시킬 수 있다.
• 엔디안은 크게 두 가지로 나뉨
  • 빅 엔디안
    • 보통 큰 단위가 앞에 나옴 : 네트워크
  • 리틀 엔디안
    • 작은 단위가 앞에 나옴. 대다수 데스크탑 컴퓨터

 

5. 진수

10진수 -> 타 진수로 변환

• 원하는 타진법의 수로 나눈뒤 나머지를 거꾸로 읽는다.2149-> 1

  2	74	-> 0
  2	37	-> 1
  2	18	-> 0
  2	9	-> 1
  2	4	->0
  2	2	-> 0
  	1

  • 149 -> (10010101)2

 

6. 실수

실수의 표현

• 컴퓨터는 실수를 표현하기 우해 부동 소수점 표기법을 사용한다.
• 부동 소수점 표기 방법은 소수점의 위치를 고정시켜 표현하는 방식이다.
  • 소수점의 위치를 왼쪽의 가장 유효한 숫자 다음으로 고정시키고 밑수의 지수승으로 표현1001.001 -> 1.0010011 X 2**3

 

실수를 저장하기 위한 형식

• 단정도 실수(32비트) 부호 1비트 | 지수 8비트 | 가수 32 비트
• 배전도 실수(64비트) 부호 1비트 | 지수 11비트 | 가수 52 비트
• 가수부(mantissa) : 실수의 우효 자릿수들을 부호화된 고정 소수점으로 표현한 것
• 지수부(exponent) : 실제 소수점의 위치를 지수 승으로 표현한 것

 

단정도 실수의 가수 부분을 만드는 방법

• 예: 1001.0011
  • 정수부 첫 번째 자리가 1이 되도록 오른쪽으로 시프트
  • 소수점 이하를 23비트로 만든다
  • 소수점 이하만을 가수 부분에 저장
  • 지수 부분은 스프트한 자리수 만큼 증가 또는 감소

 

단정도 실수의 지수 부분을 만드는 방법

• 지수부에는 8비트가 배정
• 숫자로는 0-255까지 나타낼 수 있지만, 음수 값을 나타낼 수 있엉 하므로 익세스 표현법을 사용
  • 익세스 표현법 : 지수부의 값을 반으로 나누어 그 값을 0으로 간주하여 음수지수와 양수지수를 표현하는 방법