๐งฎ ์๊ณ ๋ฆฌ์ฆ
-
๊ทธ๋ฆฌ๋ ์๊ณ ๋ฆฌ์ฆ(Greedy Algorithm) ๊ทธ๋ฆฌ๋ ์๊ณ ๋ฆฌ์ฆ์ "๋งค ์ ํ์์ ๋น์ฅ ์ข์๊ฒ๋ง์ ์ ํํด ๋๊ฐ๋ ๋ฐฉ๋ฒ"์ ๋ปํ๋ค. ํน์ ๊ธฐ์ค์ ๋ฐ๋ผ์ ์ข์ ๊ฒ์ ์ ํํด์ผํ๋ ์๊ณ ๋ฆฌ์ฆ์ด๊ธฐ ๋๋ฌธ์ ๋ฌธ์ ์์ ์ด๋์ ๋ ์ ์ํด์ค๋ค. ๊ทธ๋ฆฌ๊ณ ์ข๋ค, ๋์๋ค์ ๊ธฐ์ค์ ์ธ์์ผํ๊ธฐ ๋๋ฌธ์ ์ ๋ ฌ ์๊ณ ๋ฆฌ์ฆ๊ณผ ์์ฌ์ ๋์ค๋ ๋ฌธ์ ๋ค์ด ๋ง๋ค. ๊ฐ๋จํ ์์ (๊ฑฐ์ค๋ฆ ๋) ๊ทธ๋ฆฌ๋ ์๊ณ ๋ฆฌ์ฆ์ ๋ํํ๋ ๋ฌธ์ ๋ก '๊ฑฐ์ค๋ฆ ๋' ๋ฌธ์ ๊ฐ ์๋ค. ์ํ๊ธฐ์ ๊ฑฐ์ค๋ฆ๋์ ๋ฐฐ์ถํด์ผ ํ๋๋ฐ , ์ํ๊ธฐ์๋ 500, 100, 50, 10์์ง๋ฆฌ๊ฐ ๋ฌด์ํ ์กด์ฌํ๋ค. ์ด๋ ๊ฑฐ์ฌ๋ฌ์ค ์ต์ ๋์ ์ ๊ฐ์๋ฅผ ๊ตฌํ๋ผ. (๋จ, ๊ฑฐ์ค๋ฆ ๋์ ํญ์ 10์ ๋ฐฐ์์ด๋ค.) ์ด๋ฌํ ๋ฌธ์ ๊ฐ ์๋ค๋ฉด, ๋ฌด์กฐ๊ฑด ํฐ ๋จ์์ ๋์ (500์)์ผ๋ก ์ต๋ํ ๊ฑฐ์ฌ๋ฌ์ฃผ๊ณ , ๊ทธ ๋ค์ ๊ฐ๋ฅํ ํฐ ๋จ์์ ๋์ (..
๊ทธ๋ฆฌ๋ ์๊ณ ๋ฆฌ์ฆ (Greedy Algorithm) , ํ์๊ทธ๋ฆฌ๋ ์๊ณ ๋ฆฌ์ฆ(Greedy Algorithm) ๊ทธ๋ฆฌ๋ ์๊ณ ๋ฆฌ์ฆ์ "๋งค ์ ํ์์ ๋น์ฅ ์ข์๊ฒ๋ง์ ์ ํํด ๋๊ฐ๋ ๋ฐฉ๋ฒ"์ ๋ปํ๋ค. ํน์ ๊ธฐ์ค์ ๋ฐ๋ผ์ ์ข์ ๊ฒ์ ์ ํํด์ผํ๋ ์๊ณ ๋ฆฌ์ฆ์ด๊ธฐ ๋๋ฌธ์ ๋ฌธ์ ์์ ์ด๋์ ๋ ์ ์ํด์ค๋ค. ๊ทธ๋ฆฌ๊ณ ์ข๋ค, ๋์๋ค์ ๊ธฐ์ค์ ์ธ์์ผํ๊ธฐ ๋๋ฌธ์ ์ ๋ ฌ ์๊ณ ๋ฆฌ์ฆ๊ณผ ์์ฌ์ ๋์ค๋ ๋ฌธ์ ๋ค์ด ๋ง๋ค. ๊ฐ๋จํ ์์ (๊ฑฐ์ค๋ฆ ๋) ๊ทธ๋ฆฌ๋ ์๊ณ ๋ฆฌ์ฆ์ ๋ํํ๋ ๋ฌธ์ ๋ก '๊ฑฐ์ค๋ฆ ๋' ๋ฌธ์ ๊ฐ ์๋ค. ์ํ๊ธฐ์ ๊ฑฐ์ค๋ฆ๋์ ๋ฐฐ์ถํด์ผ ํ๋๋ฐ , ์ํ๊ธฐ์๋ 500, 100, 50, 10์์ง๋ฆฌ๊ฐ ๋ฌด์ํ ์กด์ฌํ๋ค. ์ด๋ ๊ฑฐ์ฌ๋ฌ์ค ์ต์ ๋์ ์ ๊ฐ์๋ฅผ ๊ตฌํ๋ผ. (๋จ, ๊ฑฐ์ค๋ฆ ๋์ ํญ์ 10์ ๋ฐฐ์์ด๋ค.) ์ด๋ฌํ ๋ฌธ์ ๊ฐ ์๋ค๋ฉด, ๋ฌด์กฐ๊ฑด ํฐ ๋จ์์ ๋์ (500์)์ผ๋ก ์ต๋ํ ๊ฑฐ์ฌ๋ฌ์ฃผ๊ณ , ๊ทธ ๋ค์ ๊ฐ๋ฅํ ํฐ ๋จ์์ ๋์ (..
2021.06.13 -
๋ฌธ์ ๋ถ๋ฅ : ์์ ํ์ Lv.2 ์๊ฐ ์ข ์ด์ ๋ช๊ฐ ๊ทธ๋ ค๋ณด๋ฉด์ ์ ํ์์ ์ธ์๋ณด์๋ค. yellow = (width -2) * (height - 2) brown = (width * height) - yellow ์ด๊ฑธ ํตํด์ ๋ฑ ๋จ์ด์ง๋ ์ด๋ค ์์ ๋์ถํด ๋ด์ง๋ ๋ชปํ๋ค. ๊ทธ๋์ width์ height์ ๊ฐ์ ๊ณ์ ๋ฐ๊พธ์ด ๋์ ํด๋ณด๋ฉด์ ์ ์์ ๋ถํฉํ๋์ง ํ์ธํ๋ ๋ฐฉ๋ฒ์ผ๋ก ์ฝ๋๋ฅผ ์งฐ๋ค. ์ด๋ ๋ฒ์๊ฐ ์ค์ํ๋ค๊ณ ์๊ฐํ๋๋ฐ, ๋ฌธ์ ์์ ๋ณด๋ฉด yellow์ ์ต๋ ๋ฒ์๋ 2,000,000์ด๊ณ , brown์ 5,000์ด๋ค. ๊ฐ์ฅ width๊ฐ ๊ธธ์ด์ง๋๋ height์ด 3์นธ์ด๋ฉด์ ๋์์ brown์ ์ต๋๊ฐ์ผ๋์ผ ๊ฒ์ด๋ค. ๋๋ต์ ์ผ๋ก ๊ณ์ฐํด๋ณด์๋ฉด, brown์ ๋งจ ์, ๋งจ ์๋ ๋์ค๋ก ์ด๋ฃจ์ด์ ธ์๋ค. ๊ทธ๋ฌ๋ฏ๋ก ๋๋๊ธฐ 2๋ฅผ ํด์ฃผ๋ฉด ์ต..
[ํ๋ก๊ทธ๋๋จธ์ค] (Python) - ์นดํซ๋ฌธ์ ๋ถ๋ฅ : ์์ ํ์ Lv.2 ์๊ฐ ์ข ์ด์ ๋ช๊ฐ ๊ทธ๋ ค๋ณด๋ฉด์ ์ ํ์์ ์ธ์๋ณด์๋ค. yellow = (width -2) * (height - 2) brown = (width * height) - yellow ์ด๊ฑธ ํตํด์ ๋ฑ ๋จ์ด์ง๋ ์ด๋ค ์์ ๋์ถํด ๋ด์ง๋ ๋ชปํ๋ค. ๊ทธ๋์ width์ height์ ๊ฐ์ ๊ณ์ ๋ฐ๊พธ์ด ๋์ ํด๋ณด๋ฉด์ ์ ์์ ๋ถํฉํ๋์ง ํ์ธํ๋ ๋ฐฉ๋ฒ์ผ๋ก ์ฝ๋๋ฅผ ์งฐ๋ค. ์ด๋ ๋ฒ์๊ฐ ์ค์ํ๋ค๊ณ ์๊ฐํ๋๋ฐ, ๋ฌธ์ ์์ ๋ณด๋ฉด yellow์ ์ต๋ ๋ฒ์๋ 2,000,000์ด๊ณ , brown์ 5,000์ด๋ค. ๊ฐ์ฅ width๊ฐ ๊ธธ์ด์ง๋๋ height์ด 3์นธ์ด๋ฉด์ ๋์์ brown์ ์ต๋๊ฐ์ผ๋์ผ ๊ฒ์ด๋ค. ๋๋ต์ ์ผ๋ก ๊ณ์ฐํด๋ณด์๋ฉด, brown์ ๋งจ ์, ๋งจ ์๋ ๋์ค๋ก ์ด๋ฃจ์ด์ ธ์๋ค. ๊ทธ๋ฌ๋ฏ๋ก ๋๋๊ธฐ 2๋ฅผ ํด์ฃผ๋ฉด ์ต..
2021.06.12 -
๋ฌธ์ ๋ถ๋ฅ : ์์ ํ์ Lv.2 Code(python) from itertools import permutations as pm def prime(n) : if (n < 2) : return False for i in range(2, int(n**0.5) + 1) : if (n % i ==0) : return False return True def check(numbers) : numbers = list(numbers) cnt = 0 for i in numbers : if prime(i) : cnt += 1 return cnt def get_permutations(numbers): max_len = len(numbers) numbers = list(numbers) int_nb = list(map(int,..
[ํ๋ก๊ทธ๋๋จธ์ค] (Python) - ์์ ์ฐพ๊ธฐ๋ฌธ์ ๋ถ๋ฅ : ์์ ํ์ Lv.2 Code(python) from itertools import permutations as pm def prime(n) : if (n < 2) : return False for i in range(2, int(n**0.5) + 1) : if (n % i ==0) : return False return True def check(numbers) : numbers = list(numbers) cnt = 0 for i in numbers : if prime(i) : cnt += 1 return cnt def get_permutations(numbers): max_len = len(numbers) numbers = list(numbers) int_nb = list(map(int,..
2021.06.12 -
* ๋ฌธ์ ๋งํฌ programmers.co.kr/learn/courses/30/lessons/72410 ์ฝ๋ฉํ ์คํธ ์ฐ์ต - ์ ๊ท ์์ด๋ ์ถ์ฒ ์นด์นด์ค์ ์ ์ฌํ ์ ์ ๊ฐ๋ฐ์ ๋ค์ค๋ "์นด์นด์ค๊ณ์ ๊ฐ๋ฐํ"์ ๋ฐฐ์น๋์ด, ์นด์นด์ค ์๋น์ค์ ๊ฐ์ ํ๋ ์ ์ ๋ค์ ์์ด๋๋ฅผ ์์ฑํ๋ ์ ๋ฌด๋ฅผ ๋ด๋นํ๊ฒ ๋์์ต๋๋ค. "๋ค์ค"์๊ฒ ์ฃผ์ด์ง ์ฒซ ์ ๋ฌด๋ ์๋ก programmers.co.kr * ๋ฌธ์ ๋ถ๋ฅ , ๋์ด๋ ๋ถ๋ฅ : 2021 KAKAO BLIND RECRUITMENT ๋์ด๋ : Lv1 * ํ์ด์ฌ(Pyhton) ์ฝ๋ def solution(new_id) : #step1 ๋๋ฌธ์ -> ์๋ฌธ์๋ก ์นํ new_id = new_id.lower() #step2 ์๋ฌธ์, ์ซ์, -, _, . ๋ฅผ ์ ์ธํ ๋ฌธ์์ด ์ ๊ฑฐ for idx, char in e..
[ํ๋ก๊ทธ๋๋จธ์ค] (Python) - ์ ๊ท ์์ด๋ ์ถ์ฒ* ๋ฌธ์ ๋งํฌ programmers.co.kr/learn/courses/30/lessons/72410 ์ฝ๋ฉํ ์คํธ ์ฐ์ต - ์ ๊ท ์์ด๋ ์ถ์ฒ ์นด์นด์ค์ ์ ์ฌํ ์ ์ ๊ฐ๋ฐ์ ๋ค์ค๋ "์นด์นด์ค๊ณ์ ๊ฐ๋ฐํ"์ ๋ฐฐ์น๋์ด, ์นด์นด์ค ์๋น์ค์ ๊ฐ์ ํ๋ ์ ์ ๋ค์ ์์ด๋๋ฅผ ์์ฑํ๋ ์ ๋ฌด๋ฅผ ๋ด๋นํ๊ฒ ๋์์ต๋๋ค. "๋ค์ค"์๊ฒ ์ฃผ์ด์ง ์ฒซ ์ ๋ฌด๋ ์๋ก programmers.co.kr * ๋ฌธ์ ๋ถ๋ฅ , ๋์ด๋ ๋ถ๋ฅ : 2021 KAKAO BLIND RECRUITMENT ๋์ด๋ : Lv1 * ํ์ด์ฌ(Pyhton) ์ฝ๋ def solution(new_id) : #step1 ๋๋ฌธ์ -> ์๋ฌธ์๋ก ์นํ new_id = new_id.lower() #step2 ์๋ฌธ์, ์ซ์, -, _, . ๋ฅผ ์ ์ธํ ๋ฌธ์์ด ์ ๊ฑฐ for idx, char in e..
2021.04.24 -
* ๋ฌธ์ ๋งํฌ programmers.co.kr/learn/courses/30/lessons/42576 ์ฝ๋ฉํ ์คํธ ์ฐ์ต - ์์ฃผํ์ง ๋ชปํ ์ ์ ์๋ง์ ๋ง๋ผํค ์ ์๋ค์ด ๋ง๋ผํค์ ์ฐธ์ฌํ์์ต๋๋ค. ๋จ ํ ๋ช ์ ์ ์๋ฅผ ์ ์ธํ๊ณ ๋ ๋ชจ๋ ์ ์๊ฐ ๋ง๋ผํค์ ์์ฃผํ์์ต๋๋ค. ๋ง๋ผํค์ ์ฐธ์ฌํ ์ ์๋ค์ ์ด๋ฆ์ด ๋ด๊ธด ๋ฐฐ์ด participant์ ์์ฃผํ ์ ์ programmers.co.kr * ๋ฌธ์ ๋ถ๋ฅ , ๋์ด๋ ๋ถ๋ฅ : ํด์ ๋์ด๋ : Lv1 * ํ์ด์ฌ(Pyhton) ์ฝ๋ def solution(participant, completion): participant = sorted(participant) completion = sorted(completion) for i in range(len(completion)): if pa..
[ํ๋ก๊ทธ๋๋จธ์ค] (Python) - ์์ฃผํ์ง ๋ชปํ ์ ์ Lv1* ๋ฌธ์ ๋งํฌ programmers.co.kr/learn/courses/30/lessons/42576 ์ฝ๋ฉํ ์คํธ ์ฐ์ต - ์์ฃผํ์ง ๋ชปํ ์ ์ ์๋ง์ ๋ง๋ผํค ์ ์๋ค์ด ๋ง๋ผํค์ ์ฐธ์ฌํ์์ต๋๋ค. ๋จ ํ ๋ช ์ ์ ์๋ฅผ ์ ์ธํ๊ณ ๋ ๋ชจ๋ ์ ์๊ฐ ๋ง๋ผํค์ ์์ฃผํ์์ต๋๋ค. ๋ง๋ผํค์ ์ฐธ์ฌํ ์ ์๋ค์ ์ด๋ฆ์ด ๋ด๊ธด ๋ฐฐ์ด participant์ ์์ฃผํ ์ ์ programmers.co.kr * ๋ฌธ์ ๋ถ๋ฅ , ๋์ด๋ ๋ถ๋ฅ : ํด์ ๋์ด๋ : Lv1 * ํ์ด์ฌ(Pyhton) ์ฝ๋ def solution(participant, completion): participant = sorted(participant) completion = sorted(completion) for i in range(len(completion)): if pa..
2021.04.23 -
* ๋ฌธ์ ๋งํฌ programmers.co.kr/learn/courses/30/lessons/64061 ์ฝ๋ฉํ ์คํธ ์ฐ์ต - ํฌ๋ ์ธ ์ธํ๋ฝ๊ธฐ ๊ฒ์ [[0,0,0,0,0],[0,0,1,0,3],[0,2,5,0,1],[4,2,4,4,2],[3,5,1,3,1]] [1,5,3,5,1,2,1,4] 4 programmers.co.kr * ๋ฌธ์ ๋ถ๋ฅ , ๋์ด๋ ๋ถ๋ฅ : 2019 ์นด์นด์ค ๊ฐ๋ฐ์ ๊ฒจ์ธ ์ธํด์ฝ ๋์ด๋ : Lv1 * ํ์ด์ฌ(Pyhton) ์ฝ๋ def drop_in_basket(board, move, basket): for i in range(len(board)) : if (board[i][move-1] != 0 ) : basket.append(board[i][move-1]) board[i][move-1] = 0..
[ํ๋ก๊ทธ๋๋จธ์ค] (Python) - ํฌ๋ ์ธ ์ธํ๋ฝ๊ธฐ ๊ฒ์* ๋ฌธ์ ๋งํฌ programmers.co.kr/learn/courses/30/lessons/64061 ์ฝ๋ฉํ ์คํธ ์ฐ์ต - ํฌ๋ ์ธ ์ธํ๋ฝ๊ธฐ ๊ฒ์ [[0,0,0,0,0],[0,0,1,0,3],[0,2,5,0,1],[4,2,4,4,2],[3,5,1,3,1]] [1,5,3,5,1,2,1,4] 4 programmers.co.kr * ๋ฌธ์ ๋ถ๋ฅ , ๋์ด๋ ๋ถ๋ฅ : 2019 ์นด์นด์ค ๊ฐ๋ฐ์ ๊ฒจ์ธ ์ธํด์ฝ ๋์ด๋ : Lv1 * ํ์ด์ฌ(Pyhton) ์ฝ๋ def drop_in_basket(board, move, basket): for i in range(len(board)) : if (board[i][move-1] != 0 ) : basket.append(board[i][move-1]) board[i][move-1] = 0..
2021.04.23