관리도는 통계적 공정관리에서 매우 중요한 요소로서 제품을 측정하고 그 제품의 품질특성치의 평균을 나타내는 중심과 상한선(USL)과 하한선(LSL)을 설정해두고 공정의 상태를 나타내는 그래프를 말한다.

일반적으로 정상적으로 돌아가는 공장에서도 어떤 값을 중심으로 품질이 퍼져있는 형태인데 아무리 잘 설계된 공정과 관리라 하더라도 동일 품질의 제품을 계속해서 만드는 것은 불가능하다. 왜 그런가 하면 다음 두가지 요인에 의해서 설명이 될 수 있다.

1. 우연원인(chance cause) - 생산조건이 엄격하게 관리된 상태하에서도 발생하는 어느 정도의 불가피한 변동을 주는 원인으로, 작업자간 숙련도의 차이 ,환경의 차이, 원자재간 미세한 품질의 차이 등 수도없는 이 변수들이 이러한 변동을 만들며 따라서 동일 품질의 제품을 만드는 것이 불가능한 이유가 된다. 우연원인으로 인한 품질의 변동을 줄이기 위한 비용은 무한대...이다. 그래도 우연원인으로 인한 변동을 어느정도까지는 줄일 수 있는데 제품이나 공정에 대한 근복적인 분석과 조사가 필요하며 일반원인(common cause)라고도 불린다.

2. 이상원인(assignable cause) - 작업자의 부주의, 불량자재의 사용, 생산 시스템의 이상 등을 말하며 위 우연원인처럼 항상 존재하는 것이 아니라 산발적으로 발생하여 품질 변동을 일으키는 원인이다. 이상원인을 특수원인(special cause)라고도 부른다.

이렇듯 관리도를 사용하여 모든 점들이 상한선과 하한선안에서만 있으며 점의 움직임에 어떠한 패턴이 없으면 생산공정에 있어서 우연원인에 의해서만 발생하는 경우로 볼 수 있으며 이러한 경우 공정은 관리상태에 있다고 한다. 그렇지 않고 점의 움직임에 어떠한 패턴이 있거나 상한선 하한선을 벗어난 경우 공정은 이상상태에 있다고한다.

만약 어떤 컵라면 공장에서 컵라면의 중량의 평균이 u이고 표준편차를 σ라고 할 때 이것을 모수라고 한다. 모수는 측정하고자하는 생산된 제품에서 측정하는데 이상요인이 발생하면 원래 모수값과 새롭게 측정한 제품들에서 나온 모수 값이 달라지게 된다. 예를들어 n개의 컵라면을 생산하는 공장에서 평균 u가 커졌다면 u=np (여기서 p는 중량이 불량일 확률이다)
즉 항상 n개를 생산하는데 평균이 커졌으므로 자연스럽게 불량률이 올라갔다는 결론을 얻을 수 있으다.
생산공정이 정상상태에 있을 때 품질특성의 확률분포의 모수를 θ₀라고 하며 시료를 추출하고 새롭게 측정해서 나온 모수를 θ라고하면 이를 가설검정 문제로 치환이 가능하다.
H₀ : θ=θ₀
H₀ : θ=θ₀
이렇게 가설검정을 할 때 기각역을 정해야하는데 여기서 바로 6σ를 사용하여 나타낸다. 평균을 중심으로 +3σ된 지점의 선을 그으면 관리상한선이 되며 평균을 중심으로 -3σ가 된 지점의 선을 그으면 관리하한선이 된다.

이 6σ 관리도는 W.A. Shewhart가 제안한 것으로 이러한 종류의 관리도를 Shewhart 관리도라고 부르기도 한다. 

3. 관리상태의 판정

• 연속된 7점 혹은 그 이상의 점들이 중심선의 어느 한쪽에 위치했을 때
• 연속된 11점 중 적어도 10점이 중심선의 어느 한쪽에 위치했을 때
• 연속된 14점 중 적어도 12점이 중심선의 어느 한 쪽에 위치할 때 
• 연속된 17점 중 적어도 14점이 중심선의 어느 한 쪽에 위치할 때
• 연속된 20점 중 적어도 16점이 중심선의 어느 한 쪽에 위치할 때
• 연속된 3점 중 2점 이상이 2σ를 벗어날 때
• 연속된 5점 중 4점 이상이 1σ를 벗어날 때
• 연속된 7개 혹은 그 이상의 점이 계속해서 상승 혹은 하락할 때
• 연속된 14점 이상이 중심선 주위에 위치할 때
• 그외 이동,주기,층화 경향이 나타날 때

비어있는 이진 트리에서 다음 순서로 값을 넣어보자

insert(1,2,3,4,5)

그러면 다음과 같은 형태의 이진트리가 나온다.

?? 이렇게 되면 O(logn)을 자랑하는 이진 트리가 연결리스트의 O(n)의 시간복잡도이 되었다. 

무엇을 위해서 그 복잡한 트리를 공부했는가 아까워서라도 트리의 탐색시간을 다시 O(logn)으로 만들어야한다. 그래서 나온 것이 AVL 트리이다. AVL 트리는 균형을 유지하는 알고리즘을 가지고 있는 균형 이진 트리이다. AVL 트리를 만든 아델슨 베스키와 E.M 랜디가 저렇게 트리가 편향되는 경우를 찾아보니 4가지 형태로 편향된다는 것을 찾았고 그 편향됨을 다시 고치는 방법 또한 만들었다. 따라서 AVL 트리는 편향된 트리를 고치는 4가지 방법 + 균형이 무너졌는지 알아내는 알고리즘을 가지고 있다. 

