본문 바로가기

Coding Test

 (34)
[Leetcode] 787번 - k 경유지 내 가장 저렴한 항공권 1. 문제 파악문제 링크: https://leetcode.com/problems/cheapest-flights-within-k-stops/description/문제 정의: 시작점부터 도착지점까지 k개의 정점을 거쳐서 가는 최단 거리를 구해라.문제의 제약 파악 (입력값 크기, 상수 조건)1 2. 문제 풀이1. 핵심 문제 풀이 도출(문제 의도 파악): 어떻게 하면 시간 복잡도 내로 줄일수 있을까?일단, 이문제는 최단 경로를 구하는 문제이다. 일반적인 최단 경로 문제는 다익스트라 알고리즘을 쓰는 것이 좋지만 이문제는 조건이 있다. 주어진 k개 만큼만 정점 이동이 가능하단 점이다. 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차원 배열은 인접 행렬이다.그래프 탐색 문제 핵심 사항은 문제를 보고 어떤 방향으로 탐색할건지 정의를 해야한다. 이 문제에서는 순회 지점으로부터 수직과..
[Programmers] 42626번 - 더 맵게 1. 문제 파악문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/42626문제 정의: 배열에 저장된 요소값이 K 미만이면, 가장 작은 2개의 값을 주어진 공식에 대입해서 결과값이 k이상이 될수있도록 반복한다. 그리고 모든 값이 K 이상이면 공식에 대입한 회수를 반환해라. 만일, 모든 값들이 k 이상이 될수없다면 -1을 반환해라.문제의 제약 파악 (입력값 크기, 상수 조건)주어진 배열의 길이는 2 이상 1,000,000 이하: 시간복잡도가 O(NlogN) 이내여야 통과한다.2. 문제 풀이1. 브루트 포스로 문제 풀이 도출기존의 배열에서 오름차순 정렬을 한다. -> 정렬: O(nlogn)가장 작은 값을 가져와서 K보다 작다면, 가장 작은 두개..
[Leetcode] 973번 - 원점에 가장 가까운 k개의 점 1. 문제 파악문제 링크: https://leetcode.com/problems/k-closest-points-to-origin/description/문제 정의: 이차원 배열에 저장된 각 배열의 두 요소의 제곱 합이 가장 작은 순서대로 k개를 반환해랴.문제의 제약 파악 (입력값 크기, 상수 조건)1 2. 문제 풀이1. 브루트 포스로 문제 풀이 도출이차원 배열을 각 배열의 두 요소의 제곱 합을 오름차순으로 정렬: O(nlogn)정렬한 배열을 k개 만큼 복사해서 반환: O(k)public int[][] kClosest(int[][] points, int k) { // O(NlogN) Arrays.sort(points, (a, b) -> { int distA = a[0] * a[0] +..
[Leetcode] 23번 k개의 리스트 병합 1. 문제 파악문제 링크: https://leetcode.com/problems/merge-k-sorted-lists/문제 정의: 주어진 오름차순 k개의 연결리스트를 하나의 오름차순 리스트 병합해라.문제의 제약 파악 (입력값 크기, 상수 조건)0 0 2. 문제 풀이1. 브루트 포스로 문제 풀이 도출부르트 포스로 풀이하면, 리스트들을 모두 순회하면서 순차적 병합하는 것이다. 연결리스트의 개수는 k개이고 각 연결리스트의 노드 개수가 n개이면, 이는 for(0 로직이므로 O(kn)이 걸린다. 2. 핵심 문제 풀이 도출(문제 의도 파악): 어떻게 하면 시간 복잡도 내로 줄일수 있을까?시간복잡도 내로 풀기 위해서는 O(NlogN)이나 O(N)으로 풀어야한다. 각 연결리스트의 순회 시간만 하더라도 O(N)이 걸린다..
[Leetcode] 739번 - 일일 온도 1. 문제 파악문제 링크: https://leetcode.com/problems/daily-temperatures/description/문제 정의: 배열을 순회하면서 현재 지정된 배열 요소보다 큰값이 몇 번째 뒤에 위치하는지 저장하는 배열 반환문제의 제약 파악 (입력값 크기, 상수 조건)1 30 2. 문제 풀이1. 브루트 포스로 문제 풀이 도출주어진 배열과 동일한 크기의 반환 배열을 초기화한다.배열을 순회하면서 순차적으로 요소 하나를 지정지정된 요소의 이후 배열 요소를 순회하면서, 지정된 요소보다 큰 요소 중에 가장 가까운 요소를 찾는다.지정된 요소의와 지정된 요소보다 큰 요소 중에 가장 가까운 요소의 인덱스 차이를 구한다.인덱스 차이를 반활 배열에 저장한다.for (int i = 0; i 두개의 요소..

티스토리툴바