IN DEPTH CAKE/Supercoder
-
๋์ด๋: Mediumํค์๋: Array ๋ฌธ์ ๋ฌธ์ ์๋ฌธ: https://leetcode.com/problems/merge-intervals/description/์ฃผ์ด์ง ๊ฐ๊ฒฉ ๋ฐฐ์ด์์, intervals[i] = [starti, endi]์ธ ๊ฐ๊ฒฉ๋ค์ด ์์ ๋, ๊ฒน์น๋ ๋ชจ๋ ๊ฐ๊ฒฉ์ ๋ณํฉํ๊ณ , ์ ๋ ฅ๋ ๋ชจ๋ ๊ฐ๊ฒฉ์ ํฌ๊ดํ๋ ๊ฒน์น์ง ์๋ ๊ฐ๊ฒฉ๋ค์ ๋ฐฐ์ด์ ๋ฐํํ์์ค. ๋ฌธ์ ํ์ด ๊ฒน์น๋ ๊ตฌ๊ฐ๋ค์ ํฉ์ณ์ฃผ๊ธฐ์ํด์, intervals ๋ฅผ start time ๊ธฐ์ค์ผ๋ก sortingํ๊ณ merge๋ฅผ ์งํํ๋ค. ๊ทธ๋ฌ๋ฉด sort๋ O(n log n)์ด ๋ณด์ฅ๋๊ณ , sorting ๋ array์ ๋ํด์ merge๋ง ํด์ฃผ๋ฉด ๋๋ฏ๋ก O(n). ์ต์ข ์ ์ผ๋ก O(n log n) ๋ณต์ก๋๋ก ํด๊ฒฐ. #include #include using na..
[c++/LeetCode-Array] 56. Merge Intervals๋์ด๋: Mediumํค์๋: Array ๋ฌธ์ ๋ฌธ์ ์๋ฌธ: https://leetcode.com/problems/merge-intervals/description/์ฃผ์ด์ง ๊ฐ๊ฒฉ ๋ฐฐ์ด์์, intervals[i] = [starti, endi]์ธ ๊ฐ๊ฒฉ๋ค์ด ์์ ๋, ๊ฒน์น๋ ๋ชจ๋ ๊ฐ๊ฒฉ์ ๋ณํฉํ๊ณ , ์ ๋ ฅ๋ ๋ชจ๋ ๊ฐ๊ฒฉ์ ํฌ๊ดํ๋ ๊ฒน์น์ง ์๋ ๊ฐ๊ฒฉ๋ค์ ๋ฐฐ์ด์ ๋ฐํํ์์ค. ๋ฌธ์ ํ์ด ๊ฒน์น๋ ๊ตฌ๊ฐ๋ค์ ํฉ์ณ์ฃผ๊ธฐ์ํด์, intervals ๋ฅผ start time ๊ธฐ์ค์ผ๋ก sortingํ๊ณ merge๋ฅผ ์งํํ๋ค. ๊ทธ๋ฌ๋ฉด sort๋ O(n log n)์ด ๋ณด์ฅ๋๊ณ , sorting ๋ array์ ๋ํด์ merge๋ง ํด์ฃผ๋ฉด ๋๋ฏ๋ก O(n). ์ต์ข ์ ์ผ๋ก O(n log n) ๋ณต์ก๋๋ก ํด๊ฒฐ. #include #include using na..
2024.05.04 -
๋์ด๋: Mediumํค์๋: Array ๋ฌธ์ ๋ฌธ์ ์๋ฌธ: https://leetcode.com/problems/find-peak-element/description/ Peak ์์๋ ์ด์๋ณด๋ค ์๊ฒฉํ๊ฒ ํฐ ์์๋ฅผ ๋ปํ๋ค. 0๋ถํฐ ์์ธ์ด ์ง์ ๋ ์ ์ ๋ฐฐ์ด nums๊ฐ ์ฃผ์ด์ก์ ๋, Peak ์์๋ฅผ ์ฐพ๊ณ ํด๋น ์์ธ์ ๋ฐํํ๋ผ. ๋ฐฐ์ด์ ์ฌ๋ฌ ๊ฐ์ Peak์ด ํฌํจ๋์ด ์์ผ๋ฉด ์ด๋ค Peak์ ์์ธ์ด๋ ๋ฐํํ ์ ์๋ค.nums[-1] = nums[n] = -∞๋ก ๊ฐ์ฃผํด๋ ๋๋ค. ์ฆ, ๋ฐฐ์ด ์ธ๋ถ์ ์๋ ์ด์๋ณด๋ค ์์๋ ํญ์ ์๊ฒฉํ๊ฒ ํฌ๋ค๊ณ ๊ฐ์ฃผ๋๋ค.O(log n) ์๊ฐ ๋ด์ ์คํ๋๋ ์๊ณ ๋ฆฌ์ฆ์ ์์ฑํด์ผ ํ๋ค. ๋ฌธ์ ํ์ด ๋ฌธ์ ์์ฒด๋ง ๋๊ณ ๋ณด๋ฉด Medium ๋์ด๋๋ ์๋๋ค. ๊ฐ์ฅ ์ฝ๊ฒ ์๊ฐํด๋ณด๋ฉด O(n) ์์ itera..
[c++/LeetCode-Array] 162. Find Peak Element๋์ด๋: Mediumํค์๋: Array ๋ฌธ์ ๋ฌธ์ ์๋ฌธ: https://leetcode.com/problems/find-peak-element/description/ Peak ์์๋ ์ด์๋ณด๋ค ์๊ฒฉํ๊ฒ ํฐ ์์๋ฅผ ๋ปํ๋ค. 0๋ถํฐ ์์ธ์ด ์ง์ ๋ ์ ์ ๋ฐฐ์ด nums๊ฐ ์ฃผ์ด์ก์ ๋, Peak ์์๋ฅผ ์ฐพ๊ณ ํด๋น ์์ธ์ ๋ฐํํ๋ผ. ๋ฐฐ์ด์ ์ฌ๋ฌ ๊ฐ์ Peak์ด ํฌํจ๋์ด ์์ผ๋ฉด ์ด๋ค Peak์ ์์ธ์ด๋ ๋ฐํํ ์ ์๋ค.nums[-1] = nums[n] = -∞๋ก ๊ฐ์ฃผํด๋ ๋๋ค. ์ฆ, ๋ฐฐ์ด ์ธ๋ถ์ ์๋ ์ด์๋ณด๋ค ์์๋ ํญ์ ์๊ฒฉํ๊ฒ ํฌ๋ค๊ณ ๊ฐ์ฃผ๋๋ค.O(log n) ์๊ฐ ๋ด์ ์คํ๋๋ ์๊ณ ๋ฆฌ์ฆ์ ์์ฑํด์ผ ํ๋ค. ๋ฌธ์ ํ์ด ๋ฌธ์ ์์ฒด๋ง ๋๊ณ ๋ณด๋ฉด Medium ๋์ด๋๋ ์๋๋ค. ๊ฐ์ฅ ์ฝ๊ฒ ์๊ฐํด๋ณด๋ฉด O(n) ์์ itera..
2024.05.02 -
๋ณธ ๊ธ์ LeetCode Top Interview 150์ ์ ๋ฆฌ๋ ๋ฌธ์ ๋ฅผ ์์ฝํ๊ณ ์ด์ ๋ํ ๊ฐ์ธ์ ์ธ ํ์ด๋ฅผ ํฌํจํ๊ณ ์์ต๋๋ค. ๋ณธ ํฌ์คํ ์๋ฆฌ์ฆ๋ 150 list์ ์์๋ฅผ ๋ฐ๋ผ์ ๊ฒ์ฌ๋ฉ๋๋ค. ํ์ด ์ธ์ด๋ python3์ ์ฌ์ฉํฉ๋๋ค. ๋์ด๋: Medium ํค์๋: Array, Sorting ๋ฌธ์ ๋ฌธ์ ์๋ฌธ: https://leetcode.com/problems/h-index/description/?envType=study-plan-v2&envId=top-interview-150 ์ ์ ๋ฐฐ์ด citations ์ด ์ฃผ์ด์ง ๋ H-index๋ฅผ ๋ฐํํด๋ผ ๋ฌธ์ ํ์ด class Solution: def hIndex(self, citations: List[int]) -> int: citations.sort(reverse..
[์ฝ๋ฉ/LeetCode150-(11)] 274. H-Index๋ณธ ๊ธ์ LeetCode Top Interview 150์ ์ ๋ฆฌ๋ ๋ฌธ์ ๋ฅผ ์์ฝํ๊ณ ์ด์ ๋ํ ๊ฐ์ธ์ ์ธ ํ์ด๋ฅผ ํฌํจํ๊ณ ์์ต๋๋ค. ๋ณธ ํฌ์คํ ์๋ฆฌ์ฆ๋ 150 list์ ์์๋ฅผ ๋ฐ๋ผ์ ๊ฒ์ฌ๋ฉ๋๋ค. ํ์ด ์ธ์ด๋ python3์ ์ฌ์ฉํฉ๋๋ค. ๋์ด๋: Medium ํค์๋: Array, Sorting ๋ฌธ์ ๋ฌธ์ ์๋ฌธ: https://leetcode.com/problems/h-index/description/?envType=study-plan-v2&envId=top-interview-150 ์ ์ ๋ฐฐ์ด citations ์ด ์ฃผ์ด์ง ๋ H-index๋ฅผ ๋ฐํํด๋ผ ๋ฌธ์ ํ์ด class Solution: def hIndex(self, citations: List[int]) -> int: citations.sort(reverse..
2023.08.23 -
๋ณธ ๊ธ์ LeetCode Top Interview 150์ ์ ๋ฆฌ๋ ๋ฌธ์ ๋ฅผ ์์ฝํ๊ณ ์ด์ ๋ํ ๊ฐ์ธ์ ์ธ ํ์ด๋ฅผ ํฌํจํ๊ณ ์์ต๋๋ค. ๋ณธ ํฌ์คํ ์๋ฆฌ์ฆ๋ 150 list์ ์์๋ฅผ ๋ฐ๋ผ์ ๊ฒ์ฌ๋ฉ๋๋ค. ํ์ด ์ธ์ด๋ python3์ ์ฌ์ฉํฉ๋๋ค. ๋์ด๋: Medium ํค์๋: Array, DP ๋ฌธ์ ๋ฌธ์ ์๋ฌธ: https://leetcode.com/problems/jump-game-ii/?envType=study-plan-v2&envId=top-interview-150 ์ ์ํ ๋ฐฐ์ด nums๊ฐ ์ฃผ์ด์ก๋ค๊ณ ํ์. ๋น์ ์ ์ฒ์์ ๋ฐฐ์ด์ ์ฒซ๋ฒ์งธ index์ ์์นํ๋ค. ๊ทธ๋ฆฌ๊ณ ๋ฐฐ์ด์ ๊ฐ ์์๋ ํด๋น ์์น์์๋ถํฐ ๋น์ ์ด ์ต๋๋ก ์ ํํ ์ ์๋ ๊ธธ์ด๋ฅผ ๋ํ๋ธ๋ค. ์ด ๋, ๋ง์ง๋ง index ์ ๋๋ฌํ๋๋ฐ ํ์ํ jump ์์ ์ต์๊ฐ..
[์ฝ๋ฉ/LeetCode150-(10)] 45. Jump Game II๋ณธ ๊ธ์ LeetCode Top Interview 150์ ์ ๋ฆฌ๋ ๋ฌธ์ ๋ฅผ ์์ฝํ๊ณ ์ด์ ๋ํ ๊ฐ์ธ์ ์ธ ํ์ด๋ฅผ ํฌํจํ๊ณ ์์ต๋๋ค. ๋ณธ ํฌ์คํ ์๋ฆฌ์ฆ๋ 150 list์ ์์๋ฅผ ๋ฐ๋ผ์ ๊ฒ์ฌ๋ฉ๋๋ค. ํ์ด ์ธ์ด๋ python3์ ์ฌ์ฉํฉ๋๋ค. ๋์ด๋: Medium ํค์๋: Array, DP ๋ฌธ์ ๋ฌธ์ ์๋ฌธ: https://leetcode.com/problems/jump-game-ii/?envType=study-plan-v2&envId=top-interview-150 ์ ์ํ ๋ฐฐ์ด nums๊ฐ ์ฃผ์ด์ก๋ค๊ณ ํ์. ๋น์ ์ ์ฒ์์ ๋ฐฐ์ด์ ์ฒซ๋ฒ์งธ index์ ์์นํ๋ค. ๊ทธ๋ฆฌ๊ณ ๋ฐฐ์ด์ ๊ฐ ์์๋ ํด๋น ์์น์์๋ถํฐ ๋น์ ์ด ์ต๋๋ก ์ ํํ ์ ์๋ ๊ธธ์ด๋ฅผ ๋ํ๋ธ๋ค. ์ด ๋, ๋ง์ง๋ง index ์ ๋๋ฌํ๋๋ฐ ํ์ํ jump ์์ ์ต์๊ฐ..
2023.08.22 -
๋ณธ ๊ธ์ LeetCode Top Interview 150์ ์ ๋ฆฌ๋ ๋ฌธ์ ๋ฅผ ์์ฝํ๊ณ ์ด์ ๋ํ ๊ฐ์ธ์ ์ธ ํ์ด๋ฅผ ํฌํจํ๊ณ ์์ต๋๋ค. ๋ณธ ํฌ์คํ ์๋ฆฌ์ฆ๋ 150 list์ ์์๋ฅผ ๋ฐ๋ผ์ ๊ฒ์ฌ๋ฉ๋๋ค. ํ์ด ์ธ์ด๋ python์ ์ฌ์ฉํฉ๋๋ค. ๋์ด๋: Medium ํค์๋: Array, DP ๋ฌธ์ ๋ฌธ์ ์๋ฌธ: https://leetcode.com/problems/jump-game/description/?envType=study-plan-v2&envId=top-interview-150 ์ ์ํ ๋ฐฐ์ด nums๊ฐ ์ฃผ์ด์ก๋ค๊ณ ํ์. ๋น์ ์ ์ฒ์์ ๋ฐฐ์ด์ ์ฒซ๋ฒ์งธ index์ ์์นํ๋ค. ๊ทธ๋ฆฌ๊ณ ๋ฐฐ์ด์ ๊ฐ ์์๋ ํด๋น ์์น์์๋ถํฐ ๋น์ ์ด ์ต๋๋ก ์ ํํ ์ ์๋ ๊ธธ์ด๋ฅผ ๋ํ๋ธ๋ค. ์ด ๋, ๋ง์ง๋ง index ์ ๋๋ฌํ ์ ์๋ ๊ฒฝ์ฐ t..
[์ฝ๋ฉ/LeetCode150-(9)] 55. Jump Game๋ณธ ๊ธ์ LeetCode Top Interview 150์ ์ ๋ฆฌ๋ ๋ฌธ์ ๋ฅผ ์์ฝํ๊ณ ์ด์ ๋ํ ๊ฐ์ธ์ ์ธ ํ์ด๋ฅผ ํฌํจํ๊ณ ์์ต๋๋ค. ๋ณธ ํฌ์คํ ์๋ฆฌ์ฆ๋ 150 list์ ์์๋ฅผ ๋ฐ๋ผ์ ๊ฒ์ฌ๋ฉ๋๋ค. ํ์ด ์ธ์ด๋ python์ ์ฌ์ฉํฉ๋๋ค. ๋์ด๋: Medium ํค์๋: Array, DP ๋ฌธ์ ๋ฌธ์ ์๋ฌธ: https://leetcode.com/problems/jump-game/description/?envType=study-plan-v2&envId=top-interview-150 ์ ์ํ ๋ฐฐ์ด nums๊ฐ ์ฃผ์ด์ก๋ค๊ณ ํ์. ๋น์ ์ ์ฒ์์ ๋ฐฐ์ด์ ์ฒซ๋ฒ์งธ index์ ์์นํ๋ค. ๊ทธ๋ฆฌ๊ณ ๋ฐฐ์ด์ ๊ฐ ์์๋ ํด๋น ์์น์์๋ถํฐ ๋น์ ์ด ์ต๋๋ก ์ ํํ ์ ์๋ ๊ธธ์ด๋ฅผ ๋ํ๋ธ๋ค. ์ด ๋, ๋ง์ง๋ง index ์ ๋๋ฌํ ์ ์๋ ๊ฒฝ์ฐ t..
2023.08.22 -
๋ณธ ๊ธ์ LeetCode Top Interview 150์ ์ ๋ฆฌ๋ ๋ฌธ์ ๋ฅผ ์์ฝํ๊ณ ์ด์ ๋ํ ๊ฐ์ธ์ ์ธ ํ์ด๋ฅผ ํฌํจํ๊ณ ์์ต๋๋ค. ๋ณธ ํฌ์คํ ์๋ฆฌ์ฆ๋ 150 list์ ์์๋ฅผ ๋ฐ๋ผ์ ๊ฒ์ฌ๋ฉ๋๋ค. ํ์ด ์ธ์ด๋ python์ ์ฌ์ฉํฉ๋๋ค. ๋์ด๋: Medium ํค์๋: Array, Greedy ๋ฌธ์ ๋ฌธ์ ์๋ฌธ: https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/description/?envType=study-plan-v2&envId=top-interview-150 prices๋ผ๋ ๋ฐฐ์ด์ด ์ฃผ์ด์ง๋ค๊ณ ํ์. ์ด ๋ฐฐ์ด์ i๋ฒ์งธ ์์๋ค์ ์ฃผ์์ ๊ฐ๊ฒฉ์ ์๋ฏธํ๋ค. ํ ๋ฒ์ ํ๋์ ์ฃผ์๋ง ๊ฐ์ง๊ณ ์์ ์ ์๋ค. ๋จ, ์ฃผ์์ ํ์๋ง์ ๋น์ผ์ ๋ฐ๋ก ์ด ์ ์๋ค. ..
[์ฝ๋ฉ/LeetCode150-(8)] Best Time to Buy and Sell Stock II (122)๋ณธ ๊ธ์ LeetCode Top Interview 150์ ์ ๋ฆฌ๋ ๋ฌธ์ ๋ฅผ ์์ฝํ๊ณ ์ด์ ๋ํ ๊ฐ์ธ์ ์ธ ํ์ด๋ฅผ ํฌํจํ๊ณ ์์ต๋๋ค. ๋ณธ ํฌ์คํ ์๋ฆฌ์ฆ๋ 150 list์ ์์๋ฅผ ๋ฐ๋ผ์ ๊ฒ์ฌ๋ฉ๋๋ค. ํ์ด ์ธ์ด๋ python์ ์ฌ์ฉํฉ๋๋ค. ๋์ด๋: Medium ํค์๋: Array, Greedy ๋ฌธ์ ๋ฌธ์ ์๋ฌธ: https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/description/?envType=study-plan-v2&envId=top-interview-150 prices๋ผ๋ ๋ฐฐ์ด์ด ์ฃผ์ด์ง๋ค๊ณ ํ์. ์ด ๋ฐฐ์ด์ i๋ฒ์งธ ์์๋ค์ ์ฃผ์์ ๊ฐ๊ฒฉ์ ์๋ฏธํ๋ค. ํ ๋ฒ์ ํ๋์ ์ฃผ์๋ง ๊ฐ์ง๊ณ ์์ ์ ์๋ค. ๋จ, ์ฃผ์์ ํ์๋ง์ ๋น์ผ์ ๋ฐ๋ก ์ด ์ ์๋ค. ..
2023.08.22