가즈아아아 꾸준히

Entity먼저 데이터베이스에 저장하기 위해 유저가 정의한 클래스가 필요한데 그런 클래스를

Entity라고 한다. Domain이라고 생각하면 된다.

일반적으로 RDBMS에서 Table을 객체화 시킨 것으로 보면 된다.

그래서 Table의 이름이나 컬럼들에 대한 정보를 가진다.

/**
* Created by Itner on 2017. 7. 20..
*/

@Entity
public class Member {
@Id
@GeneratedValue(strategy= GenerationType.AUTO)
private long id;

@Column
private String name;

@Column
private int age;

public long getId() {
return id;
}

public void setId(long id) {
this.id = id;
}

public String getName() {
return name;
}

public void setName(String name) {
this.name = name;
}

public int getAge() {
return age;
}

public void setAge(int age) {
this.age = age;
}
}

@Id

primary key를 가지는 변수를 선언하는 것을 뜻한다. @GeneratedValue 어노테이션은 해당 Id 값을

어떻게 자동으로 생성할지 전략을 선택할 수 있다. 여기서 선택한 전략은 "AUTO"이다.

@Table

별도의 이름을 가진 데이터베이스 테이블과 매핑한다. 기본적으로 @Entity로 선언된 클래스의 이름은 실제

데이터베이스의 테이블 명과 일치하는 것을 매핑한다. 따라서 @Entity의 클래스명과 데이터베이스의 테이블명이

다를 경우에 @Table(name=" ")과 같은 형식을 사용해서 매핑이 가능하다.

@Column

@Column 선언이 꼭 필요한 것은 아니다. 하지만 @Column에서 지정한 변수명과 데이터베이스의 컬럼명을

서로 다르게 주고 싶다면 @Column(name=" ") 같은 형식으로 작성하면 된다.

그렇지 않은 경우에는 기본적으로 멤버 변수명과 일치하는 데이터베이스 컬럼을 매핑한다.

Repository

Entity클래스를 작성했다면 이번엔 Repository 인터페이스를 만들어야 한다.

스프링부트에서는 Entity의 기본적인 CRUD가 가능하도록 JpaRepository 인터페이스를 제공한다.

/**
* Created by Itner on 2017. 7. 20..
*/

public interface MemberRepository extends JpaRepository<Member, Long> {

}

Spring Data JPA에서 제공하는 JpaRepository 인터페이스를 상속하기만 해도 되며,

인터페이스에 따로 @Repository등의 어노테이션을 추가할 필요가 없다.

JpaRepository를 상속받을 때는 사용될 Entity 클래스와 ID 값이 들어가게 된다.

즉, JpaRepository<T, ID> 가 된다.

그렇게 JpaRepository를  단순하게 상속하는 것만으로 위의 인터페이스는 Entity 하나에 대해서

아래와 같은 기능을 제공하게 된다.

위의 기본기능을 제외한 조회 기능을 추가하고 싶으면 규칙에 맞는 메서드를 추가해야한다.

/**
* Created by Itner on 2017. 7. 20..
*/

public interface MemberRepository extends JpaRepository<Member, Long> {

Member findByName(String name);

Page<Member> findByName(String name, Pageable pageable);
}

위와 같이 Query 메소드를 추가하여 스프링에게 알릴 수 있다.

그러기위해서는 규칙에 맞는 메서드를 작성해야 하는데, 그 규칙은 다음과 같다.

위의 findBy에 이어 해당 Entity 필드 이름을 입력하면 검색 쿼리를 실행한 결과를 전달한다.

SQL의 where절을 메서드 이름을 통해 전달한다고 생각하면 된다.

메서드의 반환형이 Entity 객체이면 하나의 결과만을 전달하고, 반환형이 List라면 쿼리에 해당하는

모든 객체를 전달한다. 

Query 메소드에 포함할 수 있는 키워드는 다음과 같다.

좀 더 자세한 키워드와 쿼리를 보고 싶다면 JPA 레퍼런스를 참고하면 된다.

