λ³Έλ¬Έ λ°”λ‘œκ°€κΈ°
728x90
λ°˜μ‘ν˜•

πŸ–₯ Computer Science/Algorithm16

[Algorithm] LRU(Least Recently Used) Cache μ•Œκ³ λ¦¬μ¦˜μ΄λž€? (feat. νŽ˜μ΄μ§€ ꡐ체 μ•Œκ³ λ¦¬μ¦˜) μ•ˆλ…•ν•˜μ„Έμš” Foma μž…λ‹ˆλ‹€. μ˜€λŠ˜μ€ 효과적으둜 λ©”λͺ¨λ¦¬λ₯Ό 관리할 수 μžˆλŠ” νŽ˜μ΄μ§€ ꡐ체 기법 쀑 ν•˜λ‚˜μΈ LRU Cache μ•Œκ³ λ¦¬μ¦˜μ— λŒ€ν•΄μ„œ 닀뀄 보렀고 ν•©λ‹ˆλ‹€. λ°”λ‘œ μ‹œμž‘ν• κ²Œμš”~ Least Recently Used Cache Algorithmμ΄λž€? LRU μ•Œκ³ λ¦¬μ¦˜μ€ FIFO, LFU, MFU λ“±κ³Ό 같은 νŽ˜μ΄μ§€ ꡐ체 기법 쀑 ν•˜λ‚˜μΈλ°μš”. (νŽ˜μ΄μ§€ ꡐ체 기법에 λŒ€ν•œ 것은 μ—¬κΈ° μ—μ„œ 확인해 μ£Όμ„Έμš” γ…œ) κ·Έ μ€‘μ—μ„œλ„ κ°€μž₯ μ˜€λž«λ™μ•ˆ μ‚¬μš©ν•˜μ§€ μ•Šμ€ νŽ˜μ΄μ§€λ₯Ό κ΅μ²΄ν•˜λŠ” λ°©λ²•μž…λ‹ˆλ‹€. LRU Design LRU Cache μ•Œκ³ λ¦¬μ¦˜μ€ μ˜€λž«λ™μ•ˆ μ‚¬μš©ν•˜μ§€ μ•Šμ€ νŽ˜μ΄μ§€λ₯Ό μ‚­μ œν•΄ μ£Όκ³  μƒˆλ‘­κ²Œ μ‚¬μš©λœ νŽ˜μ΄μ§€λ₯Ό μΆ”κ°€ν•΄ μ€˜μ•Ό ν•©λ‹ˆλ‹€. μ‚­μ œμ™€ μΆ”κ°€λ₯Ό 효율적으둜 λΉ λ₯΄κ²Œ ν•˜λŠ” 것이 ν•΅μ‹¬μΈλ°μš”. 즉, O(1) μ‹œκ°„ λ³΅μž‘λ„λ‘œ ν•΄λ‹Ή κΈ°λŠ₯을 μˆ˜ν–‰ν•΄μ•Ό .. 2022. 9. 22.
[Algorithm] Floyd's Cycle Detectionμ΄λž€? (feat. Linked List) μ•ˆλ…•ν•˜μ„Έμš” Foma μž…λ‹ˆλ‹€! μš”μƒˆ LeetCodeμ—μ„œ Linked List의 사이클에 κ΄€λ ¨λœ 문제λ₯Ό ν‘ΈλŠ”λ° slow, fast 포인터λ₯Ό 많이 μ΄μš©ν•˜λ”λΌκ΅¬μš”. ν•΄λ‹Ή 풀이가 이해가 μ•ˆλΌμ„œ μ°Ύμ•„ λ³΄λ‹ˆ κ΄€λ ¨λœ μ•Œκ³ λ¦¬μ¦˜μ΄ μžˆμ—ˆκ³ , 그것이 Floyd's Cycle Detection μ΄μ—ˆμŠ΅λ‹ˆλ‹€. κ·Έλž˜μ„œ μ˜€λŠ˜μ€ λ§ν¬λ“œ λ¦¬μŠ€νŠΈμ—μ„œ 사이클이 μžˆλŠ”μ§€ μ—†λŠ”μ§€λ₯Ό 확인할 수 있고, ν•΄λ‹Ή μ‚¬μ΄ν΄μ˜ μ‹œμž‘μ μ΄ 어디인지 μ•Œμ•„λ‚Ό 수 μžˆλŠ” Floyd's Cycle Detection 에 λŒ€ν•΄μ„œ μ•Œμ•„λ³΄λ €κ³  ν•©λ‹ˆλ‹€. λ°”λ‘œ μ‹œμž‘ν• κ²Œμš”~ Floyd's Cycle Detection μ΄λž€? πŸ” Robert W. Floydκ°€ κ³ μ•ˆν•œ 리슀트의 사이클을 λΉ λ₯΄κ³  적은 λ©”λͺ¨λ¦¬λ‘œ μ°ΎλŠ” μ•Œκ³ λ¦¬μ¦˜μž…λ‹ˆλ‹€. (Robert W. FloydλŠ” ν”Œλ‘œμ΄λ“œ 와샬 μ•Œκ³ λ¦¬μ¦˜μ„ λ§Œλ“€.. 2022. 9. 18.
[Algorithm] μ†Œμˆ˜μ™€ κ΄€λ ¨λœ μ•Œκ³ λ¦¬μ¦˜(feat. μ—λΌν† μŠ€ ν…Œλ„€μŠ€μ˜ 체) μ•ˆλ…•ν•˜μ„Έμš” Foma πŸ’» μž…λ‹ˆλ‹€! μ•Œκ³ λ¦¬μ¦˜ 문제λ₯Ό ν’€λ‹€ 보면 μ†Œμˆ˜λ₯Ό 찾아햐 ν•˜λŠ” μœ ν˜•μ΄ λ§Žμ€λ°μš”. μ†Œμˆ˜μ˜ 갯수λ₯Ό μ°Ύμ•„μ•Ό ν•  λ•Œ, μ†Œμˆ˜μΈμ§€ μ•„λ‹Œμ§€ 뢄별해야 ν•  λ•Œ λ“± 효율적인 μ•Œκ³ λ¦¬μ¦˜μ΄ ν•„μš”ν•©λ‹ˆλ‹€. μ˜€λŠ˜μ€ μ •ν™•νžˆ μ•Œκ³  λΉ λ₯΄κ²Œ μ°ΎκΈ° μœ„ν•΄μ„œ 글을 정리해보렀고 ν•©λ‹ˆλ‹€. λ°”λ‘œ μ‹œμž‘ν• κ²Œμš”~! 기쑴의 μ†Œμˆ˜λ₯Ό μ°ΎλŠ” 방법 기쑴의 μ†Œμˆ˜λ₯Ό μ°ΎλŠ” 방법은 kλΌλŠ” μˆ˜κ°€ μžˆλ‹€λ©΄ λ‹¨μˆœν•˜κ²Œ 2λΆ€ν„° nκΉŒμ§€ k둜 λ‚˜λˆ μ„œ λ‚˜λˆ„μ–΄ λ–¨μ–΄μ§€λŠ” 숫자의 갯수λ₯Ό νŒλ³„ν•˜λ©΄ 되겠죠? ν•˜μ§€λ§Œ 이런 방법은 μˆ«μžκ°€ 컀지면 컀질수둝 λΉ„νš¨μœ¨μ μ΄κΈ° λ•Œλ¬Έμ— μ‹œκ°„μ΄ 였래 걸리게 λ©λ‹ˆλ‹€. κ·ΈλŸ¬λ―€λ‘œ 효율적인 방법을 μ‚¬μš©ν•΄μ•Ό ν•˜λŠ”λ°μš”. μ—λΌν† μŠ€ ν…Œλ„€μŠ€μ˜ 체 λ¨Όμ € 2λΆ€ν„° nκΉŒμ§€μ˜ κ΅¬κ°„μ—μ„œ μ†Œμˆ˜μ˜ κ°―μˆ˜λ‚˜, μ–΄λ–€ μ†Œμˆ˜κ°€ μžˆλŠ”μ§€ ν™•μΈν•˜κΈ° μœ„ν•΄μ„  "μ—λΌν† μŠ€ ν…Œλ„€μŠ€μ˜ 체"λ₯Ό μ•Œκ³ λ¦¬μ¦˜μ„.. 2022. 1. 19.
[Algorithm] 동적 κ³„νšλ²•(Dynamic Programming)μ΄λž€? μ•ˆλ…•ν•˜μ„Έμš” Foma πŸ’» μž…λ‹ˆλ‹€! κ·Έ λ™μ•ˆ μ•Œκ³ λ¦¬μ¦˜ 문제λ₯Ό ν’€λ©΄μ„œ 동적 κ³„νšλ²• κ΄€λ ¨λœ λ¬Έμ œκ°€ λ‚˜μ˜€λ©΄ 어렀움을 κ²ͺκ³€ ν–ˆλŠ”λ°μš”.. μ˜€λŠ˜μ€ 동적 κ³„νšλ²•μ— λŒ€ν•΄μ„œ μ œλŒ€λ‘œ 정리λ₯Ό 해보렀고 ν•©λ‹ˆλ‹€. λ°”λ‘œ μ‹œμž‘ν• κ²Œμš”! 동적 κ³„νšλ²•(Dynamic Programming)μ΄λž€? λ‹€μ΄λ‚˜λ―Ή ν”„λ‘œκ·Έλž˜λ°μ€ 1950λ…„λŒ€ 미ꡭ의 μˆ˜ν•™μžμΈ λ¦¬μ²˜λ“œ 벨맨이 μ΅œμ ν™” 문제(Optimization Problem)λ₯Ό ν•΄κ²°ν•˜κΈ° μœ„ν•΄μ„œ κ³ μ•ˆλ˜μ—ˆλ‹€. λ³΅μž‘ν•œ 문제λ₯Ό κ°„λ‹¨ν•œ μ—¬λŸ¬ 개의 문제둜 λ‚˜λˆ„μ–΄ ν‘ΈλŠ” 방법을 λ§ν•˜λ©° 이것은 λΆ€λΆ„ 문제 반볡과 졜적 λΆ€λΆ„ ꡬ쑰λ₯Ό 가지고 μžˆλŠ” μ•Œκ³ λ¦¬μ¦˜μ„ 일반적인 방법에 λΉ„ν•΄ λ”μš± 적은 μ‹œκ°„ 내에 ν’€ λ•Œ μ‚¬μš©ν•œλ‹€. - μœ„ν‚€ λ°±κ³Ό - 즉, λΆ„ν•  정볡 μ•Œκ³ λ¦¬μ¦˜κ³Ό 같이 큰 문제λ₯Ό μž‘κ²Œ μͺΌκ°œμ„œ 문제λ₯Ό ν•΄κ²°ν•΄ λ‚˜κ°€λŠ” μ•Œκ³ λ¦¬μ¦˜μž…λ‹ˆλ‹€. λ‹€.. 2021. 12. 9.
[Algorithm] 퀡 μ •λ ¬(Quick Sort)λž€? (feat. Swift) μ•ˆλ…•ν•˜μ„Έμš” Foma πŸ’» μž…λ‹ˆλ‹€! μ˜€λŠ˜μ€ λ“œλ””μ–΄ μ •λ ¬ μ•Œκ³ λ¦¬μ¦˜μ—μ„œ 말 κ·ΈλŒ€λ‘œ 맀우 λΉ λ₯Έ μˆ˜ν–‰μ‹œκ°„μ„ 가진 퀡 정렬에 λŒ€ν•΄μ„œ μ•Œμ•„λ³΄λ €κ³  ν•©λ‹ˆλ‹€! λ°”λ‘œ μ‹œμž‘ν• κ²Œμš”~ 퀡 μ •λ ¬(Quick Sort)μ΄λž€? 🧐 퀡 μ •λ ¬(Quicksort)은 찰슀 μ•€ν„°λ‹ˆ λ¦¬μ²˜λ“œ ν˜Έμ–΄κ°€ κ°œλ°œν•œ μ •λ ¬ μ•Œκ³ λ¦¬μ¦˜μ΄λ‹€. λ‹€λ₯Έ μ›μ†Œμ™€μ˜ λΉ„κ΅λ§ŒμœΌλ‘œ 정렬을 μˆ˜ν–‰ν•˜λŠ” 비ꡐ 정렬에 μ†ν•œλ‹€. - μœ„ν‚€ λ°±κ³Ό - (참고둜 λ¦¬μ²˜λ“œ ν˜Έμ–΄κ°€ 퀡 정렬을 κ°œλ°œν–ˆμ„ λ‹Ήμ‹œ λ‚˜μ΄λŠ” 26살이라고 ν•˜λ„€μš”...) 합병 μ •λ ¬κ³Ό 같이 λΆ„ν•  정볡 μ•Œκ³ λ¦¬μ¦˜μ— μ†ν•˜κ³  ν‰κ· μ μœΌλ‘œ 맀우 λΉ λ₯Έ μˆ˜ν–‰μ†λ„λ₯Ό μžλž‘ν•©λ‹ˆλ‹€. 퀡 μ •λ ¬ κ³Όμ • πŸ”¨ 퀡 정렬을 ν•˜κΈ° μœ„ν•΄μ„  피봇(Pivot)이 핡심이 λ˜λŠ”λ°μš”. μ—¬κΈ°μ„œ 피봇은 μ–΄λ–€ κ²ƒμΌκΉŒμš”? 피봇은 λ°”λ‘œ κΈ°μ€€μž…λ‹ˆλ‹€. 피봇을 κ°€μž₯ 첫 번째 인덱슀λ₯Ό 선택할 μˆ˜λ„ .. 2021. 10. 25.
[Algorithm] νž™ μ •λ ¬(HeapSort)μ΄λž€? (feat.Swift) μ•ˆλ…•ν•˜μ„Έμš” Foma πŸ’» μž…λ‹ˆλ‹€! μ €λ²ˆ μ‹œκ°„μ— νž™μ΄λž€ μžλ£Œκ΅¬μ‘°μ— λŒ€ν•΄μ„œ μ•Œμ•„λ³΄μ•˜λŠ”λ°μš”. (ν˜Ήμ‹œλΌλ„ μ•ˆλ³΄μ‹  뢄은 μ—¬κΈ° μ—μ„œ 보고 μ™€μ£Όμ„Έμš”!) μ˜€λŠ˜μ€ νž™μ„ μ΄μš©ν•΄μ„œ 정렬을 ν•˜λŠ” νž™μ†ŒνŠΈμ— λŒ€ν•΄μ„œ μ•Œμ•„λ³΄λ €κ³  ν•©λ‹ˆλ‹€! λ°”λ‘œ μ‹œμž‘ν• κ²Œμš”~ νž™ μ •λ ¬((HeapSort)μ΄λž€? 🧐 νž™ μ •λ ¬(Heap sort)μ΄λž€ μ΅œλŒ€ νž™ νŠΈλ¦¬λ‚˜ μ΅œμ†Œ νž™ 트리λ₯Ό ꡬ성해 정렬을 ν•˜λŠ” λ°©λ²•μœΌλ‘œμ„œ, λ‚΄λ¦Όμ°¨μˆœ 정렬을 μœ„ν•΄μ„œλŠ” μ΅œλŒ€ νž™μ„ κ΅¬μ„±ν•˜κ³  μ˜€λ¦„μ°¨μˆœ 정렬을 μœ„ν•΄μ„œλŠ” μ΅œμ†Œ νž™μ„ κ΅¬μ„±ν•˜λ©΄ λœλ‹€. - μœ„ν‚€ λ°±κ³Ό - 즉, νž™μ„ μ΄μš©ν•΄μ„œ 정렬을 ν•˜λŠ” λ°©μ‹μ΄μ—μš”. νž™ μ •λ ¬ κ³Όμ • πŸ”¨ νž™ μ •λ ¬ 과정은 νž™μ—μ„œ μ‚­μ œλ₯Ό κ΅¬ν˜„ν•  λ•Œμ™€ λ˜‘κ°™μ•„μš”. μ‚­μ œκ³Όμ •μ΄ μ•„λž˜μ™€ κ°™μ€λ°μš”. λͺ¨λ“  λ…Έλ“œλ₯Ό μ‚­μ œν•˜κ³  배열에 μ°¨λ‘€λ‘œ μŒ“κ²Œλ˜λ©΄ μ–΄λ–»κ²Œ λ κΉŒμš”? μ΅œλŒ€νž™μ΄λΌλ©΄ κ°€μž₯ 큰 μˆ«μžκ°€ μ°¨λ‘€.. 2021. 10. 19.
[Algorithm] 합병 μ •λ ¬(Merge Sort)λž€? (feat. Swift) μ•ˆλ…•ν•˜μ„Έμš” Foma πŸ’» μž…λ‹ˆλ‹€! μ˜€λŠ˜μ€ λΆ„ν•  정볡 μ•Œκ³ λ¦¬μ¦˜ 쀑 ν•˜λ‚˜μΈ 합병 정렬에 λŒ€ν•΄μ„œ μ•Œμ•„λ³΄λ €κ³  ν•©λ‹ˆλ‹€. λ°”λ‘œ μ‹œμž‘ν• κ²Œμš”~ λΆ„ν•  정볡(Divide and Conquer Algorithm) μ•Œκ³ λ¦¬μ¦˜μ΄λž€? 🏑 μœ„μ—μ„œ 합병 정렬은 λΆ„ν•  정볡 μ•Œκ³ λ¦¬μ¦˜ 쀑 ν•˜λ‚˜λΌκ³  λ§μ”€λ“œλ ΈλŠ”λ°μš”. κ·Έλ ‡λ‹€λ©΄ λΆ„ν•  정볡 μ•Œκ³ λ¦¬μ¦˜μ€ λ¬΄μ—‡μΌκΉŒμš”? 말 κ·ΈλŒ€λ‘œ μ§€κΈˆ ν•΄κ²°ν•  수 μ—†λŠ” 문제λ₯Ό μž‘κ²Œ μͺΌκ°œμ„œ(λΆ„ν• ) ν’€μ–΄λ‚˜κ°€λŠ”(정볡) κ²ƒμž…λ‹ˆλ‹€. μž‘μ€ 문제λ₯Ό ν•΄κ²°ν•˜μ—¬ 큰 문제λ₯Ό ν•΄κ²°ν•΄λ‚˜κ°€λŠ” μ•Œκ³ λ¦¬μ¦˜μœΌλ‘œ μž¬κ·€ ν•¨μˆ˜λ₯Ό 톡해 μžμ—°μŠ€λŸ½κ²Œ κ΅¬ν˜„ν•  수 μžˆμŠ΅λ‹ˆλ‹€. 합병 μ •λ ¬μ΄λž€? 🀼‍♀️ 합병 μ •λ ¬ λ˜λŠ” 병합 정렬은 비ꡐ 기반 μ •λ ¬ μ•Œκ³ λ¦¬μ¦˜μ΄λ‹€. 일반적인 λ°©λ²•μœΌλ‘œ κ΅¬ν˜„ν–ˆμ„ λ•Œ 이 정렬은 μ•ˆμ • 정렬에 μ†ν•˜λ©°, λΆ„ν•  정볡 μ•Œκ³ λ¦¬μ¦˜μ˜ ν•˜λ‚˜μ΄λ‹€. μ‘΄ 폰 λ…Έμ΄λ§Œμ΄ 1.. 2021. 10. 14.
[Algorithm] μ‹œκ°„λ³΅μž‘λ„(Time-Complexity)λž€? (feat. Big O) μ•ˆλ…•ν•˜μ„Έμš” Foma πŸ’» μž…λ‹ˆλ‹€! μš”μ¦˜ λ“€μ–΄ μ•Œκ³ λ¦¬μ¦˜ 곡뢀λ₯Ό ν•˜λŠ”λ° μ•Œκ³ λ¦¬μ¦˜μ˜ 핡심인 μ‹œκ°„λ³΅μž‘λ„μ— λŒ€ν•΄μ„œ μ •λ¦¬ν•˜μ§€ μ•Šμ€ 것 κ°™μ•„μ„œ.. 이번 κΈ°νšŒμ— ꡬ체적으둜 μ‹œκ°„λ³΅μž‘λ„μ— λŒ€ν•΄μ„œ μ •λ¦¬ν•΄λ³΄κ² μŠ΅λ‹ˆλ‹€! λ°”λ‘œ μ‹œμž‘ν• κ²Œμš”~ μ‹œκ°„λ³΅μž‘λ„λž€? ⏱ 컴퓨터곡학 μš©μ–΄λ‘œ, 컴퓨터 ν”„λ‘œκ·Έλž¨μ˜ μž…λ ₯κ°’κ³Ό μ—°μ‚° μˆ˜ν–‰ μ‹œκ°„μ˜ 상관관계λ₯Ό λ‚˜νƒ€λ‚΄λŠ” 척도이닀. 일반적으둜 μ‹œκ°„ λ³΅μž‘λ„λŠ” 점근 ν‘œκΈ°λ²•μ„ μ΄μš©ν•˜μ—¬ λ‚˜νƒ€λ‚Έλ‹€. 즉, κ³„μ‚°λ˜λŠ” 양에 λ”°λΌμ„œ μ‹œκ°„μ΄ μ–Όλ§ˆλ‚˜ 걸릴지λ₯Ό λ‚˜νƒ€λ‚΄λŠ” κ²ƒμž…λ‹ˆλ‹€. μ‹œκ°„λ³΅μž‘λ„ ν‘œκΈ°λ²• πŸ–Š μ‹œκ°„λ³΅μž‘λ„ ν‘œκΈ°λ²•μ€ λΉ…μ˜€λ©”κ°€,빅세타,λΉ…μ˜€ μ΄λ ‡κ²Œ 3가지가 μžˆμŠ΅λ‹ˆλ‹€. 1. BigΩ (Best case) λΉ…μ˜€λ©”κ°€ ν‘œκΈ°λ²•μ€ μ΅œμ„ μ˜ μ‹€ν–‰μ‹œκ°„ 즉, κ°€μž₯ λΉ λ₯Έ μΌ€μ΄μŠ€λ₯Ό λ‚˜νƒ€λ‚΄λŠ” κ²ƒμž…λ‹ˆλ‹€. 2. Big𝚯 (Average case) 빅세타 ν‘œκΈ°λ²•μ€.. 2021. 9. 29.
[Algorithm] μ‚½μž… μ •λ ¬(Insertion Sort) μ΄λž€? (feat.Swift) μ•ˆλ…•ν•˜μ„Έμš” FomaπŸ’» μž…λ‹ˆλ‹€! μ˜€λŠ˜μ€ 학ꡐ μ•Œκ³ λ¦¬μ¦˜ μˆ˜μ—…μ„ λ“£λŠ” 쀑에 μ‚½μž… 정렬을 κ΅¬ν˜„ν•΄λ³΄λŠ” κ³Όμ œκ°€ μžˆμ—ˆλŠ”λ°... λ”± 이 방식이 μ–΄λ–€ 것이고 μ–΄λ–»κ²Œ κ΅¬ν˜„ν•΄μ•Ό ν•œλ‹€! 라고 ꡬ체적으둜 λ– μ˜€λ₯΄μ§€κ°€ μ•Šλ”λΌκ΅¬μš”... κ·Έλž˜μ„œ μ‚½μž… 정렬이 무엇이고 μ–΄λ–»κ²Œ κ΅¬ν˜„ν•΄μ•Ό ν•˜λŠ”μ§€μ— λŒ€ν•΄ 정리해보렀고 ν•©λ‹ˆλ‹€! λ°”λ‘œ μ‹œμž‘ν• κ²Œμš”~ μ‚½μž… μ •λ ¬μ΄λž€? μ‚½μž… 정렬은 자료 λ°°μ—΄μ˜ λͺ¨λ“  μš”μ†Œλ₯Ό μ•žμ—μ„œλΆ€ν„° μ°¨λ‘€λŒ€λ‘œ 이미 μ •λ ¬λœ λ°°μ—΄ λΆ€λΆ„κ³Ό λΉ„κ΅ν•˜μ—¬, μžμ‹ μ˜ μœ„μΉ˜λ₯Ό μ°Ύμ•„ μ‚½μž…ν•¨μœΌλ‘œμ¨ 정렬을 μ™„μ„±ν•˜λŠ” μ•Œκ³ λ¦¬μ¦˜μ΄λ‹€. -μœ„ν‚€ λ°±κ³Ό - μ •λ ¬ν•˜λŠ” 과정을 μ‚΄νŽ΄λ³΄λ©΄ μ•„λž˜μ™€ κ°™μŠ΅λ‹ˆλ‹€. μ‚½μž… μ •λ ¬ κ³Όμ • 82,10,9,72,31,45,60λ₯Ό μ‚½μž… 정렬을 ν•˜λŠ” 과정은 μ•„λž˜μ™€ κ°™μŠ΅λ‹ˆλ‹€. 1. λ¨Όμ € 맨 첫 번째인 82와 κ·Έ λ‹€μŒ 숫자인 10을 λΉ„κ΅ν•΄μ€λ‹ˆλ‹€. 10이 더.. 2021. 9. 28.
[Algorithm] λ°±νŠΈλž˜ν‚Ή(Backtracking)μ΄λž€? (feat. μ˜ˆμ œν¬ν•¨) μ•ˆλ…•ν•˜μ„Έμš” Foma πŸ’» μž…λ‹ˆλ‹€! μ˜€λŠ˜μ€ ν”„λ‘œκ·Έλž˜λ¨ΈμŠ€ N-Queen 문제λ₯Ό ν’€λ©΄μ„œ ν•΄λ‹Ή λ¬Έμ œκ°€ λ°±νŠΈλž˜ν‚Ή λ¬Έμ œλΌλŠ” 것을 μ•Œκ²Œ λ˜μ—ˆλŠ”λ°μš”. κ·Έλž˜μ„œ λ°±νŠΈλž˜ν‚Ήμ΄ 무엇이고 μ–΄λ–»κ²Œ κ΅¬ν˜„ν•΄μ„œ μ‚¬μš©ν•΄μ•Ό ν•˜λŠ”μ§€μ— λŒ€ν•΄ 정리해보렀고 ν•©λ‹ˆλ‹€. λ°”λ‘œ μ‹œμž‘ν• κ²Œμš”~ λ°±νŠΈλž˜ν‚Ήμ΄λž€? λͺ¨λ“  경우의 수λ₯Ό μ „λΆ€ κ³ λ €ν•˜λŠ” μ•Œκ³ λ¦¬μ¦˜ μƒνƒœκ³΅κ°„μ„ 트리둜 λ‚˜νƒ€λ‚Ό 수 μžˆμ„ λ•Œ μ ν•©ν•œ 방식이닀. μΌμ’…μ˜ 트리 탐색 μ•Œκ³ λ¦¬μ¦˜μ΄λΌκ³  봐도 λœλ‹€. 방식에 λ”°λΌμ„œ κΉŠμ΄μš°μ„ νƒμƒ‰(Depth First Search, DFS)κ³Ό λ„ˆλΉ„μš°μ„ νƒμƒ‰(Breadth First Search, BFS), μ΅œμ„  μš°μ„  탐색(Best First Search/HeuristicSearch)이 μžˆλ‹€. λͺ¨λ“  경우의 수λ₯Ό κ³ λ €ν•΄μ•Ό ν•˜λŠ” 문제라면, DFSκ°€ λ‚«λ‹€. BFSλ‘œλ„ κ΅¬ν˜„μ΄ λ¬Όλ‘  κ°€λŠ₯ν•˜μ§€λ§Œ,.. 2021. 8. 28.
[Algorithm] μ‘°ν•©(Combination)μ΄λž€? (feat.Swift) μ•ˆλ…•ν•˜μ„Έμš” Foma πŸ‘Ÿ μž…λ‹ˆλ‹€! μ˜€λŠ˜μ€ μ•Œκ³ λ¦¬μ¦˜ λ¬Έμ œμ—μ„œ 정말 λΉˆλ²ˆν•˜κ²Œ μ‚¬μš©λ˜λŠ” "μ‘°ν•©" 에 λŒ€ν•΄μ„œ μ•Œμ•„λ³΄λ„λ‘ ν•˜κ² μŠ΅λ‹ˆλ‹€. λ°”λ‘œ μ‹œμž‘ν• κ²Œμš”~ μ‘°ν•©μ΄λž€? n개의 μ›μ†Œμ—μ„œ r 개의 μ›μ†Œλ₯Ό μˆœμ„œμ— 상관없이 λ½‘λŠ” 경우의 수 - λ‚˜λ¬΄ μœ„ν‚€ - μˆœμ—΄κ³Ό λ‹€λ₯΄κ²Œ μˆœμ„œλŠ” μ€‘μš”ν•˜μ§€ μ•Šμ•„μš”. μ‰½κ²Œ μ„€λͺ…ν•˜λ©΄ 물건을 사고 총 가격을 κ΅¬ν•˜λŠ” 것과 λΉ„μŠ·ν•΄μš”. 과일둜 예λ₯Ό λ“€λ©΄ 사과,포도,μˆ˜λ°•μ΄ μžˆλ‹€λ©΄ 사과,포도,μˆ˜λ°• 포도,사과,μˆ˜λ°• μˆ˜λ°•,사과,포도 ... λ“± μ–΄λ–€ λ°©μ‹μœΌλ‘œ 사도 총 가격을 λ˜‘κ°™κ² μ£ ? 즉, 이루어진 과일이 λ˜‘κ°™λ‹€λ©΄ ν•˜λ‚˜μ˜ μ‘°ν•©μœΌλ‘œ μƒκ°ν•˜λŠ” κ²ƒμž…λ‹ˆλ‹€. μ½”λ“œ κ΅¬ν˜„ λ¨Όμ € 경우의 수λ₯Ό 담을 배열을 λ§Œλ“€μ–΄μ€λ‹ˆλ‹€. var cases:[[Int]] = [] combination의 νŒŒλΌλ―Έν„°λ₯Ό μ„€μ •ν•΄μ£ΌλŠ”λ° μΈλ±μŠ€λ“€μ„ λ‹΄κ³ μžˆλŠ” ind.. 2021. 6. 27.
[Algorithm] μˆœμ—΄(Permutation)μ΄λž€? (feat.Swift) μ•ˆλ…•ν•˜μ„Έμš” Foma πŸ‘Ÿ μž…λ‹ˆλ‹€! μ˜€λŠ˜μ€ μ•Œκ³ λ¦¬μ¦˜ λ¬Έμ œμ—μ„œ 정말 λΉˆλ²ˆν•˜κ²Œ μ‚¬μš©λ˜λŠ” "μˆœμ—΄"에 λŒ€ν•΄μ„œ μ•Œμ•„λ³΄λ„λ‘ ν•˜κ² μŠ΅λ‹ˆλ‹€. λ°”λ‘œ μ‹œμž‘ν• κ²Œμš”! μˆœμ—΄μ΄λž€? μ„œλ‘œ λ‹€λ₯Έ n개의 μ›μ†Œμ—μ„œ r개λ₯Ό 쀑볡없이 골라 μˆœμ„œμ— μƒκ΄€μžˆκ²Œ λ‚˜μ—΄ν•˜λŠ” 것을 이λ₯Έλ‹€. - λ‚˜λ¬΄ μœ„ν‚€ - μ‰½κ²Œ μ„€λͺ…ν•˜λ©΄ 쀄 μ„Έμš°κΈ°μ™€ λ˜‘κ°™μ•„μš”. A,B,CλΌλŠ” 학생을 쀄 μ„Έμš°λŠ” 방법은 ABC,ACB,BAC,BCA,CAB,CBA 등이 있겠죠? 이 μ€‘μ—μ„œ 2λͺ…μ˜ ν•™μƒμœΌλ‘œ 쀄 μ„Έμš°λŠ” 방법은 AB,AC,BA,BC,CA,CB 등이 μžˆμ„κ±°μ—μš”. μ½”λ“œ κ΅¬ν˜„ 경우의 μˆ˜λ“€μ„ 담을 이쀑 배열을 λ§Œλ“€μ–΄μ€λ‹ˆλ‹€. var cases:[[Int]] = [] λͺ‡ 개λ₯Ό 뽑을지 μ •ν•΄μ€λ‹ˆλ‹€. let pickCount = 3 본격적으둜 μˆœμ—΄ ν•¨μˆ˜λ₯Ό λ§Œλ“€μ–΄μ€λ‹ˆλ‹€. νŒŒλΌλ―Έν„°λ‘œλŠ” 전체 μΈλ±μŠ€κ°€ λ‹΄κΈ΄.. 2021. 6. 27.
728x90
λ°˜μ‘ν˜•