Priv's Blog

1. 정렬된 배열에 원소를 추가하는 알고리즘 이진 검색으로 원소가 추가될 위치를 확인한다. 검색 실패 시, 중앙에 위치한다. 원소가 이동하는 데 필요한 시간 복잡도는 O(n)이다. 원소 삭제 시에도 동일한 비용이 발생한다. 2. 해시법 (Hashing) 해시법이란, 간단한 연산을 통해 데이터를 저장할 위치를 구하는 방법이다. 원소의 검색 외에 추가 및 삭제 작업도 효율적으로 구현할 수 있다. 데이터의 저장과 검색에 극단적인 효율을 가지고 있어 빠른 응답을 요구하는 프로그램에 활용된다. 해시값 (Hash Value)이란, 해시법을 통해 계산된 데이터 저장 위치(인덱스)를 말한다. 해시 테이블 (Hash Table)이란, 해시값을 인덱스로 하는 배열을 말한다. 버킷 (Bucket)이란, 해시 테이블에서 원소..

1. 이진 검색 (Binary Search) 이진 검색 알고리즘이란, 원소가 오름차순이나 내림차순으로 정렬된 배열에서 효율적으로 검색할 수 있는 알고리즘이다. 이진 검색 트리를 기반으로 동작하며, 주목한 원소보다 값이 크면 우측으로, 값이 작으면 좌측으로 움직이면서 검색을 진행한다. 주목한 원소가 이동할 때마다 검색 범위가 1/2로 줄어든다. 정렬된 배열에 대해서 선형 검색보다 매우 빠르게 검색이 가능하다. 이진 검색의 종료 조건은 다음과 같다. 중앙 원소가 키 값과 일치하는 경우, 검색 성공 검색 범위가 더 이상 없는 경우, 검색 실패 from typing import Any, Sequence def bin_search(a: Sequence, key: Any) -> int : pl = 0 pr = le..

1. 검색 알고리즘 (Search Algorithm) 검색 알고리즘이란, 데이터 집합에서 원하는 값을 지닌 원소를 찾아내는 알고리즘 또는 어떤 조건을 만족하는 데이터를 찾아내는 알고리즘을 말한다. 1.1) 키(Key) 데이터의 일부로 검색 조건에서 주목하는 항목이다. 데이터가 정수 값이나 문자열일 경우, 데이터 값 그 자체가 키가 되기도 한다. 국적이 한국인인 사람을 찾는다. (국적: 키값과 일치하도록 지정) 나이가 21세 이상 27세 미만인 사람을 찾는다. (나이: 키값의 구간을 지정) 이름에 '김'자가 들어산 사람을 찾는다. (문자: 키값에 가깝도록 지정) 검색 조건은 1개만 지정할 수도 있고, 논리곱이나 논리합을 사용해 복합적으로 지정할 수 있다. 2. 검색의 종류 검색 알고리즘의 종류는 다음과 같..

1. 개별적으로 생성한 리스트의 동일성 판단하기 다음과 같이 2개의 리스트를 생성했다고 가정하자. lst1 = [1, 2, 3, 4, 5] lst2 = [1, 2, 3, 4, 5] 이 2개의 리스트를 다음과 같이 is 연산자로 동일성(identity)을 판단해보자. lst1 is lst2 이 연산 결과는 False이다. 따로따로 생성한 리스트(튜플)의 경우, 리터럴이 아니기 때문에 서로 다른 식별 번호를 가진다. 또한 is 연산자는 이 식별 번호가 동일한 지를 판단하는 연산자이다. 2. 리스트(튜플)의 대입 이제 리스트 2개를 선언하여 서로 대입하면 어떻게 되는지 알아보자. lst1 = [1, 2, 3] lst2 = lst1 lst1[2] = 9 print(lst1) print(lst2) 위의 결과는 다..

1. 배열 원소 최댓값 구하기 배열 a의 원소가 3개인 경우 max = a[0] if a[1] > max : max = a[1] if a[2] > max : max = a[2] 배열 a의 원소가 4개인 경우 max = a[0] if a[1] > max : max = a[1] if a[2] > max : max = a[2] if a[3] > max : max = a[3] 코드를 이렇게 작성할 경우, 배열의 크기가 커지면 if문의 개수도 많아지기 때문에 적합하지 않다. 2. 배열 원소의 최댓값 구하기 배열 원소의 최댓값을 구하는 과정은 다음과 같다. 원소(a[0])의 값을 maximum에 대입한다. 필요에 따라 if 문에서 maximum 값을 업데이트한다. 원소 수가 n일 경우, if문은 n-1번 실행된다...

1. 두 값 교환하기 들어가기에 앞서 이전에 살펴보았던 두 변수의 값을 교환하는 과정을 다시 살펴본다. python에서 제공하는 튜플(tuple)을 사용한 방식과 임시 변수를 사용한 방식의 비교이다. 이번 파트에서는 python에서 이처럼 매우 간편한 작업이 어떻게 가능한지에 대해서 살펴본다. 2. python의 변수 python에서는 모든 데이터, 함수, 클래스, 모듈, 패키지 등의 구성 요소들을 객체(object)로 취급한다. 객체는 자료형을 가지며, 메모리 공간을 차지한다. 이는 다시 말해, python의 변수는 값을 가지지 않는다는 것을 의미한다. 일반적으로 다른 언어에서는 변수에 값을 '대입'한다고 표현한다. 이는 변수의 자료형에 따라 정해진 메모리 공간이 할당되고, 그 주소 공간에 사용자가 대..

1. 자료구조 (Data Structure) 자료구조란, 데이터 단위와 데이터 자체 사이의 물리적 또는 논리적 관계로 이루어진 데이터 구성을 말한다. 컴퓨터에서 처리해야 하는 많은 데이터들을 효율적으로 관리, 구조화하는데 필요한 개념이다. 2. 학생 성적 분석 알고리즘 학생 5명의 시험 점수를 입력받아 합계, 평균을 구하는 알고리즘을 작성해보자. 사용자에게 입력받은 각 학생의 점수를 score 1, score 2, ~ , score n에 대입하고, 합계와 평균을 수식으로 계산한다. print("학생 그룹 점수의 합계, 평균을 구하는 알고리즘") ## User Input ## score1 = int(input("1번 학생 점수: ")) score2 = int(input("2번 학생 점수: ")) score..

1. 반복 구조 (Repetition Structure) 어떤 조건이 성립하는 동안 프로그램 명령문이나, 명령어의 집합을 반복 처리하는 구조를 반복 구조라고 부른다. 일반적으로 루프(Loop)라고 부른다. 1.1) 판단 반복 구조 조건식을 이용하여 반복을 계속할 것인지 판단하는 반복 구조를 판단 반복 구조라고 부른다. 사전 판단 반복 구조와 사후 판단 반복 구조로 구분된다. 2. 1~n까지 정수 합 구하기 정수 n을 입력받아 1부터 n까지의 정수 합(1+2+3+4+~+n)을 구하는 알고리즘을 구현해보자. python이 지원하는 반복문은 for문과 while문이 있다. 이 2가지 방법을 모두 활용해 구현해보자. 2.1) while 문을 사용하여 구현하기 ### 1~n까지의 합 계산하기(while문 사용) ..