>> http://docs.spring.io/spring-data/jpa/docs/1.10.1.RELEASE/reference/html/#jpa.sample-app.finders.strategies

Pageable

위 코드 중 한가지 설명이 빠진 것이 있는데, 바로 Pageable이다.

Query 메소드의 입력변수로 위와 같이 Pageable 변수를 추가하면 Page타입을 반환형으로 사용할 수 있다.

Pageable 객체를 통해 페이징과 정렬을 위한 파라미터를 전달한다.

Pageable 입력 변수는 아래와 같이 Controller에서부터 전달받아야 한다.

/**
* Created by Itner on 2017. 7. 20..
*/

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

@Autowired
MemberService memberService;

@RequestMapping("")
Page<Member> getMembers(Pageable pageable){
return memberService.getList(pageable)
}
}

위와 같이 작성된 Pageable에서는 다음과 같은 파라미터를 자동 수집한다.

아래는 위 Controller를 통해 HTTP요청으로 페이징과 정렬된 데이터를 전달받는 URI 샘플이다.

GET /users?page=1&size=10&sort=createdAt,desc&sort=userId,asc

이렇게 웹 페이지 개발에 필수적인 정렬과 페이지 정보를 접속 URI에서부터 Repository까지 바로 전달이 가능하다.

1. JPA(Java Persistence API)?

RDBMS 와 OOP 객체 사이의 불일치에서 오는 패러다임을 해결하기 위해

자바는 ORM(Object-Relational Mapping) 기술을 만들어 냈다.

문자 그대로 ORM 은 객체와 RDBMS 를 매핑하는 역할을 한다.

ORM 기술을 구현하기 위해 만들어져 사용되어 온 프레임워크가 Hibernate 이고,

시간이 지나면서 Hibernate 이외에도 ORM 기술을 구현하는 프레임워크(TopLink, CoCobase) 가 등장하였다.

그리고 이런 ORM 기술을 구현한 프레임워크에 대한 표준화가 이루어 졌는데,

그 결과로 만들어진 것이 JPA 인 것이다.

JDBC API 가 어플리케이션과 DMBS 사이에서 인터페이스 역할을 해 주기 때문에,

개발자는 사용할 DB 의 드라이버만 변경해 주면 되는 것처럼,

(DB 드라이버는 JDBC 표준에 맞추어 DB 관련 처리가 구현되어 있고, DB 드라이버는 각 DB 회사가 알아서 만들어 놓았다)

개발자는 ORM 을 기술을 사용할 때, JPA 인터페이스에 맞추어 구현되어 있는 

Hibernate, TopLink, CoCoBase 프레임워크 중 골라서 사용하면 된다.

만약, JPA 같은 표준 인터페이스가 없다면, 

ORM 기술을 사용하기 위한 Hibernate, TopLink, CoCoBase 의 필드와 메소드가 다를 것이다.

같은 기능을 가지는 메소드인데 Hibernate 에서는 냥냥고고( ), TopLink 에서는 멍멍고고( )로 정의되어 있다면,

사용하는 개발자가 ORM 프레임워크를 변경해야 할 때 난감할 것이다.

그래서 JPA API 가 이 기능은 통일해서 냥이최고( ) 로 구현하라고 강제하는 것이다(인터페이스의 중요 기능).

ORM 프레임워크를 사용하면 개발자가 객체를 데이터베이스에 저장할 때 SQL을 직접 작성할 필요 없이,

자바 컬렉션에 저장하는 것처럼 ORM 프레임워크에 저장하면 된다.

객체를 받은 ORM 프레임워크는 저장된 자바 객체를 분석해서 적절한 SQL을 생성하고 데이터베이스에 저장시킨다.  

2. 영속성(Persistence)

(1) Entity Class

엔티티 클래스는 자바 클래스에 @Entity 어노테이션을 붙여, 테이블과 매핑한다고 JPA 에게 알려주는 클래스다.

그리고 엔티티 클래스에서 만들어진 객체를 엔티티라고 한다.

