본문 바로가기

Coding Test

 (34)
[Programmers] 42897번 - 도둑질 1. 문제 파악문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/42897문제 요구사항: 턴 집의 최대 금액을 구해라.시간복잡도: 입력크기는 10⁶ 이므로 시간복잡도는 O(nlogn) 이내 여야한다. (10⁶ × 20 = 2 × 10⁷)2. 문제 풀이1. 문제 접근문제는 다음 2개의 조건이 있다.인접한 집은 동시에 털 수 없다.각 집의 금액 nums[i]는 0 이상이다.i번째 집을 털지 말지에 따라 선택지가 갈리게된다는 것을 알수있다. 구하고자 하는 것은 0 ~ i 까지 턴 집의 최대 금액이다. 4번째 집을 턴다면, 그전까지의 턴 집의 최대 누적합을 구해야한다. 따라서 그전까지의 턴 집의 최대 누적합은 작은 문제이고 앞으로의 턴 집의 최대..
[Leetcode] 198번 - 집도둑 1. 문제 파악문제 링크: https://leetcode.com/problems/house-robber/문제 요구사항: 턴 집의 최대 금액을 구해라.시간복잡도: 입력 크기가 100개이므로 2^n은 안된다.(2^10)^10 = 2^1002^10 = 10241,024^10≈(10^3)^10≈10^1010^10 > 10^8 이므로 시간 복잡도 초과2. 문제 풀이1. 문제 접근문제는 다음 2개의 조건이 있다.인접한 집은 동시에 털 수 없다.각 집의 금액 nums[i]는 0 이상이다.i번째 집을 털지 말지에 따라 선택지가 갈리게된다는 것을 알수있다. 구하고자 하는 것은 0 ~ i 까지 턴 집의 최대 금액이다. 4번째 집을 턴다면, 그전까지의 턴 집의 최대 누적합을 구해야한다. 따라서 그전까지의 턴 집의 최대 누적..
[Leetcode] 70번 - 계단 오르기 1. 문제 파악문제 링크: https://leetcode.com/problems/climbing-stairs/문제 요구사항: n번째 계단을 오르는 경우의 수를 찾아라. 계단은 1칸 혹은 2칸씩 오를수있다.시간복잡도: 입력 크기가 45개이므로 2^n은 안된다.(2^10)^4.5 = 2^452^10 = 10241,024^4.5 ≈ (10^3)^4.5 ≈ 10^13.510^13.5 > 10^8 이므로 시간 복잡도 초과2. 문제 풀이1. 핵심 문제 풀이 도출: 어떻게 하면 시간복잡도 내로 풀수있을까?일단, 문제의 패턴을 파악했다. 문제의 n >= 1 조건과 점화식의 f(n-2) 때문에, 점화식은 n > 2일때부터 성립한다. 그럼 점화식의 초기 조건은 n = 1일때 1이며, n = 2일때 2이다. 따라서 점화식..
[Leetcode] 53번 - Maximum Subarray 1. 문제 파악문제 링크: https://leetcode.com/problems/maximum-subarray/description/문제 정의: 배열 요소의 총합이 제일큰 subarray의 총합을 구해라.시간복잡도: 입력크기가 10^5 이기 때문에 시간복잡도는 O(nlogn)이햐여야한다.2. 문제 풀이1. 문제 접근 과정처음에 subarray에서 최대값을 구하는 문제라 슬라이딩 윈도우로 접근했다.하지만 슬라이딩 윈도우로 풀리지 않았다.문제의 핵심은 '배열을 순회하면서 총합이 양수이기만해도 최대값의 크기는 커진다'라는 것을 발견했다.그다음 그리디 문제처럼 최적의 해를 찾아서 푸는 알고리즘을 도출하였다.2. 핵심 문제 풀이문제의 핵심은 '배열을 순회하면서 총합이 양수이기만해도 최대값의 크기는 커진다' 라는 ..
[Leetcode] 509번 - 피보나치 수열 1. 문제 파악문제 링크: https://leetcode.com/problems/fibonacci-number/description/문제 요구사항: 피보나치 수열을 구현해라.시간복잡도: 입력 크기가 30개이므로 (2^10)^3=1,024^3≈(10^3)^3≈10^9이다. 따라서 10^8을 초과하므로 통과를 못할수도 있다.2. 문제 풀이1. 브루트 포스로 문제 풀이 도출피보나치 수열은 특정 숫자를 구하기 위해서 그 한칸 앞에 있는 값과 두칸 앞에 있는 값을 더해야한다. 따라서 피보나치 수열의 점화식은 f[i] = f[i-1] + f[i-2]이다. 위의 공식에 따르면, 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 ...이다. 만일, 단순하게 분할 정복 기법을 사용해서 10번째 피보나치 ..
[Leetcode] 406번 - 키에 따른 대기열 재구성 1. 문제 파악문제 링크: https://leetcode.com/problems/queue-reconstruction-by-height/description/문제 정의: 자기 보다 키큰 사람의 수(k)에 맞춰서 큐에 저장해라.입력크기: 1 2. 문제 풀이1. 핵심 문제 풀이 도출(문제 의도 파악): 어떻게 하면 시간 복잡도 내로 줄일수 있을까?이 문제는 '내 앞에 나보다 키가 크거나 같은 사람이 k명 있어야 한다' 라는 점이다. 따라서 핵심은 키 큰 사람부터 위치를 확정하면 나중에 작은 사람을 끼워 넣어도 조건이 깨지지 않는다는 점이다. 큰 키부터 배치해놓으면, 이후에 들어오는 사람은 그보다 작거나 같은 키이므로, 앞에 큰 사람의 수는 변하지 않는다. 따라서 먼저 키(h) 큰 사람 순으로 배치해놓는다. ..
[Leetcode] 122번 - 주식을 사고팔기 가장 좋은 시점 II 1. 문제 파악문제 링크: https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/description/문제 정의: 최대 한 주까지만 보유하면서 매일 주식을 매수 또는 매도를 반복해서 최대 이익을 낼수있는 값을 찾아라1 2. 문제 풀이1. 핵심 문제 풀이 도출(문제 의도 파악): 어떻게 하면 시간 복잡도 내로 줄일수 있을까?그리디 알고리즘은 '순간의 최적 선택을 반복하여 전체 최적을 찾는 방법'이다.순회중 산 값을 지정하고 보다 작은 값 있으면 업데이트한다.산값 보다 큰값이 있으면 팔고 판값을 이익에 누적한다. 그리고 판값을 산값으로 업데이트한다.input: 3 1 4 2 3 6output: 3 + 1 + 3 = 7input: 7 1 5 3 6..
[Programmers] 1844 - 게임 맵 최단거리 1. 문제 파악문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/1844문제 정의: 맵에서 값이 0이 아닌 1인곳으로만 상하좌우 이동해서 시작지점으로부터 도착지점까지 최단거리를 구하는 문제이다.문제의 제약 파악 (입력값 크기, 상수 조건)1 2. 문제 풀이1. 핵심 문제 풀이 도출(문제 의도 파악): 어떻게 하면 시간 복잡도 내로 줄일수 있을까?해당 문제는 가중치가 없으므로 다익스트라와 같은 최단 경로 풀이보단 BFS를 사용하는 것이 더 적합하다고 생각했다.추가적으로 각 간선이 동일 가중치라면, DFS와 BFS 차이는 아래와같다.DFS는 탐색 과정에서 깊이를 끝까지 탐색하기 때문에, 도착지점까지 탐색한 경로의 거리의 순차를 구할수없다.BF..

티스토리툴바