본문 바로가기

algorithm88

[백준 2178번] 미로 탐색 from collections import deque n,m = map(int,input().split()) # n x m 크기의 미로 maze = [] # 방문 여부 확인용 2차원 배열 visited = [[False]*m for _ in range(n)] # 미로 입력받고 저장 for _ in range(n): maze.append(list(map(int,input()))) # bfs 함수 def bfs(x,y): # 방문 처리 visited[x][y] = True # queue 자료구조 선언 queue = deque([(x,y)]) while queue: v = queue.popleft() vx = v[0] vy = v[1] nx = [-1,1,0,0] ny = [0,0,-1,1] # 상-하-좌-우.. 2023. 2. 12.
[백준 2606번] 바이러스 from collections import deque vertex_count = int(input()) edge_count = int(input()) graph = [[] for _ in range(vertex_count + 1)] for _ in range(edge_count): x, y = map(int,input().split()) graph[x].append(y) graph[y].append(x) visited = [False] * (vertex_count+1) count = 0 def dfs(graph, v, visited): global count visited[v] = True count += 1 for i in graph[v]: if not visited[i]: dfs(graph,i,vis.. 2023. 2. 12.
[백준 1260번] DFS와 BFS from collections import deque n, m ,v = map(int,input().split()) graph = [[] for _ in range(n+1)] visited_dfs = [False] * (n+1) visited_bfs = [False] * (n+1) # 노드와 간선 정보 받기 for _ in range(m): x, y = map(int,input().split()) graph[x].append(y) # 두 정점 사이의 간선은 양방향이므로 양방향으로 저장 graph[y].append(x) # 방문할 수 있는 정점이 여러 개인 경우 정점 번호가 작은 것 부터 방문해야 하므로 # 각 노드마다 정렬 for i in graph: i.sort() # DFS 함수 구현 def dfs(.. 2023. 2. 12.
[BFS] BFS 알고리즘의 개념 및 동작과정 / DFS와 BFS 선정 기준 BFS는 Breadth-First Search, 너비 우선 탐색이라고 부르며 가까운 노드부터 탐색하는 알고리즘이다. BFS 구현에서는 선입선출 방식인 Queue 자료구조를 이용하는 것이 정석이다. 인접한 노드를 반복적으로 큐에 넣도록 알고리즘을 작성하면 자연스럽게 먼저 들어온 것이 나가게 되어, 가까운 노드부터 탐색을 진행하게 된다. BFS 알고리즘의 동작 과정 1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다. 2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 한다. 3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다. 너비 우선 탐색 알고리즘인 BFS는 Queue 자료구조에 기초한다는 점에서 구현이 간단하다. 실제로 구현 함에 .. 2023. 2. 11.
[DFS] DFS 알고리즘의 기본 개념 및 활용법 DFS DFS는 Depth-First Search, 깊이 우선 탐색이라고 부르며 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. 그래프의 기본 구조: 노드(Node) or 정점(Vertex) 간선(Edge) 그래프의 탐색이란 하나의 노드를 시작으로 다수의 노드를 방문하는 것을 말한다. 또한 두 노드가 간선으로 연결되어 있다면 두 노드는 인접(Adjacent)하다고 표현한다. 프로그래밍에서는 그래프를 크게 2가지 방식으로 표현할 수 있는데, 코딩테스트에서는 이 2가지 방식 모두 필요하니 두 개념에 대해 확실하게 알고 있도록 하자. 인접 행렬(Adjacency Matrix) : 2차원 배열로 그래프의 연결 관계를 표현하는 방식 인접 리스트(Adjacency List) : 리스트로 그래프의 연결 관계.. 2023. 2. 10.
[백준 5585번] 거스름돈 n = int(input()) change = 1000 - n money_unit = [500,100,50,10,5,1] count = 0 for i in money_unit: if change//i > 0: count += (change//i) change %= i print(count) 이번 문제는 그리디 알고리즘의 대표적인 기본 문제로, 그리디 알고리즘을 처음 공부할 때 내용을 이해하기 좋은 문제이다. 이 문제의 핵심은 잔돈을 최대한 적은 개수의 잔돈으로 거슬러주는 것인데, 위 문제와 같은 경우에는 모든 돈의 단위가 서로 배수 관계를 가지고 있기 때문에 단순히 금액이 큰 순서대로 거슬러 주어도 문제없이 풀 수 있다. 만약에 잔돈이 800원이고 가진 돈의 단위가 [500, 400, 100] 이라면 단.. 2023. 2. 8.

티스토리툴바