Coding Test/DFS,BFS

[[Algorithm] ] BFS 알고리즘 기본 함수 작성 방법 (파이썬)

안녕하세요. Harry입니다. 본 포스팅의 목적은, 코딩테스트를 준비함에 있어 스스로 공부한 지식을 정리하고자 합니다. 오늘 작성할 내용은 굉장히 간단한 문제지만, 제가 간과하고 있던 부분이라 따로 작성하게 됐습니다. BFS알고리즘을 함수로 만들때, 탐색조건을 작성하는 순서가 매우 중요하다는 것입니다. 결론부터 말씀드리면, BFS알고리즘 함수 정의 시, 1. def bfs(x,y): 2. q = deque() 선언 3.q에 x,y 담기(append) 4. while q 5. x,y = q.popleft() 6. for i in range(4) (동서남북 방향 탐색) -------여기 까진 알던 내용 ------- 7. if 범위 이탈, continue 8. if 갈 수 없는 영역, continue 9. ..

[Algorithm] DFS 알고리즘(깊이 우선 탐색) 코딩테스트 문제 유형 분석(파이썬)

안녕하세요. Harry입니다. 본 포스팅의 목적은, 코딩테스트를 준비함에 있어 스스로 공부한 지식을 정리하고자 합니다. 앞서 정리한 DFS 알고리즘 기초 학습에 이어 코딩테스트에선 어떤 유형으로 등장하는지 정리한 내용을 올리고자 합니다. 이전 학습내용 [Algorithm] DFS 알고리즘(깊이 우선 탐색)&BFS 알고리즘(너비 우선 탐색)이란? 안녕하세요. Harry입니다. 본 포스팅의 목적은, 코딩테스트를 준비함에 있어 스스로 공부한 지식을 정리하고자 합니다. - 무슨 개념인지? - 개념이 나오게 된 배경은? - 그 개념은 왜 쓰는지? - 장점 hyem5019.tistory.com 1. DFS 알고리즘이란? 그래프 탐색 시 시작 노드부터 다음 분기로 넘어가기 전 해당 분기를 모두 탐색하고 넘어가는 탐색..

[DFS 알고리즘] 1388번 바닥장식 풀이(파이썬)

안녕하세요. Harry입니다. 본 포스팅의 목적은, 코딩테스트를 준비함에 있어 백준에 제시된 문제 풀이와 스스로 얻은 정보를 정리하고자 합니다. 그러므로 단순히 문제를 푸는 것이 중요한 것이 아니라, 문제를 통해 얻어가는 것이 있어야하기 때문에 접근 방식은 이전 기초 300제를 풀었을 때랑 동일합니다. [접근 방식] - 문제에서 요구하는 역량은 무엇인지? - 알고 있어야하는 지식은 무엇인지? 에 기반하여 풀이하고자 합니다. - 백준 문제 링크입니다. : https://www.acmicpc.net/problem/1388 1388번: 바닥 장식 형택이는 건축가이다. 지금 막 형택이는 형택이의 남자 친구 기훈이의 집을 막 완성시켰다. 형택이는 기훈이 방의 바닥 장식을 디자인했고, 이제 몇 개의 나무 판자가 필..

[Algorithm] DFS 알고리즘(깊이 우선 탐색)&BFS 알고리즘(너비 우선 탐색)이란?

안녕하세요. Harry입니다. 본 포스팅의 목적은, 코딩테스트를 준비함에 있어 스스로 공부한 지식을 정리하고자 합니다. - 무슨 개념인지? - 개념이 나오게 된 배경은? - 그 개념은 왜 쓰는지? - 장점/단점은 무엇인지? - (유사한 것이 있다면) 서로 차이는 무엇인지? 를 최대한 고려하여 정리해보겠습니다. DFS알고리즘을 이해하기 위해선, 먼저 아래와 같은 사전지식 학습이 필요합니다. 1) 자료구조인 스택/큐에 대한 이해 2) 재귀함수에 대한 이해 3) 그래프(간선 및 노드, 가중치)에 대한 이해 4) 인접행렬 및 인접리스트에 대한 이해 위 내용은 다른 포스팅에서 다뤄보도록 하겠습니다. 1. DFS 알고리즘이란?(what?) 깊이 우선 탐색(DFS, Depth-First-Serach) 알고리즘으로, ..