728x90

13. 웹 프로그래밍 설계 모델

13-1 웹 프로그래밍 구축하기 위한 설계모델

Model 1  :

 브라우저  ⇔  WAS(웹 어플리케이션 서버)  ⇔ 데이터 베이스

                    (JSP  ⇔ Service & DAO)

HTML에 java 태그를 동시 사용... 유지보수 어려움. 


Model 2  :

 브라우저  ⇔  WAS(웹 어플리케이션 서버)  ⇔  Model ⇔ 데이터 베이스

                    (Controller ⇔ Service ⇔ DAO)

                     View (JSP)

13-2 스프링 MVC 프레임워크 설계구조

브라우저 ⇔ DispatcherServlet ⇒ HandlerMapping

                                       ⇔  HandlerAdapter  ⇔ Controller

      ⇒View(jsp)                          ⇒ 브라우저

      ⇒ ViewResolver : 처리 결과를 출력할 view 선택     


사진 출처 : http://wondongho.tistory.com/59    

 

 13-3 DispatcherServlet 설정

web.xml 서플릿을 맴핑

스프링 설정파일 있으면(servlet-context.xml) 맵핑 하여--> 스프링 컨테이너생성 : HanderMapping, HandlerAdapter, ViewResolver

초기화 파라메터에서 스프링 설정 파일 지정하지 않은경우 서블릿 별칭( appServlet-context.xml)을 이용 --> 스프링 컨테이너 생성 : HanderMapping, HandlerAdapter, ViewResolver

13-4. Controller 객체 @Controller

DispatcherServlet  ⇔  HandlerAdapter ⇔ Controller

servlet-context.xml  :   

<annotation-driven/>

 @Controller

public class HomeContoller{}


13-5 Controller 객체  @RequestMapping

DispatcherServlet  ⇔  HandlerAdapter ⇔ Controller

@RequestMapping("/success")

public String success(Model model){

     return "success";

13-6 Controller 객체  Model 타입의 파라메터

DispatcherServlet  ⇔  HandlerAdapter ⇔ Controller

@RequestMapping("/success")

public String success(Model model){

model.setAttribute("tempData", "model has data!!");

     return "success";


: 개발자는 Model 객체에 데이터를 담아서 DispatcherServlet 에전달가능

: DispatcherServlet에 전달된 Model 데이터는 View 에서 가공되어 클라이언트에게 응답처리


13-7. View 객체

DispatcherServlet  ⇔  HandlerAdapter ⇔ Controller

<!-- Resolves views selected for rendering by @Controllers to .jsp resources in the /WEB-INF/views directory -->

<beans:bean class="org.springframework.web.servlet.view.InternalResourceViewResolver">

<beans:property name="prefix" value="/WEB-INF/views/" />

<beans:property name="suffix" value=".jsp" />

</beans:bean>

:: 리턴값을 갖고 viewResolver 설정 값을 합쳐서 jsp를 만들어줌. 


13-8. 전체적인 웹 프로그래밍 구조

브라우저: 최초 사용자 요청 ex) ip/cho4/sucess

 ⇒ DispatcherServlet  

⇔  Controller :  @Controller 적용 클래스 검색

⇔  @RequestMapping("success") :사용자 요청 해당 메서드 실행

⇒ ViewResolver : 처리 결과를 출력할 view 선택     

⇒ View : 브라우저에 JSP 응답

14. 스프링 MVC 웹서비스

14-1. 웹 서버(Tomcat)다운로드

현재 실무에서 7, 8 주로사용
Binary Distributions > Core: >zip (pgp, sha512)

14-2. 웹 서버(Tomcat)와 이클립스 연동

Tomcat 더블클릭
Server Location > Use Tomcat Installation ( Takes control of Tomcat Installation)
Server Options > Publish module contexts to seprate XML files
Ports > HTTP/1.1    8090   (Oracle 8080 을 써서 임의 변경)

cf) 톰캣 재설치 불가 가이드 : http://linguist79.tistory.com/24

http://localhost:8090/  or  http://127.0.0.1:8090/   접속

14-3. 이클립스 STS (String Tool Suit) 설치

Eclips Marketspace > sts  설치

14-4. STS를 이용한 웹 프로젝트 생성

