Home > Archive > DataStructure > πŸ“¦[DataStructure] 문제 μ •μ˜μ™€ μ„ ν˜• μŠ€μΊ”

πŸ“¦[DataStructure] 문제 μ •μ˜μ™€ μ„ ν˜• μŠ€μΊ”
DataStructure

문제 μ •μ˜.

μƒˆλ‘œμš΄ μ•Œκ³ λ¦¬μ¦˜μ„ μ •μ˜ν•˜κΈ° 전에, 항상 κ·Έ μ•Œκ³ λ¦¬μ¦˜μ΄ ν•΄κ²°ν•˜λ €λŠ” 문제λ₯Ό μ •μ˜ν•΄μ•Ό ν•©λ‹ˆλ‹€.

μ—¬κΈ°μ„œλŠ” λ¦¬μŠ€νŠΈμ—μ„œ 주어진 λͺ©ν‘―κ°’κ³Ό μΌμΉ˜ν•˜λŠ” μ›μ†Œλ₯Ό ν•˜λ‚˜ 찾을 수 μžˆλŠ” 효율적인 μ•Œκ³ λ¦¬μ¦˜μ„ λ§Œλ“€λ €κ³  ν•©λ‹ˆλ‹€.

이 탐색 문제λ₯Ό ν˜•μ‹μ μœΌλ‘œ μ •μ˜ν•˜λ©΄ λ‹€μŒκ³Ό κ°™μŠ΅λ‹ˆλ‹€.

μΌμƒμƒν™œμ—μ„œλŠ” μ΄λŸ¬ν•œ μž‘μ—…μ„ β€˜μ–΄λ–€ 것을 μ°Ύμ•„μ€˜β€™ 라고 ν‘œν˜„ν•©λ‹ˆλ‹€.

  • 이 탐색 λ¬Έμ œλŠ” μš°λ¦¬κ°€ ν•˜λ£¨μ—λ„ λͺ‡ λ²ˆμ”© μ§λ©΄ν•˜λŠ” λ¬Έμ œμž…λ‹ˆλ‹€.
    • μ‚¬μ „μ—μ„œ 단어λ₯Ό μ°Ύκ±°λ‚˜ μ—°λ½μ²˜ λͺ©λ‘μ—μ„œ 이름을 μ°Ύκ±°λ‚˜ 역사적 사건 λͺ©λ‘μ—μ„œ νŠΉμ • λ‚ μ§œλ₯Ό μ°Ύκ±°λ‚˜ μƒν’ˆμœΌλ‘œ 꽉 μ°¬ μŠˆνΌλ§ˆμΌ“ μ„ λ°˜μ—μ„œ μ’‹μ•„ν•˜λŠ” 컀피 λΈŒλžœλ“œλ₯Ό μ°ΎλŠ” 경우 등이 μžˆμŠ΅λ‹ˆλ‹€.
      • μš°λ¦¬μ—κ²ŒλŠ” λŒ€μƒ λͺ©λ‘κ³Ό λͺ©ν‘―κ°’μ˜ 일치 μ—¬λΆ€λ₯Ό 확인할 수 μžˆλŠ” 방법이 ν•„μš”ν•©λ‹ˆλ‹€.

μ„ ν˜• μŠ€μΊ”

이진 μ°Έμƒ‰μ˜ 이점을 μ΄ν•΄ν•˜κΈ° μœ„ν•΄ 비ꡐ λŒ€μƒμ„ μ œκ³΅ν•˜κ² μŠ΅λ‹ˆλ‹€.

더 κ°„λ‹¨ν•œ μ•Œκ³ λ¦¬μ¦˜μ€ μ„ ν˜• μŠ€μΊ”(linear scan) λΆ€ν„° μ‚΄νŽ΄λ΄…μ‹œλ‹€.

  • μ„ ν˜• μŠ€μΊ”μ€ λ¦¬μŠ€νŠΈμ—μ„œ ν•œ λ²ˆμ— ν•˜λ‚˜μ”© 값을 λͺ©ν‘―값을 μ°Ύκ±°λ‚˜ λͺ©λ‘μ˜ 끝에 도달할 λ•ŒκΉŒμ§€ 비ꡐ해 λͺ©ν‘―값을 μ°ΎμŠ΅λ‹ˆλ‹€.

수둜 이뀄진 λ°°μ—΄ Aμ—μ„œ λͺ©ν‘―값을 찾으렀 ν•œλ‹€κ³  κ°€μ •ν•΄λ΄…μ‹œλ‹€.

  • 이 경우 target = 21을 μ‚¬μš©ν•©λ‹ˆλ‹€.
    • λ°°μ—΄μ˜ 각 μƒμž μ•ˆμ— λ“  값이 21κ³Ό 같은지 λ°˜λ³΅ν•΄μ„œ ν™•μΈν•©λ‹ˆλ‹€.
      • 이 과정이 μ•„λž˜μ˜ 그림에 λ¬˜μ‚¬λ˜μ–΄ μžˆμŠ΅λ‹ˆλ‹€.

LinearScan(Array: A, Integer: target):
    Integer: i = 0
    WHILE i < length(A):
        IF A[i] == target:
            return i
                i = i + 1
            return -1

