본문 바로가기

graph

 (6)
[Programmers] 49189번 - 가장 먼 노드 1. 문제 파악문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/49189문제 정의: 주어진 간선 정보로 최단경로로 이동했을때 가장 간선의 개수가 많은 노드의 개수를 반환해라.문제의 제약 파악 (입력값 크기, 상수 조건): 인접 행렬은 O(V^2) = 20000 x 20000이므로 10^8을 초과해서 시간 내에 풀지 못한다. 그래서 인접 리스트O(V+E) = 20000 + 50000으로 풀수있다.노드의 개수 n은 2 이상 20,000 이하간선은 양방향이며 총 1개 이상 50,000개 이하의 간선2. 문제 풀이1. 핵심 문제 풀이 도출(문제 의도 파악): 어떻게 하면 시간 복잡도 내로 줄일수 있을까?최단 경로로 탐색했을때 간선의 개수가 가장..
[Programmers] 43162번 - 네트워크 1. 문제 파악문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/43162문제 정의: 주어진 인접 행렬에서 경로(네트워크)의 개수를 구해라.문제의 제약 파악 (입력값 크기, 상수 조건)컴퓨터의 개수 n은 1 이상 200 이하각 컴퓨터는 0부터 n-1인 정수로 표현i번 컴퓨터와 j번 컴퓨터가 연결되어 있으면 computers[i][j]를 1로 표현computer[i][i]는 항상 1입니다.2. 문제 풀이1. 입출력 케이스 도출 및 문제 풀이 도출 확인정점인 컴퓨터의 개수가 200개 이하이므로 주어진 인접행렬로 그래프 탐색을 하여도 40000 2. 핵심 문제 풀이 도출(문제 의도 파악)해당 문제는 인접행렬에서 조건에 맞는 경로를 모두 탐색하는..
[Leetcode] 787번 - k 경유지 내 가장 저렴한 항공권 1. 문제 파악문제 링크: https://leetcode.com/problems/cheapest-flights-within-k-stops/description/문제 정의: 시작점부터 도착지점까지 k개의 정점을 거쳐서 가는 최단 거리를 구해라.문제의 제약 파악 (입력값 크기, 상수 조건)1 2. 문제 풀이1. 핵심 문제 풀이 도출(문제 의도 파악): 어떻게 하면 시간 복잡도 내로 줄일수 있을까?일단, 이문제는 가중치의 최단 경로를 구하는 문제이다. 그러므로 다익스트라 알고리즘을 쓰는 것이 적합하지만, 주어진 `k`개 만큼만 정점 이동 제약조건이 있다. 따라서 무가중치에서 최단경로를 구하는 BFS도 쓸수있다.BFS로 탐색은 다음 레벨(깊이)의 인접한 정점들 중에서 가장 비용이 적은 정점까지의 거리를 업데이트..
[Leetcode] 743번 - 네트워크 딜레이 시간 1. 문제 파악문제 링크: https://leetcode.com/problems/network-delay-time/문제 정의: n개의 정점에서 시작 정점로부터 가장 늦게 신호를 받는 정점간에 시간을 구해라.문제의 제약 파악 (입력값 크기, 상수 조건)1 2. 문제 풀이1. 브루트 포스로 문제 풀이 도출그래프에서 노드간에 탐색을 하게 되면 n x n - 1 x n -2 ...이므로 n!이다. 따라서 브루트 포스로 풀면 100!시간을 초과하게된다. 2. 핵심 문제 풀이 도출(문제 의도 파악): 어떻게 하면 시간 복잡도 내로 줄일수 있을까?나의 경우에는 쉽게 풀기 위해서 주어진 2차원 배열로 입력받은 인접 행렬을 만들어서 다익스트라 알고리즘을 구현하였다.n개의 정점이 주어지므로 n x n 인접행렬을 생성하였..
[Leetcode] 17번 - 전화번호 문자 조합 1. 문제 파악문제 링크: https://leetcode.com/problems/letter-combinations-of-a-phone-number/문제 정의: 주어진 문자열 digits의 문자와 매칭되는 String 문자열을 digits의 길이만큼 조합한 문자열을 반환해라.문제의 제약 파악 (입력값 크기, 상수 조건)0 총 입력크기: digit에 매칭되는 문자열이 최대 길이 ^ digits의 길이 = 4^42. 문제 풀이1. 핵심 문제 풀이 도출(문제 의도 파악)입력: digits = "23"출력: ["ad","ae","af","bd","be","bf","cd","ce","cf"]위의 예시를 보면, 문자열 digits길이만큼 각 숫자가 가질 수 있는 문자 조합을 전부 나열해야한다. 그러므로 문자열 di..
[Leetcode] 200번 - 섬의 개수 1. 문제 파악문제 링크: https://leetcode.com/problems/number-of-islands/문제 정의: 십자가 형태인 상하좌우로 0이나 끝점으로 둘러 쌓인 1로 구성된 면적의 개수를 구해라.문제의 제약 파악 (입력값 크기, 상수 조건)m == grid.lengthn == grid[i].length1 총 입력크기: m × n = 900002. 문제 풀이1. 브루트 포스로 문제 풀이 도출각 칸마다 m x n 만큼을 순회할수있으므로 (m x n)^2이 되어서 O((mn)^2) 2. 핵심 문제 풀이 도출(문제 의도 파악)이 문제에서 주어진 2차원 배열은 인접 행렬이다.그래프 탐색 문제 핵심 사항은 문제를 보고 어떤 방향으로 탐색할건지 정의를 해야한다. 이 문제에서는 순회 지점으로부터 수직과..

티스토리툴바