必要な資料構造の基礎

何が探求ですか?

大量のデータから必要なデータを検索するプロセス.プログラミングでは,グラフィック,ツリーなどの資料構造において探索を行う問題によく関連する.

典型的なナビゲーションアルゴリズムはDFSとBFSを含む.しかし、この2つを理解するには、スタックとキュー、および再帰関数を理解する必要があります.

データ構造とは「データを表示、管理、処理するための構造」を表します。スタックとキューは、次の2つのコア関数からなる資料構築の基礎概念です。

삽입(PUSH) : 데이터를 삽입.
삭제(POP) : 데이터를 삭제.

もちろん、実際にスタックとキューを使用する場合は、挿入と削除に加えて、オーバーフローとバックフローも考慮されます.

オーバーフロー:データ構造が満たされている場合、挿入演算が実行されると発生します.すなわち,データが空間をオーバーフローすると発生する.
≪バックフロー｜Backflow｜oem_src≫:データ構造にまったく存在しない場合に削除操作を実行すると、データはまったく存在しません.

スタック

スタックとは?箱の山にたとえられる。先入後出

入口と出口が同じかごがあると思えば大丈夫です.

Pythonでスタックを使用する場合は、個別のライブラリを使用する必要はありません。基本リストでは、append()メソッドとpop()メソッドを使用して、スタックデータ構造と同じ操作を行うことができます。

stack = []

stack.append(5) 
stack.append(2)
stack.append(3)
stack.append(7)
stack.append(5)
stack.pop()
stack.append(1)
stack.append(4)
stack.pop


print(stack)
print(stack[::-1])

キュー

Q？行列にたとえることができます。先入先出

よく遊園地に並ぶように.先着順の「公正な資料構造」

Pythonキューを実装する場合は、Collectionsモジュールが提供するDequeデータ構造を使用します。

dequeはスタックとキューの両方の利点を採用しており、データの追加と削除速度はリスト型よりも効率的であり、quequeライブラリを使用するよりも簡単です。さらに、ほとんどのcoteでは、collectionsなどのデフォルトライブラリの使用も許可されています。

from collections import deque

queue = deque()

queue.append(5)
queue.append(2)
queue.append(3)
queue.append(7)
queue.popleft()
queue.append(1)
queue.append(4)
queue.popleft()
print(queue)
queue.reverse()
print(queue)

さいきかんすう

貴重な関数とは?独自の関数を再呼び出し

def recursive_function():
	print("재귀 함수를 호출합니다.")
    recursive_function()
    
    
    
recursive_function()

上の関数を実行すると、「再帰関数を呼び出します.」この無限
そしてエラー.

def recursive_function(i) : 


  if i == 100:
    return


  print(i, '번째 재귀 함수에서', i + 1, '번째 재귀 함수를 호출합니다')
  recursive_function(i + 1)
  print(i, "번째 재귀 함수를 종료합니다.")


recursive_function(1)

コンピュータ内部では,再帰関数の実行にスタックデータ構造を採用する.

したがって、スタックデータ構造を使用する必要があるアルゴリズムの多くは、再帰関数を使用して簡単に実現することができる。ex) DFS

*再帰関数の使用例

#반복적으로 구현한 n!
def factorial_iterative(n):
    result = 1


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

#재귀적으로 구현한 n!
def factorial_recursive(n):
    if n <= 1:
      return 1
    return n * factorial_recursive(n-1)

print(factorial_iterative(5))
print(factorial_recursive(5))

実行結果は同じです.では、文を繰り返すのではなく再帰関数を使用すると、どのようなメリットが得られますか?
=>数学の点化(再帰)をソースコードに直接移行できるため、コードはより簡潔になります.

ナビゲーションアルゴリズムDFS/BFS

<グラフィックベース>

グラフィックはノード(Node)と幹線(edge)で表され、ノードは頂点(Vertex)とも呼ばれます.

