DFS
-
[Algorithm] - DFS를 통한 모든 경우의 수Algorithm/Algorithm 2022. 9. 24. 01:49
DFS 특정 Start를 기반으로 Node를 재귀로 타고 들어가 자신이 도착하는 경우의 수를 추출한다. 모든 경우의 수 구하기 아래 경우에서 Node 1에서 4로 가는 경우의 수를 탐색한다고 하여보자. DFS로 구현을 하게 된다면 일반적으로 1-2-3-4 탐색 후 끝나는 것이 일반적이지만, 우리는 모든 경우의 수를 구현해야 한다. 알고리즘 기존의 DFS코드를 활용한다. 이 때 나머지 경우에도 탐색을 해야하기 때문에 Visited edge값을 되돌려주고 임의의 값을 빼준다. 코드 n = 5 edges = [[1,2],[1,3],[2,3],[2,5],[3,4],[3,5],[5,4]] from collections import defaultdict def solution(n,edges): graphs = de..
-
[프로그래머스] - 여행경로Algorithm/프로그래머스 2022. 9. 16. 18:34
문제 [프로그래머스] - 여행경로 https://school.programmers.co.kr/learn/courses/30/lessons/43164 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 이해 더보기 문제 설명 주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다. 항상 "ICN" 공항에서 출발합니다. 항공권 정보가 담긴 2차원 배열 tickets가 매개변수로 주어질 때, 방문하는 공항 경로를 배열에 담아 return 하도록 solution 함수를 작성해주세요. 제한사항 모든 공항은 알파벳 대문자 3글자로 이루어집니다. 주어진 공항 수는 3..
-
[프로그래머스] - 네트워크Algorithm/프로그래머스 2022. 9. 5. 16:04
문제 [프로그래머스] - 네트워크 https://school.programmers.co.kr/learn/courses/30/lessons/43162 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 이해 더보기 문제 설명 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 ..
-
[Algorithm] - Graph( Node / Edge/ BFS / DFS )Algorithm/Algorithm 2022. 8. 30. 19:53
1. Graph Node와 Edge로 이루어진 자료구조 1-1) Direction fo Edge Degree = Node에 연결되어 있는 edge의 수 Indegree = Node로 들어오는 edge의 수 Outdegree = Node에서 나가는 edge의 수 Airflow의 기본 구조 1-2) 싸이클 임의의 한 점에서 출발해 자기 자신으로 돌아올 수 있는 경로 순환 그래프(Cyclic graph) = 싸이클이 한개 이상 비순환 그래프(Acyclic graph) = 싸이클이 X 1-3) 연결 그래프 서로 다른 Node 연결되어 있는 Edge를 보고 완전 그래프 / 연결 그래프인지 확인 주의점 : 일반적인 코딩테스트에 나오는 그래프는 단순 그래프(정점 사이의 Edge는 한개이며, 루프가 존재하지 않는다 )..