SERIES

πŸ’‘ Algorithm

11 PostsΒ·Last updated on May 16, 2022

πŸ’‘ Graph 이둠

December 28, 2021

πŸ“– κ·Έλž˜ν”„ 계측적인 ꡬ쑰보닀 μ’€ 더 일반적이고 κ°•λ ₯ν•œ 자료 ꡬ쑰, μ‚¬λ¬Όμ΄λ‚˜ κ°œλ… κ°„μ˜ μ—°κ²° ꡬ쑰 ex. μ—¬λŸ¬ λ„μ‹œλ“€μ„ μ—°κ²°ν•˜λŠ” λ„λ‘œλ§, μ‚¬λžŒλ“€ κ°„μ˜ 지인 관계, μ›Ή μ‚¬μ΄νŠΈ κ°„μ˜ 링크 νŠΈλ¦¬μ— μžˆμ—ˆλ˜ λΆ€λͺ¨ μžμ‹ 관계에 λŒ€ν•œ μ œμ•½μ΄ μ—†μ–΄ μ’€ 더 λ‹€μ–‘ν•˜κ³  자유둜운 ꡬ쑰 ν‘œν˜„μ΄ κ°€λŠ₯ν•˜λ‹€. πŸ’‘ μ •μ˜ κ·Έλž˜ν”„ G(V, E)λŠ” μ–΄λ–€ μžλ£Œλ‚˜ κ°œλ…μ„ ν‘œν˜„ν•˜λŠ” 정점(verte…


πŸ’‘ λ¬Έμ œν•΄κ²°κ°œκ΄€

February 03, 2022

ν”„λ‘œκ·Έλž˜λ° λŒ€νšŒμ—μ„œ λ°°μš°λŠ” μ•Œκ³ λ¦¬μ¦˜ 문제 ν•΄κ²° μ „λž΅ - κ΅¬μ’…λ§Œμ„ 읽고 μ •λ¦¬ν•œ POSTμž…λ‹ˆλ‹€. πŸ’‘ 문제 ν•΄κ²° κ³Όμ • πŸ” 파인만 μ•Œκ³ λ¦¬μ¦˜ : ν˜„μž¬ 인λ₯˜μ—κ²Œ μ•Œλ €μ§„ κ°€μž₯ κ°•λ ₯ν•œ 일반적 문제 ν•΄κ²° μ•Œκ³ λ¦¬μ¦˜ μΉ νŒμ— 문제λ₯Ό μ λŠ”λ‹€. 골똘히 μƒκ°ν•œλ‹€. μΉ νŒμ— λ‹΅μ•ˆμ„ μ λŠ”λ‹€. 사싀 λ°˜μ―€μ€ 농담인 이 μ•Œκ³ λ¦¬μ¦˜μ—μ„œ, μš°λ¦¬λŠ” μ•„λž˜μ™€ 같은 것을 배울 수 μžˆλ‹€. 문제 ν•΄κ²° 과정을…


πŸ’‘ μ•Œκ³ λ¦¬μ¦˜ 뢄석

March 28, 2022

ν”„λ‘œκ·Έλž˜λ° λŒ€νšŒμ—μ„œ λ°°μš°λŠ” μ•Œκ³ λ¦¬μ¦˜ 문제 ν•΄κ²° μ „λž΅ - κ΅¬μ’…λ§Œμ„ 읽고 μ •λ¦¬ν•œ POSTμž…λ‹ˆλ‹€. πŸ’‘ κ°œκ΄€ μ–΄λ–€ μž‘μ—…μ΄ μ£Όμ–΄μ‘Œμ„ λ•Œ 컴퓨터가 이 μž‘μ—…μ„ ν•΄κ²°ν•˜λŠ” 방법을 μ•Œκ³ λ¦¬μ¦˜μ΄λΌκ³  ν•œλ‹€. 또 λ‹€λ₯΄κ²ŒλŠ”, 같은 일을 ν•˜λŠ” μ—¬λŸ¬ κ°€μ§€μ˜ 방법이 μ‘΄μž¬ν•œλ‹€. μ΄λ•Œ μ£Όμ–΄μ§„ 문제λ₯Ό ν•΄κ²°ν•˜λŠ” ν•œ κ°€μ§€ 방법을 λͺ…λ£Œν•˜κ²Œ 써놓은 것을 μ•Œκ³ λ¦¬μ¦˜μ΄λΌκ³  ν•œλ‹€. μ΄λŸ¬ν•œ μΈ‘λ©΄μ—μ„œ, 주관적…


πŸ’‘ Sorting μ•Œκ³ λ¦¬μ¦˜

April 24, 2022

Sorting μ•Œκ³ λ¦¬μ¦˜μ€ 크게 Comparisons 방식과 Non-Comparisons λ°©μ‹μœΌλ‘œ λ‚˜λˆŒ 수 μžˆλ‹€. 🧷 Comparisons 방식 μ•Œκ³ λ¦¬μ¦˜ , , , , , 🧷 Non-Comparisons 방식 μ•Œκ³ λ¦¬μ¦˜ , Stable sort : μ€‘λ³΅λœ ν‚€λ₯Ό μˆœμ„œλŒ€λ‘œ μ •λ ¬ν•˜λŠ” μ •λ ¬ 방식이닀. 즉, 값이 같은 μ›μ†Œκ°€ μžˆμ–΄λ„ μ •λ ¬ μ‹œ κ·Έ μˆœμ„œλ₯Ό 보μž₯ν•˜λŠ” 방…


πŸ’‘ 이뢄 탐색(Binary Search)

May 05, 2022

🧷 이뢄 탐색 탐색 λ²”μœ„λ₯Ό 두 λΆ€λΆ„μœΌλ‘œ λΆ„ν• ν•˜λ©΄μ„œ μ°ΎλŠ” 방식 μ²˜μŒλΆ€ν„° λκΉŒμ§€ νƒμƒ‰ν•˜λŠ” 것보닀 더 λΉ λ₯Έ μ‹œκ°„ λ³΅μž‘λ„λ₯Ό κ°€μ§€λŠ” 방식 πŸͺš κ³Όμ • κ°€μž₯ 핡심은 정렬이 λ˜μ–΄ μžˆμ–΄μ•Ό ν•œλ‹€λŠ” 점이닀. 와 λ₯Ό μ‚¬μš©ν•΄ λ₯Ό μ„€μ •ν•œλ‹€. 와 κ΅¬ν•˜κ³ μž ν•˜λŠ” 값을 λΉ„κ΅ν•œλ‹€. κ΅¬ν•˜κ³ μž ν•˜λŠ” 값이 더 큰 경우, 더 μž‘μ€ 경우, κ°€ 될 λ•ŒκΉŒμ§€ 반볡 탐색할 λ°°μ—΄μ˜ λ²”μœ„λ₯Ό 벗어…


πŸ’‘ ν•΄μ‹œ ν…Œμ΄λΈ” (Hash Table)

May 06, 2022

🧷 ν•΄μ‹œ ν…Œμ΄λΈ” μ™„μ „ νƒμƒ‰μœΌλ‘œλŠ” μ‹œκ°„μ΄ˆκ³Όμ— λΉ μ§€κ²Œ λ˜λŠ” λ¬Έμ œμ—μ„œλŠ” ν•΄μ‹œλ₯Ό μ μš©μ‹œμΌœ 탐색 μ‹œκ°„μ„ 쀄일 수 μžˆλ‹€. λŠ” λ‚΄λΆ€μ μœΌλ‘œ 배열을 μ‚¬μš©ν•˜μ—¬ 데이터λ₯Ό μ €μž₯ν•˜μ—¬ μž‘μ€ λ©”λͺ¨λ¦¬λ‘œλ„ ν”„λ‘œμ„ΈμŠ€ 관리가 κ°€λŠ₯ν•΄μ§€κ³ , λΉ λ₯Έ 검색 속도λ₯Ό κ°–λŠ”λ‹€. 고유의 둜 μ ‘κ·Όν•˜μ—¬ νŠΉμ • 값을 νƒμƒ‰ν•˜κΈ°μ— ν‰κ· μ μœΌλ‘œ 이 λœλ‹€. 좩돌 ν˜„μƒμœΌλ‘œ 인해 "평균적"으둜 이닀. λ¬Έμ œλŠ” 이 둜 저…


πŸ’‘ 졜μž₯ 증가 μˆ˜μ—΄(LIS)

May 09, 2022

🧷 졜μž₯ 증가 μˆ˜μ—΄ κ°€μž₯ κΈ΄ μ¦κ°€ν•˜λŠ” λΆ€λΆ„ μˆ˜μ—΄(Longest Increasing Sequence)둜, μΌλ°˜μ μœΌλ‘œλŠ” DPλ₯Ό μ΄μš©ν•΄ ν•΄κ²°ν•œλ‹€. πŸͺš DPλ₯Ό ν™œμš©ν•œ κ΅¬ν˜„ 및 μ‹œκ°„ λ³΅μž‘λ„ ν•˜μ§€λ§Œ μœ„μ™€ 같이 DPλ₯Ό ν™œμš©ν•˜λŠ” λ°©μ‹μ˜ μ‹œκ°„ λ³΅μž‘λ„λŠ” 이닀. 이λ₯Ό μ€„μ΄λŠ” 쒋은 방법은 이뢄 탐색을 ν™œμš©ν•˜λŠ” 것이닀. πŸͺš 이뢄 탐색을 ν™œμš©ν•œ κ΅¬ν˜„ 및 μ‹œκ°„ λ³΅μž‘λ„ LISλ₯Ό ꡬ성…


πŸ’‘ DP (Dynamic Programming)

May 13, 2022

🧷 동적 κ³„νšλ²• (DP) λ³΅μž‘ν•œ 문제λ₯Ό κ°„λ‹¨ν•œ μ—¬λŸ¬ 개의 문제둜 λ‚˜λˆ  ν‘ΈλŠ” λ°©λ²•μœΌλ‘œ, 큰 μ˜λ―Έμ—μ„œ λΆ„ν•  정볡과 같은 μ ‘κ·Ό 방식을 μ˜λ―Έν•œλ‹€. ν•œ κ°€μ§€ λ¬Έμ œμ— λŒ€ν•΄, 단 ν•œ 번만 풀도둝 λ§Œλ“€μ–΄μ£ΌλŠ” μ•Œκ³ λ¦¬μ¦˜μœΌλ‘œ, λ™μΌν•œ 연산을 λ°˜λ³΅ν•˜μ§€ μ•ŠλŠ”λ‹€. μ‹€ν–‰ μ‹œκ°„μ„ 쀄이기 μœ„ν•΄ 많이 μ΄μš©λ˜λŠ” μ•Œκ³ λ¦¬μ¦˜ (μ΅œμ ν™” μ•Œκ³ λ¦¬μ¦˜) νš¨μœ¨μ„± ν…ŒμŠ€νŠΈκ°€ μžˆλŠ” 경우, DPλ‚˜ 이진 탐색을 …


πŸ’‘ μ΅œμ†Œ 곡톡 쑰상(LCA)

May 13, 2022

🧷 μ΅œμ†Œ 곡톡 쑰상 Lowest Common Ancestor μ•Œκ³ λ¦¬μ¦˜μœΌλ‘œ, νŠΈλ¦¬μ—μ„œ 두 정점이 λ§Œλ‚˜λŠ” 졜초 λΆ€λͺ¨ 정점을 μ°ΎλŠ” μ•Œκ³ λ¦¬μ¦˜μ΄λ‹€. 트리 λ¬Έμ œμ—μ„œ 곡톡 쑰상을 μ°Ύμ•„μ•Ό ν•˜κ±°λ‚˜, 정점과 정점 μ‚¬μ΄μ˜ 이동거리 λ˜λŠ” 방문경둜λ₯Ό μ €μž₯ν•΄μ•Ό ν•  경우 μ‚¬μš©ν•  수 μžˆλ‹€. πŸͺš κ³Όμ • ν•΄λ‹Ή μ •μ μ˜ 와 λ₯Ό μ €μž₯ν•˜λŠ” 방식이닀. μœ„ κ·Έλ¦Όμ—μ„œμ˜ 와 λŠ” μ•„λž˜μ™€ κ°™λ‹€. ν•˜β€¦


πŸ’‘ λ‹€μ΅μŠ€νŠΈλΌ(Dijkstra) μ•Œκ³ λ¦¬μ¦˜

May 13, 2022

🧷 λ‹€μ΅μŠ€νŠΈλΌ(Dijkstra) μ•Œκ³ λ¦¬μ¦˜ DPλ₯Ό ν™œμš©ν•œ μ΅œλ‹¨ 경둜 탐색 μ•Œκ³ λ¦¬μ¦˜μœΌλ‘œ, μ‹œμž‘ 정점 μ—μ„œλΆ€ν„° λ‹€λ₯Έ μ •μ λ“€κΉŒμ§€μ˜ μ΅œλ‹¨ 거리λ₯Ό κ³„μ‚°ν•œλ‹€. DPκ°€ μ μš©λ˜λŠ” μ΄μœ λŠ”, ꡳ이 ν•œ 번 μ΅œλ‹¨ 거리λ₯Ό κ΅¬ν•œ 곳은 λ‹€μ‹œ ꡬ할 ν•„μš”κ°€ μ—†κΈ° λ•Œλ¬Έμ΄λ‹€. 그리고 이λ₯Ό ν™œμš©ν•΄ μ •μ μ—μ„œ μ •μ κΉŒμ§€ 간선을 따라 이동할 λ•Œ μ΅œλ‹¨ 거리λ₯Ό 효율적으둜 ꡬ할 수 μžˆλ‹€. κ°„μ„ μ˜ 값이 …