Spring Legacy Projedt 생성
Spring MVC Project 선택

패키지명 등록

프로젝트 명등록
com.drengneer.spring   -->접속주소 : http://localhost:8090/spring/

14-5. 스프링 MVC 프레임워크를 이용한 웹 프로젝트 분석


15. 스프링 MVC 웹서비스2

15-1. 프로젝트 전체구조

webapp: 웹과 관련된 파일 : 스프링 설정파일, jsp, HTML, 등
resources: JSP 파일을 제외한 HTML, css, js 파일등 위치
spring 폴더 스프링 컨테이너를 생성하기 위한 스프링 설정파일이 위치
views. jsp 파일
pom.xml 메인 레파지토리에서 프로젝트에 필요한 라이브러리를 내려받기 위한 메이븐 설정파일

15-2. web.xml

<servlet>

<servlet-name>appServlet</servlet-name>

<servlet-class>org.springframework.web.servlet.DispatcherServlet</servlet-class>

<init-param>

<param-name>contextConfigLocation</param-name>

<param-value>/WEB-INF/spring/appServlet/servlet-context.xml</param-value>

</init-param>

<load-on-startup>1</load-on-startup>

</servlet>

<servlet-mapping>

<servlet-name>appServlet</servlet-name>

<url-pattern>/</url-pattern>

</servlet-mapping> 

15-3. DispatcherServlet

웹 어플리케이션 최초 사용자의 요청이 발생되면 DispatcherServlet이 사용자의 요청을 받는다. 
따라서 DispatcherServlet을 서블릿으로 등록해주는 과정을 설정해주어야 하고 요청을 받기 위해 서블릿 맵핑 경로는 "/" 로 설정

브라우저 ⇔ DispatcherServlet ⇒ HandlerMapping

                                       ⇔  HandlerAdapter  ⇔ Controller

      ⇒ ViewResolver  ⇒View(jsp)                          ⇒ 브라우저


HandlerMapping : 컨트롤러 검색

HandlerAdapter : 메서드 실행요청

Model And View 객체 이용 

15-4. servlet-context.xml

<annotation-driven />  : 어노테이션 사용을 위한 태그

<resources mapping="/resources/**" location="/resources/" /> : 리소스   : index.html, common.css...

<beans:bean class="org.springframework.web.servlet.view.InternalResourceViewResolver">
<beans:property name="prefix" value="/WEB-INF/views/" />
<beans:property name="suffix" value=".jsp" />
</beans:bean>
<context:component-scan base-package="com.drengineer.spring" /> : 패키지 이름

15-5. Controller

15-6. View


16. STS를 이용하지 않은 웹 프로젝트

16-1. 스프링 MVC 웹 에플리케이션 제작을 위한 폴더 생성

16-2. pom.xml 및 이클립스 import

16-3. web.xml

16-4. 스프링설정파일(servlet-context.xml)생성

16-5. root-context.xml 작성

16-6. 컨트롤러와 뷰 작성

16-6. 실행


17. Service & DAO 객체 구현

17-1. 웹 어플리케이션 준비

17-2. 한글 처리

  <!-- 한글설정 -->

<filter>

<filter-name>encodingFilter</filter-name>

<filter-class>org.springframework.web.filter.CharacterEncodingFilter</filter-class>

<init-param>

<param-name>encoding</param-name>

<param-value>UTF-8</param-value>

</init-param>

<init-param>

<param-name>forceEncoding</param-name>

<param-value>true</param-value>

</init-param>

</filter>


<filter-mapping>

<filter-name>encodingFilter</filter-name>

