Algo Rhythm๐บ๐
-
[Algo Rhythm๐บ๐] BOJ 16288. Passport ControlAlgo Rhythm๐บ๐/BOJ 2020. 9. 3. 10:32
๐ ๋ฌธ์ ์ค๋ช $N$๋ช ์ ์ ๊ตญ ์น๊ฐ์ด ์ฌ๊ถ ์ฌ์ฌ๋ฅผ ์ํ์ฌ ๊ทธ๋ฆผ G.1 ๊ณผ ๊ฐ์ด ์ ๊ตญ ๋๊ธฐ ์ค์์ $[1, 2, … , N − 1, N]$ ์์๋ก ๊ธฐ๋ค๋ฆฌ๊ณ ์๋ค. ์ ๊ตญ ์น๊ฐ์ ์ค๋น๋ $k$๊ฐ์ ์ฌ๊ถ ์ฌ์ฌ ์ฐฝ๊ตฌ ์ค ํ๋๋ฅผ ํต๊ณผํ ๋ค ๊ณตํญ์ ๋น ์ ธ๋๊ฐ ์ ์๋ค. ์ ๊ตญํ ๋์ ์ค ์ ์น๊ฐ์ ์์๋ฅผ $[1, 2, … , N − 1, N]$์ด๋ผ๊ณ ํ ๋ $k$๊ฐ์ ์ฌ๊ถ ์ฌ์ฌ ์ฐฝ๊ตฌ๋ฅผ ํต๊ณผํ์ฌ ์ ๊ตญ์ฅ์ ๋น ์ ธ๋๊ฐ๋ ์์ $[π_{1}, π_{2}, … π_{N−1}, π_{N}]$๋ ์ฒ์๊ณผ ๋ฌ๋ผ์ง ์ ์๋ค. $k$๊ฐ ์ฌ๊ถ ์ฌ์ฌ ์ฐฝ๊ตฌ๊ฐ ์ค๋น๋์ด ์์ ๋, ์ด ์ ๊ตญ์ฅ์ ๋น ์ ธ๋๊ฐ๋ ์์๊ฐ ๊ฐ๋ฅํ ์์์ธ๊ฐ๋ฅผ ๊ณ์ฐํด์ผ ํ๋ค. ์๋ฅผ ๋ค์ด ์ค๋ช ํด๋ณด์. ๋ง์ผ $N = 3, k = 2$ ๋ผ๊ณ ํ ๋ ์ ๊ตญ์ฅ์ ๋น ์ ธ๋๊ฐ๋ ์์ ์ค $[1, ..
-
[Algo Rhythm๐บ๐] BOJ 17528. Two MachinesAlgo Rhythm๐บ๐/BOJ 2020. 8. 26. 21:06
๐ ๋ฌธ์ ์ค๋ช ์ค์ผ์ค๋ง ์ต์ ํ ํ์ฌ์ธ SOPT ์ ์๋ฃํด์ผ ํ n๊ฐ์ ์์ t1, t2, ..., tn ์ด ์๋ค. SOPT ํ์ฌ๋ ๋ ๋์ ๋จธ์ A ์ B ๋ฅผ ๋ณด์ ํ๊ณ ์๋ค. ๊ฐ ์์ ti๋ฅผ ์๋ฃํ๊ธฐ ์ํด SOPT ๋ ๋จธ์ A ์ B ๋ ์ค์ ์ค์ง ํ๋๋ฅผ ์ ํํ ์ ์๋ค. ์์ ti๋ฅผ ์๋ฃํ๊ธฐ ์ํด ๋จธ์ A๋ฅผ ์ ํํ๋ฉด ai์๊ฐ์ด ๊ฑธ๋ฆฌ๊ณ ๋จธ์ B๋ฅผ ์ ํํ๋ฉด bi ์๊ฐ์ด ๊ฑธ๋ฆฐ๋ค. ๊ฐ ๋จธ์ ์ ์ด๋ ์๊ฐ์ ์ต๋ ํ๋์ ์์ ๋ง ์ํํ ์ ์์ผ๋ฉฐ, ํ ์์ ์ด ์์๋๋ฉด ๊ทธ ์์ ์ ์๋ฃํ๊ธฐ ์ ๊น์ง ๋ค๋ฅธ ์์ ์ ๊ทธ ๋จธ์ ์์ ์ํํ ์ ์๋ค. SOPT ๋ ๋ชจ๋ ์์ ์ ์๋ฃํ๊ธฐ ์ํ ์ต์์ ์๋ฃ ์๊ฐ์ ๊ตฌํ๊ณ ์ ํ๋ค. ์๋ฅผ ๋ค์ด, ์ธ ๊ฐ์ ์์ ์ด t1, t2, t3๊ฐ ์ฃผ์ด์ ธ ์๊ณ a1 = 2, b1 = 3, a2 = 5, ..
-
[Algo Rhythm๐บ๐] LeetCode 653. Two Sum IV - Input is a BSTAlgo Rhythm๐บ๐/LeetCode 2020. 8. 24. 15:24
๐ Problem description Given a Binary Search Tree and a target number, return true if there exist two elements in the BST such that their sum is equal to the given target. Example 1: Input: 5 / \ 3 6 / \ \ 2 4 7 Target = 9 Output: True Example 2: Input: 5 / \ 3 6 / \ \ 2 4 7 Target = 28 Output: False ๐ฏ Solution /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNo..
-
[Algo Rhythm๐บ๐] LeetCode 167. Two Sum II - Input array is sortedAlgo Rhythm๐บ๐/LeetCode 2020. 8. 24. 15:19
๐ Problem description Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number. The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Note: Your returned answers (both index1 and index2) are not zero-based. You may assume that each inp..
-
[Algo Rhythm๐บ๐] BOJ 17626. Four SquaresAlgo Rhythm๐บ๐/BOJ 2020. 8. 24. 15:06
๐ ๋ฌธ์ ์ค๋ช ๋ผ๊ทธ๋์ฃผ๋ 1770๋ ์ ๋ชจ๋ ์์ฐ์๋ ๋ท ํน์ ๊ทธ ์ดํ์ ์ ๊ณฑ์์ ํฉ์ผ๋ก ํํํ ์ ์๋ค๊ณ ์ฆ๋ช ํ์๋ค. ์ด๋ค ์์ฐ์๋ ๋ณต์์ ๋ฐฉ๋ฒ์ผ๋ก ํํ๋๋ค. ์๋ฅผ ๋ค๋ฉด, 26์ 52๊ณผ 12์ ํฉ์ด๋ค; ๋ํ 4^2 + 3^2 + 1^2์ผ๋ก ํํํ ์๋ ์๋ค. ์ญ์ฌ์ ์ผ๋ก ์์ฐ์ ๋ช ์๋ค์๊ฒ ๊ณตํต์ ์ผ๋ก ์ฃผ์ด์ง๋ ๋ฌธ์ ๊ฐ ๋ฐ๋ก ์์ฐ์๋ฅผ ๋ท ํน์ ๊ทธ ์ดํ์ ์ ๊ณฑ์ ํฉ์ผ๋ก ๋ํ๋ด๋ผ๋ ๊ฒ์ด์๋ค. 1900๋ ๋ ์ด๋ฐ์ ํ ์์ฐ๊ฐ๊ฐ 15663 = 125^2 + 6^2 + 1^2 + 1^2๋ผ๋ ํด๋ฅผ ๊ตฌํ๋๋ฐ 8์ด๊ฐ ๊ฑธ๋ ธ๋ค๋ ๋ณด๊ณ ๊ฐ ์๋ค. ์ข ๋ ์ด๋ ค์ด ๋ฌธ์ ์ ๋ํด์๋ 56์ด๊ฐ ๊ฑธ๋ ธ๋ค: 11339 = 105^2 + 15^2 + 8^2 + 5^2. ์์ฐ์ n์ด ์ฃผ์ด์ง ๋, n์ ์ต์ ๊ฐ์์ ์ ๊ณฑ์ ํฉ์ผ๋ก ํํํ๋ ์ปดํจํฐ ํ๋ก๊ทธ๋จ..
-
[Algo Rhythm๐บ๐] BOJ 17521. Byte coinAlgo Rhythm๐บ๐/BOJ 2020. 8. 24. 13:48
๐ ๋ฌธ์ ์ค๋ช ๊ตญ์ ์๋ณธ๋ถ๋์ฐํ์ฌ(ICPC)๋ ๋ฐ์ดํธ ์ฝ์ธ(Byte Coin)์ ์๊ธ์ ํฌ์ํ๊ณ ์๋ค. ๋ฐ์ดํธ ์ฝ์ธ์ ๊น๋ฐ์ฌ๊ฐ ๋ง๋ ๊ฐ์ ํํ์ด๋ค. ์ค์ ๋ก๋ ๋ฐ์ดํธ ์ฝ์ธ ๊ฐ๊ฒฉ์ ์์ํ ์ ์์ง๋ง ์ด ๋ฌธ์ ์์๋ ๋ฐ์ดํธ ์ฝ์ธ ๊ฐ๊ฒฉ ๋ฑ๋ฝ์ ๋ฏธ๋ฆฌ ์ ํํ ์์ธกํ ์ ์๋ค๊ณ ๊ฐ์ ํ์. ์ฐ๋ฆฌ๋ 1์ผ๋ถํฐ n์ผ๊น์ง n์ผ ๋์ ๊ทธ๋ฆผ 1๊ณผ ๊ฐ์ด ๋ฐ์ดํธ ์ฝ์ธ์ ๋ฑ๋ฝ์ ๋ฏธ๋ฆฌ ์ ์ ์์ผ๋ฉฐ ์ฐ๋ฆฌ์๊ฒ๋ ์ด๊ธฐ ํ๊ธ W๊ฐ ์ฃผ์ด์ ธ ์๋ค. ๊ทธ๋ฆผ 1์ ๋นจ๊ฐ์ ๋ค๋ชจ๋ ํด๋น ์ผ์์ ๋ฐ์ดํธ ์ฝ์ธ ๊ฐ๊ฒฉ์ ๋ํ๋ธ๋ค. ๋งค์ผ ๋ฐ์ดํธ ์ฝ์ธ์ ๋งค์ํ๊ฑฐ๋ ๋งค๋ํ ์ ์๋ค๊ณ ํ์. ๋ค๋ง ๋ฐ์ดํธ ์ฝ์ธ ํ๋๋ฅผ ๋๋์ด ๋งค๋ํ๊ฑฐ๋ ๋งค์ํ ์๋ ์๋ค. ์ฐ๋ฆฌ๋ n์ผ ๋ ๋ณด์ ํ๊ณ ์๋ ๋ชจ๋ ์ฝ์ธ์ ๋งค๋ํ ๋ ๊ฐ์ง๊ณ ์๋ ํ๊ธ์ ์ต๋ํํ๊ณ ์ถ๋ค. ๊ทธ๋ฆผ 1. 10 ์ผ๊ฐ ๋ฐ์ดํธ..
-
[Algo Rhythm๐บ๐] BOJ 17520. Balanced StringAlgo Rhythm๐บ๐/BOJ 2020. 8. 24. 13:36
๐ ๋ฌธ์ ์ค๋ช 0๊ณผ 1๋ก ์ด๋ฃจ์ด์ง ์ด์ง ๋ฌธ์์ด 0101101์ 0๊ณผ 1์ ๊ฐ์์ ์ฐจ์ด๊ฐ 1 ์ดํ์ด๋ค. ๋ฟ๋ง ์๋๋ผ, ์ฒซ ๋ฒ์งธ ๋ฌธ์๋ฅผ ํฌํจํ๋ ๋ชจ๋ ๋ถ๋ถ ๋ฌธ์์ด 0, 01, 010, 0101, 01011, 010110, 0101101 ๋ชจ๋ 0๊ณผ 1์ ๊ฐ์์ ์ฐจ์ด๊ฐ 1 ์ดํ์ด๋ค. ์ด์ ๊ฐ์ด, ์ด์ง ๋ฌธ์์ด ์ค์์ ์ฒซ ๋ฒ์งธ ๋ฌธ์๋ฅผ ํฌํจํ๋ ๋ชจ๋ ๋ถ๋ถ ๋ฌธ์์ด์ 0๊ณผ 1์ ๊ฐ์์ ์ฐจ์ด๊ฐ 1์ดํ์ธ ๋ฌธ์์ด์ ๊ท ํ์กํ ๋ฌธ์์ด์ด๋ผ ๋ถ๋ฅธ๋ค. ๋ฌธ์์ด ์์ฒด๋ ์์ ์ ๋ถ๋ถ ๋ฌธ์์ด์ด๋ค. ์์ ์ ์ n ์ด ์ฃผ์ด์ง ๋, ๊ธธ์ด๊ฐ n ์ธ ์ด์ง ๋ฌธ์์ด ์ค์์ ๊ท ํ์กํ ๋ฌธ์์ด์ ์๋ฅผ ๊ตฌํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค. ์๋ฅผ ๋ค์ด, n = 3์ธ ๊ฒฝ์ฐ์๋ 010, 011, 100, 101 ๋ค ๊ฐ์ ๋ฌธ์์ด์ด ๊ท ํ์กํ ๋ฌธ์์ด์ด๋ค. ์ ๋ ฅ ์ ๋ ฅ์ ํ์ค์ ๋ ฅ์..
-
[Algo Rhythm๐บ๐] LeetCode 78. SubsetsAlgo Rhythm๐บ๐/LeetCode 2020. 8. 22. 23:38
๐ Problem description Given a set of distinct integers, nums, return all possible subsets (the power set). Note: The solution set must not contain duplicate subsets. Example: Input: nums = [1,2,3] Output: [ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ] ๐ฏ Solution 1. Backtracking class Solution { List answer = new ArrayList(); public List subsets(int[] nums) { List list = new ArrayList(); bac..