(2) 영속성 컨텍스트(Persistence Context)

영속성 컨텍스트는 엔티티 클래스에서 만들어지는 엔티티를 영구 저장하고 관리하는 환경이다.

영속성 컨텍스트 와 관련한 엔티티의 4가지 상태

 ① 비영속(new/transient) - 엔티티 객체가 만들어져서 아직 저장되지 않은 상태로, 영속성 컨텍스트와 전혀 관계가 없는 상태

 ② 영속(managed) - 엔티티가 영속성 컨텍스트에 저장되어, 영속성 컨텍스트가 관리할 수 있는 상태

 ③ 준영속(detached) - 엔티티가 영속성 컨텍스트에 저장되어 있다가 분리된 상태로, 영속성 컨텍스트가 더 이상 관리하지 않는 상태

 ④ 삭제(removed) - 엔티티를 영속성 컨텍스트와 데이터베이스에서 삭제

영속성 컨텍스트의 특징

 ① 영속성 컨텍스트는 엔티티를 식별자 값(@Id로 테이블의 기본키와 매핑한 필드 값)으로 구분한다. 

     그렇기 때문에 영속 상태는 식별자 값이 반드시 있어야 한다.

 ② 영속성 컨텍스트에 엔티티를 저장하면 바로 데이터베이스에 저장되는 것이 아니라, 1차 캐시에 엔티티를 생성하고,

     쓰기 지연 SQL 저장소에 쿼리문을 생성해서 저장한다. 이렇게 쌓인 쿼리문은 flush( )가 실행될 때 데이터베이스에 반영된다.

(3) 엔티티 생성

1. 자바 어플리케이션에서 어떤 엔티티가 만들어져서 JPA에게 데이터베이스 저장을 부탁하면,

2. 만들어진 엔티티는 1차적으로 영속성 컨텍스트에 저장된다. 1차 캐시 정도라고 생각하면 된다.

   그리고, 저장한 엔티티를 데이터베이스에 저장하기 위한 쿼리문을 생성시켜 쓰기 지연 SQL 저장소에  저장한다.

   계속해서 엔티티를 넘기면 엔티티들과 쿼리문들은 차곡차곡 영속성 컨텍스트에 저장된다.

3. 그러다가 자바 어플리케이션에서 커밋 명령이 내려지면 영속 컨텍스트에는 자동으로 flush( )가 호출되고,

4. 영속성 컨텍스트의 변경내용을 데이터베이스와 동기(flush)화 한다(SQL 저장소의 쿼리를 실행시킨다).

5. 마지막으로 데이터베이스에게 commit 쿼리문을 명령한다.

(4) 엔티티 조회 

1. 자바 어플리케이션에서 JPA에게 데이터베이스 조회를 부탁하면,

   1차적으로 영속성 컨텍스트에서 엔티티를 찾는다. 

2. 있으면 자바 어플리케이션에 엔티티를 넘긴다.

3. 영속성 컨텍스트에 없는 엔티티 조회를 부탁하면

4. 쿼리문을 사용해 데이터베이스에서 찾아와 

5. 영속성 컨텍스트에 엔티티로 저장하고

6. 자바 어플리케이션에 그 엔티티를 넘긴다.

(5) 엔티티 변경

JPA는 엔티티를 영속성 컨텍스트에 보관할 때, 최초의 상태를 복사해서 저장해 두는데,

이것을 스냅샷이라 한다.

1. 자바 어플리케이션에서 커밋 명령이 들어오면, 영속 컨텍스트에는 자동으로 flush( )가 호출되고,

2. 엔티티와 스냅샷을 비교해서 변경된 엔티티를 찾는다.

3. 변경된 엔티티가 있으면 데이터베이스에 변경사항을 저장하기 위해 쿼리를 생성하고,

4. 영속성 컨텍스트의 변경내용을 데이터베이스와 동기(flush)화 한다(SQL 저장소의 쿼리를 실행시킨다).

5. 마지막으로 데이터베이스에게 commit 쿼리문을 명령한다.