グラフィックブラウズとは、1つのノードから複数のノードにアクセスすることです.

2つのノードが幹線で接続されている場合は、「2つのノードが隣接している」ことを示します.

プログラミングでは、グラフィックは2つの方法で表すことができます.

<隣接マトリクス>:2 D配列を使用してグラフィックの接続関係を表します.
->ノードが多いほどメモリが無駄になります.

INF = 99999999999999 #무한의 비용 선언

#이차원 리스트를 이용해 인접 행렬 표현

graph = [
  [0, 7, 5],
  [7, 0, INF],
  [5, INF, 0]
]

<隣接リスト>:グラフの接続関係をリストで表す方法
=>2 Dリストを使用します.
->接続情報のみを格納するため、効率的に
->ただし、2つの特定のノードが接続されているかどうかの情報を取得する速度は遅い.

#행(Row)이 3개인 2차원 리스트로 인접 리스트 표현
graph = [[] for _ in range(3)]

#노드 0에 연결된 노드 정보 저장(노드, 거리)
graph[0].append((1,7))
graph[0].append((2,5))

#노드 1에 연결된 노드 정보 저장(노드, 거리)
graph[1].append((0,7))


#노드 2에 연결된 노드 정보 저장(노드, 거리)
graph[2].append((0,5))


print(graph)

DFS

動作原理:スタック、実装方法:再帰関数の使用

Depth-First Searchは、深さ優先探索とも呼ばれ、図形の中で深部を優先的に探索するアルゴリズムである.

このアルゴリズムは、特定のパスを検索し、特定の場合にできるだけノードに深くアクセスし、他のパスに戻って検索するアルゴリズムである.

スタック・データ構造に基づいています.実際には,スタックを書く必要がなく,ナビゲーションを実行する際にN個のデータがある場合にはO(N)時間が必要となる.

DFSはスタックを用いたアルゴリズムであるため,実際の実装は再帰関数を用いた場合に非常に簡潔である.

＜具体的な操作手順＞

1)ナビゲーション開始ノードをスタックに挿入してアクセス処理を行う.
2)スタックの最上位ノードに未アクセスの隣接ノードがある場合は,スタックに入れてアクセス処理を行う.アクセスされていない隣接ノードがない場合は、スタックから最上位ノードを取り出します.
3)2)再実行できなくなるまでプロセスを繰り返す.
tip)通常、隣接ノードに複数の未アクセスノードがある場合、番号の低い順序から処理を開始する./'「アクセス処理」は、スタックに1回挿入することで、処理ノードが再び挿入されないことを保証します.アクセス処理により、ノードごとに1回しか処理できません.

def dfs(graph, v, visetd):
  #현재 노드를 방문 처리
  visetd[v] = True
  print(v, end= ' ')
  #현재 노드와 연결된 다른 노드를 재귀적으로 방문
  for i in graph[v]:
    if not visetd[i]:
        dfs(graph, i, visetd)

#각 노드가 연결된 정보를 리스트 자료형으로 표현(2차원 리스트)
graph = [
[],
[2,3,8],
[1,7],
[1,4,5],
[3,5],
[3,4],
[7],
[2,6,8],
[1,7]

]

#각 노드가 방문된 정보를 리스트 자료형으로 표현(1차원 리스트)
visted = [False] * 9



dfs(graph, 1, visted)

BFS

動作原理:キュー、実装方法:キュー材料構造の使用

Breadth First Searchアルゴリズムは「幅優先探索」の意味を持つ.簡単に言えば,近接ノードから探索を開始するアルゴリズムである.

DFSはできるだけ遠くのノードを優先的に閲覧するように動作するが,BFSは逆であるという.

BFS実装では、通常、先入先出のキューリソース構造が採用される.実際の実装では、Dequeライブラリを使用することをお勧めします.また、ナビゲーションを実行するのにO(N)時間がかかります.

通常、実際の実行時間はDFSよりも優れている

