📦[DataStructure] 변수와 배열이 중요한 이유와 이진 탐색

변수와 배열이 중요한 이유. 변수와 배열은 초급 프로그래밍 수업의 필수 요소이며, 그래서 재미없어 보일 수 있지만 컴퓨터 프로그래밍과 자료 구조의 근간을 제공하기 때문에 꼭 탐구해야 할 중요한 개념입니다. 또 이런 개념은 알고리즘에 미치는 동적 자료 구조의 영향을 평가하는 기준을 제공합니다. 이진 탐색(binary search). 이진 탐색(binary search) 은 정렬된 리스트에서 특정 값을 빠르게 찾는 알고리즘입니다. 이 알고리즘은 리스트를 반으로 나워서 목푯값이 어느 쪽 절반에 속하는지 결정하고, 나머지 절반은 버리면서 목푯값이 포함될 가능성이 있는 절반을 탐색하는 방식으로 동작합니다. 이 알고리즘의 구현 방법과 논리적 간결성은 컴퓨터 과학 입문 과목에 적합하기 때문에 거의 모든 컴퓨터 과학 교과서와 강의에서 이진 탐색 알고리즘을 다룹니다. “정렬된 리스트에서 탐색하는 일이 얼마나 자주 있을까?” 혹은 더 구체적으로 “내 정렬된 리스트에서 탐색 함수를 직접 구현할 일이 얼마나 자주 있을까? 이미 수백만 명이 이 짓을 하지 않았나? 라이브러리에 있지 않은가?” 라고 생각할 수도 있습니다. 하지만 언젠가 자신만의 이진 탐색이 필요할 가능성을 배제헤서는 안 되며, 이진 탐색의 진정한 중요성은 단순히 이진 탐색을 구현하는 일을 넘어섭니다. 이진 탐색은 똑똑한 알고리즘이 정렬된 데이터처럼 아주 단순한 자료 주고에서 조차 데이터가 저장되어 있는 구조를 활용해 상당한 계산 비용을 절약할 수 있음을 보여주는 예입니다. 이진 탐색은 정확성과 효율성을 쉽게 분석할 수 있고 속도와 정확성 모두를 보장하며 데이터와 알고리즘의 상호 작용을 잘 보여줍니다. 그렇기 때문에 이진 탐색은 연결 리스트, 배열, 그 외의 여러 트리 기반 알고리즘과 같은 데이터 저장 기법들의 차이점을 살펴보는 훌륭한 렌즈가 될 수 있습니다.

Archive · 2024-04-23

