nyunu

강의 출처) 숙명여자대학교 소프트웨어융합전공 강의 "자료구조", 이현자 교수님 1. 트리 : 계층적 자료의 표현에 적합한 자료 구조 = 루트 노드 + 서브 트리 2. 이진트리 1) 이진트리란 ? : 모든 노드가 2개의 서브 트리(노드)를 갖는 트리 서브 트리는 공집합일 수도 있음 루트와 왼쪽 서브트리 & 오른쪽 서브트리로 구성된 노드들의 집합 이진트리의 서브트리는 모두 이진트리 2) 허프만 코드 트리 : 문자에 대한 컴퓨터 내부 표현 중 하나 -> 텍스트 문서 압축 빈도수가 높은 문자에 대해서는 짧은 코드를 부여 빈도수가 적은 문자에 대해서는 긴 코드를 부여 결론적으로 최대한 적은 비트만 차지하도록 하는 것 3) 트리 관련 용어 노드 : 데이터와 연결선으로 구성된 트리의 한 유닛 노드의 차수 : 해당 노..

강의 출처) 숙명여자대학교 소프트웨어융합전공 강의 "자료구조", 이현자 교수님 원형 리스트 1. 원형 리스트란 ? 단일 리스트에서의 마지막 노드가 맨처음 노드와 연결된 형태 마지막 노드의 link가 NULL이 아님 head가 변경되어도 연결리스트를 유지할 수 있음 2. 원형 리스트 구현 1) 노드 기본 구현 class Node: def __init__(self, item): self.data = item self.link = None 2) 원형 연결 리스트 연산 종류 삽입 연산 삭제 연산 리스트 길이 계산 3) 원형 연결 리스트 구현 (1) 삽입 연산 삽입 연산의 경우의 수 세 가지 빈리스트에 삽입하는 경우 리스트 맨 앞 위치로 삽입하는 경우 리스트 중간(OR 끝)에 삽입하는 경우 코드 구현1 - 빈리스..

강의 출처) 숙명여자대학교 소프트웨어융합전공 강의 "자료구조", 이현자 교수님 연결리스트의 기본 구조 데이터 필드와 하나 이상의 링크 필드로 구성된 노드가 연결된 형태 => 노드 = 데이터 필드(해당 노드가 담고있는 data) + 링크 필드(다음 노드를 가리키는 link) 단일 연결 리스트 1. 단일 연결 리스트란 ? 노드들이 한 방향으로 연달아 연결되어 있는 구조 head, tail 노드 head : 리스트의 첫 노드 tail : 리스트의 끝 노드 2. 단일 연결 리스트 구현 1) 노드 기본 구현 class Node: def __init__(self, item): self.data = item self.link = None 2) 단일 연결 리스트 연산 종류 삽입 연산 삭제 연산 리스트 길이 계산 리스트..

강의 출처) 숙명여자대학교 소프트웨어융합전공 강의 "자료구조", 이현자 교수님 [목차] 1. 수식 표기 방식 2. 후위 수식 계산 3. 중위 -> 후위 변환 1. 수식 표기 방식 (1) 중위 표기법 연산자를 두 피연산자 사이에 표기 사람이 이해하기 좋은 표현법 우선순위에 따라 연산 순서 결정 괄호에 의해 연산 순서 조정 (2) 후위 표기법 피연산자를 먼저 표시하고 연산자를 나중에 표시 컴퓨터가 이해하기 좋은 표현법 우선순위 상관없음 괄호 없음 (3) 전위 표기법 연산자를 먼저 표시하고 연산에 필요한 피연산자를 나중에 표기 (4) 중위 vs 후위 vs 전위 (5) 연산자 우선순위 (C 기준) 2. 후위 수식 계산 (1) 기본 과정 수식의 왼쪽부터 토큰(문자)을 읽어냄 읽어낸 토큰이 피연산자 -> 스택에 p..

강의 출처) 숙명여자대학교 소프트웨어융합전공 강의 "자료구조", 이현자 교수님 스택(Stack) 1. 스택이란 ? 후입선출 = Last In First Out = LIFO 스택 연산 : push(데이터 넣고), pop(데이터 빼고) 사용 예시 시스템 스택 함수 호출을 관리하는 스택으로 운영체제가 사용하는 스택 복귀할 주소를 기억하는데 사용 컴퓨터 실행시에 이전으로 돌아가기 기능을 사용하면 가장 최근에 실행했던 내용을 삭제해주는 것과 같은 이치 -> 가장 최근에 실행했던 내용을 삭제하고 바로 이전의 상태로 돌아갈 수 있는 복귀할 주소를 기억 스택 프레임 (= 활성 레코드) 시스템 스택의 top에 스택프레임이 push = 함수가 호출될 때마다(새로운 프로그램이 or 동작이 실행될 때마다) 스택 프레임이 만들..

강의 출처) 2023-1 숙명여자대학교 소프트웨어학부 강의 "데이터마이닝및분석", 이기용 교수님 Random Forest : decision tree를 여러 개 랜덤하게 사용하여 만든 것 -> 어떻게 랜덤하게 decision tree를 여러 개 만드느냐가 포인트 ! bagging과 동일하게 샘플링 splitting feature를 잡을 때, p개의 feature를 랜덤하게 먼저 뽑고 그 중에서 베스트를 뽑아서 사용 -> 이때문에 모두 다른 트리가 되는 것 => random forest는 training instances와 features를 모두 새롭게 조합하여 사용 1. 기본 과정 (1) n개의 instance와 d개의 feature를 가진 training set D가 있다고 가정 (2) ..

강의 출처) 2023-1 숙명여자대학교 소프트웨어학부 강의 "데이터마이닝및분석", 이기용 교수님 1. Bagging [Bootstrap aggregating] 1) 기본 과정 (1) 데이터셋으로부터 반복적으로 샘플 추출 (2) 각 bootstrap 샘플에 대해 base classifier를 학습 (3) test data를 활용하여 전체 base classifier를 예측 (4) 전체 base classifier의 예측값 중 다수결로 결과를 채택 2) 데이터셋 추출시 주의할 점 [왕왕중요] 복원 추출 (with replacement) 뽑힌 데이터는 다시 그대로 제자리에 매번 뽑을 때마다 전체 데이터에서 하나씩 추출 이 성질 때문에 하나의 샘플 데이터셋에는 같은 데이터가 여러 개 뽑힐수도 ! 반대로 말하면 ..

강의 출처) 2023-1 숙명여자대학교 소프트웨어학부 강의 "데이터마이닝및분석", 이기용 교수님 앙상블이란 ? : 여러 개 분류기의 예측 결과를 합쳐서 분류 정확도를 높이는 기술 1. 기본 아이디어 (1) Training data로부터 base classifier을 조합을 형성하고 (2) 각 base classifier로부터 만들어진 예측을 가지고 투표를 진행해 결과를 냄 ※ 주의사항 각 base classifier의 정확도는 50% 이상이어야 함 -> 정확도가 낮은 모델끼리 모아놓으면 오히려 정확도가 더 떨어지는 효과 . . . 각 base classifier는 독립적이어야 함 독립적이면 base classifier 중 절반 이상이 잘못 예측해야만 오분류가 발생 -> 그러니까 정확도를 높일 수 있는 것..