이렇게 엔티티의 변경사항을 데이터베이스에 자동으로 반영하는 기능을 변경감지(Dirty Checking)이라 한다.

(6) 엔티티 삭제

앞의 과정과 마찬가지로, 자바 어플리케이션에서 엔티티 삭제 명령이 들어오면,

엔티티를 찾고 쓰기 지연 SQL 저장소에 delete 쿼리를 생성한다.

그리고 자바 어플리케이션에서 커밋 명령이 들어오면, 자동으로 flush( )가 호출되고,

영속성 컨텍스트의 변경내용을 데이터베이스와 동기(flush)화 한다(SQL 저장소의 쿼리를 실행시킨다).

마지막으로 데이터베이스에게 commit 쿼리문을 명령한다. 

3. JPA 메소드

(1) flush( )

영속성 컨텍스트의 변경 내용을 데이터베이스에 반영한다.

실행되었을 때 일어나는 일

  ① 변경 감지가 동작해서 영속성 컨텍스트에 있는 모든 엔티티를 스냅샵과 비교해서 수정된 엔티티를 찾고,

      수정된 엔티티를 데이터베이스에 반영하기 위해 수정 쿼리를 생성하여 지연 SQL 저장소에 등록

  ② 쓰기 지연 SQL 저장소의 쿼리를 데이터 베이스에 전송(등록, 수정, 삭제 쿼리)

보통 직접 사용하지 않고, 자바 어플리케이션에서 커밋 명령이 들어왔을 때, 자동으로 실행된다.

(2) detach( )

특정 엔티티를 준영속 상태로 만든다. 

준영속 상태가 된 엔티티는 더이상 영속 컨텍스트의 관리를 받지 않으며,

영속 컨텍스트가 지원하는 어떤 기능도 동작하지 않게 된다.

영속 상태가 영속성 컨텍스트로에게 관리(managed)되는 상태라고 하면,

준영속 상태는 영속성 컨텍스트로부터 분리(detached)된 상태이다.

(3) clear( )

영속성 컨텍스트를 초기화 한다.

영속성 컨텍스트의 모든 엔티티를 준영속 상태로 만든다.

(4) close( )

영속성 컨텍스트를 종료한다.

영속성 컨텍스트가 관리하던 영속 상태의 엔티티가 모둔 준영속 상태가 된다.

영속 상태의 엔티티는 주로 영속성 컨텍스트가 종료되면서 준영속 상태가 된다.

개발자가 직접 준영속 상태로 만드는 일은 거의 없다.

(5) merge( )

준영속 상태의 엔티티의 특징

 ① 거의 비영속 상태에 가깝다. 영속성 컨텍스트가 관리하지 않으므로 영속성 컨텍스트가 제공하는 어떠한 기능도 동작하지 않는다.

 ② 식별자 값을 가지고 있다. 비영속 상태의 엔티티는 식별자(엔티티를 구분하기 위한 유일한 값, ID)를 가지지 않고 있을 수도 있지만,

     준영속 상태는 이미 한 번 영속 상태였기 때문에, 식별자 값을 가지고 있다.

merge( )는 준영속 상태의 엔티티를 이용해서 새로운 영속 상태의 엔티티를 반환한다.

실행되었을 때 일어나는 일

 ① 파라미터로 넘어온 준영속 엔티티의 식별자 값으로 1차 캐시에서 엔티티를 조회

     (1차 캐시에 엔티티가 없으면 데이터베이스에서 엔티티를 조회하고 1차 캐시에 저장)

 ② 조회한 영속 엔티티에 준영속 엔티티의 값을 채워 넣는다.

 ③ 생성된 새로운 영속 엔티티를 반환한다.

새롭게 생성된 영속 상태의 엔티티를 가지고 이제 영속성 컨텍스트가 지원하는 기능을 사용할 수 있다.

준영속 상태의 엔티티를 영속 상태로 변경하는 것이 아니라, 새로운 영속 상태의 엔티티를 만들어서,

준영속 상태의 엔티티 값을 영속 상태의 엔티티에 채워 넣어서 반환하는 점에 주의해야 한다.

