델타 탐색이란 현재 위치를 기준으로 우-하-좌-상 으로 방향 전환이 고정되어 있다는 점을 활용하여 방향 전환 횟수 및 각 방향에서 움직이는 횟수에 대한 규칙을 사용하는 풀이이다. 예시 문제 swexpertacademy : 1954_달팽이 숫자 문제 문제풀이 아이디어 N자리 달팽이 숫자에서 방향 전환은 (2N-1)번 일어난다. 각 방향에서 움직임 횟수는 N ~ N-1 ~ N-1 ~ N-2 ~ N-2 ~ … ~ 2 ~ 2 ~ 1 ~ 1 순으로 발생한다는 것을 알 수 있습니다. dr = (0, 1, 0, -1) dc = (1, 0, -1, 0) for tc in range(1, int(input()) + 1): N = int(input()) snail = [[0] * N for _ in range(N)] r,..
BFS 란? BFS와 DFS의 차이는 어떤 자료구조를 사용하느냐로 너비 우선 탐색인지, 깊이 우선 탐색인지 갈리게 된다. BFS는 Queue 자료구조를 사용하여 들어온 순서대로 나가는 FIFO 원칙에 따라 너비 우선 탐색이 수행된다. 코드 정리 V, E = map(int, input().split()) # Vertex, Edge 갯수 adj_matrix = [[0] * (V + 1) for _ in range(V + 1)] # 인접행렬 기본틀 for _ in range(E): # 간선 갯수만큼 돌면서 연결 정보를 받음 start, end = map(int, input().split()) # 시작점과 끝점 adj_matrix[start][end] = 1 adj_matrix[end][start] = 1 # ..
분류 Graph와 Tree의 구분은 Cycle이 생기냐 마냐의 차이이다. Tree는 Graph에 속한다. DFS는 크게 정보정리와 로직으로 구분된다. 정보정리 1. 인접행렬을 사용하여 자료구조를 (Tree 혹은 Graph) 표현(정보정리) 2. 인접 리스트를 사용하여 자료구조를 (Tree 혹은 Graph) 표현(정보정리) 로직 1. 스택을 활용한 풀이 2. 재귀함수를 활용한 풀이 따라서 4가지 경우의 수로 DFS를 풀 수 있다. 어떤 방식이 우월하다 하는 것은 없고, 많이 사용되는 방식은 인접행렬-스택 or 인접리스트-스택 방식이다.(이게 재귀보다 빠르기 때문) 다만 더 어려운 문제풀이의 경우 재귀방식이 사용된다.(ex) Segment Tree) 양방향 입력 예시 7 8 # Vertex = 7개, Edg..
코딩하며 알게되는 내용을 계속 업데이트할 예정입니다. 파이썬 내장함수 input()을 sys.stdin.readline()으로 변경하여 시간초과 해결. 입력부분에서 문자만 들어오는 경우와 문자,숫자 모두 들어오는 경우가 있었는데 (ex all , add 3 의 차이) text,num = sys.stdin.readline().split()# 이 아닌 text = sys.stdin.readline().split() #로 저장하여 text[0]과 text[1]에 저장되는 데이터를 불러 사용할 수 있음. strip() 함수로 \n이나 공백제거가 가능하더라. dictionary 자료형은 dict["key"] = values 형태로 저장가능함. DP문제에 대한 풀이가 익숙하지 않음.DP의 특성상 발생하는 idnex..
