1. 스트링 알고리즘 관련 기본 개념스트링( string )이란?문자가 연속적으로 나열된 문자열예시ATATCGCCCACTAT001011010001110101알파벳 ( alphabet, Σ )스트링에 사용되는 문자들의 집합예시DNA 서열 ➝ Σ = { A, C, G, T }이진 데이터 ➝ Σ = { 0, 1 }2. 스트링 알고리즘스트링에 대한 다양한 문제를 해결하는 알고리즘을 통칭스트링 매칭스트링 압축최장 공통 부분 수열최장 반복 서브스트링최장 회문 서브스트링접미부 트리접미부 배열…3. 스트링 매칭텍스트에서 패턴이 나타나는 위치를 찾는 것텍스트 T = t₀t₁t₂⋯tₙ₋₁ → 긴 스트링, 길이 n패턴 P = p₀p₁p₂⋯pₘ₋₁ → 짧은 스트링, 길이 mn ≥ m예시T = a a b a a b a a aP..
1. 동적 프로그래밍문제의 크기가 작은 소문제에 대한 해를 테이블에 저장해 놓고, 이를 이용해서 크기가 보다 큰 문제의 해를 점진적으로 만들어가는 상향식 접근 방법각 소문제는 원래 주어진 문제와 동일한 문제 ➝ 입력 크기만 작아진 문제소문제들은 서로 독립일 필요는 없음동적 “프로그래밍” ➝ “동적 계획법”컴퓨터 프로그램과는 무관, 해를 구축하는 데 테이블을 이용한다는 의미최소값 / 최댓값을 구하는 최적화 문제에 주로 사용"최적성의 원리 ( principle of optimality )"를 반드시 만족하는 문제에만 적용 가능최적성의 원리란?주어진 문제에 대한 최적해는 주어진 문제의 소문제에 대한 최적해로 구성동적 프로그래밍 방법의 처리 과정(0) 최적성의 원리가 주어진 문제에 성립하는 지 확인(1) 주어진..
1. 벨만-포드 알고리즘단일 출발점 최단 경로를 구하는 알고리즘음의 가중치를 갖는 간선이 존재하는 경우에도 처리 가능단, 음의 사이클이 없는 경우에만 동작함G=(V, E)에서 |V|=n일 때, 단계적으로 최단 경로를 구해 나가는 방식간선을 최대 1개 사용하는 최단 경로간선을 최대 2개 사용하는 최단 경로…간선을 최대 (n-1)개 사용하는 최단 경로수행 과정초기화출발점 s의 거리 d[s] = 0나머지 모든 정점 v의 거리 d[v] = ∞for i ← 1 to |V| - 1모든 간선을 한 번씩 조사하면서 거리값 조정 여부 결정d[v] ← min{ 기존 거리 d[v], 간선 ⟨u, v⟩를 지나는 경우의 거리 d[u] + w }전 단계에서 거리값 d[ ]의 조정이 발생한 정점에 부수된 간선만 조사하는 방식으로 ..
1. 두 모집단의 비교 사례제품 A를 사용한 집단과 제품 B를 사용한 집단 간 선호도 차이는 있을까두 생산 라인에서 생산되는 제품 간 수율 차이는 있을까어느 직장의 직무연수가 연수 이전에 비해 직원들의 직무능력을 향상시켰는가각 모집단의 특성을 나타내는 값, 평균을 고려한다면 두 모집단의 비교는 모평균의 비교 문제로 귀결된다.2. 독립표본 시 두 모집단의 비교두 모집단의 모평균 μ₁, μ₂ 차이에 대한 기준값이 δ₀일 때, 다음 세 가지 가설을 세울 수 있다.① H₀: μ₁ − μ₂ = δ₀ ( 귀무가설 ) H₁: μ₁ − μ₂ > δ₀ ( 대립가설 )② H₀: μ₁ − μ₂ = δ₀ ( 귀무가설 )H₁: μ₁ − μ₂ ③ H₀: μ₁ − μ₂ = δ₀ ( 귀무가설 ) H₁: μ₁ − μ₂ ≠ δ₀ ( 대..
1. 트랜잭션의 개념트랜잭션의 정의데이터베이스를 조작하기 위한 하나의 논리적 단위를 이루는 일련의 데이터베이스 연산의 집합예시 : 예금 인출작업 단위 : 예금 1000원 인출일련의 연산 : Read(A), A=A-1000, Write(A)데이터베이스를 사용하여 처리하는 작업을 하나의 묶음으로 인식하여 묶음 단위로 실행된 것과 동일한 결과가 도출되도록 정의한 개념2. 데이터 읽기와 쓰기데이터베이스의 두 연산Read(X)데이터베이스에서 데이터 X를 읽고, 트랜잭션이 실행되는 메모리의 변수 X에 값을 저장하는 연산Write(X)트랜잭션이 실행되는 메모리에 있는 변수 X의 값을 데이터베이스에 저장하는 연산예시계좌 A에서 B로 1,000원을 이체하는 트랜잭션Read(A)A := A - 1000Write(A)Rea..
1. 모비율의 가설검정 - 귀무가설과 대립가설귀무가설𝐻₀: p = p₀대립가설단측 검정𝐻₁: p 𝐻₁: p > p₀ ( 우측 단측 검정 )양측 검정𝐻₁: p ≠ p₀ ( 양측 검정 )2. 모비율의 가설검정 - 검정통계량Z = (p̂ - p₀) / √[p₀(1 - p₀) / n] ∼ N(0,1)p̂ : 표본 비율 (sample proportion)p₀ : 귀무가설 하의 모비율n : 표본 크기N(0,1) : 평균 0, 분산 1의 표준 정규분포3. 모비율의 가설검정 - 검정방법가설기각역을 이용한 검정유의확률을 이용한 검정𝐻₀: p = p₀𝐻₁: p > p₀Z > zₐ 이면 𝐻₀를 기각p값 = P(Z > z_obs | 𝐻₀)→ p값이 α보다 작으면 𝐻₀를 기각𝐻₀: p = p₀𝐻₁: p Z ..
1. 불확실한 상황 속 의사결정통계적 추론 : 추정과 검정가설검정불확실한 상황 속에서 의사결정모집단으로부터 추출한 데이터를 이용하여 모집단의 가설에 대해 체계적인 결론을 도출하는 것A인지, 아닌지를 결론으로 도출2. 귀무가설과 대립가설통계적 가설( hypothesis testing )2개의 가설, 이 중 하나 가설 선택귀무가설( null hypothesis ) : 𝐻₀기존의 사실대립가설( alternative hypothesis ) : 𝐻₁ 또는 𝐻ₐ밝히고자 하는 사실Randi의 통계적 실험, 재판과정과 통계적 가설검정귀무가설 : 모수가 비교 값과 같다.𝐻₀ : μ = 12.0𝐻₀ : μₐ = μᵦ대립가설 : 주장하고자 하는 가설𝐻₁: μ ≠ 12.0, 𝐻₁: μₐ ≠ μᵦ𝐻₁: μ > 1..
1. 파일의 역할컴퓨터에 의해 처리될 또는 처리된 데이터와 정보가 임시적으로 저장된 상태일련의 연속된 바이트프로그램( 파이썬 소스코드 )에 읽혀 가공∙처리2. 파일의 구성연속된 바이트와 파일의 시작, 파일 포인터( 작업 위치 ), 파일의 끝( EoF : End of File )으로 표현3. 파일의 종류데이터가 저장되는 방식에 따라 구분텍스트 파일 ( text encoding )데이터를 구성하는 개별 문자를 인코딩 체계를 통해 바이트로 변경하여 연속적으로 저장바이너리 파일 ( binary encoding )실제 바이너리 숫자로 저장4. 파일 함수파일의 시작, 파일 포인터, 파일의 끝을 활용하여 데이터 읽기, 쓰기를 위한 함수 및 메소드를 내장멤버open( ):file : obj 파일과 연결되어 있는 파일 ..
11강. 모듈
1. 모듈의 개념함수, 상수 또는 클래스를 모아 놓은 집합체이들은 주제 지향적으로 모아 놓은다.클래스 : 다른 모듈의 확장함수 : 특정 작업을 처리상수( 변수 ) : 불변의 값2. 모듈, 패키지, 라이브러리모듈 : 클래스, 함수, 상수의 집합( 파일 단위 )패키지 : 하위 패키지 및 모듈의 집합( 폴더 단위 )라이브러리 : 패키지 및 모듈의 집합3. 모듈의 등록 1구문형식import 모듈이름 [ as 별칭 ]파이썬 모듈을 프로그램 내부에서 사용할 수 있게 네임스페이스에 추가하는 명령어모듈이름 / 별칭.변수모듈이름 / 별칭.함수( )모듈이름 / 별칭.클래스4. 모듈의 등록 2구문형식from 모듈이름 import 메소드1, [메소드2/함수/클래스 …]이는 모듈 내 특정한 메소드만 가지고 오게 된다.from ..
1. 객체지향의 개념객체와 객체 사이의 상호작용으로 프로그램을 구성하는 프로그래밍 패러다임프로그램을 유연하고 변경을 쉽게 만들어 대규모 소프트웨어 개발에 사용객체지향 패러다임의 특징추상화 : 공통의 속성이나 기능을 도출캡슐화 : 데이터 구조와 데이터의 연산을 결합상속 : 상위 개념의 특징이 하위 개념에 전달다형성 : 유사 객체의 사용성을 그대로 유지2. 객체와 클래스객체는 추상화와 캡슐화의 결과실세계의 사물에 대한 상태( 데이터 )와 연산( 메소드 )을 표현한 단위멤버( 데이터 필드, 메소드 )는 클래스에 의해 결정3. 클래스 정의구문형식class 클래스 이름: [Tab] 초기자 정의 [Tab] 메소드 정의메소드( method )객체에 대한 행동( 연산 )을 정의함수의 정의 및 사용 방법과 동일초기자( ..