5주차

수강한 분량

알고리즘을 수강했다. 검색, 순위, 정렬 등 기본부터 특정 값(최대, 최소, 최빈 등)을 구하는 것, 그리고 알고리즘에서 가장 많이 활용되는 것 같아 보이는 재귀까지 다양한 알고리즘을 배웠다.

각 강의별 학습한 핵심 내용 정리

• algorithm
  - 일련의 절차나 방법을 공식화한 형태로 표현한 것
• API
  - application Programming Interface
  - 사용자가 사용하기 쉽게 이미 만들어둔 함수, 속성
  - 알고리즘을 활용해 만듬

선형 검색

• 선형으로 나열되어 있는 데이터를 순차적으로 스캔하며 원하는 값을 찾는다
  - 검색 성공 / 실패
• 보초법
  - 마지막 인데스에 찾으려는 값을 추가해, 찾는 과정을 간략화 한다
  - 검색 성공: 마지막 이전에 값이 검색된 경우
  - 검색 실패: 마지막에 값이 검색된 경우

이진 검색

• 정렬되어 있는 자료구조에서 중앙값과의 크고 작음을 이용해 데이터를 검색한다
  - 중요 변수
  - staIdx
  - 첫 인덱스
  - endIdx
  - 마지막 인덱스
  - midIdx
  - 중앙값 인덱스
  - (staIdx + endIdx) // 2
  - midVal
  - 중앙값
  - 의사코드
  - 검색 데이터가 주어진 데이터들의 범위 안엔 있는지 먼저 확인
  - 검색 데이터가 중앙값보다 크다면 staIdx를 중앙값 인덱스 +1
  - 검색 데이터가 중앙값보다 작다면 endIdx를 중앙값 인덱스 -1
  - 검색 데이터가 중앙값과 같다면 midIdx를 반환

순위, Rank

• 수의 크고 작음을 이용해서 정렬되지 않은 수의 순서를 정하는 것

• 중요변수
  - ranks = [0 for i in range(n)]
  - 기존 자료구조의 순위를 저장하는 자료구조, n은 기존 자료구조의 수와 동일

• 의사코드
  - 중첩구문을 활용해 기존 자료구조의 모든 숫자와 나머지의 모든 숫자와 비교한다
  - 기준 숫자와 비교해 더 작은 경우 rank값에 1을 더해준다

• class를 활용한 실습사항
  - 변수 초기화
  - 반복적으로 활용하는 함수를 만들고, 그것을 활용해 특정 상황마다 앞의 함수에 적용하는 함수, 그리고 적용된 결과물을 불러오는 함수를 따로 만들었다
  - setRank
  - setMidRank
  - getMidRank

버블 정렬, Bubble

• 처음부터 끝가지 인접하는 인덱스 값을 순차적으로 비교하여 큰 숫자를 가장 끝으로 옮기는 알고리즘

• 중요변수
  - tmp 활용해 두 자료를 맞교환할 수 있다. 그러나 아래와 같이 python에서는 swap에 유용한 구조가 있다
  - tmp = a; a = b; b = tmp
  - a, b = b, a

• 의사코드
  - 중첩 반복문을 활용해 처음 두 변수를 비교해 더 큰 수가 오른쪽에 오게 한다.
  - 한 싸이클을 다 돌고 나면 다시 처음부터 비교하는데 이때 지난 싸이클에서 비교한 제일 마지막 숫자는 제외한다

• 깊은 복사

import copy

def 함수명(데이터, deepCopy = True):
	if deepCopy:
		cns = copy.copy(데이터)
	else:
		cns = 데이터 

삽입 정렬, Insert

• 정렬되어 있는 자료 배열과 하나씩 비교해 정렬 위치를 찾는 알고리즘

• 중요변수
  - cNum
  - 현재 비교 기준 변수
  - i2
  - 현재 비교 기준 변수와 비교할 앞 변수 인덱스
  - 이 인덱스를 가진 자료값이 cNum과 비교하여 오름차순일 때는 크다면, 내림차순일 때는 작다면 i2 + 1 인덱스를 가진 자료값에 이 인덱스 자료값을 넣어주고, i2값은 하나 빼어 0까지 변화한다.
  - 만약 비교 후 변화가 없다면 i2보다 작은 인덱스를 가진 값들은 이미 정렬되어 있으므로 비교X

• 의사코드
  - 두 번째 요소부터 마지막까지 범위인 반복문을 만들어, 현재 비교 기준 변수 인덱스로 할당한다.
  - 현재 비교 기준 변수 인덱스 왼쪽에 존재하는 변수와 값을 비교하여 변화해야 하는 경우 비교 인덱스 + 1 위치에 비교 인덱스의 자료값을 넣어주고, 비교 인덱스는 하나를 빼어 더 왼쪽값을 비교한다. 이때 비교 인덱스가 0보다 크거나 같을 때까지를 조건으로 둔다

