๋ถ๋ฅ ์ ์ฒด๋ณด๊ธฐ
-
๋์ด๋: Mediumํค์๋: DP ๐ ๋ฌธ์ ์ํ๋ฒณ A-Z์ ๋ฌธ์๋ก ์ด๋ฃจ์ด์ง ๋ฉ์์ง๋ ๋ค์ ๋งคํ์ ์ฌ์ฉํ์ฌ ์ซ์๋ก ์ธ์ฝ๋ฉ๋ ์ ์์ต๋๋ค:'A' -> "1"'B' -> "2"...'Z' -> "26" ์ธ์ฝ๋ฉ๋ ๋ฉ์์ง๋ฅผ ๋์ฝ๋ฉํ๋ ค๋ฉด, ๋ชจ๋ ์ซ์๋ฅผ ๊ทธ๋ฃนํํ๊ณ ์์ ๋งคํ์ ๋ฐ๋๋ก ์ฌ์ฉํ์ฌ ๋ค์ ๋ฌธ์๋ก ๋งคํํด์ผ ํฉ๋๋ค (์ฌ๋ฌ ๋ฐฉ๋ฒ์ด ์์ ์ ์์). ์๋ฅผ ๋ค์ด, "11106"์ ๋ค์๊ณผ ๊ฐ์ด ๋งคํ๋ ์ ์์ต๋๋ค:(1 1 10 6)์ ๊ทธ๋ฃนํํ์ฌ "AAJF"(11 10 6)์ ๊ทธ๋ฃนํํ์ฌ "KJF"(1 11 06)์ ๊ทธ๋ฃนํํ๋ ๊ฒ์ "06"์ 'F'๋ก ๋งคํํ ์ ์์ผ๋ฏ๋ก ์๋ชป๋ ๊ฒ์์ ์ ์ํ์ธ์.์ซ์๋ง ํฌํจํ๋ ๋ฌธ์์ด s๊ฐ ์ฃผ์ด์ก์ ๋, ์ด๋ฅผ ๋์ฝ๋ฉํ๋ ๋ฐฉ๋ฒ์ ์๋ฅผ ๋ฐํํ์ธ์.ํ ์คํธ ์ผ์ด์ค๋ ๋ต์ด 32๋นํธ ์ ์์ ๋ง๋..
[c++/LeetCode-DP] 91. Decode Ways (w/ DP ํ์ด ์ ๋ต)๋์ด๋: Mediumํค์๋: DP ๐ ๋ฌธ์ ์ํ๋ฒณ A-Z์ ๋ฌธ์๋ก ์ด๋ฃจ์ด์ง ๋ฉ์์ง๋ ๋ค์ ๋งคํ์ ์ฌ์ฉํ์ฌ ์ซ์๋ก ์ธ์ฝ๋ฉ๋ ์ ์์ต๋๋ค:'A' -> "1"'B' -> "2"...'Z' -> "26" ์ธ์ฝ๋ฉ๋ ๋ฉ์์ง๋ฅผ ๋์ฝ๋ฉํ๋ ค๋ฉด, ๋ชจ๋ ์ซ์๋ฅผ ๊ทธ๋ฃนํํ๊ณ ์์ ๋งคํ์ ๋ฐ๋๋ก ์ฌ์ฉํ์ฌ ๋ค์ ๋ฌธ์๋ก ๋งคํํด์ผ ํฉ๋๋ค (์ฌ๋ฌ ๋ฐฉ๋ฒ์ด ์์ ์ ์์). ์๋ฅผ ๋ค์ด, "11106"์ ๋ค์๊ณผ ๊ฐ์ด ๋งคํ๋ ์ ์์ต๋๋ค:(1 1 10 6)์ ๊ทธ๋ฃนํํ์ฌ "AAJF"(11 10 6)์ ๊ทธ๋ฃนํํ์ฌ "KJF"(1 11 06)์ ๊ทธ๋ฃนํํ๋ ๊ฒ์ "06"์ 'F'๋ก ๋งคํํ ์ ์์ผ๋ฏ๋ก ์๋ชป๋ ๊ฒ์์ ์ ์ํ์ธ์.์ซ์๋ง ํฌํจํ๋ ๋ฌธ์์ด s๊ฐ ์ฃผ์ด์ก์ ๋, ์ด๋ฅผ ๋์ฝ๋ฉํ๋ ๋ฐฉ๋ฒ์ ์๋ฅผ ๋ฐํํ์ธ์.ํ ์คํธ ์ผ์ด์ค๋ ๋ต์ด 32๋นํธ ์ ์์ ๋ง๋..
2024.05.06 -
์๋ ํ์ธ์. ์ค๋์ ์๊ทธ๋์ ๋ฐฉ๋ฌธ ํ๊ธฐ๋ฅผ ๋จ๊ฒจ๋ณผ๊น ํฉ๋๋ค. 4์ ๋ง๊ฒฝ ์ฃผ์ค์ ๋ฐฉ๋ฌธํ์ด์. ํน๋ณํ ์ด๋ฒคํธ๊ฐ ์์ด ๊ฐ๋ ๊ฑด ์๋๊ณ ์ฃผ์ค์ ์ฌ์ ๋ก์์ ๋๋ ค๋ณด์ ์ถ์ด์ ํธ์บ์ค ๊ฒธ ๋ฐฉ๋ฌธํ์ต๋๋ค. (์ฐธ๊ณ ๋ก, ์์ฌ๋ด๋ค๋ณด๋ ์ฌ์ง์ด ๋๋ฌด ๋ง์์. ์ฐธ๊ณ ๋ถํ๋๋ฆฝ๋๋ค)๊ธ์ด ๊ธด ํธ์ด๋ ์ํ์๋ ์ ๋ณด๋ ์์ Contents์์ ๋ฐ์ด๋๊ธฐํ์ ์ ๋ณด์ธ์ :) ๐ ํฌ์ ์ ๋ณด ์ฃผ์ค 1๋ฐ 2์ผํฌ์ ์ธ์ 3๋ช ์์คํธ๋ผ๋ฒ ๋ ์ถ๊ฐ๋ฆฌ๋ฒ ๋ทฐ ์ ๊ทธ๋ ์ด๋์กฐ์ 3์ธ ํฌ์ ์ธ์์ 3๋ช ์ด์์ด์. ์์๋ณด๋ ์ธ์ ์ถ๊ฐ ๋น์ฉ์ ๋๋ฐฐ๋ฅผ ๋ด๋ฉด ์นจ๋์ถ๊ฐ๊ฐ ๋๊ธธ๋ (์นจ๋ ์ถ๊ฐ ์ ์ธ์ ์ถ๊ฐ ๋น์ฉ ์์) 12๋ง 1์ฒ์ ๋ด๊ณ ์์คํธ๋ผ๋ฒ ๋ ์ ์ฒญํ๊ตฌ์. ๋ฆฌ๋ฒ๋ทฐ ์ ํ์ผ๋ก 6๋ง 500์ ์ถ๊ฐํ์ต๋๋ค.์ฐธ๊ณ ๋ก, ์ ๋ง ์์กฐ ๋น์ฉ๋ 6๋ง 500์ ์ถ๊ฐํ๋ฉด ์ ๊ทธ๋ ์ด๋๊ฐ ๋๋๋ฐ ๋ค..
์๊ทธ๋์ ์์ธ ๋ฆฌ๋ทฐ feat. ์กฐ์, ๋ฐ๋ ๋ฒ ์ด๊ธ, ๋น์ฆ ์ ์ค์๋ ํ์ธ์. ์ค๋์ ์๊ทธ๋์ ๋ฐฉ๋ฌธ ํ๊ธฐ๋ฅผ ๋จ๊ฒจ๋ณผ๊น ํฉ๋๋ค. 4์ ๋ง๊ฒฝ ์ฃผ์ค์ ๋ฐฉ๋ฌธํ์ด์. ํน๋ณํ ์ด๋ฒคํธ๊ฐ ์์ด ๊ฐ๋ ๊ฑด ์๋๊ณ ์ฃผ์ค์ ์ฌ์ ๋ก์์ ๋๋ ค๋ณด์ ์ถ์ด์ ํธ์บ์ค ๊ฒธ ๋ฐฉ๋ฌธํ์ต๋๋ค. (์ฐธ๊ณ ๋ก, ์์ฌ๋ด๋ค๋ณด๋ ์ฌ์ง์ด ๋๋ฌด ๋ง์์. ์ฐธ๊ณ ๋ถํ๋๋ฆฝ๋๋ค)๊ธ์ด ๊ธด ํธ์ด๋ ์ํ์๋ ์ ๋ณด๋ ์์ Contents์์ ๋ฐ์ด๋๊ธฐํ์ ์ ๋ณด์ธ์ :) ๐ ํฌ์ ์ ๋ณด ์ฃผ์ค 1๋ฐ 2์ผํฌ์ ์ธ์ 3๋ช ์์คํธ๋ผ๋ฒ ๋ ์ถ๊ฐ๋ฆฌ๋ฒ ๋ทฐ ์ ๊ทธ๋ ์ด๋์กฐ์ 3์ธ ํฌ์ ์ธ์์ 3๋ช ์ด์์ด์. ์์๋ณด๋ ์ธ์ ์ถ๊ฐ ๋น์ฉ์ ๋๋ฐฐ๋ฅผ ๋ด๋ฉด ์นจ๋์ถ๊ฐ๊ฐ ๋๊ธธ๋ (์นจ๋ ์ถ๊ฐ ์ ์ธ์ ์ถ๊ฐ ๋น์ฉ ์์) 12๋ง 1์ฒ์ ๋ด๊ณ ์์คํธ๋ผ๋ฒ ๋ ์ ์ฒญํ๊ตฌ์. ๋ฆฌ๋ฒ๋ทฐ ์ ํ์ผ๋ก 6๋ง 500์ ์ถ๊ฐํ์ต๋๋ค.์ฐธ๊ณ ๋ก, ์ ๋ง ์์กฐ ๋น์ฉ๋ 6๋ง 500์ ์ถ๊ฐํ๋ฉด ์ ๊ทธ๋ ์ด๋๊ฐ ๋๋๋ฐ ๋ค..
2024.05.06 -
๋์ด๋: Easyํค์๋: DP ๐ ๋ฌธ์ ์ ์ ๋ฐฐ์ด cost๊ฐ ์ฃผ์ด์ง๋ฉฐ, cost[i]๋ ๊ณ๋จ์ i๋ฒ์งธ ๋จ๊ณ์ ๋น์ฉ์ ๋๋ค. ๋น์ฉ์ ์ง๋ถํ๋ฉด 1๊ฐ ๋๋ 2๊ฐ์ ๋จ๊ณ๋ฅผ ์ค๋ฅผ ์ ์์ต๋๋ค.์ธ๋ฑ์ค 0 ๋๋ ์ธ๋ฑ์ค 1์ ๋จ๊ณ์์ ์์ํ ์ ์์ต๋๋ค.์ต์์ ์ธต์ ๋๋ฌํ๊ธฐ ์ํ ์ต์ ๋น์ฉ์ ๋ฐํํ์ธ์. Example 1:Input: cost = [10,15,20]Output: 15Explanation: You will start at index 1.- Pay 15 and climb two steps to reach the top.The total cost is 15. Example 2:Input: cost = [1,100,1,1,1,100,1,1,100,1]Output: 6Explanation: You will..
[c++/LeetCode-DP] 746. Min Cost Climbing Stairs๋์ด๋: Easyํค์๋: DP ๐ ๋ฌธ์ ์ ์ ๋ฐฐ์ด cost๊ฐ ์ฃผ์ด์ง๋ฉฐ, cost[i]๋ ๊ณ๋จ์ i๋ฒ์งธ ๋จ๊ณ์ ๋น์ฉ์ ๋๋ค. ๋น์ฉ์ ์ง๋ถํ๋ฉด 1๊ฐ ๋๋ 2๊ฐ์ ๋จ๊ณ๋ฅผ ์ค๋ฅผ ์ ์์ต๋๋ค.์ธ๋ฑ์ค 0 ๋๋ ์ธ๋ฑ์ค 1์ ๋จ๊ณ์์ ์์ํ ์ ์์ต๋๋ค.์ต์์ ์ธต์ ๋๋ฌํ๊ธฐ ์ํ ์ต์ ๋น์ฉ์ ๋ฐํํ์ธ์. Example 1:Input: cost = [10,15,20]Output: 15Explanation: You will start at index 1.- Pay 15 and climb two steps to reach the top.The total cost is 15. Example 2:Input: cost = [1,100,1,1,1,100,1,1,100,1]Output: 6Explanation: You will..
2024.05.06 -
๋์ด๋: Easyํค์๋: DP ๐ ๋ฌธ์ ๊ณ๋จ์ ์ค๋ฅด๊ณ ์์ต๋๋ค. ๊ผญ๋๊ธฐ์ ๋๋ฌํ๊ธฐ ์ํด n๊ฐ์ ๋จ๊ณ๊ฐ ํ์ํฉ๋๋ค.๊ฐ ๋จ๊ณ๋ง๋ค 1๊ฐ ๋๋ 2๊ฐ์ ๋จ๊ณ๋ฅผ ์ค๋ฅผ ์ ์์ต๋๋ค. ๊ผญ๋๊ธฐ์ ๋๋ฌํ๋ ๋ฐ ๋ช ๊ฐ์ง ๋ค๋ฅธ ๋ฐฉ๋ฒ์ด ์๋์ง ๊ณ์ฐํ์ธ์. Example 1:Input: n = 2Output: 2Explanation: There are two ways to climb to the top.1. 1 step + 1 step2. 2 steps Example 2:Input: n = 3Output: 3Explanation: There are three ways to climb to the top.1. 1 step + 1 step + 1 step2. 1 step + 2 steps3. 2 steps + 1 step ๋ฌธ..
[c++/LeetCode-DP] 70. Climbing Stairs๋์ด๋: Easyํค์๋: DP ๐ ๋ฌธ์ ๊ณ๋จ์ ์ค๋ฅด๊ณ ์์ต๋๋ค. ๊ผญ๋๊ธฐ์ ๋๋ฌํ๊ธฐ ์ํด n๊ฐ์ ๋จ๊ณ๊ฐ ํ์ํฉ๋๋ค.๊ฐ ๋จ๊ณ๋ง๋ค 1๊ฐ ๋๋ 2๊ฐ์ ๋จ๊ณ๋ฅผ ์ค๋ฅผ ์ ์์ต๋๋ค. ๊ผญ๋๊ธฐ์ ๋๋ฌํ๋ ๋ฐ ๋ช ๊ฐ์ง ๋ค๋ฅธ ๋ฐฉ๋ฒ์ด ์๋์ง ๊ณ์ฐํ์ธ์. Example 1:Input: n = 2Output: 2Explanation: There are two ways to climb to the top.1. 1 step + 1 step2. 2 steps Example 2:Input: n = 3Output: 3Explanation: There are three ways to climb to the top.1. 1 step + 1 step + 1 step2. 1 step + 2 steps3. 2 steps + 1 step ๋ฌธ..
2024.05.06 -
๋์ด๋: Mediumํค์๋: Hash Table ๐ฒ ๋ฌธ์ X-Y ํ๋ฉด์์ ์ ๋ค์ ๋ฐฐ์ด points๊ฐ ์ฃผ์ด์ก์ต๋๋ค. ์ฌ๊ธฐ์ points[i] = [xi, yi]์ ๋๋ค.์ด๋ฌํ ์ ๋ค๋ก ํ์ฑ๋ X์ถ๊ณผ Y์ถ์ ํํํ ์ง์ฌ๊ฐํ์ ์ต์ ๋ฉด์ ์ ๋ฐํํฉ๋๋ค. ๋ง์ฝ ๊ทธ๋ฌํ ์ง์ฌ๊ฐํ์ด ์๋ค๋ฉด, 0์ ๋ฐํํฉ๋๋ค. ๋ฌธ์ ์๋ฌธ: https://leetcode.com/problems/minimum-area-rectangle/description/ Example 1:Input: points = [[1,1],[1,3],[3,1],[3,3],[2,2]]Output: 4 ๐ฒ ๋ฌธ์ ํ์ด๋ง๋ค ์ ์๋ ์ฌ๊ฐํ์ ํ์ํ๋ฉด์ ์ฌ๊ฐํ๋ค ์ค ์ต์ ๋ฉด์ ๊ฐ์ ๊ตฌํ๊ณ ์ํ๋ค.์ด๋ฅผ ์ํด์ ๋ ๊ฐ์ ์ ์ด ์ฃผ์ด์ก์ ๋ ์ด ๋ ์ ์ธ์ ์ฌ๊ฐํ์ ๋ง๋ค ์ ..
[c++/LeetCode-Hash Table] 939. Minimum Area Rectangle๋์ด๋: Mediumํค์๋: Hash Table ๐ฒ ๋ฌธ์ X-Y ํ๋ฉด์์ ์ ๋ค์ ๋ฐฐ์ด points๊ฐ ์ฃผ์ด์ก์ต๋๋ค. ์ฌ๊ธฐ์ points[i] = [xi, yi]์ ๋๋ค.์ด๋ฌํ ์ ๋ค๋ก ํ์ฑ๋ X์ถ๊ณผ Y์ถ์ ํํํ ์ง์ฌ๊ฐํ์ ์ต์ ๋ฉด์ ์ ๋ฐํํฉ๋๋ค. ๋ง์ฝ ๊ทธ๋ฌํ ์ง์ฌ๊ฐํ์ด ์๋ค๋ฉด, 0์ ๋ฐํํฉ๋๋ค. ๋ฌธ์ ์๋ฌธ: https://leetcode.com/problems/minimum-area-rectangle/description/ Example 1:Input: points = [[1,1],[1,3],[3,1],[3,3],[2,2]]Output: 4 ๐ฒ ๋ฌธ์ ํ์ด๋ง๋ค ์ ์๋ ์ฌ๊ฐํ์ ํ์ํ๋ฉด์ ์ฌ๊ฐํ๋ค ์ค ์ต์ ๋ฉด์ ๊ฐ์ ๊ตฌํ๊ณ ์ํ๋ค.์ด๋ฅผ ์ํด์ ๋ ๊ฐ์ ์ ์ด ์ฃผ์ด์ก์ ๋ ์ด ๋ ์ ์ธ์ ์ฌ๊ฐํ์ ๋ง๋ค ์ ..
2024.05.05 -
๋์ด๋: Mediumํค์๋: Hash Table ๐ฒ ๋ฌธ์ ๋ฌธ์์ด ๋ฐฐ์ด words์ ์ ์ k๊ฐ ์ฃผ์ด์ก์ ๋, k๊ฐ์ ๊ฐ์ฅ ๋น๋ฒํ ๋ฌธ์์ด์ ๋ฐํํฉ๋๋ค.๋น๋์๊ฐ ๋์ ์์๋๋ก ์ ๋ ฌ๋ ๋ต์ ๋ฐํํฉ๋๋ค. ๋์ผํ ๋น๋๋ฅผ ๊ฐ์ง ๋ฌธ์์ด์ ์ฌ์ ์์ผ๋ก ์ ๋ ฌํฉ๋๋ค. ๐ฒ ์์Example 1:Input: words = ["i","love","leetcode","i","love","coding"], k = 2Output: ["i","love"]Explanation: "i" and "love" are the two most frequent words.Note that "i" comes before "love" due to a lower alphabetical order. Example 2:Input: words = ["th..
[c++/LeetCode-Hash Table] 692. Top K Frequent Words๋์ด๋: Mediumํค์๋: Hash Table ๐ฒ ๋ฌธ์ ๋ฌธ์์ด ๋ฐฐ์ด words์ ์ ์ k๊ฐ ์ฃผ์ด์ก์ ๋, k๊ฐ์ ๊ฐ์ฅ ๋น๋ฒํ ๋ฌธ์์ด์ ๋ฐํํฉ๋๋ค.๋น๋์๊ฐ ๋์ ์์๋๋ก ์ ๋ ฌ๋ ๋ต์ ๋ฐํํฉ๋๋ค. ๋์ผํ ๋น๋๋ฅผ ๊ฐ์ง ๋ฌธ์์ด์ ์ฌ์ ์์ผ๋ก ์ ๋ ฌํฉ๋๋ค. ๐ฒ ์์Example 1:Input: words = ["i","love","leetcode","i","love","coding"], k = 2Output: ["i","love"]Explanation: "i" and "love" are the two most frequent words.Note that "i" comes before "love" due to a lower alphabetical order. Example 2:Input: words = ["th..
2024.05.05