📦[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의 자료 구조에 대해 아무것도 모르면 프로세스를 최적화할 수 있는 방법이 없습니다. 목푯값이 모든 상자에 있을 수 있으므로 모든 상자를 확인해야 할 수도 있습니다. 선형 스캔의 한계를 보여주기 위해, 교실 바깥에 줄 서 있는 기초 프로그래밍 과목을 듣는 학생들 같은 물리적인 시퀀스에서 이러한 탐색을 수행한다고 상상해보자. 특정 학생의 숙제를 반환하려는 교사는 각 학생에게 “이름이 제레미입니까?” 라고 묻고 다음 학생으로 이동할 수 있습니다. 교사가 올바른 학생을 찾거나 줄 끝까지 이동하면 탐색이 중지됩니다. 학생들은 교사가 비효율적이라고 생각하면서 궁시렁될 것 입니다. 때로 선형 탐색에서 각각의 비교를 더 빨리 할 수 있는 방법이 있는 경우가 가끔 있습니다. 예를 들어, 복잡한 데이터가 문자열일 때는 앞서 올린 포스팅에서 설명한 것처럼 최초로 일치하지 않는 글자에서 비교를 멈춤으로써 비교에 걸리는 시간을 최적화할 수 있습니다. 그러나 이런 최적화에도 한계가 있습니다. 여전히 모든 원소를 하나씩 확인해야 하기 때문입니다.

Archive · 2024-04-23

📦[DataStructure] 삽입 정렬

삽입 정렬. 배열 구조를 어떻게 사용할 수 있는지 이해하는 가장 좋은 방법은 실제 알고리즘을 검토하는 것입니다. 삽입 정렬(insertion sort) 은 배열의 값을 정렬하는 알고리즘으로, 순서를 정할 수 있는 모든 유형의 값에서 작동합니다. 정수, 문자열, 심지어 유통기한에 따라 저장된 창고 안 커피까지 삽입 정렬로 정렬할 수 있습니다. 삽입 정렬은 배열의 일부를 정렬하고, 이 정렬된 범위를 전체 배열이 정렬될 때까지 확장합니다. 알고리즘은 정렬되지 않은 배열의 각 원소를 반복하면서 정렬된 부분의 올바른 위치로 이동합니다. i의 반복을 시작하는 시점에 i-1 이하의 위치에 있는 원소는 모두 정렬되 있습니다. 알고리즘은 이제 인덱스 i에 있는 원소를 선택하고, 정렬된 접두사에서 이 원소의 올바른 위치를 찾아 나머지 원소를 뒤로 이동시켜서 선택한 원소가 들어갈 공간을 만든 수 삽입합니다. 그러면 정렬된 접두사가 하나 더 커지면서 0에서 i까지 모든 상자가 정렬된 상태가 됩니다. 처음에는 첫 번째 원소를 초기 정렬된 접두사로 선언하고 i = 1부터 반복을 시작할 수 있습니다. 커피 컬렉션을 신선도순으로 정렬하고 싶다고 합시다. 무엇보다 프리미엄 커피가 창고 깊숙이 박혀 있다 상해버리는 비극은 바람직하지 않습니다. 따라서 유통기한이 제일 짧게 남은 커피를 가장 앞쪽에 넣어서 쉽게 접근할 수 있게 해야합니다. 우선 커피백 하나를 정렬된 부분으로 선언하고, 이를 기준으로 정렬 범위를 설정함으로써 커피 정렬을 시작합니다. 그 다음에는 가장 앞쪽에서 두 번째 백부터 날짜를 비교해 정렬된 부분의 백보다 더 앞에 넣어야 할지를 판단합니다. 위치를 바꿀 필요가 있는 경우엔 순서를 바꾸고, 그렇지 않은 경우엔 자리를 유지합니다. 이제 자신 있게 맨 앞의 두 백이 정렬됐다고 말할 수 있습니다. 이렇게 부분적으로 정렬하는 과정을 마지막 백까지 진행하면서 위치를 바꾸는 작업을 반복하면, 커피 컬렉션을 완벽하게 정리할 수 있습니다. 아래 코드와 같이 중첩된 루프를 이용해 삽입 정렬을 구현할 수 있습니다. InsertionSort(array: A): Integer: N = length(A) Integer: i = 1 WHILE i < N: // 1 Type: current = A[i] Integer: j = i - 1 WHILE j >= 0 AND A[j] > current: // 2 A[j + 1] = A[j] j = j - 1 A[j + 1] = current i = i +1 바깥쪽 루프는 최초의 정렬되지 않은 원소인 인덱스 i가 1인 원소부터 시작하고 정렬되지 않은 범위에 있는 각 값을 반복합니다(1) 안쪽 루프는 인덱스 j를 사용해 정렬된 접두사의 원소를 맨 뒤에서부터 하나씩 반복합니다(2) 반복 각 단계에서 현재 값과 정렬된 접두사 안에 있는 인덱스 j의 값을 비교해 확인합니다. j에 있는 원소가 더 크면 두 값의 순서가 잘못됐으므로 교환해야 합니다. 현재 값을 별도의 변수인 current에 저장했기 때문에 이전 상자에서 데이터를 직접 복사합니다. 즉, i번째와 j번째의 값을 완전히 교환할 필요가 없습니다. 내부 루프는 현재 값을 배열의 맨 앞에 밀어넣거나 현재 값보다 이전 값이 더 작을 때까지만(이 경우가 바로 현재 값이 정렬된 접두사의 올바른 위치에 있음을 나타냅니다.) 계속 진행합니다. 이제 내부 루프의 끝에서 현재 값을 올바른 위치에 쓰기만 하면 됩니다. 바깥쪽 루프는 다음 정렬되지 않은 값으로 진행합니다. 아래 그림은 알고리즘이 어떻게 동작하는지 시각화해 보여줍니다. 각 줄은 반복 시작 시 배열의 상태를 보여줍니다. 빨간색 상자는 현재 위치에 있는 원소를 나타내며, 화살표는 현재 위치의 원소를 삽입하면서 발생하는 이동을 나타냅니다. 삽입 정렬은 그렇게 효율적이지 않습니다. 배열에 원소를 삽입할 때, 상당 부분을 이동해야 할 수도 있습니다. 최악의 경우(worst-case), 알고리즘의 비용은 시퀀스 원소 수의 제곱에 비례합니다. 즉, 최악의 경우 리스트의 모든 원소마다 앞의 모든 원소를 이동해야합니다. 배열의 크기를 2배로 늘리면, 최악의 경우 비용이 4배 증가합니다. 그럼에도 불구하고 삽입 정렬은 배열이 어떻게 작동하는지 중요한 통찰을 제공합니다. 이 간단한 알고리즘은 인덱스를 사용해 원소레 직접 접근할 수 있어야 하며, 새 원소를 삽입할 때 값을 교환할 수 있어야 하며, 모든 원소를 반복(iteration)할 수 있어야 한다는 배열의 여러 특성을 보여줍니다.

Archive · 2024-04-22

📦[DataStructure] 문자열

문자열(String) 은 종종 특수한 종류의 배열로 생각할 수 있는, 순서가 지정된 문자의 리스트다. 문자열의 각 칸에는 문자, 숫자, 기호, 공뱁 또는 제한된 특수 기호 중 하나가 포함됩니다. 마지막 칸에 있는 특수 기호 /는 종종 문자열의 끝을 나타냅니다. 인덱스를 사용해 문자열의 문자에 직접 접근할 수 있습니다. 일부 프로그래밍 언어에서는 문자열을 그냥 문자 배열로 직접 구현합니다. 몇몇 다른 언어에서는 문자열이 객체일 수 있으며, 문자열 클래스는 문자를 담고 있는 배열이나 다른 자료 구조를 감싼 래퍼(wrapper) 클래스 역할을 합니다. 문자열 래퍼 크래스는 문자열의 크기를 동적으로 조정하거나 부분 문자열을 탐색하는 등 추가 기능을 제공합니다. 두 경우 모두 일반 배열과 유사한 구조가 문장열에 대한 작업에 어떤 영향을 미칠지 생각해보는 것이 유용합니다. 컴퓨터 화면에 문자열을 표시할 때는 문자열의 각 문자를 반복하면서 하나씩 문자를 표시합니다. 동등성(equality) 검사는 더 흥미롭습니다. 한 번의 연산으로 직접 비교할 수 있는 정수와 달리, 문자열은 각 문자를 반복하면서 비교해야 합니다. 두 문자열을 비교할 때는 서로 일치하지 않는 문자를 발견할 때까지 두 문자열에서 같은 위치에 존재하는 문자를 서로 비교합니다. 아래의 코드는 두 문자열의 동등성을 확인하는 알고리즘을 보여줍니다. StringEqual(String: str1, String: str2): IF length(str1) != length(str2): return False Integer: N = length(str1) Integer: i = 0 WHILE i < N AND str1[i] == str2[i]: i = i + 1 return i == N 알고리즘은 먼저 문자열의 크기를 비교합니다. 길이가 다르면 알고리즘은 해당 시점에 중지됩니다. 길이가 같으면 알고리즘은 각 위치를 반복하면서 해당 위치에 있는 두 문자를 비교합니다. 이때 두 문자가 서로 일치하지 않으면 루프를 중지할 수 있습니다. 문자열을 모두 비교했는데 불일치가 일어나지 않았다면 두 문자열을 같다고 선언할 수 있습니다. 아래의 그림은 이 알고리즘이 두 문자열에 대해 어떻게 작동하는지 보여줍니다. =는 비교할 때 서로 일치한 문자 쌍을 나타냅니다. X는 최초 불일치로 인해 검사가 종료된 문자쌍을 나타냅니다. 문자열 비교에서 최악의 경우 계산 비용은 문자열의 길잉 비례해 증가합니다. 두 작은 문자열을 비교하는 작업에서는 무시할 수 있지만, 두 긴 문자열을 비교하는 작업에서는 시간이 오래 걸릴 수 있습니다. 예를 들어, 어떤 책의 1판과 2판을 처음부터 한 글자씩 비교하면서 두 책의 본문 문자 배열의 차이를 찾는 지겨운 과정을 상상해볼 수 있습니다. 가장 좋은 경우에는 초기에 일치하지 않는 부분을 찾을 수 있지만, 최악의 경우에는 책의 대부분을 검사해야 합니다. 많은 프로그래밍 언어, 예를 들어 파이썬과 같은 언어는 직접 비교할 수 있는 문자열 클래스를 제공합니다. 따라서 위 코드와 같은 비교 코드를 직접 구현할 필요가 없습니다. 그러나 간단한 비교 함수의 뒤에는 모든 문자를 반복하는 루프가 있습니다. 이 중요한 세부 사항을 이해하지 않으면 문자열 비교 비용을 과소평가할 수 있습니다.

Archive · 2024-04-22

📦[DataStructure] 배열

Archive · 2024-04-21

📦[DataStructure] 복합 자료 구조

Archive · 2024-04-21

📦[DataStructure] 변수

변수. 개변 데이터 조각을 종종 변수(variable)에 저장하곤 합니다. 변수(variable) : 컴퓨터 메모리 내 데이터 위치(또는 주소)를 표현하는 이름입니다. 프로그램 실행 중 변경되는 정보를 추적할 수 있게 합니다. 예를 들어 For 루프를 몇 번지나갔는지 세어야 할 경우, 게임에서 플레이어의 점수를 추적해야하는 경우 등 변수가 없으면 프로그램의 내부 상태를 추적, 평가(evaluate), 변경(update)할 수 없습니다. 변수를 생성하면 시스템이 그것을 자동으로 할당하고 위치를 지정합니다. 그리고 나서 원하는 변수 이름을 사용해 자유롭게 해당 위치에 데이터를 쓰고, 데이터를 쓸 때 사용한 변수 이름을 사용해 저장된 데이터를 읽을 수 있습니다. 변수 이름만 알고 있다면 데이터의 메모리 위치를 알 필요가 없습니다. 컴퓨터 메모리를 여러 상자가 일렬로 늘어선 것처럼 생각할 수도 있습니다. 각 변수는 저장한 데이터의 크기에 따라 하나 이상의 인접한 상자를 차지합니다. 아래 그림은 Level, Score, AveScore라는 세 변수를 보여줍니다. 여기서 평균 점수(AveScore)는 메모리 상자를 두 개 사용하는 부동 소수점 수(floating point number, 소수점이 있는 숫자)입니다. 어떤 측면에서 변수는 종이 문서를 담는 폴더에 붙은 종이 라벨과 비슷합니다. 아래 그림처럼 라벨을 붙인 후에는 폴더의 순서나 정확한 위치를 기억할 필요가 없습니다. 그 이유는 라벨로 폴더를 찾으면 되기 때문입니다. 이때 충분한 정보가 포함된 이름을 사용하는 것이 중요합니다. 만약에 파일 캐비닛에 할 일, 중요한 일, 다른 할 일, 그 밖의 일과 같이 이름이 겹치는(이를 오버로드(overload)라고 말합니다) 폴더가 많을 경우 내용을 파악하기 어렵습니다. 마찬가지로, 변수의 이름이 모호하면 변수가 어떤 값을 나타내는지 추측하기 어려워집니다. 많은 프로그래밍 언어에서 변수는 정수(integer), 부동 소수점 값(float), 불린 값(Boolean) 등과 같이 저장된 데이터의 타입과 연관이 있습니다. 타입은 변수가 얼마나 많은 메모리를 차지하고 메모리에 저장된 내용을 어떻게 사용해야 하는지를 프로그램에 알려줍니다. 예를 들어, 불린 변수는 제한된 범위의 값(즉, 참과 거짓)만 저장하며 적은 양의 메모리만 사용하는 경우가 많습니다. 반면, 2배 정밀도(double-precision) 부동 소수점 수는 훨씬 더 크고 정확한 숫자를 저장하므로 여러 상자를 사용합니다. 타입을 정의하는 문법이나 타입을 명시적으로 정의해야만 하는지 여부는 프로그래밍 언어마다 다릅니다. 아래 예제를 봐봅시다. 예제에서는 변수를 명시할 때 언어와 무관한 <타입>: <변수이름>이라는 의사 코드(pseudocode) 형식을 사용합니다. Integer: coffee_count = 5 Float: percentage_words_spelled_correctly = 21.0 Boolean: had_enough_coffee = False 가씀 Type이라는 타입이 지정된 변수도 있습니다. 이 타입은 어떻게 구현하는지에 따라 다양한 타입이 될 수 있다는 사실을 나타냅니다. 대부분의 프로그래밍 언어에서 일반적으로 사용되는 구문을 사용해 변수를 다룰 것입니다. 예를 들어, 변수에 값을 대입할 때는 =을 사용합니다. coffee_count = coffee_count + 1

Archive · 2024-04-21

devkobe24.com

Contact

DataStructure