• 함수에서 동일 데이터를 옵션만 바꾸어 활용하고 싶을 때를 위해 옵션만 바꾸는 함수를 class 내부에 선언해주기도 함

class 클래스명:
	def __init__(self, 데이터, asc = True):
		self.data = 데이텆
		self.isAsc = asc
		
	def isAscending(self, flag):
		self.isAsc = flag

객체명 = 클래스명.함수(데이터)
# 위에서 잔뜩 활용한 객체명에 특정 옵션만 바꾸어 마저 활용할 수 있다
객체명.isAscending(False)

선택 정렬, Select

• 주어진 리스트 중에 최솟값을 찾아 그 값을 맨 앞에 위치한 값과 교체하는 방식으로 자료를 정리하는 알고리즘

• 중요변수
  - minIdx
  - 최솟값 인덱스
  - tempNum
  - 기준값과 최소인덱스를 교환할 때 사용하는 임시변수

• 의사코드
  - 중첩 반복문을 활용하여, 주어진 자료 처음부터 마지막 -1 까지 반복문은 비교 기준 인덱스 값을, 비교 기준인덱스 + 1부터 마지막까지 반복하는 내부 반복문은 비교 인덱스값으로 활용한다.
  - 첫번째 반복문을 시작할 때 반복문에 활용하는 i값을 minIdx 초기값으로 할당한다.
  - 주어진 값을 상호 비교하여 비교 기준 인덱스의 자료값이 비교 인덱스 자료값보다 크다면 minIdx에 비교 인덱스 값을 할당한다
  - 내부 반복문이 완료되면, i번째 값과 minIdx번째 값을 상호교환한다.

• 깊은 복사를 함수 외부에서도 활용할 수 있음
  - 아래와 같이 활용할 경우 원본 데이터 훼손을 막을 수 있음

import copy
result = 클래스명.함수명(copy.deepcopy(데이터))

최댓값, Max

• 자료구조에서 가장 큰 값을 찾는다.
• 중요변수
  - maxNum
  - 가장 큰 수
  - 임의로 자료구조의 가장 첫 번째 요소를 할당
• 의사코드
  - maxNum에 자료구조 가장 첫 번째 요소를 할당한다
  - maxNum을 주어진 자료구조의 두 번째 요소부터 마지막 요소까지 비교하여, maxNum이 더 작을 경우 비교 요소를 maxNum에 할당한다

최솟값, Min

• 자료구조에서 가장 작은 값을 찾는다
• 중요변수
  - minNum
  - 가장 작은 수
  - 임의로 자료구조의 가장 첫 번째 요소를 할당
• 의사코드
  - minNum에 자료구조 가장 첫 번째 요소를 할당한다
  - minNum을 주어진 자료구조의 두 번째 요소부터 마지막 요소까지 비교하여, minNum이 더 클 경우 비교 요소를 minNum에 할당한다

최빈값,

• 자료구조에서 빈도수가 가장 많은 데이터
• 중요변수
  - indexes
  - 자료구조에 포함된 데이터값을 인덱스로 두고 빈도를 체크할 리스트
  - maxAlgorithm
  - 최댓값 알고리즘을 활용해 원래 자료구조에서 가장 큰 값을 구하고, 이후에 새로운 리스트에서 가장 큰 값을 구하는데 활용한다.
• 의사코드
  - 자료구조에서 최댓값 알고리즘을 활용해 가장 큰값을 구해, 0부터 가장 큰 값까지 0이 배정된 새로운 리스트를 만든다
  - 자료구조 데이터가 나올 때 마다 새로운 리스트의 해당 인덱스값에 1을 더해준다.
  - 최댓값 알고리즘을 활용해 새로운 리스트에서 가장 큰 값의 인덱스를 구한다.

근삿값, Near

• 자료구조에서 특정 값(참값)에 가장 가까운 값
• 중요변수
  - inputNum
  - 찾고 싶은 숫자
• 의사코드
  - 주어진 자료구조 각 데이터에서 찾고 싶은 숫자를 빼고, 절대값 함수 abs() 처리를 한다
  - 위의 처리를 한 각 값을 비교하여 가장 작은 값을 가진 숫자를 찾아 출력한다
  - 만약 근삿값을 이용해 새로운 값을 기존 리스트에 추가하는 경우에는 제일 끝에 있는 것부터 하나씩 뒤로 밀어두고, 근사값 인덱스 자리에 새로운 값을 추가한다

평균, Average

• 여러 수나 양의 중간값을 갖는 수
• 중요변수
  - total
  - 모든 수의 합
  - len(자료구조)
  - 모든 수의 갯수
  - cnt
  - 조건을 만족한 모든 수의 갯수