먼저 균형이 무너졌는지 알아내는 알고리즘을 알아보자 AVL 트리에서는 밸런스 팩터(Balance Facter)가 바로 이 것인데 밸런스 팩터는 왼쪽 서브 트리의 높이 - 오른쪽 서브트리의 높이 이다. 이 밸런스 팩터 값이 2이상이면 트리를 고치는 알고리즘이 작동한다. 

이제 균형이 무너지는 상태 4개와 고치는 방법 4개를 알아보자. 이진트리에서 균형이 무너지는 상태 LL, RR, LR, RL이 있다. 약간 복잡하니 심호흡 한번하고 보는게 좋다. 이것을 이해하면 그 복잡한 레드-블랙 트리도 쉽게 이해할 수 있다.

1. LL

위의 노드를 보면 71을 기준으로 왼쪽 왼쪽 이렇게 2개의 노드가 달려있는 것을 볼 수 있다. 참고로 사이트 오류인지 맨 마지막 노드의 숫자가 안보인다 넣은 숫자는 40이다.

아무튼 왼쪽 왼쪽 이렇게 2개 있으므로  LL이라고 부른다.

이를 해결하기 위해 LL회전이라는 것을 하는데 바로 무너진 지점을 루트로 보고 균형을 맞춘다.

즉 50이 루트가 되며 자동적으로 나머지 40은 왼쪽자식 71은 오른쪽 자식이 된다.

2.RR

이 역시 위의 기준과 같다. 그냥 대칭 구조일 뿐이다. 7을 루트로 만들어 주면 1은 왼쪽 자식 9는 오른쪽 자식이 된다.

3. LR

이번엔 복잡하다 정신 바짝 차리고 이해해보자.
이렇게 골때리는 형태로 있으면 일단 아는것은 LL와 RR 수리는 방법 뿐이요 그렇다면 그 방법을 쓰면 된다. 여기서 3의 오른쪽 자식에 NULL 노드를 붙이자 그러면 1,3,null 이렇게 RR편향이 된다. 그러면 고치면 1노드 자리에는 3이 들어가고 3노드 왼쪽에는 1이 있으며 오른쪽 자식은 NULL이다. 이제 NULL 노드를 떼면 다음과 같이 된다.
그렇다 LL 노드가 되었다 이제 LL 회전을 하면 다음과 같이 균형을 맞출 수 있다.

우린 답을 찾을 것이다 늘 그랬듯이...

4. RL
이제 균형을 어떻게 맞추는지 대략적으로 알았으므로 이번엔 실전 예제처럼 해보자 실제 트리에서는 자식 밑에 서브 트리가 주렁주렁 매달려 져 있는 경우가 있다.

AVL 트리의 시간 복잡도는 다음과 같다.

얼마나 외우기도 쉽고 아름다운가!

3. 구현

동적 프로그래밍은 어떤 답을 도출하기 위해 전에 구했던 답을 재활용하는 기법이다. 다음 동적 프로그래밍 실제 예제들을 모아보았다.

2. 예제

데이터베이스 설계에서 가장 중요한 개념 관계이다. 관계란 두 엔티티(테이블) 사이의 논리적인 관계를 말한다. 관계를 표현하는 변수는 차수와 선택성이 있다. 

차수란 두개의 엔티티간 관계에서 참여자의 수를 표현한 것을 말한다. 아래 예제의 선택성은 편의상 모두 필요(Mandatory)로 작성한다.

2.1. 차수의 종류

2.2.선택성

2.3. 관계의 종류

3. 구현

E = 엔티티 R = 관계 다이어그램은 시스템 엔티티 사이의 논리적인 관계와 상호작용(인터랙션)을 보이는 모델이다. ERD는 시스템에 대한 전체 뷰와 물리적 데이터 구조를 생성하기 위한 청사진을 제공한다.

릴레이셔널 문서를 참조해야 이해가 가능합니다.

먼저 시스템 분석 단계에서 파악한 엔티티 리스트를 작성하고 연결시킬 관계를 고안한다. ER-D를 그리는 방법은 여러가지가 있으나 보편적인 방법은
엔티티= 사각형
관계 = 다이아몬드
엔티티는 명사이며 관계는 동사이다.
또한 엔티티 옆에 숫자가 있는데 이것은 차수이다.



차량번호 한개는 차량 한대로 등록되어 있다.
차량 한대는 차량번호 한개로 등록되어 있다.

회사 부서 한부서는 직원 여러명이 일을 한다.
직원 한명은 한 회사 부서에서 일을 한다.

학생 한명이 강의 여러개를 수강 신청한다.
강의 한개는 학생 여러명의 수강 신청이 있다.
사실 해석하다 보면 약간 관계의 말을 비틀어야하는 경우가 있는데 이것은 er-d는 영어권에서 발명이 되었기 때문에 한국 문법과 차이를 보이는 것이다. 사실 좀 더 까다로운 정의로 이러한 차이를 매꿀 수 있는데 그럴려면 기호학을 끌고 와야한다......