TIL - 2024/03/27

방향 전환하는 편리한 방법 in python

dx = [ 0, 1, 0, -1 ]
dy = [ -1. 0, 1, 0 ]

direction = 0

def turn(is_right):
	global direction
	
	if is_right:
		direction = (direction + 1) % 4
	else:
		direction = (direction - 1) % 4

모듈러(mod) 분배 법칙

알고리즘 문제 중 출력값이 너무 크기 때문에 특정 수로 나눈 나머지를 구하는 문제가 나온다.

결과 값에 단순히 mod 연산을 적용하면 이미 결과값이 너무 커진 상태에서 연산을 수행하기 때문에 연산 시간이 많이 소요된다. 아래의 모듈러 분배법칙에 따라서 연산 마다 모듈러 연산이 적용할 수 있기 때문에 알아두면 유용할 것 같다.

(A + B) % p = ((A % p) + (B % p)) % p
(A * B) % p = ((A % p) * (B % p)) % p
(A - B) % p = ((A % p) - (B % p) + p) % p

브루트 포스 알고리즘(Brute Force)

모든 경우를 다 따지며 해를 찾는 방식. 주어진 문제를 해결할 수있는 해가 있을 것으로 예상되는 구간을 설정하고, 무식하게 모든 경우의 수를 탐색하며 조건에 맞는 결과를 가져온다.

브루트 포스 알고리즘 경우 100%확률로 정답을 보여준다는 장점이 있다.

선형 구조를 탐색하는 선형 탐색, 비선형 구조를 탐색하는 너비 우선 탐색(BFS, Breadth First Search)와 너비 우선 탐색(WFS, Width First Search), 백 트레킹(Back Tracking)등이 있다. (추후 정리 예정)

• 조합 (Combination) 경우의 수.

  from itertools import combinations
  
  arr = ['A', 'B', 'C']
  print(list(cominations(arr,2))

• 순열 ( Permutaition) 순서를 고려하여 나열하는 경우의 수