N

https://leetcode.com/problems/cheapest-flights-within-k-stops/ Cheapest Flights Within K Stops - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 다익스트라 알고리즘 활용. 우선 graph라는 이름의 n 크기의 배열을 선언하여 []로 초기화. 또한, n 크기의 dist 배열도 선언하여 infinity로 초기화. flights를 순회하여 그래프를 그려준다. 단방향이기 때문에 from, to,..

https://programmers.co.kr/learn/courses/30/lessons/77486 코딩테스트 연습 - 다단계 칫솔 판매 민호는 다단계 조직을 이용하여 칫솔을 판매하고 있습니다. 판매원이 칫솔을 판매하면 그 이익이 피라미드 조직을 타고 조금씩 분배되는 형태의 판매망입니다. 어느정도 판매가 이루어진 후, programmers.co.kr Map을 이용한 문제 풀이. map = enroll과 referral 배열의 부모-자식 관계를 나타내기 위한 Map. profit = 각 사람들의 판매 이익을 나타내기 위한 Map. enroll을 순회하면서 부모-자식 관계를 나타내도록 하자. enroll[i]를 key, referral[i]를 value로 가지도록 하여 map에 저장한다. 이후 seller..

https://leetcode.com/problems/letter-combinations-of-a-phone-number/ Letter Combinations of a Phone Number - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 각 번호에 맵핑된 문자의 모든 조합을 찾아내는 문제. 완전 탐색으로 풀이. dfs에 넘겨주는 인자는 (현재 문자열, 현재 digits의 인덱스, 현재 문자의 길이)다. dfs 함수. 우선 digits[index]를 numbe..

https://leetcode.com/problems/spiral-matrix/ Spiral Matrix - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 주어진 배열을 Spiral로 순회하면서 수를 저장하는 문제. m과 n을 각각 matrix의 가로, 세로 길이로 저장. direct는 spiral로 순회하기 위한 방향 배열. visited는 방문 여부 확인 배열. x와 y는 현재 좌표를 뜻하며, d는 direct의 인덱스를 나타낸다. rangeCheck() 함..

https://leetcode.com/problems/multiply-strings/ Multiply Strings - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 문자열로 주어진 두 수를 곱한 값을 리턴. 문자열의 길이가 200이기 때문에 Number 형으로 나타낼 수 있는 수를 초과할 수 있다. 우선 num1과 num2 중 하나라도 "0"이라면 바로 "0"을 리턴. arr는 num1과 num2의 길이를 합한 크기로 선언하여 0으로 초기화한다. 이후, 두 문..

https://leetcode.com/problems/house-robber-ii/ House Robber II - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com DP 알고리즘. nums의 length만큼 DP 배열을 선언하여 0으로 초기화 한다. DP 배열은 총 2개를 선언하는데, 이는 0번째 집을 털었을 때의 경우 = dp1, 0번째 집을 털지 않았을 경우 = dp2 로 계산하기 위함이다. (0번째 집을 털었을 경우는 마지막 집을 털수 없기 때문) for문은..

https://programmers.co.kr/learn/courses/30/lessons/60060 코딩테스트 연습 - 가사 검색 programmers.co.kr Trie 알고리즘 활용. 물음표가 쿼리의 앞에 존재하는지, 뒤에 존재하는지에 따라 Trie 탐색을 다르게 해야 한다. 2가지의 Trie를 선언하여 단어를 저장하는데, 앞에서 단어를 검색하는 경우와 뒤에서 단어를 검색하는 경우를 저장하기 위함이다. 각 Trie를 frontTrie, backTrie라는 이름으로 선언했다. 우선 words에 있는 단어를 중복제거를 하여 newWords에 저장한다. newWords 배열을 순회하면서 단어를 frontTrie와 backTrie에 저장한다. backTrie에 저장하기 위해서는 단어를 뒤집어야 하기 때문에..

https://leetcode.com/problems/house-robber/ House Robber - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com DP 이용. nums.length만큼 dp 배열을 선언하여 0으로 초기화. dp[0] = nums[0]으로 저장하고 for문으로 1 ~ length만큼 반복한다. 점화식으로는 dp[i] = Math.max(nums[i] + (dp[i - 2] || 0), dp[i - 1])을 구할 수 있다. dp[i - 2] |..