그리고, 준영속 뿐만 아니라, 비영속 상태의 엔티티도 병합하여 새로운 영속 상태의 엔티티를 만들어 반환한다.

자세한 내용은 위의 엔티티 변경 참조.

(6) find( )

식별자 값을 가지고 엔티티를 찾아서 반환한다.

자세한 내용은 위의 엔티티 조회 참조

(7) persist( )

자바 어플리케이션에서 생성된 엔티티를 영속성 컨텍스트와 데이터베이스에 저장한다.

자세한 내용은 위의 엔티티 생성 참조

(8) remove( )

식별자 값을 가지고 엔티티를 찾아서 삭제한다.

자세한 내용은 위의 엔티티 삭제 참조

출처: https://tinkerbellbass.tistory.com/24 [Welcome to NeverLand]

1. 프로젝트의 pom.xml에 lombok 의존성 추가 (필요한 버전이 있다면 버전을 표시)

view rawlombokPom.xml hosted with ❤ by GitHub

2. lombok.jar가 다운로드된 경로로 가서  shift+우클릭 -> 여기서 명령 창 열기(W) 클릭 하면 다음과 같이 cmd 창이 뜸

3, lombok.jar를 실행

  - 더블클릭으로 실행이 안되면, java -jar lombok-1.16.10.jar 를 입력

4. Installer 화면이 나오면 

  - Specify location...을 클릭

  - eclipse 폴더에서 실행파일 선택

  - Install / Update 클릭

  - 프로젝트에 lombok.jar를 추가하는 것을 잊지말고, eclipse 재시작을 해야하고, -vm parameter로 -vmargs -javaagent: lombok.jar가 추가 되었다는 메시지가 나옴

 - eclipse 폴더에 있는 STS.ini  (혹은 eclipse.ini) 파일을 열어 보면 마지막에 두줄이 추가 되어 있는 것을 확인 가능

?

5. eclipse를 재시작

6. 다음과 같이 @Data를 추가하였을 때, 자동으로 getter, setter, Constructor 등이 추가 되었음을 확인 할 수 있다.

(코드상으로는 나타나지 않음!)

출처: https://countryxide.tistory.com/16 [배워서 남주자]

Spring MVC 라이프 사이클을 이해하는 것이 개발의 기본이 되리라 생각한당~

http://terasolunaorg.github.io/guideline/1.0.1.RELEASE/en/Overview/SpringMVCOverview.html#id2

Client(브라우저)로 부터 요청(Request)을 받고 응답(Response)하기까지 Spring MVC의 처리 흐름은 위와 같다.

1. 먼저 브라우저로부터 요청이 들어오면 일단 Filter을 거치게 된다. Filter에서 하는 대표적인 처리를 보면 Encoding이 있다.

<Filter는 요청을 실질적으로 처리하기 전에 처리해야 될 부분을 담당>

2. 다음으로 DispatcherServlet이 Controller에 요청을 전달하기 전에 가로챈다. 요청을 가로챈 후 HandlerMapping을 통해 요청에 해당하는 적절한 Controller을 찾게 된다. 그리고 DispatcherServlet에 그것을 전달한다.

3. DispatcherServlet은 실행할 Controller 정보를 HandlerAdapter에 전달하게 된다.

4. HandlerAdapter는 해당 Controller을 호출하게 된다.

5. Controller에서는 전달된 요청을 처리한다. 예를 들어 게시판의 글 목록을 가져오는 요청을 받으면 Controller는 게시판 Service를 호출하고 Service에서는 DAO를 통해 게시판 글 목록을 가져오게 된다.  

요청을 처리한 후 그 결과를 Model에 담고, View의 이름을 HandlerAdapter에게 전달하게 된다.

6. 전달받은 View의 이름을 가지고 ViewResolver에서 매핑된 View를 찾아서 반환한다.

7. DispatcherServlet은 반환된 View를 넘기게 된다.

출처: https://all-record.tistory.com/164?category=733072 [세상의 모든 기록]

