[Advanced] 1. 시작하기 - 이론편

*SW Expert Academy - Advanced Course를 공부한 내용입니다.

이론

알고리즘

어떠한 문제를 해결하기 위한 절차로, 유한한 단계를 통해 문제를 해결하기 위한 절차나 방법이다. 

 

알고리즘의 복잡도

알고리즘의 효율성

알고리즘 설계 > 실행에 필요한 자원 분석 > 효율성 제시
공강적 효율성 / 시간적 효율성

점근적 표기 (Asymtotic Notation)

Big-O(점근적 상항), Big-Omega(점근적 하한), Theta(동일한 증가율) 표기법 등이 있다.

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

 

 

비트 연산

연산 속도를 향상시키거나 메모리 절약 가능

&	비트 AND 연산
|	비트 OR 연산
^	비트 XOR 연산(같으면 0 다르면 1)
~	비트 반전
<<	비트열을 왼쪽으로 이동
>>	비트열을 오른쪽으로 이동

ex)
양의 정수 값의 홀짝 판별 문제
1. 모듈러 연산자 이용 (N % 2)
2. AND 연산자를 이용해 마지막 비트값이 1인지 0인지 판단 (N & 1)

 

진수

진법 변환

• 10진수를 다른 진수로 변환하는 방법 ?
  원하는 n진수의 2로 나눈 뒤 나머지를 거꾸로 읽음

10진수의 2진수 변환

• n진수를 10진수로 변환하는 방법?
  각 자릿값에 해당 진수의 k제곱 값을 곱해서 구함

8진수의 10진수 변환

 

---

꿀팁!

비트연산

1 << n	2^n 값을 가짐 원소가 n개인 집합의 부분집합의 수를 의미 Power set - 공집합과 자기 자신을 포함한 모든 부분집합 - 각 원소가 포함되거나 포함되지 않는 2가지 경우의 수를 계산하면 모든 부분집합이 계산됨
i & (1 << j)	i의 j번째 비트가 1인지 아닌지 판별

⭐ 부분 집합들을 구하고 싶다면!

A # 집합
N = len(A)

for i in range(1<<N): # 2^N 만큼 반복
    part = [] # 부분 집합이 들어갈 리스트
    for j in range(N):
    	if i & (1<<j):
            part.append(A[j])
    print(part) # 부분집합 중 하나

 

비트 연산 예제

1. 특정 위치의 비트값을 확인하는 예제

def BitPrint(i):
    for j in range(7,-1,-1):
        print('1' if (i&(1<<j)) else '0', end="")
        
for i in range(-5,6):
    print(f"{i}=", end="") # 십진수 출력
    BitPrint(i) # 이진수 출력
    print()

실행결과

 

2. 엔디안

컴퓨터의 메모리와 같은 1차원 공간에 여러 개의 연속된 대상을 배열하는 방법

종류	0x1234의 표현
빅 엔디안	12 34
리틀 엔디안	34 12