알고리즘 응용 준비
- SW 문제 해결 역량이란 ?
프로그램의 제약 조건과 요구사항을 이해하고 최선의 방법을 찾아내는 능력
= 코딩을 잘 하는 능력
프로그래머가 사용하는 언어나 라이브러리, 자료구조, 알고리즘에 대한 지식을 적재적소에 배치하고 연결하여 큰 그림을 만드는 능력
- 문제 해결 전략
- 하나하나 꼼꼼히 읽으면서 한 문장도 빼놓지 않고 이해하기
- 문제 풀이 전 계획을 세우기
- 프로그램으로 구현하기 → 검증 및 디버깅도 진행 가능
- 복잡도 분석
알고리즘 = 문제를 해결하기 위한 방법
알고리즘의 효율
→
공간적 효율성 : 연산량 대비 얼마나 적은 메모리 공간을 필요로 하는가
시간적 효율성 : 연산량 대비 얼마나 적은 시간을 필요로 하는가 (반복문을 얼마나 썼니)
효율성이 좋을수록 공간/시간 복잡도는 낮다. 실행시간이 더 빠르고 메모리를 조금 사용함.
- 빅오 표기
O 표기는 복잡도의 점근적 상한을 나타낸다.
상수는 버린다!! 최고차항만 따진다.
그래서 50번 반복하는 알고리즘도 빅오 표기법으로 나타내면 O(1) 이다.
그런데 가령 5배수를 강조해서 표현하고 싶을 때, O(N) 이라고 적지 않고, O(5N) 이라고 적기도 한다.
또는 기존 알고리즘은 7N 인데 2N 으로 발전시키면 2를 강조하려고 O(2N)이라고 적는 등
- 자주 사용하는 O 표기
O(1) : 상수 시간
O(log n) : 로그(대수) 시간
O(n) : 선형 시간
O(n log n) : 로그 선형 시간
O(n**2) : 제곱 시간
O(n**3) : 세제곱 시간
O(2**n) : 지수 시간
O(log n) 은 O(1) 보다는 느리지만, 유사한 성능을 보이고
O(n log n) 은 O(n) 보다는 느리지만, 유사한 성능을 보인다고 볼 수 있다.
ex)
pop(0) 의 시간 복잡도는 O(n) 이지만,
deque 모듈의 popleft()의 시간 복잡도는 O(1) 이다. 그래서 pop 말고 popleft 쓰는게 좋다.
시간 복잡도가 O(log n)인 연산 사례 → 이진탐색
시간 복잡도가 O(n log n)인 연산 사례 → sort
- 표준 입출력
콘솔 입력 대신, 파일 입력으로
import sys
sys.stdin = open('input.txt', 'r') # r = read
sys.stdout = open('output.txt', 'w') # w = write
num1, num2 = map(int, input().split())
print(num1 + num2, end=' ')
print(num1 * num2)
파일 출력도 가능하다!
연산 결과가 콘솔에 나오지 않고 파일에 입력된다.
- 진수 (진법)
10진수 : 사람이 사용하는 진수
2진수 : 컴퓨터가 사용하는 진수
16진수 : 2진수를 더 가독성 있게 사용, 수 하나를 0, 1, … 9, A, B, C … E, F 로 표현
16진수는 왜 중요할까?
→ 2진수를 10진수로 변환할 때 연산이 오래 걸리지만, 16진수로 변환 시 연산 속도가 매우 빠르다.
10진수를 2진수로 변환하는 코드 구현하기
tar = 149
result = []
while tar != 0: # 10진수를 지속적으로 2로 나눈다
result.append(tar % 2)
tar //= 2
result.reverse() # 마지막에 리스트를 거꾸로 뒤집는다.
print(result)
2진수를 10진수로 변환하는 코드 구현하기 (7 bit씩 쪼개서)
arr = '0000000111100000011000000111100110000110000111100111100111111001100111'
for i in range(0, len(arr), 7):
val = 0
for j in range(i, i + 7):
if arr[j] == '1':
val = val*2 + 1
else:
val = val*2 + 0
print(val, end=' ')
print()
# ======================================
for i in range(0, len(arr), 7):
print(int(arr[i:i+7], 2), end=' ')
print()
# ======================================
for i in range(0, len(arr), 7):
val = 0
for j in range(7):
if arr[i+j] == '1':
val |= (1 << (6 - j))
print(val, end=' ')
print()
arr = '0000000111100000011000000111100110000110000111100111100111111001100111'
# 7자리씩 읽어서 정수로 변환해서 출력
N = 7
arr = '0101001'
num = 0
for digit in arr:
num = num * 2 + (1 if digit == '1' else 0)
print(num)
num = 0
for i in range(N):
if arr[i] == '1':
num = num | (1 << (N-1 - i))
print(num)
# 가장 간단한 방법은 역쉬나...라이브러리 사용
print(int(arr, 2))
print(int('123', 5))
print(int('1a', 16))
print(bin(10), type(bin(10)))
print(oct(10))
print(hex(10))
16진수를 2진수로 변환하는 코드 구현하기
arr = '416A676F725974684D2050726F626C656D20536F6C76696E6'
hex_dict = { '0': '0000', '1': '0001', '2': '0010', '3': '0011',
'4': '0100', '5': '0101', '6': '0110', '7': '0111',
'8': '1000', '9': '1001', 'A': '1010', 'B': '1011',
'C': '1100', 'D': '1101', 'E': '1110', 'F': '1111' }
# 16진수를 2진수로 변환해서 List(또는 문자열)로 저장
bin_str = ''
for ch in arr:
bin_str += hex_dict[ch]
print(bin_str)
# =====================================================
hex_dict = { '0': [0, 0, 0, 0], '1': [0, 0, 0, 1], '2': [0, 0, 1, 0], '3': [0, 0, 1, 1],
'4': [0, 1, 0, 0], '5': [0, 1, 0, 1], '6': [0, 1, 1, 0], '7': [0, 1, 1, 1],
'8': [1, 0, 0, 0], '9': [1, 0, 0, 1], 'A': [1, 0, 1, 0], 'B': [1, 0, 1, 1],
'C': [1, 1, 0, 0], 'D': [1, 1, 0, 1], 'E': [1, 1, 1, 0], 'F': [1, 1, 1, 1] }
bin_str = []
for ch in arr:
bin_str += hex_dict[ch]
print(bin_str)
# =====================================================
bin_str = []
for ch in arr:
# ch => 정수로 변환
# if '0' <= ch <= '9':
# num = ord(ch) - ord('0')
# else:
# num = 10 + ord(ch) - ord('A')
num = int(ch, 16)
bin_str.append(1 if num & 8 else 0) # 8 == 1 << 3
bin_str.append(1 if num & 4 else 0) # 4 == 1 << 2
bin_str.append(1 if num & 2 else 0) # 2 == 1 << 1
bin_str.append(1 if num & 1 else 0) # 1 == 1 < 0
print(bin_str)
# ========================================
res = ''
for i in range(len(arr)):
tmp = bin(int(arr[i], 16)).lstrip('0b')
while len(tmp) < 4: tmp = '0' + tmp
res += tmp
print(res)