문제

항승이는 품질이 심각하게 나쁜 수도 파이프 회사의 수리공이다. 항승이는 세준 지하철 공사에서 물이 샌다는 소식을 듣고 수리를 하러 갔다.

파이프에서 물이 새는 곳은 신기하게도 가장 왼쪽에서 정수만큼 떨어진 거리만 물이 샌다.

항승이는 길이가 L인 테이프를 무한개 가지고 있다.

항승이는 테이프를 이용해서 물을 막으려고 한다. 항승이는 항상 물을 막을 때, 적어도 그 위치의 좌우 0.5만큼 간격을 줘야 물이 다시는 안 샌다고 생각한다.

물이 새는 곳의 위치와, 항승이가 가지고 있는 테이프의 길이 L이 주어졌을 때, 항승이가 필요한 테이프의 최소 개수를 구하는 프로그램을 작성하시오. 테이프를 자를 수 없고, 테이프를 겹쳐서 붙이는 것도 가능하다.

입력

첫째 줄에 물이 새는 곳의 개수 N과 테이프의 길이 L이 주어진다. 둘째 줄에는 물이 새는 곳의 위치가 주어진다. N과 L은 1,000보다 작거나 같은 자연수이고, 물이 새는 곳의 위치는 1,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 항승이가 필요한 테이프의 개수를 출력한다.

<출처> https://www.acmicpc.net/

상당히 쉬운 문제라고 생각이 든다.

알고리즘의 순서입니다.

1. 물이 새는 파이프를 입력 받으면서 bool 배열[파이프 번호]의 값을 true로 설정.
   1. 입력받은 파이프 번호 중 가장 큰 값을 변수에 저장해 놓는다.
2.  1부터 저장해 놓은 가장 큰 파이프 번호까지 for 문을 돌린다.
   1. bool 배열의 값이 true 이면 문제가 있는 파이프 이므로 int 변수에 테이프의 길이(L) -1 을 저장해 놓는다.
   2. 이후 테이프의 길이를 감소 시키면서 for 문을 진행한다
   3. 테이프의 길이가 1보다 작으면 테이프를 한번 붙인 것이므로, 다시 문제 있는 파이프를 찾는다.

<실행 코드>

#include<iostream>
#include<algorithm>
using namespace std;

int N, L, res;
bool ary[1001];
int main() {
	cin >> N >> L;
	int maxidx = 0;
	for (int i = 0; i < N; i++) {
		int a;
		cin >> a;
		ary[a] = true;
		if (a > maxidx) {
			maxidx = a;
		}
	}
	bool check = false;
	int tem = 0;
	for (int i = 1; i <= maxidx; i++) {
		if (tem  <1) {
			check = false;
		}
		if (!check&&ary[i]) {
			tem = L-1;
			res++;
			check = true;
			continue;
		}
		tem--;
	}
	cout << res << endl;
}

후기

다른 분들의 풀이를 보면 파이프를 int 배열에 입력을 받고 오름차순 정렬 후 테이프의 길이 만큼 bool 배열을 true로 만들며 고쳤다고 표시하는 방식을 사용하였다.

내가 한건 뭔가 가독성이 좋지 않아보인다..

나는 스터디 카페 정기권을 끊고 공부를 하고 있다.

근데 에어컨이 너무 춥다.. 내가 에어컨을 끄면 누가 다시 틀고 후우우우

추워 죽겠옹~~~

그래서 옷을 두껍게 입고 가는데 갈때는 더워 주글것 같다 

그래도 비싸지 않은 가격에 이용해서 만족~!

문제

기숙사에서 살고 있는 준규는 한 개의 멀티탭을 이용하고 있다. 준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등 여러 개의 전기용품을 사용하면서 어쩔 수 없이 각종 전기용품의 플러그를 뺐다 꽂았다 하는 불편함을 겪고 있다. 그래서 준규는 자신의 생활 패턴을 분석하여, 자기가 사용하고 있는 전기용품의 사용순서를 알아내었고, 이를 기반으로 플러그를 빼는 횟수를 최소화하는 방법을 고안하여 보다 쾌적한 생활환경을 만들려고 한다.

