반응형

분류 전체보기 2934

P - NP 문제

안녕하세요. 언제나 휴일, 언휴예요. 이번에는 NP 완전(NP - Completeness) 이론에 관해 소개할게요. 1971년 스티븐 쿡(Steven Cook)과 1972년 리처드 카프(Richard Karp)는 논문을 통해 P-NP 문제를 꺼내들었죠. P는 Polynominal(다항) 시간에 문제를 풀수 있는 문제를 말해요. n 개의 자료가 있을 때 문제를 해결하는데 걸리는 시간을 n의 다항식(1, n, n^2 등)으로 표현할 수 있는 문제예요. 예를 들어 버블 정렬 알고리즘은 점근식 표기 O(n^2)으로 표현할 수 있어서 P 문제죠. 이와 같은 문제는 전산학에서 풀기 쉬운 문제 혹은 컴퓨터로 계산할 수 있는 문제라고 말합니다. NP는 문제 해결 방법을 찾는 것은 어렵지만 답을 제시했을 때 맞는지 틀리..

알고리즘 이야기

안녕하세요. 언제나 휴일, 언휴예요. 이번에는 알고리즘에 관한 이야기를 해 볼게요. 알고리즘은 9세기 페르시아 수학자 알콰리즈미(al khowarazmi)에서 시작하였다고 하네요. 알콰리즈미는 숫자를 상호 관계적인 개념으로 해석하면서 대수학의 아버지로 불리는 인물입니다. 그리고 본격적인 알고리즘은 유클리드(Euclid)의 호제법에서 출발했다고 합니다. 유클리드의 호제법은 다음과 같은 이론이예요. 자연수 a와 b가 있고 a ≥ b이고 a%b = r일 때 r이 자연수이면 GCD(a,b) = GCD(b,r) 이고 r이 0이면 GCD(a,b) = b 이다. ( GCD, Greatest Common Divisor) 예를 들어 a가 36, b가 24일 때 36 % 24 = 12 GCD(36, 24) = GCD(24..

[C++] 87. 최종 실습 - 소스 코드

[C++] 87. 최종 실습 - 소스 코드 68. 최종 실습 - 개발 공정 및 시나리오69. 최종 실습 - 요구 분석 및 정의70. 최종 실습 - 설계1(클래스 다이어그램)71. 최종 실습 - EHNARA 뼈대72. 최종 실습 - 프로토 타이핑73. 최종 실습 - 확장 가능한 순차 배열74. 최종 실습 - 클래스 추가하기75. 최종 실습 - 초기화 및 해제화76. 최종 실습 - 학생 생성77. 최종 실습 - 학생 이동78. 최종 실습 - 전체 보기79. 최종 실습 - 학생 복귀80. 최종 실습 - 강의 시작81. 최종 실습 - 도서관 가기82. 최종 실습 - 소등83. 최종 실습 - 거실로 가기84. 최종 실습 - 파티85. 최종 실습 - 노래방 가기86. 최종 실습 - 다이어그램 //ehglobal.h..

[C++] 86. 최종 실습 - 다이어그램

[C++] 86. 최종 실습 - 다이어그램이제까지 수행했던 최종 실습의 다이어그램을 다시 한 번 살펴보세요. [그림] EhNara의 유즈케이스 다이어그램 [그램] School의 유즈케이스 다이어그램 [그림] Village의 유즈케이스 다이어그램 [그림] Downtown의 유즈케이스 다이어그램 [그램] 클래스 다이어그램 [그림] 초기화 시퀀스 다이어그램 [그림] 해제화 시퀀스 다이어그램 [그림] 학생 생성 시퀀스 다이어그램 [그림] 학생 이동 시퀀스 다이어그램 [그림] 학교로 학생 이동 시퀀스 다이어그램 [그림] 전체보기 시퀀스 다이어그램 [그림] 학생 복귀 시퀀스 다이어그램 [그림] 강의 시퀀스 다이어그램 [그림] 도서관 가기 시퀀스 다이어그램 [그림] 소등 시퀀스 다이어그램 [그림] 거실로 가기 시퀀스..

[C++] 85. 최종 실습 - 노래방 가기

[C++] 85. 최종 실습 - 노래방 가기 이번에는 노래방 가기 기능에 관해 시퀀스 다이어그램을 작성하고 난 후에 구체적인 코드를 구현합시다. 노래방 가기에서는 학생을 선택하여 학생의 Sing을 수행합니다. 각 장소에서는 해당 장소에서 명령할 수 있는 기능만 보이게 한정하였기 때문에 IPlay 인터페이스 형식으로 학생 개체에 접근해야 합니다. 그리고 선택한 학생이 운동 학생이면 Dance 기능을 수행합니다. 물론 학생을 선택하기 위해서는 사용자에게 주민번호를 입력받아 컬렉션 내에 유닛과 비교하는 부분이 있어야 합니다. 이 부분은 이미 기반 클래스 Place에 구현하였기 때문에 이를 활용합니다.IPlay 인터페이스에 Sing 메서드를 순수 가상 메서드로 약속하세요.interface IPlay{ virtu..

[C++] 84. 최종 실습 - 파티

[C++] 84. 최종 실습 - 파티 이번에는 파티 기능에 관해 시퀀스 다이어그램을 작성하고 난 후에 구체적인 코드를 구현합시다. 파티 기능은 다운타운에 있는 모든 학생의 Drink을 수행합니다. 그런데 각 장소에서는 해당 장소에서 명령할 수 있는 기능만 보이게 한정하였기 때문에 IPlay 인터페이스 형식으로 학생 개체에 접근해야 합니다.그리고 IPlay 인터페이스에 Drink 메서드를 순수 가상 메서드로 약속하세요. interface IPlay { virtual void Drink()=0; }; 다운타운의 Party 기능을 구현합시다. void Downtown::Party()//파티 { cout

[C++] 83. 최종 실습 - 거실로 가기

[C++] 83. 최종 실습 - 거실로 가기 이번에는 거실로 가기 기능에 관해 시퀀스 다이어그램을 작성하고 난 후에 구체적인 코드를 구현합시다. 거실로 가기에서는 학생을 선택하여 학생의 Relax를 수행하게 합니다. 각 장소에서는 해당 장소에서 명령할 수 있는 기능만 보이게 한정하였기 때문에 IRelax 인터페이스 형식으로 학생 개체에 접근해야 합니다. 그리고 선택한 학생이 마법 학생이면 Travel 기능을 수행하게 합시다. 물론 학생을 선택하기 위해서는 사용자에게 주민번호를 입력받아 컬렉션 내에 유닛과 비교하는 부분이 있어야 합니다. 이 부분은 이미 기반 클래스 Place에 구현하였기 때문에 이를 활용합니다.IRelax 인터페이스에 Relax 메서드를 순수 가상 메서드로 약속하세요.interface I..

[C++] 82. 최종 실습 - 소등

[C++] 82. 최종 실습 - 소등 이번에는 소등 기능에 관해 시퀀스 다이어그램을 작성하고 난 후에 구체적인 코드를 구현합시다. 소등 기능은 주거지에 있는 모든 학생의 Sleep을 수행하게 합니다. 그런데 각 장소에서는 해당 장소에서 명령할 수 있는 기능만 보이게 한정하였기 때문에 IRelax 인터페이스 형식으로 학생 개체에 접근해야 합니다.그리고 IRelax 인터페이스에 Sleep 메서드를 순수 가상 메서드로 약속하세요. interface IStudy { virtual void Sleep()=0; }; 주거지의 TurnOff 기능을 구현합시다. void Village::TurnOff()//소등 { cout

[C++] 81. 최종 실습 - 도서관 가기

[C++] 81. 최종 실습 - 도서관 가기 이번에는 도서관 가기 기능에 관해 시퀀스 다이어그램을 작성하고 난 후에 구체적인 코드를 구현합시다. 도서관 가기에서는 학생을 선택하여 학생의 Study를 수행하게 합니다. 각 장소에서는 해당 장소에서 명령할 수 있는 기능만 보이게 한정하였기 때문에 IStudy 인터페이스 형식으로 학생 개체에 접근해야 합니다. 그리고 선택한 학생이 학사 학생일 때는 Reading 기능을 수행하게 합시다. 물론 학생을 선택하기 위해서는 사용자에게 주민번호를 입력받아 컬렉션 내에 유닛과 비교하는 부분이 있어야 합니다. 이 부분은 이미 기반 클래스 Place에 구현하였기 때문에 이를 활용합니다.IStudy 인터페이스에 Study 메서드를 순수 가상 메서드로 약속하세요.interfac..

[C++] 80. 최종 실습 - 강의 시작

[C++] 80. 최종 실습 - 강의 시작 이번에는 강의 시작 기능에 관해 시퀀스 다이어그램을 작성하고 난 후에 구체적인 코드를 구현합시다. 강의 시작 기능은 학교에 있는 모든 학생의 ListenLecture를 수행하게 합니다. 그런데 각 장소에서는 해당 장소에서 명령할 수 있는 기능만 보이게 한정하였기 때문에 IStudy 인터페이스 형식으로 학생 개체에 접근해야 합니다.모든 장소에는 기반 클래스인 Place에 학생을 보관하는 컬렉션이 있습니다. 따라서 파생 형식인 각 장소에서 학생 개체에 접근하기 위해 컬렉션에 보관한 학생 수와 특정 인덱스의 학생 개체를 구하는 메서드를 제공하세요. class Place { ...중략... protected: ...중략... size_t GetCount()const;/..

반응형