アルゴリズムを記述して完全なノードをキューに繰り返し入れると,まず入った自然が先に出て,近いノードから検索を開始する.

＜具体的な操作手順＞

1)ナビゲーション開始ノードをキューに挿入してアクセス処理を行う.
2)ノードをキューから取り出し,そのノードのすべての隣接ノードにおいてアクセスされていないノードをキューに挿入し,アクセス処理を行う.
3)2)再実行できなくなるまでプロセスを繰り返す.

from collections import deque



def bfs(sraph, start, visted):

  #큐(queue) 구현을 위해 deque라이브러리르 사용
  queue = deque([start])
  #현재 노드를 방문 처리
  visted[start] = True
  #큐가 빌 때가지 반복
  while True:
    #큐에서 하나의 원소를 뽑아 출력
    v = queue.popleft()
    print(v, end=" ")
    #해당 원소와 연결된, 아직 방문하지 않은 원소들을 큐에 삽입
    for i in graph[v]:
      if not visted[i]:
        queue.append(i)
        visted[i] = True
      
#각 노드가 연결된 정보를 리스트 자료형으로 표현(2차원 리스트)
graph = [
[],
[2,3,8],
[1,7],
[1,4,5],
[3,5],
[3,4],
[7],
[2,6,8],
[1,7]

]

#각 노드가 방문된 정보를 리스트 자료형으로 표현(1차원 리스트)
visted = [False] * 9



bfs(graph, 1, visted)

coteの2次元配列でナビゲーションの問題が発生した場合は、グラフィック形式に変えて考えてください.

冷たい飲み物

n, m = map(int, input().split())


#2차원 리스트의 맵 정보 입력받기 
graph = []

for i in range(n):
  graph.append(list(map(int, input())))



#DFS로 특정한 노드를 방문한 뒤에 연결된 모든 노드들도 방문


def dfs(x, y):
  #주어진 범위를 벗어나는 경우에는 즉시 종료
  if x <= -1 or x >= n or y <= -1 or y >= m:
    return False

  #현재 노드를 아직 방문하지 않았다면
  if graph[x][y] == 0:
    #해당 노드를 방문처리
    graph[x][y] = 1
    #상, 하 , 좌, 우의 위치도 모두 재귀적으로 호출
    dfs(x-1, y)
    dfs(x, y-1)
    dfs(x +1, y)
    dfs(x, y+1)
    return True
  return False


#모든 노드(위치)에 대하여 음료수 채우기

result = 0
for i in range(n):
  for j in range(m):
    #현재 위치에서 DFS수행
    if dfs(i, j) == True:
      result += 1

print(result)

迷宮を脱出する

from collections import deque



#N, M을 공백으로 구분하여 입력받기

n, m = map(int, input().split())

#2차원 리스트의 맵 정보 입력받기
graph = []
for i in range(n):
  graph.append(list(map(int, input())))



#이동할 네 방향 정의(상, 하 , 좌, 우)
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]


#BFS 소스코드 구현

def bfs(x, y):

  #큐(queue) 구현을 위해 deque라이브러리 사용
  queue = deque()
  queue.append((x,y))

  #큐가 빌 때가지 반복
  while queue:
    x, y = queue.popleft()
    #현재 위치에서 네 방향으로의 위치 확인
    for i in range(4):
      nx = x + dx[i]
      ny = y + dy[i]
      #미로 찾기 공간을 벗어난 경우 무시
      if nx < 0 or ny < 0 or nx >= n or ny >= m :
        continue

      # 괴물이 있으면 못가니깐!
      if graph[nx][ny] == 0:
        continue

      #해당 노드를 처음 방문하는 경우에만 최단 거리 기록
      if graph[nx][ny] == 1:
        graph[nx][ny] = graph[x][y] + 1
        queue.append((nx, ny))

  # 가장 오른쪽 아래까지의 최단 거리 반환
  return graph[n-1][m-1]



#bfs를 수행한 결과 출력
print(bfs(0,0))