예를 들어 3 구(구멍이 세 개 달린) 멀티탭을 쓸 때, 전기용품의 사용 순서가 아래와 같이 주어진다면, 

1. 키보드
2. 헤어드라이기
3. 핸드폰 충전기
4. 디지털 카메라 충전기
5. 키보드
6. 헤어드라이기

키보드, 헤어드라이기, 핸드폰 충전기의 플러그를 순서대로 멀티탭에 꽂은 다음 디지털 카메라 충전기 플러그를 꽂기 전에 핸드폰충전기 플러그를 빼는 것이 최적일 것이므로 플러그는 한 번만 빼면 된다. 

입력

첫 줄에는 멀티탭 구멍의 개수 N (1 ≤ N ≤ 100)과 전기 용품의 총 사용횟수 K (1 ≤ K ≤ 100)가 정수로 주어진다. 두 번째 줄에는 전기용품의 이름이 K 이하의 자연수로 사용 순서대로 주어진다. 각 줄의 모든 정수 사이는 공백문자로 구분되어 있다. 

출력

하나씩 플러그를 빼는 최소의 횟수를 출력하시오.

<출처>https://www.acmicpc.net/problem/1700

이 문제는 정신을 꽉잡고 풀어야 한다. 그렇게 어려운 문제는 아니지만 고려할 점이 많기 때문이다. 

알고리즘의 순서입니다.

1. 전기용품의 사용 순서를 입력 받습니다.
2. 입력 받은 횟수만큼 반복문을 실행합니다.
   1. 비어있는 구멍이 있는가.
   2. 빈구멍이 없고 이미 꽂혀있는가.
   3. 빈구멍이 없고 꽂혀있지 않는가.
3. 2-1번 같은 경우에는 빈구멍이 있으므로 꽂고 continue를 하고, 2-2는 이미 꽂혀있기 때문에 어떤 동작을 실행할 필요가 없으므로 continue를 실행합니다.
4. 2-3번의 경우에는 꽂혀있는 전기용품 중에 이 후에 쓰이지 않거나 가장 나중에 사용되는 전기용품을 뽑고, 새로운 전기용품을 꽂습니다.

<실행 코드>

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
//틀려서 보고함
int N, M;
int use[101];
int res;
vector<int> conduc;
int main() {
	cin >> N >> M;
	for (int i = 0; i < M; i++) {
		cin >> use[i];
		
	}
	for (int i = 0; i < M; i++) {
		//콘센트에 빈 구멍이 있을 경우
		if (conduc.size() < N) {
			vector<int>::iterator iter = find(conduc.begin(), conduc.end(), use[i]);
			if (iter == conduc.end()) {
				conduc.push_back(use[i]);
			}
			continue;
		}
		//빈구멍이 없고 이미 꽂혀있는지 확인
		vector<int>::iterator iter = find(conduc.begin(), conduc.end(), use[i]);
		if (iter != conduc.end()) { //꽂힘
			continue;
		}
		
		//안꽂혀 있을 경우 뒤에 쓰이지 않거나, 가장 나중에 쓰이는 것을 뽑는다.

		int val=0, lastidx=0;
		for (int j = 0; j < N; j++) {
			int cnt = 0;
			for (int k = i + 1; k < M; k++) {
				if (use[k] == conduc[j]) {
					break;
				}
				cnt++;
			}
			if (cnt > lastidx) {
				val = j;
				lastidx = cnt;
			}
		}
		res++;
		conduc[val] = use[i];
	}
	cout << res << endl;
}

후기

이게 뭐야? 껌이네? 라고 생각하고 정신줄을 잡지 않고 풀다가 많은 실패를 겪었다.. ㅜㅅㅜ

처음에 생각한 방식은 쓰이는 횟수를 저장해 놓고 가장 적게 쓰이는 것을 뽑는다. 라고 접근을 했기 때문에 틀렸다..

