회전
- 왼쪽으로 90도 회전하기
- 오른쪽으로 90도 회전하기
💻완전 탐색 I (Exhaustive Search)
I인 이유는 더 있다... 완전탐색에는 총 3가지가 있다.
- 무식하게 풀기(Brute-Force)
- 델타 탐색(Delta Search)
💻Brute Force Algorithm
모든 경우의 수를 탐색하여 문제를 해결하는 방식이다. 모든 알고리즘의 기초가 된다.
무식하게 모두 대입해서 푸는 방식이기에 input이 커짐에 따라 연산양 또한 늘어나게 되어서 시간복잡도 측면에서 효율성은 떨어지지만 어떠한 측면에서 보면 굉장히 간단하기 때문에 편리하다.
-
가장 단순한 풀이 기법이며, 단순 조건문과 반복문을 이용하여 풀 수 있다.
-
복잡한 알고리즘보다는, 아이디어를 어떻게 코드로 구현할 것인지가 중요하다.
💻Delta Search
이차원 리스트의 완전탐색에서 많이 등장하는 유형인 델타 탐색(상하좌우 탐색)을 알아보자.
해당 데이터 뿐만 아니라 인접한 데이터까지 동시에 탐색하는 기법이 델타탐색이다.
행과 열의 변량인 -1, +1을 델타(delta)값이라 한다.
행 +- 1 열 +- 1 해서 좌표를 계산함
# 1. 행을 x, 열을 y로 표현
dx = [-1,1,0,0]
dy = [0,0,-1,1]
# 2. 행을 r, 열을 c로 표현
dr = [-1,1,0,0]
dc = [0,0,-1,1]
# 아래처럼 간단하게 리스트 하나로 나타낼 수도 있다. 오직 파이썬에서만 가능하다. 킹갓파이썬!
delta = [(-1,0), (1,0), (0,-1), (0,1)]
# 위의 방식이 어떻게 가능한가? 파이썬에서는 튜플의 연산이 가능하기 때문이다.
(x,y) = (1,3) + (4,5)
print((x,y))
# 델타 값을 이용해 상하좌우로 이동해보자.
dx = [-1,1,0,0]
dy = [0,0,-1,1]
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
##############
delta = [(-1,0), (1,0), (0,-1), (0,1)]
for i in range(4): # 0,1,2,3
for j in range(4): # 0,1,2,3
for d in delta:
print(i + d[0], j + d[1]) # 0+델타값을 표현하는데에는 총 두가지 방법이 있다.
-
리스트 두개로 표현
-
리스트에 튜플을 저장하여 리스트 하나로 표현하는 방법
⛔다른 언어에서는 2번 방법을 사용할 수 없기 때문에 좀 더 일반적인 1번 방법 사용하는 것을 연습하자!
🍯델타탐색까지만 완벽하게 익히면 삼성 IM은 통과할 수 있다! 열심히 공부하자. Index Manipulation을 완벽하게 익힐 수 있도록 하자.
만약에 탐색을 하다가 범위를 벗어나게 된다면 어떻게 해야할까?
상하 좌우로 이동 후 범위를 벗어나지 않는지 확인 및 갱신해보자.
# 1. 델타값을 이용해 상하좌우 이동
for i in range(4):
nx = x + dx[i]
ny = y +dy[i]
# 2. 범위를 벗어나지 않으면 갱신
if 0 <= nx < 3 and 0 <= ny < 3:
x = nx
y = ny최종정리 (이차원 리스트의 상하좌우 탐색 정리)
# 1. 델타값 정의(상하좌우)
dx = [-1,1,0,0]
dy = [0,0,1,-1]
# 2. 이차원 리스트 순회
for x in range(n):
for y in range(m):
# 3. 델타값을 이용해 상하좌우 이동
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
# 4. 범위를 벗어나지 않으면 갱신
if 0 <= nx < n and 0 <= ny < m:
x = nx
y = ny나중에 델타 탐색을 응용하여 8방향 델타이동을 요구하는 문제에도 적용이 가능하다.