[코딩 테스트/파이썬] 시험 직전 벼락치기 검토 노트

10진수에서 (2진수, 8진수, 16진수)로 변환 - bin(), oct(), hex() 내장함수
+) @진수에서 10진수로 변환 - int(문자열, @) 내장함수

value = 7 

# 10진수에서 2, 8, 16진수로 

b = bin(value) 
o = oct(value) 
h = hex(value) 

print(b) # 0b111 
print(o) # 0o7 
print(h) # 0x7 


# 2, 8, 16진수에서 10진수로 

d_2 = int(b, 2) 
d_8 = int(o, 8) 
d_16 = int(h, 16) 

print(d_2) # 7 
print(d_8) # 7 
print(d_16) # 7

"전수조사를 유도하는 문제의 함정에 빠지지 않기 위해서는 입출력의 패턴을 먼저 조사할 것"
예시 문제 - LV2. 2개 이하로 다른 비트
https://programmers.co.kr/learn/courses/30/lessons/77885#

코딩테스트 연습 - 2개 이하로 다른 비트

for - else 문 - for 문이 break로 종료되지 않았을 때 수행하는 코드 +) while - else 문도 있음

data = [1, 2, 3, 4, 5] 

for i in data: 
  if i > 5: 
    break 
else: 
  print('5 보다 큰 수 없음') 
    
    
# 5 보다 큰 수 없음

DP (동적계획법) 문제
특정 범위까지의 값을 구하기 위해서 그것과 다른 범위까지의 값을 이용하여 효율적으로 값을 구하는 알고리즘 설계 기법
ex) 표 문제
- 3중 이상의 반복문으로 중복된 탐색을 수행하지 말고, 정답을 누적시켜 표 값을 증가시켜 나가기
예시문제 - LV2. 가장 큰 정사각형 찾기
https://programmers.co.kr/learn/courses/30/lessons/12905

코딩테스트 연습 - 가장 큰 정사각형 찾기

"표 문제 수행시간 단축시킨다고 np.array로 변환하기 이전에 입력 데이터가 행렬이 맞는지부터 확인하기"

"3중 이상의 반복문으로 입력 값의 앞, 뒤를 왔다갔다하며 비교하고 있다면 알고리즘을 잘못 짰을 확률이 매우 높다."
→ 이 경우, 스택/큐의 사용으로 간단히 해결될 때가 많음

BFS(Breadth First Search, 너비 우선 탐색)
너비를 우선해서 그래프를 탐색하는 기법. 시작점인 루트 노드와 같은 거리에 있는 노드를 우선으로 방문
- 큐(queue)를 이용하여 구현.
큐에서 노드를 꺼내어 인접한 노드 중 방문하지 않은 노드들을 큐에 넣고, 방문처리하는 행위를 반복

DFS(Depth First Search, 깊이 우선 탐색)
갈 수 있는 한 끝까지 탐색해 리프 노드를 방문하고, 이전 갈림길에서 선택하지 않았던 노드를 방문
- 스택(stack)을 이용하여 구현.

최소힙 / 최대힙 - heapq (최대힙은 원소에 -1 곱하여 사용)

import heapq 

### 최소힙 (그대로 사용) 

min_heap = [2, 3, 5, 1, 2]

heapq.heapify(min_heap) # 리스트를 최소힙으로 바꿈 

# 원소 추가 
heapq.heappush(min_heap, 0) 

# 최소값 접근 
print(min_heap[0]) # 0 

# 원소 삭제 
print(heapq.heappop(min_heap)) # 0 

print(min_heap[0]) # 1 


### 최대힙 (모든 값에 -1을 곱하여 사용) 

max_heap = [-x for x in min_heap] 

heapq.heapify(max_heap) # 리스트를 최소힙으로 바꿈 

print(-heapq.heappop(max_heap)) # 5

팩토리얼 계산 - math.factorial() - 구현할 시간 없다. 그냥 가져다 써라.

import math 

print(math.factorial(3)) # 6

큐(queue) - collections.deque - 양방향 큐
- 그냥 리스트에서 pop(0)을 사용해도 되지만 시간 복잡도가 N임

from collections import deque 

queue = deque() # 빈 큐 생성 

list = [1, 2, 3] 

queue = deque(list) # 기존 리스트를 큐로 변환 

queue.append(0) # 맨 뒤에 0 추가 

queue.appendleft(5) # 맨 앞에 5 추가 

print(queue) # deque([5, 1, 2, 3, 0]) 

queue.pop() # 0, 맨 뒤 원소 꺼내기 

queue.popleft() # 5, 맨 앞 원소 꺼내기

리스트 내 누적 곱 - functools import reduce - 곱 연산 말고도 다른 연산 수행 가능

from functools import reduce 

lst = [1, 2, 3, 4, 5] 

reduce(lambda x,y : x*y, lst) # 120

소수 판별
- 기본 알고리즘

def is_Prime(x): 
  for i in range(2, x): 
    if x % i == 0: 
      return False # 소수가 아님 
            
  return True # 소수임 
    
    
print(is_Prime(4)) # False 

print(is_Prime(7)) # True

- 개선된 알고리즘 (약수의 성질 이용)

import math 

def is_Prime(x): 
  for i in range(2, int(math.sqrt(x)) +1): 
    if x % i == 0: 
      return False # 소수가 아님 
            
  return True # 소수임 
    
    
print(is_Prime(4)) # False

print(is_Prime(7)) # True

- 범위 내 모든 소수를 찾아야 할 때 (에라토스테네스의 체 알고리즘)
1. 2부터 N까지의 모든 나연수를 나열한다.
2. 남은 수 중에서 아직 처리하지 않은 가장 작은 수 i를 찾는다.
3. 남은 수 중에서 i의 배수를 모두 제거한다. (i는 제거하지 않음)
4. 2번과 3번의 과정을 반복한다.

import math 

n = 100 

# 2부터 100까지의 모든 소수 찾기 

# 처음엔 모든 수가 소수(True)인 것으로 초기화(0과 1은 제외) 
array = [True for i in range(n+1)] 

# 2부터 n의 제곱근까지의 모든 수 확인 
for i in range(2, int(math.sqrt(n))+1): 
  if array[i] == True: # 소수인 경우, 남은 수인 경우 
    # i를 제외한모든 i의 배수 지우기 
    j = 2 
    while i * j <= n: 
      array[i*j] = False 
      j += 1 
            
            
# 모든 소수 출력 
for i in range(2, n+1): 
  if array[i]: 
    print(i, end=" ") 
        
        
# 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 

최단거리
- 다익스트라
- 플로이드워셜 알고리즘

최대공약수(gcd)

from math import gcd 

print(gcd(1071, 1029)) # 21

최대공배수(lcm) - reduce 이용하면 여러개도 가능

from math import gcd 

def lcm(x, y): 
  return x * y // gcd(x, y) 
  
  
print(lcm(1071, 1029)) # 52479

 

아스키코드 - ord(문자), chr(숫자)

print(chr(65)) # A
print(chr(97)) # a

print(ord("Z")) # 90
print(ord("z")) # 122