정신줄을 꽉 잡자... 흑..

문제

반도체를 설계할 때 n개의 포트를 다른 n개의 포트와 연결해야 할 때가 있다.

예를 들어 왼쪽 그림이 n개의 포트와 다른 n개의 포트를 어떻게 연결해야 하는지를 나타낸다. 하지만 이와 같이 연결을 할 경우에는 연결선이 서로 꼬이기 때문에 이와 같이 연결할 수 없다. n개의 포트가 다른 n개의 포트와 어떻게 연결되어야 하는지가 주어졌을 때, 연결선이 서로 꼬이지(겹치지, 교차하지) 않도록 하면서 최대 몇 개까지 연결할 수 있는지를 알아내는 프로그램을 작성하시오

입력

첫째 줄에 정수 n(1 ≤ n ≤ 40,000)이 주어진다. 다음 줄에는 차례로 1번 포트와 연결되어야 하는 포트 번호, 2번 포트와 연결되어야 하는 포트 번호, …, n번 포트와 연결되어야 하는 포트 번호가 주어진다. 이 수들은 1 이상 n 이하이며 서로 같은 수는 없다고 가정하자.

출력

첫째 줄에 최대 연결 개수를 출력한다.

<출처> https://www.acmicpc.net/

이 문제를 풀다풀다 계속 오답이 나오길래 구글링을 통해 다른 분들의 해법을 보았다.

그런데 도무지 이해가 되지 않는 점이 ... 1가지 있었다..

먼저 LIS의 개념을 모르시는 분들을 위해

참고 사이트 : http://dyngina.tistory.com/16

다른 분들의 풀이를 보면 LIS를 이용해 풀었다. 나 또한 LIS의 개념은 일부 맞지만 이 문제의 핵심인 "선이 교차하지 않는것" 이 부분을 어긴다? 라고 생각이 들었는데 정답 처리가 되어 더 혼란속으로 빠져들었다...

이런식으로 주어졌을 때 (2와2),(4와3),(6과5) 이렇게 이어졌을 때 겹치지 않으면서 최대로 연결할 수 있다.

다른 분들의 풀이를 보면 LIS를 토대로 (2와2)(4와3)까지 이어졌을 때 오른쪽에 있는 1이 들어갈 최적의 위치를 계산해서 (2와2)를 제거하고 대신 들어가게 된다.

그러면 겹치는 선이 아닌가?? 여기서 의문이 들었다.... 지금도 모르겠다...

나는 선이 겹치는 문제 때문에 아래와 같은 방식으로 했었다.

check[1] = weight[1];
	int idx = 1;
	for (int i = 2; i <= N; i++) {
		if (check[idx] < weight[i]) {
			check[++idx] = weight[i];
			continue;
		}
		if (idx == 1) {
			check[idx] = weight[i];
		}
		else if (check[idx - 1] < weight[i]) {
			for(int k=)
			check[idx] = weight[i];
		}
	}

<마지막에 들어간 수보다 작고, 마지막 보다 한칸 전에 들어간 수보다 크다면 마지막을 대신해 넣고 작다면 아무것도 하지 않는다. 작다면 겹치는 문제가 발생하기 때문!> 이라고 생각했다. 

지금도 왜 안되는지 모르겠다.. 혹시 아시는분이 계시면 댓글로 알려주시면 감사하겠습니다!!!

결론적으로, 이 부분만 참고했고 고쳐서 통과했다.

#include<iostream>
#include<algorithm>

using namespace std;
int N;
int weight[40001];
int check[40001];
int main() {

	cin >> N;

	for (int i = 1; i <=N; i++) {
		cin >> weight[i];
	}
	check[1] = weight[1];
	int idx = 1;
	for (int i = 2; i <= N; i++) {
		if (check[idx] < weight[i]) {
			check[++idx] = weight[i];
			continue;
		}
		int iter = lower_bound(check + 1, check + 1 + idx, weight[i]) - check;
		check[iter] = weight[i];
	}
	cout << idx << endl;
}