• 의사코드
  - 반복문을 활요앻 주어진 숫자를 다 더한다
  - 모든 수의 합을 모든 수의 갯수로 나눈다
  - 만약 특정 조건을 만족해야 한다면, 조건을 만족한 경우 추가되는 새로운 리스트 자료구조를 만들어 두어도 된다. 혹은 cnt 변수를 이용해 모든 수의 갯수를 저장해두어도 괜찮다.
  - 특정 조건 중 정수들의 평균을 구할 때
  - 주어진 숫자 - int(주어진 숫자) == 0 을 조건으로 두기

재귀, Recursion

• 나 자신을 다시 호출하는 것
• 의사코드
  - 특정 조건에서만 나 스스로를 부른다
  - 이때 인수값을 하나씩 빼주는 등 변화를 주어야 한다
  - 영원히 반복되지 않도록 특정 조건2일 때 반복되지 않는 특정 값을 반환한다
• 유클리드 호제법
  - 두 자연수 n1, n2에 대해 (n1 > n2) n1을 n2로 나눈 나머지를 r이라고 할 때, n1과 n2의 최대공약수는 n2와 r의 최대공약수와 같다

하노이의 탑, Tower of hanoi

• 퍼즐 게임의 일종으로 세 개의 기둥을 이용해, 원판을 다른 기둥으로 옮기면 된다.
  - 한 번에 한 개의 원판만 옮길 수 있다
  - 큰 원판이 작은 원판 위에 있어서는 안 된다
• 중요변수
  - discCnt
  - 원판 갯수
  - fromBar
  - 출발 기둥
  - toBar
  - 도착 기둥
  - viaBar
  - 경유 기둥
• 의사코드
  - 만약 디스크 갯수가 1개라면 그 디스크를 출발 기둥에서 도착 기둥으로 옮겨라
  - 만약 디스크 갯수가 1개보다 많다면
  - 원판 갯수-1 개들을 출발 기둥에서 경유 기둥으로 옮겨라 -> 재귀 함수로 반복
  - 제일 큰 원판을 출발 기둥에서 도착 기둥으로 옮겨라
  - 원판 갯수-1 개들을 경유 기둥에서 도착 기둥으로 옮겨라 -> 재귀 함수로 반복

병합 정렬, Merge

• 자료구조를 분할하고 각각의 분할된 자료구조를 정렬한 후 다시 병합하여 정렬한다
• 상대적으로 속도가 빠르다
• 중요변수
  - midIdx
  - 중간 인덱스 값
  - leftNums
  - 0부터 midIdx까지의 값들 모음
  - rightNums
  - midIdx부터 끝까지의 값들 모음
  - mergeNums
  - 정렬된 값을 저장할 리스트
  - leftIdx
  - 왼쪽 숫자들의 인덱스
  - 처음은 0이고, 한 묶음이 끝나면 다시 0
  - rightIdx
  - 오른쪽 숫자들의 인덱스
  - 처음은 0이고, 한 묶음이 끝나면 다시 0
• 의사코드
  - 만약 주어진 데이터의 길이가 2보다 작다면 을 반환
  - 주어진 자료의 길이 중간값을 midIdx로 둔다
  - 왼쪽 숫자와 오른쪽 숫자로 나눈다
  - 왼쪽 숫자가 오른쪽 숫자보다 작다면 왼쪽 숫자[왼쪽인덱스]를 정렬된 값에 추가한다
  - 만약 오른쪽 숫자가 더 크다면 오른쪽 숫자[오른쪽인덱스]를 정렬된 값에 추가한다
  - 왼쪽인덱스가 왼쪽 숫자모음 길이보다 커지거나, 오른쪽인덱스가 오른쪽 숫자모음길이 보다 커지면 루프를 나와, 정렬된 값에 남은 숫자들을 이어 붙인다
  - 만약 순서가 바뀐다면, asc = True 와 같은 옵션을 넣어주어야 하며, 재귀로 부를 때에도 옵션에 asc = asc 등으로 명시를 해주어야 한다

퀵 정렬, Quick

• 기준 값보다 작은 값과 큰 값으로 분리한 후 다시 합친다

• 중요변수
  - midIdx
  - 기준 인덱스로, 주어진 자료의 길이를 반으로 나눈 몫으로 할당
  - midVal
  - 기준 인덱스의 자료값
  - smallNums
  - 기준 값보다 작은 숫자들의 리스트
  - sameNums
  - 기준 값과 같은 숫자들의 리스트
  - bigNums
  - 기준 값보다 큰 숫자들의 리스트

• 의사코드
  - 주어진 자료의 길이가 2보다 작다면 자료를 반환한다
  - 주어진 자료의 값이 기준값보다 작으면 smallNums에 추가
  - 주어진 자료의 값이 기준값과 같으면 sameNums에 추가
  - 주어진 자료의 값이 기준값보다 크면 bigNums에 추가
  - smallNums에 재귀적으로 적용한 것에 sameNums를 더하고, bigNums에 재귀적으로 적용한 것을 더하여 반환한다

연습문제

+ 추후에 추가

느낀점

이 글은 제로베이스 데이터 취업 스쿨의 강의 자료 일부를 발췌하여 작성되었습니다.