N-Queen
2022. 9. 27. 12:27
알고리즘 개념
제약 조건 같은 행에 두지 못한다. 같은 열에 두지 못한다. 대각에 두지 못한다. 행과 열의 정보를 저장할 1차원 리스트를 만든다. 리스트의 인덱스는 행번호, 요소는 열번호 대각에 있는지 확인 여부는 행값의 차이와 열값의 차이가 같으면 대각에 있다. 또는, 대각에 있는지를 기록해 놓는 방법도 있다. N*N 배열에서 대각선은 2N-1개 있다. (r, c)의 좌표가 어느 대각의 줄에 있는지 알면 된다. r + c 를 해보면 구별이 된다. 대략 2N개 정도의 크기를 가지는 1차원 리스트를 만들어 대각의 방문 체크를 한다. 반대의 대각은 r - c를 하면 구별할 수 있다. -(N-1) ~ (N-1)까지의 숫자가 나온다. 여기서 r-c+(N-1)을 해준다. 이 대각의 방문표시를 해줄 리스트를 2N정도로 만들어 준..
분할정복 병합정렬 (파이썬)
2022. 9. 26. 19:34
알고리즘 개념
병합 정렬 병합 정렬은 여러 개의 정렬된 자료의 집합을 병합하여 한 개의 정렬된 집합으로 만드는 방식 분할 정복 알고리즘을 활용 시간복잡도 O(nlogn) 분할 작업 병합 작업 파이썬 코드 from collections import deque; import sys; sys.stdin = open('input_분할정복_백트래킹.txt', 'r') def merge_sort(lst): global cnt if len(lst) == 1: return lst # 왼쪽과 오른쪽을 나눔 mid = len(lst)//2 left = lst[:mid] right = lst[mid:] # 왼쪽 부분과 오른쪽 부분을 재귀 l = merge_sort(left) r = merge_sort(right) # 병합 과정 rst는 ..
BFS_시작점이 여러개 (파이썬)
2022. 9. 10. 17:13
알고리즘 개념
BFS_시작점이 여러개 시작점이 여러개인 BFS 시작점이 여러개인 BFS탐색의 대표적으로 가스가 퍼지는 상황이 있다. 이 경우, 배열에 대해 완전 탐색을 하고, visited에 넣어 주는 값을 조금만 바꿔 주면 된다. 코드 def bfs(N, M): # 여러개의 시작점을 갖는 bfs, 시작점에서의 거리를 탐색하며 알아냄 for i in range(N): for j in range(M): if tomato[i][j] == 1: Q.append((i, j)) while Q: i, j = Q.popleft() for di, dj in [[0, 1], [1, 0], [-1, 0], [0, -1]]: nr, nc = i + di, j + dj if 0
Queue 큐 (파이썬)
2022. 9. 3. 21:18
알고리즘 개념
Queue Queue란? Queue는 기본적으로 stack과 동일하게 자료를 삽입, 삭제할 수 있는 자료 구조이다. 다른 점은 Queue에 삽입한 순서대로 원소가 저장되고, 가장 먼저 삽입한 원소는 가장 먼저 삭제가 된다. (선입 선출) Queue의 자료 인덱스를 가리키는 두 가지 변수가 존재한다. 머리(front)와 꼬리(rear)로 통상 지칭한다. Stack과 마찬가지로 원소를 삽입, 삭제할 때 Queue가 꽉찼는지, 비었는지 확인해야한다. 삽입과 삭제는 다음과 같이 이루어 진다. 초기 상태는 front = rear = -1이다. 생각해볼 점 Queue를 사용할 때 front와 rear를 두지 않고 append와 pop(0)을 이용하여 Queue를 사용할 수도 있다. 하지만 이런 경우, 삽입과 삭제가..
DFS (깊이 우선 탐색) (파이썬)
2022. 9. 3. 18:08
알고리즘 개념
DFS (깊이 우선 탐색) DFS란? 시작 정점의 한 방향으로 갈 수 있는 경로가 있는 곳까지 깊이 탐색해 가다가 갈 곳이 없게 되면, 가장 마지막에 만났던 갈림길의 갈 수 있는 경로로 다시 탐색하는 방법 가장 마지막에 만났던 갈림길의 정점으로 되돌아가야해서 후입선출 구조의 stack사용 DFS코드 (재귀) 나는 계속 재귀를 통한 DFS함수를 작성하고 사용해서 재귀만 쓰겠음. def dfs(v): # 함수에서 자체적으로 내부에 stack이 쌓이므로 따로 stack을 사용하지는 않음. visited[v] = 1 # visited에 방문 처리 for w in G[v]: # 간선의 정보를 담은 G리스트를 순회 if visited[w] == 0: # 방문 안했다면, dfs(w) # dfs 재귀s(w) 보면, 코..
BFS 너비우선탐색 (파이썬)
2022. 9. 2. 21:49
알고리즘 개념
BFS (너비 우선 탐색) BFS란? BFS는 탐색 시작점의 인접한 정점들을 먼저 모두 차례로 방문한 후에, 방문했던 정점을 시작으로 하여 다시 인접한 정점들을 차례로 방문하는 방식 인접한 정점들에 대해 탐색을 한 후, 다시 BFS를 진행해야 하므로 Queue를 사용 DFS와는 달리, 최고 깊이 까지 간 후 돌아오는 것이 아니라, 인접한 모든 정점을 차례대로 방문하고 그 다음 높이의 노드에 반복 그래프, 트리, 미로 등에서 활용가능함 BFS 코드 def bfs(v): # bfs 반복 코드 Q.append(v) # 일단, 시작점을 Q에 넣어준다. D[v] = 0 # D는 시작점 부터의 거리 visited[v] = 1 # visited 방문 해주고 while Q: # Q가 빈 리스트가 될 때 까지 v = Q..
Stack 스택 (파이썬)
2022. 9. 1. 23:00
알고리즘 개념
stack stack의 특성 물건을 쌓아 올리듯 자료를 쌓아 올린 형태의 구조이다. 저장된 자료는 1대1의 선형관계를 갖는다. 마지막에 삽입한 자료를 가장 먼저 꺼낸다. (후입선출) python에서는 list에 stack을 만든다. stack에 마지막 삽입한 자료의 위치를 top이라 부른다. push와 pop을 이용하여 자료를 삽입, 삭제한다. 참고 코드 stack = [0]*10 top = -1 for i in range(10): top += 1 stack[top] = i print(stack) # [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] 주의할 점 삽입할 때 에는 stack이 다 차있는지 확인해야 한다. 삭제할 때 에는 stack이 비어있는지 확인해야 한다. (비어있을 때 삭제하려하면,..
트리 순회 코드 (파이썬)
2022. 8. 28. 15:19
알고리즘 개념
def inorder(v): if v == 0: return # 전위순회 inorder(L[v]) # 중위순회 inorder(R[v]) # 후위순회