Python/DFS&BFS22 [Algorithm] 프로그래머스 타겟 넘버 | 파이썬 ※ 타겟 넘버 https://school.programmers.co.kr/learn/courses/30/lessons/43165?language=python3 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 해결 TIP DFS로 구현한다. 숫자 한 개에 대해 음수, 양수 2가지 경우의 수를 각각 뻗어나가며 모든 경우의 수 중에, 마지막 결과가 타겟과 같을 때 방법 하나를 추가하는 식으로 진행한다. 전체 코드 answer = 0 def dfs(numbers, target, result, idx): global answer # 깊이가 같고 마지막 결과가 .. 2024. 3. 26. [Algorithm] 백준 1260 DFS와 BFS | 파이썬 ※ 1260 DFS와 BFS https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 문제 해결 TIP DFS는 스택으로, BFS는 큐로 구현한다. 문제 해결 풀이 그래프 리스트에 각 노드가 연결된 정보를 표현한다. 전체 코드 from collections import deque N, M, V = map(int,input().split()) graph=[[] for _ in range(N+1)] for i in ra.. 2024. 1. 17. [Algorithm] BFS(Breadth-first search,너비 우선 탐색) BFS란? 시작 정점을 방문한 후 시작 정점에 인접한 모든 정점들을 우선 방문하는 방법이다. 두 노드사이의 최단경로를 탐색할때 활용하기 좋은 방식이다. 주로 queue을 사용하여 구현한다. BFS의 특징 해당 노드 주변을 먼저 탐색 두 노드 사이의 최단거리를 찾을 때 BFS 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사 해야 함 큐를 이용한 BFS 동작과정 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 한다. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다. 위의 과정대로 진행하면 1 2 3 8 7 4 5 6 순으로 노드를 탐색하게 된다. 일반적인 경우 실제 수행 시간은 .. 2024. 1. 5. [Algorithm] DFS(Depth-First Search,깊이 우선 탐색) DFS란? 트리나 그래프에서 한 루트로 탐색하다가 특정 상황에서 최대한 깊숙이 들어가서 확인한 뒤 다시 돌아가 다른 루트로 탐색하는 방식이다. 대표적으로 백트래킹에 사용한다. 일반적으로 재귀호출을 사용하여 구현하지만, 단순한 스택 배열로 구현하기도 한다. 구조상 스택 오버플로우를 유의해야 한다. DFS의 특징 자기 자신을 호출하는 순환 알고리즘의 형태를 가지고 있다. 가중치가 주어지거나 특정 경로를 찾아야 할 때 DFS 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사 해야 한다는 것이다. 스택을 이용한 DFS 동작과정 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리를 한다. 방문하지 않은 .. 2024. 1. 5. 이전 1 2 3 다음
