본문 바로가기

Coding Test/Graph

 (5)
[Programmers] 49191번 - 순위 1. 문제 파악문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/49191문제 정의: 방향이 있는 주어진 배열 값으로 순위를 매길수 있는 정점의 개수를 구해라.문제의 제약 파악 (입력값 크기, 상수 조건)선수의 수는 1명 이상 100명 이하입니다.경기 결과는 1개 이상 4,500개 이하입니다.results 배열 각 행 [A, B]는 A 선수가 B 선수를 이겼다는 의미입니다.모든 경기 결과에는 모순이 없습니다.2. 문제 풀이1. 입출력 케이스 도출 및 문제 풀이 도출 확인정점인 선수의 수가 100명이고 간선의 개수인 경기 결과는 4500개 이하이므로, 인접리스트(V + E)로 구현한 그래프를 DFS 탐색시에 시간복잡도 제한은 없다. 2. 핵..
[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. 핵심 문제 풀이 도출(문제 의도 파악)해당 문제는 인접행렬에서 조건에 맞는 경로를 모두 탐색하는..
[Programmers] 43165번 - 타켓 넘버 1. 문제 파악문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/43165문제 정의: 주어진 숫자의 +/- 수의 합으로 타켓 넘버를 만족하는 경우의 수를 구해라.문제의 제약 파악 (입력값 크기, 상수 조건)주어지는 숫자의 개수는 2개 이상 20개 이하입니다.각 숫자는 1 이상 50 이하인 자연수입니다.2. 문제 풀이1. 브루트 포스와 입력 크기에 따른 시간 복잡도 계산완전 탐색시 경우의 수는 2^(주어진 숫자의 개수)이다. 따라서 numbers.length = 20이므로 최대 2^20 = 1024^2 ≃ (10^3)^2 = 10^6 각 수는 +/-로 분기해서 그래보면 다음과 같다. 이는 그래프의 한 형태의 이진 트리로 표현할수있다. 깊이^..
[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차원 배열은 인접 행렬이다.그래프 탐색 문제 핵심 사항은 문제를 보고 어떤 방향으로 탐색할건지 정의를 해야한다. 이 문제에서는 순회 지점으로부터 수직과..

티스토리툴바