<url-pattern>/*</url-pattern>

</filter-mapping>

<!-- //한글설정 -->

17-2. 서비스 객체 구현

서비스 빈생성

//@Component

//@Repository

@Service


빈연결

// MemberService memberService  = new MemberService();

// @Autowired  스프링 전용, 타입으로 지정

// @Inject     자바 전용, 타입으로 지정

@Resource(name="memberService")  //자바전용 이름으로 지정, java 8부터  설정이 바뀌어 annotation 임포트 여부 확인 필요

18. Controller 객체 구현

18-1. 웹 어플리케이션 준비

18-2. @RequestMapping을 이용한 URL 맵핑

@RequestMapping("/member")
public class MemberController {


@RequestMapping(value = "/memberJoin", method = RequestMethod.POST)
public String memberJoin(Model model, HttpServletRequest request, Member member) {

18-3. 요청 파라메터

//      Member member = new Member();

// member.setMemberId(request.getParameter("memberId"));

// member.setMemberPhone2(request.getParameter("memberPhone1"));


// @RequestParam(value = "memberId", required = true) String memberId,

// @RequestParam(value = "memberId", required = false, defaultValue = "010") String memberPhone1

// member.setMemberId(memberId);

// member.setMemberPhone1(memberPhone1);

1. 멤버 커맨드 객체이용

public String memberJoin(Model model, HttpServletRequest request, Member member) {  

2.  중첩 커맨드 객체이용

PHONE: <input type="text" name="phoneList[0].memberPhone1"/>-

<input type="text" name="phoneList[1].memberPhone3"/>

19. Controller 객체 구현

19-1. @ModelAttribute

1. 닉네임 기능 : java 코드에서는 member로 사용하고 jsp 에 mem으로 사용

public String memberJoin(@ModelAttribute("mem") Member member) { // Member :: 커멘드 객체


2.  공통실행 기능
@ModelAttribute("serverTime")
public String getServicerTime(Locale locale) {
Date date = new Date();
DateFormat dateFormat = DateFormat.getDateTimeInstance(DateFormat.LONG, DateFormat.LONG, locale);
return dateFormat.format(date);
}

 

19-2. Model  @ ModelAndView

Model 은 view에 데이터만 전달하기위한 개게
Model And View 데이터 뷰를 함께 전달   Model

  ModelAndView mav = new ModelAndView();

mav.addObject("memberIp", request.getRemoteAddr());

mav.setViewName("memberLoginOk");

return mav;






728x90




1. TISCH graduates, you made it! And you're fucked.




*  92 percent of Americans your age will ever know  당신 또래의 미국인 92퍼센트가 경험한
* dropout  중퇴자
* crush 으스러뜨리다. 
* workforce 노동자

오늘 자랑스러운 졸업식 날
여러분에게 새로운 문이 열릴 것입니다
평생에 걸친 거절의 문이죠
흔히 졸업생들이 말하는 현실입니다
아무도 피할 수 없습니다
네. 여러분은 망했어요
취업난이 심각합니다. 인내심을 가지세요
많은 학부모들은 4년간 자녀를 못 봤을지도 모릅니다
오늘부터 매일 보게 될 것입니다
와이파이가 안된다고 지하방에서 올라올테니까요
혹시 자녀가 순수예술이나 철학을 전공했다면
걱정하셔도 좋습니다
자녀들이 취업할 수 있는 유일한 곳은 고대 그리스일테니까요
제가 보장할 수 있는 건, 여러분은 피할 수 없다는 겁니다
무지 증오 인종차별 어리석음 하찮은 인간들.
이게 공평해 보이지 않을 수 있겠죠
그러나 인생은 절대로 공평했던 적이 없습니다
누구도 여러분을 위해 유리계단을 마련해 놓지 않습니다
전 백수였습니다
하지만 중요한 게 있습니다
전 그만두지 않았습니다
면접장을 나와 다음 오디션을 준비했죠. 그리도 다음 오디션을.
그리고 또 다음 오디션을.
간절히 기도했습니다
제가 12살 되던 해,
저희 아버지는 안전한 직장을 잃으셨습니다.(짐 캐리 아버지는 유명한 코미디언이 될 수 있었지만 안전한 직장 회계사를 택했다.)
아버지로부터 여러 훌륭한 교훈을 얻었습니다
그 중에서도 중요했던 한 가지는
하고 싶지 않은 일을 하면서도 실패할 수 있다는 것입니다
그러니 여러분 사랑하는 일에 도전하는 것이 낫습니다
죽음을 생각하는 건
무엇을 잃을지 모른다는 두려움에서 벗어나는 최고의 방법입니다
여러분은 죽을 몸입니다 그러니 다른 사람의 삶을 사려고 시간을 낭비하지 마세요
(남들의 생각 따위) 내 알바 아니야
절대로 내버려두지마. 실패의 두려움, 비교의 두려움, 남들의 시선이
너가 하는 위대한 일을 막지 않도록!
결국에는 우리 중 누구도 보통이 될 운명은 없습니다
우리는 모두 헤성이 되기 위해 태어났습니다
우주와 시간을 가로지리는 세상 모든것과 부딪힐 때 마다 우리만의 자국을 남기는
오늘 저는 여러분에게 말합니다
실패를 두려워하든 말든
실망스러운 일은 반드시 찾아올 것입니다
그러나 아름다운 것은 그 실망을 통해 스스로를 더 명확하게 볼 수 있으며
그로부터 나에 대한 강한 신념과 남다른 독창성이 함께 따라올 것입니다
비밀 하나 알려드리죠 시작할 때는 아무도 모릅니다
아이디어라는 것은 원래 완성 상태로 떠오르지 않습니다
오직 행동하는 과정에서만 명료해질 뿐입니다
그래서 지금 바로 시작하면 되는 겁니다
쉽진 않겠지만 명확하죠. 계속 나아가셔야 합니다.
정말 간단하죠?
아빠 ! 제가 항상 말했죠?
돌아와서 내 학위 받아 갈 거라고 ^^
졸업하신 여러분 모두를 응원합니다



728x90

1/10~12  공부 (그동안 못했던것)& 생각정리

13~일 이력서, 포트폴리오 작성

14일~ 이력서 작성 & 하고 싶은거 하기. 


매일할일 ... 

1. 영어(1h)

2. IT 상식 공부(1h)

3. 코딩(4h)

일 

월 

화 

수 

목 

금 

토 

 

 

 

 

1.10 

영어공부했음. 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 



코딩 관련. 

java 8 정리 제네릭 포함

스프링

css javascript 정리 

728x90

6. 의존객체 Dependency injection

- 배터리 일체형(특정 배터리 소멸시 장난감 사야함) vs 배터리 분리형(쓸때 마다 배터리를 넣음 or 처음에 배터리가 있고 추가로 set하여 사용)

- 스프링 설정파일(applicationContext.xml)


7. 다양한 의존 객체 주입

생성자, setter, list, map 타입 DI 방법이 있다. 

7-1 :생성자를 이용한 의존 객체 주입

메소드중 첫자가 대문자면 생성자. 

public StuduntRegisterService(StudentDao studentDao){

this.studentDao= studentDao;

}

<bean id="studentDao" class="ems.member.dao.studentDao"/>

<bean id="registerService" class="ems.member.service.StudentRegisterService">

<constructor-arg ref="studentDao"></constructor-arg>

</bean>

7-2 :setter를 이용한 의존객체 주입

set 뒤의 대문자를 소문자로 바꾸고 찾음. 

 public void setJdbcUrl(String jdbcUrl){

this.jdbcUrl = jdbcUrl;

}

public void setUserId(String userId){

this.userId = userId;

}

public void setUserPw(String userPw){

this.userPw = userPw;

}

 <bean id="dataBaseConnectionInfoDev" class="ems.member.DataBaseConnectionInfo">

<property name="jdbcUrl" value="jdbc:orclae:thin:@localhost:1521:xe"/>

<property name="userId" value="scott"/>

<property name="userPw" value="tiger"/>

</bean>

7-3 :List타입 의존 객체 주입

 public void setDevelopers(List<String> developers){

this.developers=developers;

}

 <property name="developers">

<list>

<value>Cheney.</value>

<value>Eloy.</value>

<value>Jasper.</value>

<value>Dillon.</value>

</list>

</property>

7-4 :Map타입 의존 객체 주입

public void setDevelopers(Map<String, String> administrators){

this.administrators=administrators;

}

<property name="administrators">

<map>

<entry>

<key>

<value>Cheney</value>

</key>

<value>cheny@springPjt.org</value>

//<ref bean=""> 빈주입도 가능. 

<entry>

<entry>

<key>

<value>Jasper</value>

</key>

<value>Jsper@springPjt.org</value>

<entry>

</property>


8. 스프링 설정파일 분리

applicationContext.xml  --> 분리 appCtx1.xml, appCtx2.xml, appCtx3.xml

8-1-1 MainClassUseXmls.java

String[] appCtxs = {

"classpath:appCtx1.xml",

     "classpath:appCtx2.xml",

     "classpath:appCtx3.xml"

};

GenericXmlApplicationContext ctx = new GenericXmlApplicationContext(appCtxs);

8-1-1 appCtximport.xml 연결후 xml 파일에 import

<import resource="classpath:appCtx1.xml"/> 

<import resource="classpath:appCtx2.xml"/> 

<import resource="classpath:appCtx3.xml"/> 


JVM 에서 어플리케이션을 실행할때. main 을 찾아서 실행.. 프로젝트를 실행시키면 메인 메소드 목록을 보여줌. 


8-2 빈(Bean) 범위

싱클톤 singleton : 1개만 생성되며  getBean() 메소드로 호출될 때 동일한 객체가 반환된다. 

             호출1 : getBean("A"), 호출2: getBean("B")   >> 같은 메모리 주소에 있는 객체 1개만 호출. 

프로토 타입 prototype: 싱글톤 범위와 반대의 개념, scope 속성으로 명시해 주면된다. 

<bean id="injectionBean" class="scope.ex.DependencyBean" />

<bean id="dependencyBean" class="scope.ex.DependencyBean" scope="prototype">

<constructor-arg ref="injectionBean"/> 

<property name="injectionBean" ref="injectionBean"/>

</bean>


9. 의존객체 자동 주입

9-1 의존객체 자동주입이란?

스프링 설정 파일에서 의존객체를 주입할 때 Constuctor-org 또는 property 태그로 의존대상 객체를 명시하지 않아도 

스프링 컨테이너가 자동으로 필요한 의존 대상을 찾아서 의존 대상 객체가 필요한 객체에 주입해 주는 기능

구현한 방법은 @Autowired, @Resource 어노테이션을 이용해서 쉽게 구현할 수 있다. 

9-2 @Autowired

프로퍼티, 메소드, 생성자에서 객체의 타입이 일치하는 객체를 자동으로 주입한다. 

*** 프로퍼티, 메소드에 @ autowired사용시에는 반드시 default 생성자를 명시해야 한다. 

ex) sevice 에서 dao java 코드 에서 연결.. 

wordRegisterService.java

//@Autowired

private WordDao wordDao;

@Autowired

public WordRegisterService(WordDao wordDao){

this.wordDao=wordDao;


//@Autowired

//public void setW  

<Context:annotation-config/>

<bean id="wordDao" class="com.word.dao.wordDao"/>

<bean id="registerService" class="com.word.service.wordRegisterService">

<!--<constructor-arg ref="wordDao"/>-->

</bean> 


9-3 @Resource

@Autowired : 스프링컨테이너에서 객체를 찾음. 개체가 엄청많고.. 필요한 데이터 타입을 찾아 알맞은 데이터 타입을 넣어줌 
- 생성자, 프로퍼티, 메소드, 객체의 타입(WordDao를 찾음)이 일치하는 객체를 자동으로 주입한다, 디폴트 생성자 명기

@Resouce  : 객체의 타입을 보지 않고 동일한 이름이 있는지 찾아씀.    

- 프로퍼티, 메소드 객체의 이름(wordDao1를 찾음)이 일치하는 객체를 자동으로 주입한다, 디폴트 생성자 명기

- 생성자에는 못씀. 

@Autowired

public WordRegisterService(WordDao wordDao1){

this.wordDao=wordDao;

}  


10 의존 객체 선택

10-1 의존 객체 선택

동일한 객체가 2개 이상인 경우 스프링컨테이너는 자동주입 대상 객체를 판단하지 못해서 Exception을 발생시킨다. 

@Autowired

@Qualifier("userDao")

private WordDao wordDao; 

 <bean id="wordDao" class="com.word.dao.WordDao">

<qualifier value="usedDao"/>  //퀄리 필러 : 예선통과자

</bean>

<bean id="wordDao2" class="com.word.dao.WordDao"/>

<bean id="wordDao3" class="com.word.dao.WordDao"/>


10-2 의존객체 자동주입 체크

@Autowired(required=false)

10-3 @Inject (java 기능)

@Autowired(spring 기능) 와 유사 의존객체 자동 주입 체크 못함 

@Named  : @Qualifier와 유사  , Qualifier와 달리 xml 작성 안해도 됨. 







728x90

스프링 프레임워크

DI, AOP, MVC, JDBC  : 구조 만들어 나가는 방법론들.

AOP : 관점지향 프로그래밍 : 주요부분만 작업 공통부분 뺐다 더했다. 


- 스프링프레임워크, 모바일 프레임워크(안드로이드)

내비게이션 없음 : 네비게이션 있음 = 다양한 업무 : 본연의 업무

프레임워크가 없다면 모든 기능을 다 만들어야 함.


-스프링 프레임워크 모듈: 과거에는 라이브러리를 직접 다운받았지만, XML 파일 등을 이용 의존설정 함.

스프링 프레임워크 모듈

 기능

 spring-core 

DI, IoC(Inversion of control, 제어의 역전) 기능 제공 

 spring-aop

AOP  

 spring-jdbc

데이터베이스를 적은양의 코드로 다룰 수 있는 기능 제공 

 spring-tx

트렌젝션 관련 기능제공 

 spring-webmvc 

스프링 제공 Controller, View 이용한 스프링 MVC 구현기능제공 


-스프링 컨테이너(IoC)

스프링에 객체를 생성하고 조립하는 컨테이너로 컨테이너를 통해 생성된 객체를 Bean 이라고 부른다. 

XML 문서로 객체 생성 및 속성 데이터 작성 > 스프링 컨테이너에서 객체 생성 및 조립 > 개발문서로 애플리케이션 구현

 

- 개발환경 구축: Java 설치(java.exe: JVM 구동명령, javac.exe: 컴파일러, java -version), 환경변수 설정, 이클립스 다운로드

JDK  ⊃ JRE  ⊃ API  ⊃ JVM


프로젝트 생성

-1. 프로젝트 생성 : Maven Project

Create a simple project(skip archetype selection) 선택

Use default Workspace location 선택

Group id :  내가 사용하고 있는 프로젝트를 감싸고 있는 전체 큰 프로젝트

Artifact id : 현재 해당하는 프로젝트

 >> pom.xml 파일생성  java, resouces 파일 생성 확인

-2. pom.xml 작성

디펜시즈에 spring-context 추가

플러그인에 maven-compiler-plugin 추가. 

에러 : Project configuration is not up-to-date with : 메이븐 과 java의 버전이 맞지 않음.  >> 프로젝트 우클릭 > 메이븐>업데이트 프로젝트 

프로젝트 폴더 > src > main > java, resources

-3 pom.xml 파일의 이해

pom.xml 파일은 메이븐 설정파일로 메이븐은 라이브러리를 연결해주고 빌드를 위한 플랫폼이다. 

Maven Dependencies 폴더 :: 다운된 모듈들 다운. 

resources폴더 > applicationContext.xml :  스프링 컨테이너의 객체를 만들어줌 

                   > XML 파일 생성   : applicationContext.xml

                       Beans  ::  > <bean id="tWalk" class="testPjt.TranspotationWalk"/>

 java 코드  > GenericXmlApplicationContext ctx = new GenericXmlApplicationContext("classpath:applicationContext.xml");

                 TranspotationWalk transpotationWalk = ctx.getBean("tWalk", TranspotationWalk.class)

                 transpotation.move();

ctx.close();


또 다른 프로젝트 생성 방법

<bean/>














728x90

순환(Recursion) 알고리즘 : 재귀함수

- 모든 순환함수는 반복문(Iteration)으로 변경가능, 모든 반복문은 recursion으로 표현가능 

- 순환함수는 복잡한 알고리즘을 단순하고 알기 쉽게 표현하는 것을 가능하게 함, 하지만 오버해드가 있음(매개변수 전달, 엑티베이션 프레임 생성)

   (반복문에 비해 실행속도 불리, 경우에 따라 필요한경우도 있음)

-  순환함수가 되지 않기 위해 : 적어도 하나의 base case 존재,  Recursion을 반복하다보면 결국 base case로 수렴

- 암시적(implicit) 매개변수를 명시적(explicit) 매개변수로 바꾸어라


Factorial : n! 

0! = 1

n! = n x (n-1)! , n>0



Fibonacci Number

f0 = 0

f1=1

fn = fn-1 + fn-2   , n-1



Euclid Method : 최대공약수 

유클리드 방법 : 

m>=n 인 두 양수의 정수 m, n에 대해서 

m이 n 의 배수이면 gcd(m, n) =n 이고 그렇지 않으면  

gcd(m,n) = cde(n, m%n) 이다. 



Recursive Thinking : 순환적으로 사고하기

수학함수 뿐 아니라 다른 많은 문제들을 recursion으로 해결할 수 있다. 

문자열의 길이 계산

문자열 프린트

문자열 뒤집어 프린트

2진수로 변환하여 출력

배열데이터 정수들의 합


순환 알고리즘의 설계 DESIGNING RECURSION

- 암시적(implicit) 매개변수를 명시적(explicit) 매개변수로 바꾸어라

매개변수 암시화 : 순차탐색

// [0, n-1] 보통 생략... 즉 암시적인 매개변수  >>> 생략가능. 

매개변수의 명시화 : 순차탐색 

매개변수의 명시화 : 순차탐색 2

매개변수의 명시화 : 순차탐색 3

매개변수의 명시화 : 순차탐색 4

매개변수의 명시화 : 최대값 찾기

매개변수의 명시화 : 최대값 찾기 2

Binary Search : 이진검색








728x90

알고리즘의 분석 : 시간 복잡도

- 알고리즘의 자원(resource)  사용량을 분석 , cf)자원: 실행시간, 메모리, 저장장치, 통신, 등
- 실행시간의 분석에 대해서 다룸
  • 시간복잡도(time complexity)

- 연산의 실행 횟수를 카운트(실행시간 은 실행환경에 따라 달라짐)
- 연산 실행 횟수는 입력 데이터의 크기에 관한 함수로 표현
- 데이터의 크기가 같더라도 실제 데이터에 따라서 달라짐 
   ex) worst-case analysis vs average-case anaysis :최악의경우 시간복잡도, 평균 시간복잡도 
  • 점근적(Asymptotic) 분석

-  Θ-, Ο-: n→∞일때 수행시간이 증가하는 growth rate로 시간복잡도로 표현

- 상대적으로 간단하고 실행환경에 비의존적이여서 가장 광범위하게 사용

  1. 상수 시간 복잡도 - 시간복잡도 : O(1) 

     ex) n개 데이터 배열 n/2 번째 데이터 반환
  2. 선형 시간 복잡도 - 시간복잡도 : O(n)

    ex) n개 데이터 저장된 배열 sum
  3. 순차 탐색 최악의 경우 - 최악의 경우 시간복잡도 : O(n)

    ex) n개 데이터 저장된 배열 target 있는지 검색

    2차식(Quadratic) : - 최악의 경우 시간복잡도 : O(n^2)

    ex) n개 데이터 저장된 배열 X, n개 데이터 저장된 배열 Y, X[i]=Y[j]의 경우 n(n-1)/2
  • 점근적(Asymptotic) 표기법

-  알고리즘 포함된 연산들의 실행 횟수를 표기하는 하나의 기법, 최고차 항 차수만으로 표시

-  가장 자주 실행되는 연산, 문장의 실행횟수를 고려

  1. Ο-표기 :: upper bound를 표현 

     ex) f(n) = 32n^2 + 17n^2 -32 , f(n) <= cg(n)
  2. Ω-표기 :: lower bound를 표현 : 오메가

    ex)  f(n) = 32n^2 + 17n^2 -32 , f(n) >= cg(n)
  3. Θ-표기 :: upper bound & lower bound를 표현 :세타

    ex) f(n) = 32n^2 + 17n^2 -32 , 0 <= c2g(n) <= f(n) <= c2g(n)
   Big-O 

 O(1)

O(log n) 

O(n) 

O(n log n) 

O(n^2) 

O(n^3) 

O(2^n) 

O(n!) 

 Constant

 Logarithmic

 Linear

 Log Linear

 Quadratic

 Cubic

 Exponential

 Factorial

  • 다항시간(polynomial-time) 알고리즘

다항식일 때 사용. 

'For Real > 알고리즘' 카테고리의 다른 글

Backjoon1000_DrEngineer  (0) 2018.11.23
728x90

+ Recent posts