th42500의 TIL

https://school.programmers.co.kr/learn/courses/30/lessons/43164 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr ✔ 입출력 예시 💡 포인트 1️⃣ 항상 "ICN" 공항에서 출발 2️⃣ tickets 배열의 원소는 [출발지, 도착지] 형태로 이루어짐 3️⃣ 주어진 항공권을 모두 사용해야 함 4️⃣ 만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return ❓ 풀이방법 처음에는 BFS 알고리즘을 이용해볼까 생각했지만 알파벳 순서가 앞서는 경로를 답으로 구해야했기 때문에 DFS 알고리즘을 이용..

https://school.programmers.co.kr/learn/courses/30/lessons/1844 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr ✔ 입출력 예시 💡 포인트 1️⃣ 최단거리를 구해야 하므로 BFS 알고리즘 활용 https://ichijeochi.tistory.com/43?category=1012068 BFS (Breadth-First Search) BFS (Breadth-First Search) 그래프 탐색 알고리즘 탐색(Search)이란 많은 양의 데이터 내에서 원하는 데이터를 찾는 과정을 의미 BFS 그래프에서 부모 노드를..

BFS (Breadth-First Search) ✔ 그래프 탐색 알고리즘 탐색(Search)이란 많은 양의 데이터 내에서 원하는 데이터를 찾는 과정을 의미 ✔ BFS 그래프에서 부모 노드를 먼저 방문한 후, 방문했던 부모 노드의 자식 노드를 차례로 탐색하는 알고리즘으로, 너비 우선 탐색이라고도 불림 선입선출 형태의 Queue자료구조 활용 트리일 경우 순회 방향 (번호 순서대로 진행) 시간복잡도 : O(V+E) 👉 V : 노드 수, E : 에지 수 ✔ 동작 과정 1️⃣ 탐색 시작 노드를 Queue에 삽입하고 방문 처리 2️⃣ Queue에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리 3️⃣ 2️⃣ 과정을 수행할 수 없을 때까지 반복 ✔ 예시 1️⃣ 시작 ..