๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ

๋ฐ˜์‘ํ˜•

Algorithm/CodingTest - Python

(12)
Algorithm) Dynamic Programming ๋ฌธ์ œ 1. 1๋กœ ๋งŒ๋“ค๊ธฐ ์ •์ˆ˜ X๊ฐ€ ์ฃผ์–ด์งˆ ๋•Œ ์ •์ˆ˜X์— ์‚ฌ์šฉํ•  ์ˆ˜ ์žˆ๋Š” ์—ฐ์‚ฐ์€ ๋‹ค์Œ๊ณผ ๊ฐ™์ด 4๊ฐ€์ง€ ์ด๋‹ค. 1) X๊ฐ€ 5๋กœ ๋‚˜๋ˆ„์–ด๋–จ์–ด์ง€๋ฉด, 5๋กœ ๋‚˜๋ˆˆ๋‹ค. 2) X๊ฐ€ 3์œผ๋กœ ๋‚˜๋ˆ„์–ด๋–จ์–ด์ง€๋ฉด, 3์œผ๋กœ ๋‚˜๋ˆˆ๋‹ค. 3) X๊ฐ€ 2๋กœ ๋‚˜๋ˆ„์–ด ๋–จ์–ด์ง€๋ฉด, 2๋กœ ๋‚˜๋ˆˆ๋‹ค. 4) X์—์„œ 1์„ ๋บ€๋‹ค. ์ •์ˆ˜ X๊ฐ€ ์ฃผ์–ด์กŒ์„ ๋•Œ, ์—ฐ์‚ฐ 4๊ฐœ๋ฅผ ์ ์ ˆํžˆ ์‚ฌ์šฉํ•ด์„œ 1์„ ๋งŒ๋“ค๋ ค๊ณ  ํ•œ๋‹ค. ์—ฐ์‚ฐ์„ ์‚ฌ์šฉํ•˜๋Š” ํšŸ์ˆ˜์˜ ์ตœ์†Ÿ๊ฐ’์„ ์ถœ๋ ฅํ•˜์„ธ์š” ๋ฌธ์ œํ’€์ด ๋‹ต์•ˆ x = int(input()) # DP ํ…Œ์ด๋ธ” ์ดˆ๊ธฐํ™” d = [0] * 30001 # ๋‹ค์ด๋‚˜๋ฏน ํ”„๋กœ๊ทธ๋ž˜๋ฐ ์ง„ํ–‰ - ๋ณดํ…€์—… for i in range(2, x+1): # ํ˜„์žฌ์˜ ์ˆ˜์—์„œ 1์„ ๋นผ๋Š” ๊ฒฝ์šฐ d[i] = d[i-1] + 1 # ํ˜„์žฌ์˜ ์ˆ˜๊ฐ€ 2๋กœ ๋‚˜๋ˆ„์–ด ๋–จ์–ด์ง€๋Š” ๊ฒฝ์šฐ if i % 2 == 0: d[i] =..
Algorithm) Dynamic programming Dynamic programming(๋™์ ๊ณ„ํš๋ฒ•)์ด๋ž€ ? ๋ฉ”๋ชจ๋ฆฌ๋ฅผ ์ ์ ˆํžˆ ์‚ฌ์šฉํ•˜์—ฌ ์ˆ˜ํ–‰์‹œ๊ฐ„ ํšจ์œจ์„ฑ์„ ๋น„์•ฝ์ ์œผ๋กœ ํ–ฅ์ƒ์‹œํ‚ค๋Š” ๋ฐฉ๋ฒ• -> ๋ฉ”๋ชจ๋ฆฌ ๊ณต๊ฐ„์„ ์ตœ๋Œ€ํ•œ์œผ๋กœ ํ™œ์šฉํ•  ์ˆ˜ ์žˆ๋Š” ํšจ์œจ์ ์ธ ์•Œ๊ณ ๋ฆฌ์ฆ˜ ์ž‘์„ฑ ! ๋Œ€ํ‘œ์ ์ธ ์˜ˆ์‹œ : ํ”ผ๋ณด๋‚˜์น˜ ์ˆ˜์—ด - n ๋ฒˆ์งธ ํ”ผ๋ณด๋‚˜์น˜ ์ˆ˜ = (n-1)๋ฒˆ์งธ ํ”ผ๋ณด๋‚˜์น˜ ์ˆ˜ + (n-2)๋ฒˆ์งธ ํ”ผ๋ณด๋‚˜์น˜ ์ˆ˜ - ๋‹จ, 1๋ฒˆ์งธ ํ”ผ๋ณด๋‚˜์น˜ ์ˆ˜ = 1,2 ๋ฒˆ์งธ ํ”ผ๋ณด๋‚˜์น˜ ์ˆ˜ = 1 # ํ”ผ๋ณด๋‚˜์น˜ ํ•จ์ˆ˜ ์†Œ์Šค์ฝ”๋“œ def fibo(x): if x == 1 or x == 2: return 1 return fibo(x-1) + fibo(x-2) print(fibo(4)) -> But, ํ”ผ๋ณด๋‚˜์น˜ ์ˆ˜์—ด์˜ ์†Œ์Šค์ฝ”๋“œ๋ฅผ ์ด๋ ‡๊ฒŒ ์ž‘์„ฑํ•˜๋ฉด ์‹ฌ๊ฐํ•œ ๋ฌธ์ œ๊ฐ€ ์ƒ๊ธธ ์ˆ˜ ์žˆ๋‹ค. ๋ฐ”๋กœ f(n) ํ•จ์ˆ˜์—์„œ n์ด ์ปค์ง€๋ฉด ์ปค์งˆ์ˆ˜๋ก ์ˆ˜ํ–‰ ์‹œ๊ฐ„์ด ๊ธฐํ•˜..
Algorithm ) Binary Search ๋ฌธ์ œ ํŒŒ์ด์ฌ ์ด์ง„ ํƒ์ƒ‰ ๋ผ์ด๋ธŒ๋Ÿฌ๋ฆฌ bisect_left(a,x) : ์ •๋ ฌ๋œ ์ˆœ์„œ๋ฅผ ์œ ์ง€ํ•˜๋ฉด์„œ ๋ฐฐ์—ด a์— x๋ฅผ ์‚ฝ์ž…ํ•  ๊ฐ€์žฅ ์™ผ์ชฝ ์ธ๋ฑ์Šค๋ฅผ ๋ฐ˜ํ™˜ bisect_right(a,x) : ์ •๋ ฌ๋œ ์ˆœ์„œ๋ฅผ ์œ ์ง€ํ•˜๋ฉด์„œ ๋ฐฐ์—ด a์— x๋ฅผ ์‚ฝ์ž…ํ•  ๊ฐ€์žฅ ์˜ค๋ฅธ์ชฝ ์ธ๋ฑ์Šค๋ฅผ ๋ฐ˜ํ™˜ from bisect import bisect_left, bisect_right => ๊ฐ’์ด ํŠน์ • ๋ฒ”์œ„์— ์†ํ•˜๋Š” ๋ฐ์ดํ„ฐ ๊ฐœ์ˆ˜ ๊ตฌํ•˜๊ธฐ from bisect import bisect_left, bisect_right # ๊ฐ’์ด left_value, right_value์ธ ๋ฐ์ดํ„ฐ ๊ฐœ์ˆ˜๋ฅผ ๋ฐ˜ํ™˜ํ•˜๋Š” ํ•จ์ˆ˜ def count_by_range(a, left_value, rignt_value): right_index = bisect_right(a, right_value) left_..
Algorithm) Binary Search ์ด์ง„ํƒ์ƒ‰์— ๋“ค์–ด๊ฐ€๊ธฐ์ „ ๊ฐ€์žฅ ๊ธฐ๋ณธ ํƒ์ƒ‰ ๋ฐฉ๋ฒ•์ธ ์ˆœ์ฐจ ํƒ์ƒ‰์— ๋Œ€ํ•ด์„œ ์‚ด์ง ๋‹ค๋ฃจ๊ณ  ๊ฐ€๋ณด์Ÿˆ ! ์ˆœ์ฐจํƒ์ƒ‰(Sequential Search)์ด๋ž€ ? ๋ฆฌ์ŠคํŠธ ์•ˆ์— ์žˆ๋Š” ํŠน์ •ํ•œ ๋ฐ์ดํ„ฐ๋ฅผ ์ฐพ๊ธฐ ์œ„ํ•ด ์•ž์—์„œ๋ถ€ํ„ฐ ๋ฐ์ดํ„ฐ๋ฅผ ํ•˜๋‚˜์”ฉ ์ฐจ๋ก€๋Œ€๋กœ ํ™•์ธํ•˜๋Š” ๋ฐฉ๋ฒ• - ๋ฆฌ์ŠคํŠธ์— ํŠน์ • ๊ฐ’์˜ ์›์†Œ๊ฐ€ ์žˆ๋Š”์ง€ ์ฒดํฌ - ๋ฆฌ์ŠคํŠธ ์ž๋ฃŒํ˜•์—์„œ ํŠน์ •ํ•œ ๊ฐ’์„ ๊ฐ€์ง€๋Š” ์›์†Œ์˜ ๊ฐœ์ˆ˜๋ฅผ ์„ธ๋Š” count() ๋ฉ”์„œ๋“œ์˜ ๋‚ด๋ถ€์—์„œ์˜ ์ˆœ์ฐจํƒ์ƒ‰ # ์ˆœ์ฐจํƒ์ƒ‰ ์†Œ์Šค์ฝ”๋“œ def sequential_search(n, target, array): # ๊ฐ ์›์†Œ๋ฅผ ํ•˜๋‚˜์”ฉ ํ™•์ธํ•˜๋ฉฐ for i in range(n): # ํ˜„์žฌ์˜ ์›์†Œ๊ฐ€ ์ฐพ๊ณ ์žํ•˜๋Š” ์›์†Œ์™€ ๋™์ผํ•œ ๊ฒฝ์šฐ if array[i] == target: return i + 1 # ํ˜„์žฌ์˜ ์œ„์น˜ ๋ฐ˜ํ™˜ . ์ธ๋ฑ์Šค๋Š” 0๋ถ€ํ„ฐ ์‹œ์ž‘ํ•˜๋‹ˆ๊นŒ 1๋”ํ•˜๊ธฐ ..
Algorithm) Sorting ๊ธฐ๋ณธ๋ฌธ์ œ 1. ์œ„์—์„œ ์•„๋ž˜๋กœ ํŒŒ์ด์ฌ ๊ธฐ๋ณธ ์ •๋ ฌ ๋ผ์ด๋ธŒ๋Ÿฌ๋ฆฌ ์‚ฌ์šฉ n = int(input()) array = [] for i in range(n): array.append(int(input())) array = sorted(array, reverse= True) for i in array: print(i, end = ' ') 2. ์„ฑ์ ์ด ๋‚ฎ์€ ์ˆœ์„œ๋กœ ํ•™์ƒ ์ถœ๋ ฅํ•˜๊ธฐ ํŒŒ์ด์ฌ ๊ธฐ๋ณธ ์ •๋ ฌ ๋ผ์ด๋ธŒ๋Ÿฌ๋ฆฌ, ํŠœํ”Œ ์‚ฌ์šฉ ์ ์ˆ˜๋Œ€๋กœ ์ •๋ ฌํ•˜๊ณ  ์ด๋ฆ„๋งŒ ์ถœ๋ ฅ n = int(input()) array = [] for i in range(n): input_data = input().split() # ์ด๋ฆ„์€ ๋ฌธ์ž์—ด ๊ทธ๋Œ€๋กœ, ์ ์ˆ˜๋Š” ์ •์ˆ˜ํ˜•์œผ๋กœ ๋ณ€ํ™˜ํ•˜์—ฌ ์ €์žฅ array.append((input_data[0], int(input_data[1]))) ..
Algorithm) Sorting ๐Ÿ“Œ ์ •๋ ฌ ? ๋ฐ์ดํ„ฐ๋ฅผ ํŠน์ •ํ•œ ๊ธฐ์ค€์— ๋”ฐ๋ผ์„œ ์ˆœ์„œ๋Œ€๋กœ ๋‚˜์—ดํ•˜๋Š” ๊ฒƒ ! - ์ •๋ ฌ ์•Œ๊ณ ๋ฆฌ์ฆ˜์œผ๋กœ ๋ฐ์ดํ„ฐ๋ฅผ ์ •๋ ฌํ•˜๋ฉด ์ด์ง„ํƒ์ƒ‰์ด ๊ฐ€๋Šฅํ•ด์ง ! ์ด์ง„ํƒ์ƒ‰์˜ ์ „์ฒ˜๋ฆฌ ๊ณผ์ • - ์„ ํƒ ์ •๋ ฌ, ์‚ฝ์ž… ์ •๋ ฌ, ํ€ต ์ •๋ ฌ, ๊ณ„์ˆ˜ ์ •๋ ฌ ๋“ฑ์ด ์žˆ๋‹ค * ๊ธฐ๋ณธ์ ์œผ๋กœ ์˜ค๋ฆ„์ฐจ์ˆœ์œผ๋กœ ์˜ˆ์ œ๋ฅผ ์„ค๋ช… , ๋‚ด๋ฆผ์ฐจ์ˆœ ์ •๋ ฌ์€ ์˜ค๋ฆ„์ฐจ์ˆœ ์ •๋ ฌ์„ ์ˆ˜ํ–‰ํ•œ ๋’ค ๊ทธ ๊ฒฐ๊ณผ๋ฅผ ๋’ค์ง‘๊ธฐํ•˜์—ฌ ๋งŒ๋“ค์ˆ˜ ์žˆ๋”ฐ 1. ์„ ํƒ์ •๋ ฌ - ๋ฐ์ดํ„ฐ๊ฐ€ ๋ฌด์ž‘์œ„๋กœ ์—ฌ๋Ÿฌ๊ฐœ ์žˆ๋‹ค๋ฉด, ์ด ์ค‘์—์„œ ๊ฐ€์žฅ ์ž‘์€ ๋ฐ์ดํ„ฐ๋ฅผ ์„ ํƒํ•ด ๋งจ ์•ž์— ์žˆ๋Š” ๋ฐ์ดํ„ฐ์™€ ๋ฐ”๊พธ๊ณ  ๊ทธ ๋‹ค์Œ ์ž‘์€ ๋ฐ์ดํ„ฐ๋ฅผ ์„ ํƒํ•ด ์•ž์—์„œ ๋‘ ๋ฒˆ์จฐ ๋ฐ์ดํ„ฐ์™€ ๋ฐ”๊พธ๋Š” ๊ณผ์ •์„ ๋ฐ˜๋ณต ! => ๋งค๋ฒˆ ๊ฐ€์žฅ ์ž‘์€ ๊ฒƒ์„ ์„ ํƒ ํ•œ๋‹ค ! - ๊ฐ€์žฅ ์ž‘์€ ๋ฐ์ดํ„ฐ๋ฅผ ์•ž์œผ๋กœ ๋ณด๋‚ด๋Š” ๊ณผ์ •์„ N-1๋ฒˆ ๋ฐ˜๋ณตํ•˜๋ฉด ์ •๋ ฌ์ด ์™„๋ฃŒ ๋œ๋‹ค ! array = [7,5,9,0,3,1,6,2,4,8] ..
Algorithm) DFS/BFS ์‹ค์ „๋ฌธ์ œ ๐Ÿบ 1๋ฒˆ ์Œ๋ฃŒ์ˆ˜ ์–ผ๋ ค๋จน๊ธฐ N x M ํฌ๊ธฐ์˜ ์–ผ์Œ ํ‹€์ด ์žˆ๋‹ค. ๊ตฌ๋ฉ์ด ๋šซ๋ ค ์žˆ๋Š” ๋ถ€๋ถ„์€ 0, ์นธ๋ง‰์ด๊ฐ€ ์กด์žฌํ•˜๋Š” ๋ถ€๋ถ„์€ 1๋กœ ํ‘œ์‹œ๋œ๋‹ค. ๊ตฌ๋ฉ์ด ๋šซ๋ ค์žˆ๋Š” ๋ถ€๋ถ„๋ผ๋ฆฌ ์ƒ,ํ•˜,์ขŒ,์šฐ๋กœ ๋ถ™์–ด ์žˆ๋Š” ๊ฒฝ์šฐ ์„œ๋กœ ์—ฐ๊ฒฐ๋˜์–ด ์žˆ๋Š” ๊ฒƒ์œผ๋กœ ๊ฐ„์ฃผํ•œ๋‹ค. ์ด๋•Œ ์–ผ์Œ ํ‹€์˜ ๋ชจ์–‘์ด ์ฃผ์–ด์กŒ์„ ๋•Œ ์ƒ์„ฑ๋˜๋Š” ์ด ์•„์ด์Šคํฌ๋ฆผ์˜ ๊ฐœ์ˆ˜๋ฅผ ๊ตฌํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑ ==> DFS๋กœ ํ•ด๊ฒฐ ! ์–ผ์Œ์„ ์–ผ๋ฆด ์ˆ˜ ์žˆ๋Š” ๊ณต๊ฐ„์ด ์ƒํ•˜์ขŒ์šฐ๋กœ ์—ฐ๊ฒฐ๋˜์–ด์žˆ๋‹ค๊ณ  ํ‘œํ˜„ํ•  ์ˆ˜ ์žˆ์œผ๋ฏ€๋กœ ๊ทธ๋ž˜ํ”„ ํ˜•ํƒœ๋กœ ๋ชจ๋ธ๋ง ๊ฐ€๋Šฅ ! 1) ํŠน์ •ํ•œ ์ง€์ ์˜ ์ฃผ๋ณ€ ์ƒํ•˜์ขŒ์šฐ๋ฅผ ์‚ดํŽด๋ณธ ๋’ค์— ์ฃผ๋ณ€ ์ง€์  ์ค‘์—์„œ ๊ฐ’์ด 0 ์ด๋ฉด์„œ ์•„์ง ๋ฐฉ๋ฌธํ•˜์ง€ ์•Š์€ ์ง€์ ์ด ์žˆ๋‹ค๋ฉด ํ•ด๋‹น ์ง€์  ๋ฐฉ๋ฌธ 2) ๋ฐฉ๋ฌธํ•œ ์ง€์ ์—์„œ ๋‹ค์‹œ ์ƒํ•˜์ขŒ์šฐ๋ฅผ ์‚ดํŽด๋ณด๋ฉด์„œ ๋ฐฉ๋ฌธ์„ ๋‹ค์‹œ ์ง„ํ–‰ํ•˜๋ฉฐ, ์—ฐ๊ฒฐ๋œ ๋ชจ๋“  ์ง€์  ๋ฐฉ๋ฌธ ๊ฐ€๋Šฅ 3) 1-2๋ฒˆ์˜ ๊ณผ์ •์„ ๋ชจ๋“  ๋…ธ๋“œ..
Algorithm) DFS/BFS ๐Ÿž DFS - ๊นŠ์ด ์šฐ์„  ํƒ์ƒ‰์ด๋ผ๊ณ ๋„ ๋ถ€๋ฅด๋ฉฐ, ๊ทธ๋ž˜ํ”„์—์„œ ๊นŠ์€ ๋ถ€๋ถ„์„ ์šฐ์„ ์ ์œผ๋กœ ํƒ์ƒ‰ํ•˜๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜ - ๊ทธ๋ž˜ํ”„์˜ ๊ธฐ๋ณธ๊ตฌ์กฐ๋ฅผ ์•Œ์•„์•ผํ•จ โฌ‡๏ธ ๋”๋ณด๊ธฐ ๐Ÿ”– ๊ทธ๋ž˜ํ”„๋Š” ๋…ธ๋“œ์™€ ๊ฐ„์„ ์œผ๋กœ ํ‘œํ˜„๋˜๋ฉฐ ์ด๋•Œ ๋…ธ๋“œ๋ฅผ ์ •์ ์ด๋ผ๊ณ ๋„ ๋งํ•œ๋‹ค. ๊ทธ๋ž˜ํ”„ ํƒ์ƒ‰์ด๋ž€ ํ•˜๋‚˜์˜ ๋…ธ๋“œ๋ฅผ ์‹œ์ž‘์œผ๋กœ ๋‹ค์ˆ˜์˜ ๋…ธ๋“œ๋ฅผ ๋ฐฉ๋ฌธํ•˜๋Š” ๊ฒƒ์„ ๋งํ•œ๋‹ค. ๋˜ํ•œ ๋‘ ๋…ธ๋“œ๊ฐ€ ๊ฐ„์„ ์œผ๋กœ ์—ฐ๊ฒฐ๋˜์–ด ์žˆ๋‹ค๋ฉด ๋‘ ๋…ธ๋“œ๋Š” ์ธ์ ‘ํ•˜๋‹ค ๋ผ๊ณ  ํ‘œํ˜„ํ•œ๋‹ค - ํ”„๋กœ๊ทธ๋ž˜๋ฐ์—์„œ ๊ทธ๋ž˜ํ”„๋Š” ํฌ๊ฒŒ 2๊ฐ€์ง€ ๋ฐฉ์‹์œผ๋กœ ํ‘œํ˜„ํ•  ์ˆ˜ ์žˆ๋Š”๋ฐ ์ฝ”๋”ฉ ํ…Œ์ŠคํŠธ์—์„œ๋Š” ์ด ๋‘ ๋ฐฉ์‹ ๋ชจ๋‘ ํ•„์š”ํ•˜๋‹ˆ ๋‘ ๊ฐœ๋…์— ๋Œ€ํ•ด ๋ฐ”๋ฅด๊ฒŒ ์•Œ๊ณ  ์žˆ๋„๋ก ํ•˜์ž ! 1. ์ธ์ ‘ํ–‰๋ ฌ : 2์ฐจ์› ๋ฐฐ์—ด๋กœ ๊ทธ๋ž˜ํ”„์˜ ์—ฐ๊ฒฐ ๊ด€๊ณ„๋ฅผ ํ‘œํ˜„ํ•˜๋Š” ๋ฐฉ์‹ - 2์ฐจ์› ๋ฐฐ์—ด์— ๊ฐ ๋…ธ๋“œ๊ฐ€ ์—ฐ๊ฒฐ๋œ ํ˜•ํƒœ๋ฅผ ๊ธฐ๋กํ•˜๋Š” ๋ฐฉ์‹ - ์—ฐ๊ฒฐ๋œ ๊ทธ๋ž˜ํ”„๋ฅผ ์ธ์ ‘ ํ–‰๋ ฌ๋กœ ํ‘œํ˜„ํ•  ๋•Œ ํŒŒ์ด์ฌ์—์„œ๋Š” 2์ฐจ์› ๋ฆฌ..

๋ฐ˜์‘ํ˜•