09/28-알고리즘

#상하좌우

: N x N 크기의 정사각형 공간 위에 서 있다. 가장 왼쪽 위 좌표는 (1,1)이고 가장 오른쪽 아래는 (N,N)이다. 이동은 상,하,좌,우로 할 수 있다.
L : Left / R : Right / U : Upper / D : Down

입력조건 N (공간의 크기 N x N)
2번째 입력은 방향 L L L R R 이렇게

출력은 X,Y(좌표!)
시간복잡도는 이동횟수가 x번이면 O(x)이다. 이거 예전에 자바로 풀었던 문제랑 비슷하지?

n = int(input())
x,y  = 1,1 #시작점
directions = input().split()

dx = [ 0, 0 , -1 , 1]
dy = [-1, 1 , 0 , 0]
move = ['L', 'R' , 'U', 'D']

for direction in directions:
	for i in range(len(move)):
    	if direction == move[i]:
        	nx = x + dx[i]
            ny = y + dy[i]
    #공간 벗어나면 무시
    if nx < 1 or ny < 1 or nx > n or ny > n :
    	continue
    x = nx
    y = ny

dx= [0,0,-1,1] dy = [-1,1,0,0] 인거에 대해서 생각해보자. 왜?
L이면 왼쪽으로 한칸이동 b<-a
함수관점에서는 왼쪽한칸이니까 (-1,0)이어야하지 않을까 생각할수 있는데, 행렬에서 생각해보면
(0,1)은 0행 1열이다. (세로가 행 가로가 열이라고 생각) 즉 L은 (0,1)에서 (0,0)으로 가는거니까 (-1,0)이 아니라 (0,-1)인것이다.
R은 오른쪽으로 한칸이동 (0,1)에서 (0,2)로 가니까 (0,1)이 된다.

공간 벗어나는거에 대한 조건은 시작점이 (1,1)이기때문에 1보다 작으면 안되는것이고 nx>n or ny>n인것은 n을 넘어서는순간 조건에서 어긋나게 되기때문이다.

#시각
:정수 N이 입력되면 00시 00분 00초부터 N시 59분 59초까지 모든 시각중에서 3이 하나라도 포함하는 모든 경우의 수를 구해야함.
입력 : 첫째줄에 정수 N이 입력
출력 : 경우의수 합

sol: 이런건 완전탐색유형으로, 그냥 다 풀면 된다. 일명 쌩노가다.

N = int(input())

count = 0
for i in range(N+1):
	for j in range(60): #minute
    	for k in range(60): #second
        	if '3' in str(i) + str(j) + str(k):
            	count = count + 1
                
print(count)

#왕실의 나이트

input= input()
row = int(input[1]) #행
column = int(ord(input[0])) - int(ord('a')) + 1

steps = [ (-2,-1), (-1,-2), (1,-2), (2,-1), (2,1), (1,2),(-1,2),(-2,1)]

result = 0

for step in steps:
	next_row = row + step[0]
    next_column = column + step[1]
    
    #해당하는 위치로 이동할수 있다면 카운트 증가
    if next_row >=1 and next_row <=8 and next_column >=1 and next_column <=8:
    result = result + 1
    

#DFS/BFS
탐색이란 많은 양의 데이터중에서 원하는 데이터를 찾는 과정이다. 자료구조는 '데이터를 표현하고 관리하고 처리하기 위한 구조'를 말한다.
Push : 데이터 넣고 / Pop : 데이터 뽑고

스택은 LIFO 로 나중에 들어간게 제일먼저 나온드아~
텅빔 -> 1 -> 12 -> 123 -> 12(3삭제) -> 1(2삭제) -> 텅빔(1삭제)

스택을 짜보면

stack = []
stack.append(5) # 5
stack.append(4) # 5 4
stack.append(9) # 5 4 9
stack.pop() # 5 4
stack.append(12) # 5 4 12
stack.append(145) # 5 4 12 145
stack.pop() #  5 4 12

print(stack) #맨 밑에 있는거부터 출력 5 4 12
print(stack[::-1]) # 최신꺼부터 출력 12 4 5 

큐는 스택이랑 다르게 FIFO이다. 먼저 들어온게 먼저 나간다.

from collections import deque

queue = deque()
queue.append(5)
queue.append(4)
queue.append(9)
queue.popleft()

print(queue) #먼저 들어온 순서대로 출력 5,4
queue.reverse() # 순서 뒤집기
print(queue) 4,5

#재귀함수
재귀함수를 할때는 종료조건을 꼭 넣어줘야한다. 그렇게 안하면 무한 루프가 되니까.... ㅠㅠ

팩토리얼을 구현해보는 2가지 버전
1)반복적으로 구현한 n!

def factorial(n):
	result = 1
    for i in range(1, n+1):
    	result = result * i
    return result

2)재귀적으로

def factorial(n):
	if n <= 1:
    	return 1
    return n * factorial(n-1)

#DFS: Depth-First Search, 깊이 우선 탐색이라고 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다.

DFS전에 그래프에 대해서 알아야하는데 그래프는 Node와 간선(edge)로 구성되고 , 노드를 Vertex(정점)이라고 부른다.
노드 - (간선) - 노드 (노드와 노드 사이 선을 간선이라고 한다잉. 기억!)
그래프 탐색이란 하나의 노드를 시작으로 다수의 노드를 방문하는 것. 두 노드가 간선으로 연결되어 있다면 두 노드는 인접하다(adjacent)라고 한다.

-인접 행렬(Adjacency Matrix):2차원 배열로 그래프의 연결 관계를 표현하는 방식
-인접 리스트(Adjacency List): List로 그래프의 연결 관계를 표현하는 방식

INF = 999999999 #무한
graph = [
[0, 5 ,2],
[6,0, INF],
[5,2,0]
]

여기까지 다음 DFS는 다시