μœ„ μ½”λ“œλŠ” μ„ ν˜• μŠ€μΊ” μ½”λ“œλ₯Ό λ³΄μ—¬μ€λ‹ˆλ‹€.

  • 이 μ½”λ“œλŠ” μΌμΉ˜ν•˜λŠ” μ›μ†Œμ˜ 인덱슀λ₯Ό λ°˜ν™˜ν•˜κ³  탐색에 μ‹€νŒ¨ν•˜λ©΄ μ›μ†Œκ°€ μ—†μœΌλ―€λ‘œ -1을 인덱슀둜 λ°˜ν™˜ν•©λ‹ˆλ‹€.
    • 단일 WHILE λ£¨ν”„λŠ” λ°°μ—΄μ˜ 각 μ›μ†Œλ₯Ό λ°˜λ³΅ν•˜κ³ , λ‚΄λΆ€ IF 문은 μΈλ±μŠ€μ— ν•΄λ‹Ήν•˜λŠ” μ›μ†Œλ₯Ό λͺ©ν‘―κ°’κ³Ό λΉ„κ΅ν•©λ‹ˆλ‹€.
      • λͺ©ν‘―값을 찾은 경우 μ¦‰μ‹œ ν•΄λ‹Ή 인덱슀λ₯Ό λ°˜ν™˜ν•©λ‹ˆλ‹€.
        • λ°°μ—΄μ˜ λκΉŒμ§€ ν™•μΈν•œ 경우 -1을 λ°˜ν™˜ν•©λ‹ˆλ‹€.

μ„ ν˜• μŠ€μΊ”μ€ λ©‹μ§€κ±°λ‚˜ λ˜‘λ˜‘ν•˜μ§€ μ•ŠμŠ΅λ‹ˆλ‹€.

λͺ©ν‘œκ°€ 데이터에 μžˆλŠ”μ§€ μ°ΎκΈ° μœ„ν•΄ κ°€λŠ₯ν•œ ν•­λͺ©μ„ λͺ¨λ‘ ν™•μΈν•˜κΈ° λ•Œλ¬Έμ— β€˜λ¬΄μ‹ν•œ κ²€μ‚¬β€™μž…λ‹ˆλ‹€.

  • 특히 μ›μ†Œκ°€ μ•„μ£Ό λ§Žμ€ λ¦¬μŠ€νŠΈμ—μ„œ λΉ„νš¨μœ¨μ μž…λ‹ˆλ‹€.

A의 자료 ꡬ쑰에 λŒ€ν•΄ 아무것도 λͺ¨λ₯΄λ©΄ ν”„λ‘œμ„ΈμŠ€λ₯Ό μ΅œμ ν™”ν•  수 μžˆλŠ” 방법이 μ—†μŠ΅λ‹ˆλ‹€.

  • λͺ©ν‘―값이 λͺ¨λ“  μƒμžμ— μžˆμ„ 수 μžˆμœΌλ―€λ‘œ λͺ¨λ“  μƒμžλ₯Ό 확인해야 ν•  μˆ˜λ„ μžˆμŠ΅λ‹ˆλ‹€.

μ„ ν˜• μŠ€μΊ”μ˜ ν•œκ³„λ₯Ό 보여주기 μœ„ν•΄, ꡐ싀 λ°”κΉ₯에 쀄 μ„œ μžˆλŠ” 기초 ν”„λ‘œκ·Έλž˜λ° κ³Όλͺ©μ„ λ“£λŠ” 학생듀 같은 물리적인 μ‹œν€€μŠ€μ—μ„œ μ΄λŸ¬ν•œ 탐색을 μˆ˜ν–‰ν•œλ‹€κ³  μƒμƒν•΄λ³΄μž.

  • νŠΉμ • ν•™μƒμ˜ μˆ™μ œλ₯Ό λ°˜ν™˜ν•˜λ €λŠ” κ΅μ‚¬λŠ” 각 ν•™μƒμ—κ²Œ β€œμ΄λ¦„μ΄ μ œλ ˆλ―Έμž…λ‹ˆκΉŒ?” 라고 묻고 λ‹€μŒ ν•™μƒμœΌλ‘œ 이동할 수 μžˆμŠ΅λ‹ˆλ‹€.
    • ꡐ사가 μ˜¬λ°”λ₯Έ 학생을 μ°Ύκ±°λ‚˜ 쀄 λκΉŒμ§€ μ΄λ™ν•˜λ©΄ 탐색이 μ€‘μ§€λ©λ‹ˆλ‹€.
      • 학생듀은 ꡐ사가 λΉ„νš¨μœ¨μ μ΄λΌκ³  μƒκ°ν•˜λ©΄μ„œ κΆμ‹œλ λ  것 μž…λ‹ˆλ‹€.

λ•Œλ‘œ μ„ ν˜• νƒμƒ‰μ—μ„œ 각각의 비ꡐλ₯Ό 더 빨리 ν•  수 μžˆλŠ” 방법이 μžˆλŠ” κ²½μš°κ°€ 가끔 μžˆμŠ΅λ‹ˆλ‹€.

  • 예λ₯Ό λ“€μ–΄, λ³΅μž‘ν•œ 데이터가 λ¬Έμžμ—΄μΌ λ•ŒλŠ” μ•žμ„œ 올린 ν¬μŠ€νŒ…μ—μ„œ μ„€λͺ…ν•œ κ²ƒμ²˜λŸΌ 졜초둜 μΌμΉ˜ν•˜μ§€ μ•ŠλŠ” κΈ€μžμ—μ„œ 비ꡐλ₯Ό 멈좀으둜써 비ꡐ에 κ±Έλ¦¬λŠ” μ‹œκ°„μ„ μ΅œμ ν™”ν•  수 μžˆμŠ΅λ‹ˆλ‹€.
    • κ·ΈλŸ¬λ‚˜ 이런 μ΅œμ ν™”μ—λ„ ν•œκ³„κ°€ μžˆμŠ΅λ‹ˆλ‹€.
      • μ—¬μ „νžˆ λͺ¨λ“  μ›μ†Œλ₯Ό ν•˜λ‚˜μ”© 확인해야 ν•˜κΈ° λ•Œλ¬Έμž…λ‹ˆλ‹€.