틀려도 일단 기록하자

docker 공부 시작하기 [spring-boot] run 과 start의 차이와 attach, detach에 대해서- (3)

Sun, 26 Nov 2023 09:19:34 GMT

이 전에는 docker run만 이용해서 컨테이너를 생성하고 실행했지만, docker start를 통해 종료된 컨테이너를 다시 실행시킬 수 있습니다.

📙종료된 컨테이너 다시 실행하기

종료시킨 컨테이너를 다시 실행하기 위해서는 컨테이너 ID를 갖고 다시 실행할 수 있습니다. 컨테이너 list를 찾는 명령어는 다음과 같다.

docker ps -a

컨테이너를 다시 실행시키는 명령어는 다음과 같다.

docker start [container-id / container-name]

컨테이너를 처음 run을 통해 실행시켰을 때 주었던 옵션이 start를 통해 다시 실행했을 때 동일하게 주어진다. start를 통해 컨테이너를 실행하게 되면, run때와는 다르게 터미널을 차단하지 않는다.

📗 attach, detach

여기서 말하는 attach 와 detach의 차이는 간단하게 생각하면 현재 실행중인 컨테이너에서의 출력 내용을 볼 수 있고 없고의 차이이다. attach모드는 볼 수 있고 반대로 detach는 볼 수 없다.

run명령어를 통해 컨테이너를 생성하고 실행할 때는 attach 모드가 기본이 되며, 포그라운드로 실행하게 된다. 따라서 이때는 터미널이 차단되게 된다.

만약 run사용 시 detach모드로 실행하고 싶다면 run 명령어 사용 시 추가적으로 -d 옵션을 주면 된다. detach로 실행하게 되면 터미널이 차단되지 않고 해당 컨테이너는 백그라운드로 실행되게 된다.

docker run -d -p 8081:8081 [image-name]

start명령어로 컨테이너를 실행하게 되면 기본적으로 백그라운드 detach모드로 실행되게 된다. 이 때 만약 attch모드로 실행하고 싶다면 -a옵션을 추가하면 된다.

docker start -a [container-name / container-id]

만약, start명령어로 컨테이너를 실행하였을 때 attach모드로 들어가고 싶다면 다음과 같이 사용할 수 있다.

docker (container) attach [container-name / container-id]

추가적으로 detach모드로 실행되었지만 로그를 보고 싶다면 다음과 같이 사용하면 된다.

docker logs (-f) [container-name / container-id] -f 옵션은 fllow 옵션이다.

주의점은 이 전에 컨테이너를 종료하고 실행한 로그들이 다 보인다는 것..

docker 공부 시작하기 [spring-boot] 도커파일에 작성되는 명령어 알아보기- (2)

Wed, 22 Nov 2023 13:02:50 GMT

📕명령어 비교하기

이 전 글을 작성하면서 비슷한 역할을 하는 명령어들이 있는 것 같아서 이 글에서는 해당 명령어들을 정리해보려 합니다.

📙 RUN, CMD, ENTRYPOINT

📒RUN

RUN은 Dockerfile에서 image로 build하는 순간 실행되는 명령어 입니다. RUN 명령어는 라이브러리 설치 시 주로 사용됩니다.

#Dockerfile
FROM ...
RUN npm install

📒CMD

CMD는 image에서 container를 생성하여 실행할 시 수행됩니다.

FROM openjdk:11-jdk
CMD ["echo", "CMD test"]

📒ENTRYPOINT

CMD와 비슷합니다. container가 생성되고 최초로 실행할 때 수행되는 명령어 입니다.

#Dockerfile

FROM openjdk:11-jdk
CMD ["echo", "CMD test"]
ENTRYPOINT ["echo", "entry point test"]

해당 파일을 실행해보면 실행순서는 ENTRYPOINT 다음 CMD가 실행되는 것 같다..

📒 CMD, ENTRYPOINT 차이

동일하게 명령어를 실행하는 것 같은데 차이점은 무엇일까? ENTRYPOINT는 항상 실행이 되고, CMD는 docker run 할때 변경이 가능합니다.

#Dockerfile

FROM openjdk:11-jdk
CMD ["echo", "CMD test"]
ENTRYPOINT ["echo", "entry point test"]

Dockerfile에 CMD를 정의했음에도 docker run 할 때 명령어를 추가적으로 추가해서 실행하니 Dockerfile 에 정의한 CMD 명령어가 override되는 것을 볼 수 있다 물론 ENTRYPOINT 도 run 할때 옵션으로 override 가능하다.

📙 COPY, ADD

둘 다 Host OS에서 파일 또는 디렉토리를 컨테이너 안으로 복사하는 것이다.

COPY의 경우 Host OS에서 컨테이너 안으로 복사만 가능하지만, ADD의 경우 원격 파일 다운로드 또는 압축 헤제 등과 같은 기능을 갖고 있습니다. Host OS에서 컨테이너로 간단히 복사 시 COPY를 사용합니다.

#Dockerfile

COPY test.sh /app/copy/test.sh
ADD test.sh /app/add/test.sh

ADD 의 경우 URL을 통해 다운로드가 가능합니다.

ADD http://.... /app/add/url/index.html

📙ENV, ARG

ARG는 Dockerfile에서만 사용이 가능하고, ENV는 Dockerfile 이외에도 컨테이너에서도 환경변수로 사용이 가능하다.

#Dockerfile

# ENV [key] [value]
ENV test test
ENV test2 test2

#ENV [key]=[value] 
ENV test=test
ENV test2=test2

#ARG
ARG test=test
ARG test2=test2

다음으로 작성한 Dockerfile로 빌드된 이미지를 가지고 컨테이너를 실행하면 다음과 같다.

FROM openjdk:11-jdk
ARG test="test1111"
ENV test2="test2222"
CMD echo ">>> $test"

CMD 를 통해 ARG 변수를 출력해보면 아무것도 찍히지 않는것을 볼 수 있다. 즉, ARG는 Dockerfile 내에서만 사용되고 그 이후에는 사용되지 않는다.

다음으로는 동일하게 하되, ENV 변수의 값을 사용해서 출력해보겠습니다.

#Dockerfile

FROM openjdk:11-jdk
ARG test="test1111"
ENV test2="test2222"
CMD echo ">>>> $test2"

ARG와는 반대로 출력이 잘 되는것을 볼 수 있습니다. 즉, ENV는 환경변수로 컨테이너 내에 환경변수로 저장되어있는 것을 볼 수 있습니다.

📙EXPOSE

#Dockerfile

FROM openjdk:11-jdk
ARG PATH=./build/libs
WORKDIR /app
EXPOSE 8081
COPY ${PATH}/docker-example-0.0.1-SNAPSHOT.jar ${PATH}/docker-example-0.0.1-SNAPSHOT.jar
CMD ["java", "-jar", "./build/libs/docker-example-0.0.1-SNAPSHOT.jar"]

EXPOSE는 해당 이미지를 가지고 만든컨테이너는 EXPOSE에 명시된 포트를 수신할 것 이라는 것과 같습니다. 하지만 아무런 옵션을 주지 않고 컨테이너를 실행하게 되면 해당포트만 열려있을 뿐 Host OS와 바인딩되어있거나 하지 않습니다.

docker run 명령어 실행 시 옵션으로 -P를 주게되면 Host OS에서 랜덤 포트가 EXPOSE에 명시한 포트와 바인딩 됩니다.

docker run -P [image-name]

기존에 알고있던 옵션 -p [host-port]:[container-port] 를 통해서도 포트를 바인딩할 수 있습니다.

두 개의 다른점은 EXPOSE로 명시한 포트같은 경우는 -P 옵션을 통해 랜덤 포트가 바인딩 된다는 점 이고, -p [host-port]:[container-port]를 통해 바인딩하는 경우는 명시적으로 바인딩할 수 있다는 점입니다.

📙추가적인 테스트

만약 다음과 같은 경우에는 어떻게 될까?

EXPOSE에 명시한 포트를 -p []:[]를 통해 바인딩하면 어떻게 될까?
EXPOSE에 포트를 명시한 후 -P 옵션과 -p []:[]을 같이 주면 어떻게 될까?
EXPOSE에 포트를 명시한 후 -P옵션과 -p []:[]옵션을 같이 사용하되, -p []:[] 옵션에서 다른 포트를 바인딩하면 어떻게 될까?

📒 EXPOSE와 같은 포트 바인딩해보기

EXPOSE에 명시한 포트와 같은 포트를 -p 옵션을 통해 바인딩하면 다음과 같습니다.

#Dockerfile 

FROM openjdk:11-jdk
ARG PATH=./build/libs
WORKDIR /app
EXPOSE 8081
COPY ${PATH}/docker-example-0.0.1-SNAPSHOT.jar ${PATH}/docker-example-0.0.1-SNAPSHOT.jar
CMD ["java", "-jar", "./build/libs/docker-example-0.0.1-SNAPSHOT.jar"]

docker run -p 8081:8081 as

Host OS 8081 과 컨테이너 8081과 바인딩 된 것을 볼 수 있다.

📒 -P 옵션과 -p 같이 사용하기

-P옵션과 -p []:[]를 같이 사용하면 다음과 같습니다.

docker run -P -p 8081:8081 as

위와 동일한 것을 볼 수 있습니다.

📒 그렇다면 -p 옵션에서 다른 포트 바인딩 시엔??

이번엔 -P와 -p를 같이 쓰되, -p옵션에서 다른 컨테이너 포트를 바인딩 해보겠습니다.

docker run -P -p 10888:8088 as

컨테이너 포트를 변경해서 바인딩할 경우, -P 옵션에 의해 랜덤 포트와 바인딩 되고, -p 옵션은 따로 10888 과 8088이 바인딩 된 것을 볼 수 있습니다.

📙VOLUME, BIND MOUNT

Docker에서 컨테이너의생명주기와 관계없이 데이터를 영속적으로 저장을 해야합니다. 또는 많은 경우 여러 개의 컨테이너가 하나의 저장 공간을 공유해서 데이터를 읽거나 써야 합니다. Docker는 이에 대해 2가지 옵션인VOLUME 과 BIND MOUNT를 제공합니다.

📒VOLUME

docker volume ls를 통해 생성된 volume의 리스트를 볼수 있습니다.

docker inspect [volume] 을 통해 volume의 내용을 자세히 볼 수 있습니다.

📒VOLUME 생성하기

VOLUME생성 할 때는 docker volume create [volume-name] 으로 생성한다.

docker volume create vol-t

📒컨테이너에 VOLUME 마운트하기

컨테이너가 볼륨을 사용하기 위해서는 볼륨을 컨테이너에 마운트해줘야 합니다. 마운트하기 위해서는 -v [volume-name]:[container-location] 옵션을 추가합니다.

docker run -p 8081:8081 -v vol-t:/app as

docker inspect [container-name] 을 통해 Mounts부분을 보면 다음과 되어있는 것을 볼 수 있습니다.

-v 옵션이 없는 컨테이너는 다음과 같이 Mounts 부분이 비어있습니다.

docker run -p 8081:8081 as

volume은 다른 컨테이너에도 마운트가 가능하기 때문에 컨테이너 간 데이터 공유가 가능해집니다.

📒VOLUME 삭제

VOLUME 삭제 시에는 마운트 되어있는 컨테이너를 삭제 한 후 VOLUME을 삭제해야 합니다.

📒BIND MOUNT

바인드 마운트는 Host OS 파일 시스템의 특정 경로를 컨테이너로 바로 마운트 할 수 있습니다. 컨테이너 실행 시 옵션으로 -v [host location(file or directory)]:[container-location] 추가해주면 됩니다.

docker run -p 8081:8081 -v $(pwd):/app as

출처

https://nirsa.tistory.com/69 https://nirsa.tistory.com/70?category=868315 https://soft.plusblog.co.kr/139#google_vignette https://tech.cloudmt.co.kr/2022/06/29/%EB%8F%84%EC%BB%A4%EC%99%80-%EC%BB%A8%ED%85%8C%EC%9D%B4%EB%84%88%EC%9D%98-%EC%9D%B4%ED%95%B4-3-3-docker-image-dockerfile-docker-compose/ https://www.daleseo.com/docker-volumes-bind-mounts/#google_vignette https://seosh817.tistory.com/374

docker 공부 시작하기 [spring-boot] 도커 파일로 컨테이너 실행하기- (1)

Tue, 21 Nov 2023 14:22:51 GMT

📕 시작

이제 docker를 공부를 해야 될 것 같아서 정리도 하고, 제가 겪은 것들을 공유하기 위해 이 글을 시작합니다. 잘못된 부분이 있거나 궁금하신 부분이 있으시다면 언제든지 말씀해주세요

📕프로젝트 구성

프로젝트는 간단하게 start.spring.io 에서 spring web 만 dependency로 갖도록 하여 구성하였습니다.

이 후에 도커로 띄운 서버 테스트를 위해 간단한 controller를 만들어 주었습니다.

 @RestController
public class HelloController {

    @GetMapping("/")
    public String hello() {
        return "hello";
    }
}

잘 실행되는지 run 실행해 본 후 ./gradle build 빌드를 통해 jar 파일을 만들어 줍니다.

📙실행과정

도커 실행 과정은 크게 보면 다음과 같습니다.

도커 파일 작성 -> build 를 통해 이미지 생성 -> run을 통해 이미지를 가진container 실행

먼저 도커 파일 작성을 알아보도록 하겠습니다.

📕Dockerfile

Dokcerfile은 도커 이미지를 생성하는 데 사용되는 파일입니다. Dockerfile에 정의한 명령어들은 이미지 레이어를 형ㅇ성하며, 각 레이어는 이전 레이어를 기반으로 합니다. 처음 적는 명령어 FROM은 베이스 이미지로, 매우 중요합니다.

📒Dockerfile 말고 다른이름은 안되나요??

Docker에서는 Dockerfile이라는 특정한 파일명을 사용하도록 규정하고 있고 있습니다. 대소문자 주의!

📒Dockerfile의 위치는??

Dockerfile의 위치는 project root에 위치하는게 좋습니다.

📙작성된 Dockerfile

#Dockerfile

FROM openjdk:11-jdk

WORKDIR /app

ARG PATH=./build/libs

COPY ${PATH}/docker-example-0.0.1-SNAPSHOT.jar ${PATH}/docker-example-0.0.1-SNAPSHOT.jar
CMD ["java", "-jar", "./build/libs/docker-example-0.0.1-SNAPSHOT.jar"]

📙하나씩 알아보기

📒FROM

베이스 이미지를 결정하는 명령어 입니다. 해당 프로젝트는 java11 을 사용하기 때문에 FROM openjdk:11-jdk 를 사용하였습니다.

#Dockerfile

FROM openjdk:11-jdk

Docker 파일에 FROM 명령어만 적어서 이미지를 만들고 run 해보도록 하겠습니다.

docker 명령어를 사용할 때는 Dockerfile이 있는 root에서 명령어를 실행하였습니다. 이미지 생성 명령어는 다음과 같습니다 docker build . -t [image-name] -f [dockerfile-name] docker build . -t section01-example

도커 이미지는 docker images 명령어를 통해 생성된 이미지를 확인하실 수 있습니다.

📗실행해보기

생성된 이미지로 컨테이너를 실행해보도록 하겠습니다. 명령어는 다음과 같습니다

docker run [image-name] docker run section01-example

FROM만 작성된 Dockerfile을 이용하여 컨테이너를 실행했을 때 아래와 같습니다.

간단하게 생각해서 실행하는 명령이나 서비스를 실행하는 내용이 없기 때문입니다.

다음으로 실행하는 명령어를 추가해보겠습니다.

📒CMD

CMD는 docker run 명령어를 실행 할 때 실행되는 명령어 입니다. CMD로 실행할 명령어는 다음과 같습니다

java -jar /build/libs/docker-example-0.0.1-SNAPSHOT.jar gradle build를 통해 빌드된 jar 파일을 실행하는 것입니다.

#Dockerfile

FROM openjdk:11-jdk
CMD ["java", "-jar", "/build/libs/docker-example-0.0.1-SNAPSHOT.jar"]

이제 다시 이미지를 만들어서 컨테이너를 생성하여 실행해보겠습니다. 이 전과 같습니다.

docker build . -t section01-example , docker run section01-example

에러 내용을 보면 /build/libs/docker-example-0.0.1-SNAPSHOT.jar 해당 jarfile을 access 할 수 없다는 내용입니다. ❗️왜 이런 오류가 났을까요??❗️

간단히 생각해보면 다음과 같습니다. 이미지로 생성된 container 도 하나의 새로운 공간[컴퓨터] 입니다. 즉, /build/libs/docker-example-0.0.1-SNAPSHOT.jar 위치의 jar 파일은 local[Host OS] 에만 있을 뿐 container 안에는 없기 때문입니다.

container 내 Files 를 docker desktop으로 보면 /build/libs/docker-example-0.0.1-SNAPSHOT.jar 가 없는 것을 볼 수 있습니다.

📗어떻게 해야할까?

local에 있는 jar파일을 해당 위치로 복사 해주면 됩니다.

📒COPY

여기에서는 local [Host OS]에 위치한 jar file을 복사해서 container로 이동시키는 명령어 입니다.

COPY [local(Host OS) file] [container location]

#Dockerfile

FROM openjdk:11-jdk
COPY ./build/libs/docker-example-0.0.1-SNAPSHOT.jar /build/libs/docker-example-0.0.1-SNAPSHOT.jar
CMD ["java", "-jar", "/build/libs/docker-example-0.0.1-SNAPSHOT.jar"]

Dockerfile을 수정하였으니 동일하게 이미지를 만들고 컨테이너를 실행해보겠습니다.

COPY 명령어를 통해 해당 위치에jarfile이 복사된 것을 확인할 수 있습니다.

tomcat이 뜨는것 까지 해결되었습니다. 톰캣 서버도 떴으니 이제 다음으로 port 8081 로 떠있는 서버에 브라우저에서 접근해보도록 하겠습니다.

❗️하지만 사이트에 연결할 수 없다고 나오네요.. 왜 일까요??❗️ 위에서 말한 것처럼 이미지로 생성된 container도 하나의 새로운 공간[컴퓨터]이기 때문에 local[Host OS] 과 container를 연결해 주어야 합니다.

📗그러면 어떻게 해야 할까??

간단합니다. container를 실행할 때 옵션으로 local[Host OS]과 container의port를 바인딩 해주면 됩니다. 저는 tomcat을 8081로 띄웠기 때문에 8081로 바인딩하겠습니다.

docker run -p [local-port(Host-port)]:[container port] [image-name] docker run -p 8081:8081 section01-example

옵션을 추가해서 컨테이너를 실행해보겠습니다.

접근이 잘 되는것을 확인할 수 있습니다.

📒추가적으로

가장 처음 봤던 Dockerfile에서 사용했던 WORKDIR과 ARG 에 대해 설명을 적어보려 합니다.

📒WORKDIR

WORKDIR 명령어는 linux 명령어 cd와 같다고 생각하면 쉽다. 말 그대로 working directory이다. 그렇다면 왜 사용하는가?

사용이유는 다음과 같다. 처음 베이스이미지를 이용해 만든 파일들이 있을텐데, 해당 파일들과 구분하기 위해서 라고 생각이 들며, 만약 같은파일이름 으로 COPY할 경우 베이스 이미지에서 만든 파일이 덮어쓰기가 되어버린다.

#Dockerfile

FROM openjdk:11-jdk
WORKDIR /app
COPY ./build/libs/docker-example-0.0.1-SNAPSHOT.jar ./build/libs/docker-example-0.0.1-SNAPSHOT.jar
CMD ["java", "-jar", "./build/libs/docker-example-0.0.1-SNAPSHOT.jar"]

여기서는 조금 달라지는데, WORKDIR를 이용하여 디렉토리를 이동 하였기 때문에 COPY 부분과 CMD 부분이 달라진다.

기본에는 COPY가 ./build/libs/docker-example-0.0.1-SNAPSHOT.jar /build/libs/docker-example-0.0.1-SNAPSHOT.jar 에서 ./build/libs/docker-example-0.0.1-SNAPSHOT.jar ./build/libs/docker-example-0.0.1-SNAPSHOT.jar 로 변경되었다.

이유는 다음과 같다. WORKDIR로 /app으로 이동하였기 때문에 /build/libs에서 ./build/libs로 변경된 것이다. /build/libs를 하게되면 절대경로 /build 부터 시작하게 되어버리는 것이고, ./build를 하게 되면 현재 디렉토리인 /app에서 시작하는 것. 다시말해, ./build/libs -> /app/build/libs 가 되는 것이다.

동일하게 CMD도 마지막에 ./build로 변경된 이유도 같은 이유이다. 현재 working directory는 /app이기 때문에 현재 디렉토리에서 이동하는 것으로 ./build/libs로 시작하는 것이다.

동일하게 도커 컨테이너 실행 명령어를 실행한 다음 container 의 Files를 보면 해당 디렉토리에 COPY된 것을 볼 수 있다.

📒ARG

ARG는 말그대로 argument, 인자이다. 해당 Dockerfile을 실행할 때 사용되는 변수를 선언할 때 사용한다.

#Dockerfile

FROM openjdk:11-jdk
ARG PATH=./build/libs
WORKDIR /app
COPY ${PATH}/docker-example-0.0.1-SNAPSHOT.jar ${PATH}/docker-example-0.0.1-SNAPSHOT.jar
CMD ["java", "-jar", "./build/libs/docker-example-0.0.1-SNAPSHOT.jar"]

여기에서는 ./build/libs가 중복되어서 따로 ARG로 빼서 사용한 것이다.

📕시행착오

📒ERROR: failed to solve: no build stage in current context

위 사진처럼 Dockerfile을 만들고 명령어docker build . -t [image-name] 을 실행하던 중 발생한 문제입니다.

📗해결법

해결법은 간단합니다. Dockerfile 시작이 LABEL author="loky1" 로 시작하기 때문에 발생한 문제입니다. FROM ... 명령어를 가장 위로 올려주면 됩니다.

📒starting 무한로딩

📗해결법

OS가 window라면 실행을 검색하신 후 %AppData%를 입력한 후 확인을 눌러줍니다.

도커를 프로그램을 삭제 후[user]/[AppData]/[Local]/[Docker] 파일을 완전히 삭제해준 후 다시 설치합니다.

다음으로 Docker Desktop을 실행하면 오류가 날 수 있습니다. 그 때는 CMD창을 열어 --unregister docker-desktop-data 명령어 입력 후 등록 취소 중입니다, / 작업을 완료했습니다 가 뜬 후 다시 Docker Desktop을 실행하면 됩니다.

참고

https://ttl-blog.tistory.com/761#%EC%96%B4%EB%96%BB%EA%B2%8C%20%ED%95%B4%EA%B2%B0%ED%95%98%EB%82%98%EC%9A%94%3F%20%F0%9F%A7%90-1

[spring-vue] 웹소켓으로 채팅 구현하기 (5) - vue 화면 설명

Sun, 12 Nov 2023 09:40:31 GMT

화면을 개발하면서 생각보다 기록해두어야 할 부분이 많다고 생각하여 추가로 글을 작성합니다.

프로젝트 생성부분은 프로젝트 생성 부분을 참고해주세요

📘vue.config.js

먼저 vue.config 부분입니다. spring과 vue를 같이 개발시 npm run serve로 front server를 띄울 때 back-end server와 통신을 하기위해 설정합니다.

const { defineConfig } = require('@vue/cli-service')

const host = "localhost"; //back-end host
const port = "8081"; //back-end port
module.exports = defineConfig({
  transpileDependencies: true,

  outputDir: "../back-end/src/main/resources/static", //webpack build 시 결과물 위치


  devServer: {
    hot: true,
    proxy: {
      //http://localhost:8080/api/ -> http://localhost:8081/api/
      '/api/': {
        target: `http://${host}:${port}`,
        changeOrigin: true,
      },

      '/ws/': {
        target: `ws://${host}:${port}`,
        changeOrigin: false,
        ws: true,
      }
    }
  }
})

~~> outputDir path 설정은 resources/static 이거나, classpath 내 public 폴더도 가능합니다 참고~~

여기서 주의해서 봐야하는 부분은 proxy 부분입니다. 작성한 부분을 자세히 보자면

vue에서 /api/로 보내는 요청은 target 으로 변경되어 요청됩니다. 즉, 현재 front-server가 8080으로 떠있다면 axios를 이용해 localhost:8080/api/** 로의 요청은 localhost:8081/api/** 로 변경됩니다.

다음 /ws/또한 같은 의미로 사용됩니다. /ws/는 vue에서 웹소켓을 이용 할 때 사용합니다.

📘AXIOS 사용 시

front에서 back-end와 통신 시 axios를 많이 사용하실텐데요,여기서 주의해야할 점은 fetch할 때 input 부분입니다. 처음 input 부분에 다음과 같이 입력했는데 오류가 발생했었습니다.

fetch("http://localhost:8081/api/v1/room, ...)

개발환경에서 개발 시 위에서 설정한 대로

fetch("http://localhost:8080/api/v1/room,) 또는 fetch("/api/v1/room", )

으로 사용하셔야 합니다.

배포 후 빌드 시에는 localhost:8081로 설정되어있어야 합니다

📘STOMP

📗Client 객체 생성

해당 프로젝트에서 사용한 @stomp/stompjs 사용법은 다음과 같습니다.

const client = new Client({//config}); config 부분에는 어떤 속성들이 있는지 확인해봅시다. Client를 따라 들어가보면 와 같은 생성자가 있는 것을 확인할 수 있습니다. 저희가 여기서 봐야하는 부분은 생성자의 인자에 있는 StompConfig 부분입니다.

StompConfig

export class StompConfig {
/**
 * See [Client#brokerURL]{@link Client#brokerURL}.
 */
public brokerURL?: string;

/**
 * See [Client#stompVersions]{@link Client#stompVersions}.
 */
public stompVersions?: Versions;

/**
 * See [Client#webSocketFactory]{@link Client#webSocketFactory}.
 */
public webSocketFactory?: () => any;

/**
 * See [Client#connectionTimeout]{@link Client#connectionTimeout}.
 */
public connectionTimeout?: number;

/**
 * See [Client#reconnectDelay]{@link Client#reconnectDelay}.
 */
public reconnectDelay?: number;

/**
 * See [Client#heartbeatIncoming]{@link Client#heartbeatIncoming}.
 */
public heartbeatIncoming?: number;

/**
 * See [Client#heartbeatOutgoing]{@link Client#heartbeatOutgoing}.
 */
public heartbeatOutgoing?: number;

/**
 * See [Client#splitLargeFrames]{@link Client#splitLargeFrames}.
 */
public splitLargeFrames?: boolean;

/**
 * See [Client#forceBinaryWSFrames]{@link Client#forceBinaryWSFrames}.
 */
public forceBinaryWSFrames?: boolean;

/**
 * See [Client#appendMissingNULLonIncoming]{@link Client#appendMissingNULLonIncoming}.
 */
public appendMissingNULLonIncoming?: boolean;

/**
 * See [Client#maxWebSocketChunkSize]{@link Client#maxWebSocketChunkSize}.
 */
public maxWebSocketChunkSize?: number;

/**
 * See [Client#connectHeaders]{@link Client#connectHeaders}.
 */
public connectHeaders?: StompHeaders;

/**
 * See [Client#disconnectHeaders]{@link Client#disconnectHeaders}.
 */
public disconnectHeaders?: StompHeaders;

/**
 * See [Client#onUnhandledMessage]{@link Client#onUnhandledMessage}.
 */
public onUnhandledMessage?: messageCallbackType;

/**
 * See [Client#onUnhandledReceipt]{@link Client#onUnhandledReceipt}.
 */
public onUnhandledReceipt?: frameCallbackType;

/**
 * See [Client#onUnhandledFrame]{@link Client#onUnhandledFrame}.
 */
public onUnhandledFrame?: frameCallbackType;

/**
 * See [Client#beforeConnect]{@link Client#beforeConnect}.
 */
public beforeConnect?: () => void | Promise;

/**
 * See [Client#onConnect]{@link Client#onConnect}.
 */
public onConnect?: frameCallbackType;

/**
 * See [Client#onDisconnect]{@link Client#onDisconnect}.
 */
public onDisconnect?: frameCallbackType;

/**
 * See [Client#onStompError]{@link Client#onStompError}.
 */
public onStompError?: frameCallbackType;

/**
 * See [Client#onWebSocketClose]{@link Client#onWebSocketClose}.
 */
public onWebSocketClose?: closeEventCallbackType;

/**
 * See [Client#onWebSocketError]{@link Client#onWebSocketError}.
 */
public onWebSocketError?: wsErrorCallbackType;

/**
 * See [Client#logRawCommunication]{@link Client#logRawCommunication}.
 */
public logRawCommunication?: boolean;

/**
 * See [Client#debug]{@link Client#debug}.
 */
public debug?: debugFnType;

/**
 * See [Client#discardWebsocketOnCommFailure]{@link Client#discardWebsocketOnCommFailure}.
 */
public discardWebsocketOnCommFailure?: boolean;

/**
 * See [Client#onChangeState]{@link Client#onChangeState}.
 */
public onChangeState?: (state: ActivationState) => void;
}

간단하게 저희가 사용하는 것은 brokerURL, onConnect, onDisconnect, onStompError, onWebSocketClose, onWebSocketError 등이 있을 것 같습니다.
정의해야 하는 속성과 함께 client config를 완성시키면 다음과 같습니다.

 this.websocketClient = new Client({
    brokerURL: "ws://localhost:8080/ws/init",
    onConnect: () => {
    this.websocketClient.subscribe(`/sub/room/${this.currentRoom.id}`, msg => {
            this.messages.push(msg.body);
          });

          this.websocketClient.publish({
            destination: `/pub/room/${this.currentRoom.id}/entered`,
            body: JSON.stringify({message: `${this.textMessage}`, writer: "user1"}),
          });

    },
    onDisconnect: (frame) => {},
    onStompError: (frame) => {},
    onWebSocketClose: (_) => {}
    onWebSocketError: (_) => {},
});

추가로 마지막에 client.activate()를 호출해주셔야 합니다.

클라이언트를 생성했다면 다음으로는 subscribe입니다. subscribe은 다음과 같습니다.

client.subscribe(destination, callback=(message:IMessage) => {}, headers=[key:String])

프로젝트에서 사용한 코드는 다음과 같습니다.

this.websocketClient.subscribe(`/sub/room/${this.currentRoom.id}`, msg => {
            this.messages.push(msg.body);
          })

destination = /sub/room/${this.currentRoom.id} callback = msg => { this.messages.push(msg.body); }

📗publish 하기

sub가 비슷합니다.


client.publish(params: IPublishParams) == 
client.publish({destination: "/queue/test", body: "Hello, STOMP"});
---
export interface IPublishParams {
  /**
   * destination end point
   */
  destination: string;
  /**
   * headers (optional)
   */
  headers?: StompHeaders;
  /**
   * body (optional)
   */
  body?: string;
  /**
   * binary body (optional)
   */
  binaryBody?: Uint8Array;
  /**
   * By default, a `content-length` header will be added in the Frame to the broker.
   * Set it to `true` for the header to be skipped.
   */
  skipContentLengthHeader?: boolean;
}

프로젝트에서 사용한 코드는 다음과 같습니다.

const body = {message: `${this.textMessage}`, writer: "user1"}

this.websocketClient.publish({
        destination: `/pub/room/${this.currentRoom.id}`,
        body: JSON.stringify(body),
      });

📗disconnect하기

disconnect는 activate 와 반대로 deactivate 를 사용하면 됩니다.

this.websocketClient.deactivate();

전체 코드는 github에서 확인 가능합니다.

[spring-vue] 웹소켓으로 채팅 구현하기 (4) - DB 추가 및 엔티티 추가

Sat, 11 Nov 2023 17:05:54 GMT

이 전에 이어서 엔티티와 H2디비를 구현하여 개발해보겠습니다.

📗구현

📘엔티티 설정

관계는 필요하니, 간단하게 User 와 Room 엔티티와 User와 Room이 다대다 관계이기 때문에 중간에 EnteredRoom 이라는 다대다 해소 엔티티를 넣도록 하겠습니다.

USER

@Entity
@Getter
@NoArgsConstructor(access = AccessLevel.PROTECTED)
public class User {

  @Id @GeneratedValue
  private Long id;
  private String name;

  @OneToMany(mappedBy = "user")
  private List enteredRoom = new ArrayList<>();

  public User(String name) {
      this.name = name;
  }

}


- ROOM
```java
@Entity
@Getter
@NoArgsConstructor
public class Room {

    @Id @GeneratedValue
    private Long id;

    private String name;

    @OneToMany(mappedBy = "room")
    private List enteredRoom = new ArrayList<>();

    public Room(String name) {
        this.name = name;
    }
}

ENTEREDROOM

@Entity
@Getter
@NoArgsConstructor
public class EnteredRoom {

  @Id @GeneratedValue
  private Long id;

  @ManyToOne(fetch = FetchType.LAZY)
  @JoinColumn(name = "USER_ID")
  private User user;

  @ManyToOne(fetch = FetchType.LAZY)
  @JoinColumn(name = "ROOM_ID")
  private Room room;

  @Enumerated(value = EnumType.STRING)
  private RoomStatus roomStatus = RoomStatus.ENTER;

  public EnteredRoom(User user, Room room) {
      this.user = user;
      this.room = room;
  }
}

📘테스트 데이터 추가

엔티티도 만들었으니, 테스트 할 수 있도록 데이터를 어플리케이션이 구동될 때 넣도록 하겠습니다.

@Configuration
@EnableWebSocketMessageBroker
@RequiredArgsConstructor
public class WebSocketBrokerConfiguration implements WebSocketMessageBrokerConfigurer {


    private final UserService userService;
    private final RoomService roomService;
    private final EnteredRoomService enteredRoomService;

     @EventListener(value = ApplicationReadyEvent.class)
    public void addTestData() {

        User user1 = new User("user1");
        User user2 = new User("user2");
        User user3 = new User("user3");
        User user4 = new User("user4");

        Room room1 = new Room("채팅방1");
        Room room2 = new Room("채팅방2");

        Long savedUserId1 = userService.save(user1);
        Long savedUserId2 = userService.save(user2);
        Long savedUserId3 = userService.save(user3);
        Long savedUserId4 = userService.save(user4);


        Long savedRoomId1 = roomService.save(room1);
        Long savedRoomId2 = roomService.save(room2);

        enteredRoomService.save(savedUserId1, savedRoomId1);
        enteredRoomService.save(savedUserId2, savedRoomId1);
        enteredRoomService.save(savedUserId3, savedRoomId1);

        enteredRoomService.save(savedUserId3, savedRoomId2);
        enteredRoomService.save(savedUserId4, savedRoomId2);
    }
}

service, repository는 spring-data-jpa를 이용해서 간단하게 만들었습니다.

📘API 추가

몇 개의 API를 추가하도록 하겠습니다.

유저가 포함되어있는 ROOM LIST
ROOM 전체 LIST
~~유저가 ROOM을 나갈 경우 삭제~~
~~유저가 ROOM을 새로 들어갈 경우 등록~~

등등.. 일단 테스트에 맞춰 필요한 API만 개발하도록 하겠습니다.

room 전체 List를 가져오는 API는 단순하게 findAll()로 가져옵니다.

@RestController
@RequiredArgsConstructor
@RequestMapping("/api/v1/room")
public class RoomController {

    private final RoomService service;

    @GetMapping("")
    public Result> list() {

        return service.findAll();
    }
}

유저가 포함되어있는 ROOM List 해당 API같은 경우 userID를 넘겨 해당 유저가 속해있는 방의 정보들을 가져옵니다.

- controller
    @GetMapping("/joined")
    public Result> joinedList( RoomJoinedRequestDto requestDto) {
        return service.findAll(requestDto.getUserId());
    }

-------

- service
    public Result> findAll(Long userId) {
        User user = userRepository.findById(userId).get();
        List findRooms = enteredRoomRepository.findAll(RoomStatus.ENTER, user);

        List collect = findRooms.stream().map(EnteredRoomResponseDto::new).collect(Collectors.toList());

        return new Result<>(collect);

    }

--------

- repository

@Query("SELECT er FROM EnteredRoom er JOIN FETCH er.room r WHERE er.user = :user AND er.roomStatus = :roomStatus")
    List findAll(@Param("roomStatus") RoomStatus roomStatus, @Param("user") User user);

해당 API들은 맨 처음 화면에서 전체리스트와 유저가 속한 리스트를 가져올 때 사용됩니다.

📘시나리오1

사용자가 채팅방을 클릭했을 때 [ /sub/room/{roomId}] 와 함께 [ /pub/room/{roomId}/entered ] 웹소켓 요청을 보낸다.

front 화면은 따로 설명하지않고 github을 보고 참고해주시기 바랍니다.

client 부분을 만들다보니 설명할 부분이나 제가 기록용으로 사용하기 위해 따로 블로그 글을 쓰겠습니다.

vue에서 stomp를 사용하기 위해 두 개의 모듈을 설치합니다 stompjs - stomp npm // 참고 ws - websocket

npm i --save @stomp/stompjs ws

부가적인 기능은 현재 구현하지 않았다는 점.. 참고 부탁드립니다.

화면에서 사용자가 채팅방을 클릭하면 웹소켓 요청을 보내게 됩니다.

connect() {
      //vue.config.js 참고
      const url = "ws://localhost:8080/ws/init";
      this.websocketClient = new Client({
        brokerURL: url,
        onConnect: () => {
          this.websocketClient.subscribe(`/sub/room/${this.currentRoom.id}`, msg => {
            this.messages.push(msg.body);

          })

          this.websocketClient.publish({
            destination: `/pub/room/${this.currentRoom.id}/entered`,
            body: JSON.stringify({message: `${this.textMessage}`, writer: "user1"}),
          });

          this.isLoading = false;
        },

        onWebSocketError: () => {
          this.isLoading = false;
        },
      })

      this.websocketClient.activate();
    },

server에서는 다음 메서드가 실행되며, 브로커를 통해 메시지를 전달하게 됩니다.

    @MessageMapping("/room/{roomId}/entered")
    public void entered(@DestinationVariable(value = "roomId") String roomId, MessageDto message){
        log.info("# roomId = {}", roomId);
        log.info("# message = {}", message);
        final String payload = message.getWriter() + "님이 입장하셨습니다.";
        template.convertAndSend("/sub/room/" + roomId, payload);
    }

📘시나리오2

사용자가 메시지를 입력하고 전송 클릭 시 메시지가 다른 사용자들에게 전송된다.

이번 시나리오는 간단하게 연결되어있는 웹소켓을 통해 메시지를 서버에 전달하고, 서버에서는 해당 메시지를 브로커를 통해 다른 사용자들에게 전달하면 됩니다.

화면과 같이 왼쪽에서 메시지를 보내기를 누르게 되면, 서버에서는 아래 핸들러가호출되고, template를 통해 room에 속한 유저들에게 메시지를 보내게 됩니다.

    @MessageMapping("/room/{roomId}")
    public void sendMessage(@DestinationVariable(value = "roomId") String roomId, MessageDto message) {
        log.info("# roomId = {}", roomId);
        log.info("# message = {}", message);

        template.convertAndSend("/sub/room/" + roomId, message.getMessage());
    }

대략 흐름은 다음과 같습니다.

방에 접속한 클라이언트는 message를 보낸다.

sever에서는 해당 destination에 맞는 핸들러로 요청을 전달하고

핸들러에서는 로직을 실행 후 SimpMessagingTemplate 을 통해 sub 하고 있는 유저들에게 메시지를 전달한다.

정리

처음 구현을 목표로 했던 방에 접속하고, 접속한 유저들끼리 채팅을 할 수 있다 까지 구현이 완료되었기 때문에 추가적인 개발 부분에 대해서는 추후 개발해보도록 하겠습니다. 채팅기능에 의의를 두었기 때문에 다른분들이 이 글을 읽고 spring-vue를 이용해 채팅을 구현함에 있어 큰 어려움을 없으실꺼라 생각합니다 .

지금까지 한 코드는 github 레포지토리 에서 확인 가능하십니다.

개발하시면서 궁금하신 점이나, 안되는 부분이 있으시다면 저도 많이 못하지만.. 제가 힘이 닿는 부분까지 최대한 도와드리도록 하겠습니다. 감사합니다.

[spring-vue] 웹소켓으로 채팅 구현하기 (3) - STOMP

Sat, 11 Nov 2023 11:07:22 GMT

📕STOMP

이번에는 stomp 프로토콜을 사용해 채팅을 구현해보도록 하자. 자세한 내용은 spring doc 에 나와있습니다.

📗개요

STOMP란? Simple Text Oriented Messaged Protocol 말 그대로 텍스트 지향 프로토콜이다. STOMP는 텍스트 지향 프로토콜 이지만 페이로드는 텍스트 이거나 바이너리 일 수 있는 점.. 또한 STOMP는 pub/sub 구조로 메시지를 공급받는 쪽 [pub] 과 메시지를 소비하는 쪽 [sub]이 분리되어 있으며 이 후에 개발할 서버가 broker 역할을 하게된다.

또한 STOMP는 HTTP를 모델로 하는 프레임 기반 프로토콜이다. 이 프레임에 대해 이해하면 이 후에 구현할 때 도움이 된다. 프레임은 다음과 같다.

COMMAND
header1:value1
header2:value2

Body^@

클라이언트는 메시지 내용[message]과 수신 대상[sub]을 설명하는 대상 헤더와 함께 SEND 또는 SUBSCRIBE 명령을 사용하여 메시지를 보내거나 구독할 수 있다.

다음으로 간단하게 client가 구독할 때 서버에 보내는 헤더 내용이다.

SUBSCRIBE
id:sub-1
destination:/topic/price.stock.*

^@

Command 로 SUBSCRIBE을 보내면서 destination 정보를 전달한다. destination은 브로커에게 자신이 수신할[sub] topic을 알려주는 정보라고 이해하면 쉽다. 이 후에 해당 topic으로 pub이 오면 해당 topic을 수신하고 있던 클라이언트 들에게 pub 메시지가 전송된다.

자세한 프로토콜 사양은 프로토콜 사양에서 볼 수 있습니다.

📗사용이유

STOMP를 사용하는 이유는 다음과 같다.

이 전에 했던 코드같은 경우, 웹소켓 서버가 한 대인 경우 적용이 가능하나, 여러 대 일 경우 웹소켓 세션 정보를 서로 알 수 없다.

spring으로 구현할 경우 메모리 브로커를 사용하게 되는데, 이 외에 외부 브로커를 사용할 경우 등등..

📗구현

STOMP에 대한 자세한 내용은 spring doc를 보면 알 수 있기 때문에 이 글에서는 더 이상 설명치않고 구현을 해보도록 하겠습니다.

이 전에 만들던 프로젝트에서 브로커를 사용할 수 있도록 어노테이션을 추가하고, [WebSocketMessageBrokerConfigurer] 를 구현합니다. 구현할 메서드로는 총 3가지로 [registerStompEndpoints, configureClientInboundChannel, configureMessageBroker]를 구현합니다.

@Configuration
@EnableWebSocketMessageBroker
@RequiredArgsConstructor
public class WebSocketBrokerConfiguration implements WebSocketMessageBrokerConfigurer {


    private final WebsocketBrokerInterceptor interceptor;
    @Override
    public void registerStompEndpoints(StompEndpointRegistry registry) {
        registry.addEndpoint("/ws/init") //1
                .setAllowedOrigins("*"); 
    }

    @Override
    public void configureClientInboundChannel(ChannelRegistration registration) {
        registration.interceptors(interceptor); //2
    }

    @Override
    public void configureMessageBroker(MessageBrokerRegistry registry) {
        registry.enableSimpleBroker("/sub"); //3
        registry.setApplicationDestinationPrefixes("/pub"); //4
    }
}

최초 websocket을 연결할 때 보내는 endPoint입니다.

websocket이 연결되거나, sub/pub/send 등 client에서 메시지를 보내게 될 때 interceptor를 통해 핸들링 하게 됩니다.

client는 /sub/** 의 형태로 topic을 구독하게 됩니다.

반대로 메시지를 보낼때는 /pub 형식으로 보내게 됩니다.

다음 그림은 spring에서 제공하는 메모리 브로커를 사용할 때의 구성요소를 보여줍니다.

위 사진에서 /app은 /pub에 매칭되고, /topic은 /sub에 매칭됩니다.

/pub 형식으로 보내는 메시지에 대해서는 일반적인 controller처럼 핸들링이 가능한데 예를 들어 /pub/test 와 같이 destination 정보를 넣어 요청을 할 경우, @MessageMapping("/test") 어노테이션을 가진 컨트롤러에서 핸들링이 가능해집니다.

@Slf4j
@RestController
@RequiredArgsConstructor
public class BrokerController {

    private final SimpMessagingTemplate template;


    @MessageMapping("/test")
    public void test(SimpMessageHeaderAccessor accessor) {
        log.info("### test method {}", accessor);
    }
}

STOMP 테스트를 진행할 때는 APIC 을 이용해야 한다는 점.. 여기까지가 큰 흐름이고 이제 자세히 구현을 해보도록 하겠습니다.

다음으로는 간단하게 사용자가 방으로 들어오는 시나리오를 만들어서 구현해보록 하겠습니다.

📘시나리오1

유저가 채팅방을 클릭해서 들어오는 경우

사용자가 방을 클릭 했을 때 방 번호와 함께 /sub 을 요청하게 됩니다.

[ destination = /sub/room/{roomId} ]

서버로의 웹소켓 모든 요청의 경우 위에서 추가한 인터셉터를 타게 됩니다. 해당 인터셉터에서 CommndType을 구별하여 로직을 작성합니다.

@Component
public class WebsocketBrokerInterceptor implements ChannelInterceptor {

    @Override
    public Message preSend(Message message, MessageChannel channel) {
        final StompHeaderAccessor headerAccessor = StompHeaderAccessor.wrap(message);
        final StompCommand commandType = headerAccessor.getCommand();

        if(StompCommand.CONNECT == commandType) {
            //웹소켓 연결 요청 시 유저 인증

        } else if (StompCommand.SEND == commandType) {
            //pub 시 메시지 처리할 경우
        } else if (StompCommand.SUBSCRIBE == commandType) {
            //sub 시 처리할 코드를 여기서 작성
        } 
        return message;
    }
}

여기에서는 따로 인증 또는 PUB,SUB 시 따로 로직을 추가하지 않겠습니다.

추가로 방에 있는 유저에게 입장 메시지를 전송하기 위해 다음과 같이 요청합니다.

[ destination = /pub/room/{roomId}/entered]

pub 메시지는 MessageMapping 어노테이션이 있는 컨트롤러에서 처리하게 됩니다. 해당 핸들러에서는 입장 메시지를 생성하여 해당 room에 있는 유저에게 메시지를 보냅니다.

@Slf4j
@RestController
@RequiredArgsConstructor
public class BrokerController {

    private final SimpMessagingTemplate template;

    @MessageMapping("/room/{roomId}/entered")
    public void entered(@DestinationVariable(value = "roomId") String roomId, MessageDto message){
        log.info("# roomId = {}", roomId);
        log.info("# message = {}", message);
        final String payload = message.getWriter() + "님이 입장하셨습니다.";
        template.convertAndSend("/sub/room/" + roomId, payload);
    }
}

MessageDto

@Getter
@NoArgsConstructor
public class MessageDto {

    private String message;
    private String writer;
}

📘시나리오2

방에 들어온 유저가 메시지를 보낼경우

사용자가 방에 들어온 후 메시지를 보낼때는

[ destination = /pub/room/{roomId} ]

과 함께 메시지를 서버에 요청하게 됩니다.
여기에서는 /pub 하는 데이터를 @MemssageMapping한 controller에서 처리하게 됩니다.

    @MessageMapping("/room/{roomId}")
    public void sendMessage(@DestinationVariable(value = "roomId") String roomId, MessageDto message) {
        log.info("# roomId = {}", roomId);
        log.info("# message = {}", message);

        template.convertAndSend("/sub/room/" + roomId, message.getMessage());
    }

이제 APic 으로 테스트를 진행해보도록 하겠습니다.

📘시나리오 테스트

APIC에서 탭 2개를 열고 두 개 모두 연결을 해둔 상태에서 입장 메시지가 잘 오는지, 메시지 전송 시 잘 도착하는지 테스트 해보겠습니다.

두 개의 웹소켓을 연결해둔 상태에서 첫 탭에서 /pub/room/{roomId}/entered를 보내게되면,

반대편 탭에 도착한 것을 볼 수 있다.
다음으로는 메시지 전송을 테스트 해보자. 메시지 전송 시에는 /pub/room/{roomId} 로 보내며 payload로 message를 같이 보낸다.

잘 전송되는 것을 확인 할 수 있다.

정리

지금까지 STOMP를 이용해 기본적인 구현과 큰 흐름을 알아봤습니다. 다음에는 엔티티를 추가하고 메모리로 디비를 만들어서 좀더 살을 붙여보겠습니다.

전체 코드는 xxx-sj에서 보실 수 있습니다.

출처:

https://docs.spring.io/spring-framework/reference/web/websocket/stomp/handle-annotations.html https://brunch.co.kr/@springboot/695

[spring-vue]웹소켓으로 채팅 구현하기 (2) - 프로젝트 생성 및 스프링웹소켓

Fri, 10 Nov 2023 16:28:58 GMT

📗프로젝트 생성

이 부분은 모두 하실 줄 안다고 생각하여 빠르게 넘기겠습니다. 간단하게 제가 프로젝트를 만들면서 추가한 의존성만 보여드리고 넘어가도록 하겠습니다

dependencies {
    implementation 'org.springframework.boot:spring-boot-starter-data-jpa'
    implementation 'org.springframework.boot:spring-boot-starter-validation'
    implementation 'org.springframework.boot:spring-boot-starter-web'
    implementation 'org.springframework.boot:spring-boot-starter-websocket'
    compileOnly 'org.projectlombok:lombok'
    runtimeOnly 'com.h2database:h2'
    annotationProcessor 'org.projectlombok:lombok'
    testImplementation 'org.springframework.boot:spring-boot-starter-test'
}

웹소켓을 사용하기 위해서는 하위 의존성을 추가하자.

implementation 'org.springframework.boot:spring-boot-starter-websocket'

프로젝트 생성 후 잘 생성되었는지 반드시 WebsocketApplication으로 실행해보자.

📗spring-websocket

아래코드는 스프링 doc을 참고하여 구현합니다.

@Configuration
@EnableWebSocket
public class WebSocketConfiguration implements WebSocketConfigurer {
    @Override
    public void registerWebSocketHandlers(WebSocketHandlerRegistry registry) {
        registry.addHandler(myHandler(), "/myHandler").setAllowedOriginPatterns("*");
    }

    @Bean
    public WebSocketHandler myHandler() {
        return new MyHandler();
    }
}

@EnableWebSocket : 웹소켓 서버를 사용하도록 추가합니다.

/myHandler : 웹소켓 서버의 endPoint를 "/myHandler" 로 설정합니다.

setAllowedOriginPatterns("*") : 웹소켓 서버로의 요청을 모두 수용한다. (실제로는 제한할 것)

myHandler() : 웹소켓 핸들러로 MyHandler 클래스를 설정한다.

MyHandler의 클래스는 다음과 같다. 간단히 TextWebSocketHandler extends하여 정의한다.

public class MyHandler extends TextWebSocketHandler {


    //최초 연결 시
    @Override
    public void afterConnectionEstablished(WebSocketSession session) throws Exception {

    }

    //양방향 데이터 통신할 떄 해당 메서드가 call 된다.
    @Override
    protected void handleTextMessage(WebSocketSession session, TextMessage message) throws Exception {
        //do something
    }

    //웹소켓 종료
    @Override
    public void afterConnectionClosed(WebSocketSession session, CloseStatus status) throws Exception {

    }

    //통신 에러 발생 시
    @Override
    public void handleTransportError(WebSocketSession session, Throwable exception) throws Exception {


    }
}

MyHandler에서는 4개의 메서드를 구현하는데

afterConnectionEstablished: 최초 연결시 call 된다.

handleTextMessage: 연결 후 메세지를 주고 받을 때 call 된다.

afterConnectionClosed: 웹소켓이 끊키면 call 된다.

handleTransportError: 통신 에러 발생시 call 된다.

여기까지 기초적인 설정은 끝났으니 postman으로 테스트를 진행하면서 메서드에 어떠한 데이터들이 들어오는지 확인해보자. postman으로 websocket 테스트 하는 방법은 많은 블로그에서 소개하고 있으니 따로 적진 않겠습니다.

📘postman으로 테스트 하기

postman에서 websocket로 연결 요청을 보내면 다음과 같이 afterConnectionEstalished메서드에 break point가 걸리는 것을 확인할 수 있다.

해당 메서드의 session 인자의 데이터를 확인해보면 다음과 같다.

session 객체에 id가 보이는데, 이 session id를 key로 갖는 map을 통해 session을 관리해보도록 하자.

인스턴스 필드로 map을 선언하고, afterConnectionEstablished 메서드가 호출될 때 id 와 session을 map에 put 한다. 코드로 보면 다음과 같다.

📘session객체 저장하기

    private final Map sessions = new HashMap<>();

    //최초 연결 시
    @Override
    public void afterConnectionEstablished(WebSocketSession session) throws Exception {
        final String sessionId = session.getId();

        sessions.put(sessionId, session);

    }

다음으로는 최초 연결 시 session객체를 저장하면서, 저장되어있는 다른 session 객체들에게 알림을 보내는 코드를 추가해보자.

    @Override
    public void afterConnectionEstablished(WebSocketSession session) throws Exception {
        final String sessionId = session.getId();
        final String enteredMessage = sessionId + "님이 입장하셨습니다.";
        sessions.put(sessionId, session);

        sessions.values().forEach((s) -> {

            try {
                if(!s.getId().equals(sessionId) && s.isOpen()) {

                    s.sendMessage(new TextMessage(enteredMessage));
                }
            } catch (IOException e) {}
        });


    }

여기까지 완료했다면 postman을 통해 tab을 2개를 열어서 코드 테스트를 진행해보자.

📘postman 테스트

시나리오는 다음과 같다.

한쪽을 연결해둔 상태에서 다른 한 탭에서 웹소켓 연결 시 최초 연결했던 탭에 연결되었다는 메시지를 받아야 한다.

이제 다른 탭에서 새로 연결을 해보면~

위 화면과 같이 입장 메시지를 받을것을 확인할 수 있다.

📘handleTextMessage 메서드 구현

다음으로는 연결된 웹소켓들이 메시지를 주고받을 때 call되는 메서드를 구현한다. 이것도 별 다르지 않게 연결되어있는 모든 session에게 메시지를 보낸다.

    @Override
    protected void handleTextMessage(WebSocketSession session, TextMessage message) throws Exception {
        //do something
        final String sessionId = session.getId();
        sessions.values().forEach((s) -> {

            if (!s.getId().equals(sessionId) && s.isOpen()) {
                try {
                    s.sendMessage(message);
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
        });
    }

📘handleTextMessage 메서드 테스트

동일하게 postman으로 테스트를 진행해보자. 이번에는 두 탭 모두 연결을 한 후, 한 탭에서 메시지를 보내 메시지가 오는지 확인해보자.

일반적인 text를 입력한 후 send를 보내면 다른 쪽에 메시지가 도착하는 것을 확인할 수 있다.

📘afterConnectionClosed 메서드 구현

해당 메서드에서는 session이 끊기게 되면 map에 저장되어있는 객체를 remove 하고, 다른 접속자들에게 leave message를 보낸다.

해당 메서드의 인자 중 CloseStatus status에는 종료상태에 대해 정의되어 있으니 필요에 따라 분기를 통해 정의할 수 있다.

//웹소켓 종료
    @Override
    public void afterConnectionClosed(WebSocketSession session, CloseStatus status) throws Exception {
        final String sessionId = session.getId();
        final String leaveMessage = sessionId + "님이 떠났습니다.";
        sessions.remove(sessionId); // 삭제

        //메시지 전송
        sessions.values().forEach((s) -> {

            if (!s.getId().equals(sessionId) && s.isOpen()) {
                try {
                    s.sendMessage(new TextMessage(leaveMessage));
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
        });
    }

테스트로 잘 되는 것도 확인하였다.

📕리팩토링

간단하게 구현하긴 했지만 각각의 메서드에서 메시지를 전송하는 부분은 message를 제외하면 모두 같기 때문에 하나의 메서드를 정의하고 메서드를 call하도록 수정한다. 전체코드는 다음과 같다.


package com.sj.websocket.handler;

import org.springframework.web.socket.CloseStatus;
import org.springframework.web.socket.TextMessage;
import org.springframework.web.socket.WebSocketMessage;
import org.springframework.web.socket.WebSocketSession;
import org.springframework.web.socket.handler.TextWebSocketHandler;

import java.io.IOException;
import java.util.HashMap;
import java.util.Map;

public class MyHandler extends TextWebSocketHandler {

    private final Map sessions = new HashMap<>();

    //최초 연결 시
    @Override
    public void afterConnectionEstablished(WebSocketSession session) throws Exception {
        final String sessionId = session.getId();
        final String enteredMessage = sessionId + "님이 입장하셨습니다.";

        sessions.put(sessionId, session);

        sendMessage(sessionId, new TextMessage(enteredMessage));

    }

    //양방향 데이터 통신할 떄 해당 메서드가 call 된다.
    @Override
    protected void handleTextMessage(WebSocketSession session, TextMessage message) throws Exception {
        //do something
        final String sessionId = session.getId();
        sendMessage(sessionId, message);
    }

    //웹소켓 종료
    @Override
    public void afterConnectionClosed(WebSocketSession session, CloseStatus status) throws Exception {
        final String sessionId = session.getId();
        final String leaveMessage = sessionId + "님이 떠났습니다.";
        sessions.remove(sessionId); // 삭제

        sendMessage(sessionId, new TextMessage(leaveMessage));

    }

    //통신 에러 발생 시
    @Override
    public void handleTransportError(WebSocketSession session, Throwable exception) throws Exception {}

    private void sendMessage(String sessionId, WebSocketMessage message) {
        sessions.values().forEach(s -> {
            if(!s.getId().equals(sessionId) && s.isOpen()) {
                try {
                    s.sendMessage(message);
                } catch (IOException e) {}
            }
        });
    }
}

정리

websocket을 가지고 간단하게 구현하였는데, 위 코드는 입장 시, 퇴장 시, 메시지 보낼 때 모두 다른 세션에 메시지를 보내고 있다. 만약, 특정 사람에게 보내거나, 그룹에 보내야 한다면 최초 웹소켓 연결 시 서버에 object 형식의 데이터를 보내어 그룹을 짓거나 특정 사용자에게 메시지를 보낼 수 있다.

위의 코드는 websocket repository 에서 볼 수 있습니다.

참고

https://brunch.co.kr/@springboot/695 https://docs.spring.io/spring-framework/reference/web/websocket/server.html

[Spring-vue] 웹소켓으로 채팅 구현하기(1) - 웹소켓이란

Fri, 10 Nov 2023 13:28:16 GMT

계기

회사에서 웹소켓으로 모바일과 통신하는 프로젝트를 맡게되면서 공부도 할겸 간단한 채팅 프로젝트를 만들어 보고자 한다. 필자도 웹소켓에 대해 모른다.. 앞으로 공부하며 알아가 보도록 하자.

웹소켓 이전

웹소켓 이전에는 다음과 같은 방법으로 통신을 했었다.

⏳polling

polling 같은 경우는 client 측에서 매번 서버에 요청을 보내면서 이벤트가 발생했는지에 대한 여부를 응답으로 받는 형식이다.

⏳Long polling

long polling은 문자 그대로 좀 더 길게 polling하는 것이다. 클라이언트 측에서 요청을 보내면 이벤트가 발생하여 응답을 줄 때 까지 기다리는 것이다.

위와 같은 통신은 real-time에는 거리가 멀고, 매번 요청을 해야 하거나, 요청을 보내고 이벤트가 발생할 때 까지 기다리는 등의 낭비가 발생한다.

웹소켓이란?

먼저 쉽게 알 수 있는 ChatGPT에 웹소켓에 대해 물어보면 다음과 같이 답하는데, 그 중 몇가지 맛만 보자.

웹소켓(WebSocket)은 웹 어플리케이션에서 양방향 통신을 가능케 하는 통신 프로토콜입니다. 웹소켓은 기존의 HTTP 프로토콜과 함께 사용되며, 클라이언트와 서버 간에 실시간으로 데이터를 주고받을 수 있도록 해줍니다.

기본적인 특징과 개념은 다음과 같습니다: 양방향 통신: 웹소켓은 양방향 통신을 지원하며, 클라이언트와 서버 간에 데이터를 실시간으로 전송할 수 있습니다. 이는 클라이언트가 서버로 메시지를 보내고, 서버가 클라이언트에게 메시지를 보낼 수 있음을 의미합니다.

실시간성: 일반적인 HTTP 요청과 달리 웹소켓은 계속해서 연결을 유지하므로 실시간으로 데이터를 전송하는 데 효과적입니다. 이는 채팅 애플리케이션, 주식 시세 업데이트, 온라인 게임 등 실시간 업데이트가 필요한 시나리오에서 특히 유용합니다.

프로토콜: 웹소켓 프로토콜은 RFC 6455에 정의되어 있습니다. 기본적으로는 80번 포트를 사용하며, 보안 연결인 경우에는 443번 포트를 사용합니다.

웹소켓은 웹 어플리케이션에서 실시간 통신이 필요한 많은 경우에 사용됩니다. 브라우저에서는 JavaScript를 통해 웹소켓을 사용할 수 있고, 서버 측에서는 여러 언어 및 프레임워크를 통해 구현할 수 있습니다.

부족한 내용은 위키백과 에서 더 많이 내용을 볼 수 있다.

위의 설명에서도 볼 수 있듯이 웹소켓은 양방향으로 통신이 가능하며, 실시간으로 데이터를 주고 받을 수 있도록 해준다는 것이 포인트이다.

[백준] 2579번: 계단 오르기 - Java, 자바

Wed, 30 Aug 2023 14:44:12 GMT

문제 접근

이 문제의 키 포인트는 마지막 계단을 밟는다에 있다.
마지막에 밟는 계단이 N 이라고 했을 때, N을 밟을 수 있는 조건은 2가지가 있다.

N 과 N - 1 계단을 밟는다면 N - 2는 밟을 수 없기 때문에 N -3 까지 누적된 값을 더한다.
- 즉, (dp[N - 3] (N -3 까지의 누적합) + number[N] + number[N - 1]) 이 될 것이다.
다음으로는 N - 1을 밟지 않을 경우이다. 이때는, N 과 N - 2까지의 누적된 값을 더하게 된다.
- dp[N - 2] + number[N]

이렇게 보고 나면 쉽게 문제를 해결할 수 있다.

전체코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

    static int[] stairs;
    static Integer[] dp;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());

        stairs = new int[N + 1];
        dp = new Integer[N + 1];

        for(int i = 1;i <= N; i++) {
            stairs[i] = Integer.parseInt(br.readLine());
        }

        dp[0] = 0;
        dp[1] = stairs[1];
        //조건을 추가하지않으면 N = 1일 때, dp[2], stairs[2]에 접근하려다 오류 발생함.
        if (N >= 2) {
            dp[2] = stairs[1] + stairs[2];
        }

        System.out.println(recur(N));
    }

    private static int recur(int N) {

        if(dp[N] == null) {
            dp[N] = Math.max(recur(N - 2), recur(N - 3) + stairs[N - 1]) + stairs[N];
        }

        return dp[N];
    }
}

코드 상세

top-down

top-down 문제는 위에서 아래로 진행하며 재귀를 통해 dp를 초기화한다는 것을 기억하자.

N을 입력받는다.
입력받은 N으로 계단의 배열과 dp배열을 초기화한다.
dp배열에는 각각의 계단에 누적합이 저장된다.
```
static int[] stairs;
static Integer[] dp;
```

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

int N = Integer.parseInt(br.readLine());

stairs = new int[N + 1]; dp = new Integer[N + 1];

- 계단을 입력받아 stairs 배열을 초기화한다.
```java
for(int i = 1;i <= N; i++) {
    stairs[i] = Integer.parseInt(br.readLine());
}

초기값을 설정한다.
- 초기값으로는 dp[0]= 0;
- dp[1] 의 값으로는 이 전값이 없기 때문에 dp[1] = stairs[1] 이 된다.
- dp[2] 또한 초기화를 해주는데, 이 때는 N 이 1보다 클 때 즉, 2부터 초기화가 가능하게 한다.
  - 이유는 N = 1 을 입력받았을 때 dp[2]에 접근하려고 할 때 오류가 발생하기 때문이다.
- dp[2] 까지 초기화하는 이유는 잘 생각해보면 이후에 나올 재귀함수에서 dp[N - 3] 까지 접근하기 때문이다. 까지
```
dp[0] = 0;
dp[1] = stairs[1];
```

//조건을 추가하지않으면 N = 1일 때, dp[2], stairs[2]에 접근하려다 오류 발생함. if (N >= 2) { dp[2] = stairs[1] + stairs[2]; }

- 재귀함수를 통해 dp를 초기화한다.
  - 재귀함수 내에서는 dp[N]이 초기화 되지 않았을 때 dp[N] 값을 초기화한다.,
  - 위에서 설명한 dp[N - 2]까지 밟고 stairs[N]을 밟는 조건과
  - dp[N - 3] 까지 밟고 stairs[N - 1] + stairs[N] 두개를 밟는 조건 중 더 큰 값을 dp[N]에 저장한다.
```java
private static int recur(int N) {

    if(dp[N] == null) {
        dp[N] = Math.max(recur(N - 2), recur(N - 3) + stairs[N - 1]) + stairs[N];
    }

    return dp[N];
}

정리

이 문제는 N번쨰 계단을 밟는다.가 핵심이었다. N에 도달하기 위한 조건을 서로 비교하여 가장 큰 값을 dp배열에 넣는 문제였다. 문제에서도 조건을 주었듯이 해당 조건을 가지고 N에 도달할 수 있는 조건을 만드는 것이었다.

[백준] 1699번: 제곱수의 합 - Java, 자바

Wed, 30 Aug 2023 14:34:05 GMT

문제 접근

이 문제는 설명과 코드 상세를 보며 먼저 이해해보자.

이 문제는 손으로 직접 써보고 나서 이해하기 쉬웠다.
여기서도 dp[N]의 값은 제곱수의 최소 갯수가 저장된다.
N = 11을 기준으로 보자면 쉽게 표시를 하기위해 지수는 생략하고 밑 수만 표기하면

dp 제곱수 갯수
dp[1] = 1 = 1;
dp[2] = 1 + 1 = 2;
dp[3] = 1 + 1 + 1 = 3;
dp[4] = 2 = 1;
dp[5] = 2 + 1 = 2;
dp[6] = 2 + 1 + 1 = 3;
dp[7] = 2 + 1 + 1 + 1 = 4;
dp[8] = 2 + 2 = 2;
dp[9] = 3 = 1;
dp[10] = 3 + 1 = 2;
dp[11] = 3 + 1 + 1 = 3; 와 같다.
예전에 배운 가우스법칙을 떠올리면 11을 나타내기 위해서
10 + 1
9 + 2
8 + 3
7 + 4
6 + 5 와 같이 나타낼 수 있다. 위 값을 잘 살펴보면 N = 11 일 때
[N - 1] + [1] [N - 2] + [2] ... [N - 5] + [5] 즉, [N - i] + [i] 가 된다.
이 문제를 bottom-up 방식으로 풀어낸다면 아래와 같을 것이다.
아래 for 문을 살펴보면 먼저
min값을 초기값을 MAX_VALUE로 설정하고
이중 for문에서는 i의 반만큼 for문을 순회한다.
만약, j xj 가 i 와 같다면 즉, 3 x 3 = 9와 같이 곱하여 같다면
min 값은 1로 초기하고 다음으로 넘어간다.
그게 아니라면 min값과 dp[i - j] + dp[j] 중에 큰 값을 min에 저장한다.

마지막에 min값을 dp[i]에 저장한다.

for(int i = 2; i <= N; i++) {
  int min = Integer.MAX_VALUE;

  for(int j = 1; j <= i / 2; j++) {

      if(j * j == i) {
          min = 1;
          break;
      } else {
          min = Math.min(min, dp[i - j]  + dp[j]);
      }
  }

  dp[i] = min;
}

위의 for문을 이해했다면 다음으로 불 필요한 계산을 줄이는 방법이 있을 것이다.
여기서는 제곱 수가 포인트인데, 제곱 수로 나타낼 수 있는 수가 있다면 최소 갯수 1이된다.
1, 4, 9, 16 과 같이 = 1^1, 2^2, 3^2, 4^2와 같은 값들이다.
다시말해,
10 + 1
9 + 2
8 + 3
7 + 4
6 + 5
와 같이 다 계산할 필요없이 11아래에 존재하는 제곱 수 끼리만 비교를 하면 된다는 말이다.
11아래에 있는 제곱수는 1, 4, 9 가 있다.
즉,
10 + 1 [1^1]
7 + 4 [2^2]
2 + 9 [3^2] 값만 비교하면 된다. 이 조건을 가지고 다시 for문을 나타내면 아래와 같다.
바깥 for문은 2 ~ N까지 순회한다.
- 1을 하지않는 이유는 1로 고정이기때문에.
- 1은 1^2 값 즉, dp[1] = 1 이 초기값으로 들어가게된다.
for문에서는 기본적으로 1^2만으로 나타낸 수를 dp[i]에 초기화한다.
- 1^2로 나타내는 수는 1 + 1+ 1.... = i 즉, i개만큼 1이 더해진다.
내부 for문에서는 위에서 말했던 숫자 N 아래에 있는 제곱만을 계산할 수 있도록 조건으로
j*j <= i 로 설정하였다.
for문 내부에서는 dp[i]값과 dp[i - j*j] + 1 중 작은 값을 dp[i]에 저장한다
예를들어 i = 11 일때,
dp[11] = Math.min(dp[11], dp[11 - 1(10)] + 1);
dp[11] = Math.min(dp[11], dp[11 - 4(7)] + 1);
dp[11] = Math.min(dp[11], dp[11 - 9(2)] + 1);
중 작은 값을 dp[11]에 저장한다.
여기서 + 1을 하는 이유는 제곱 수의 갯수이다.
헷갈리지 말아야 할 것은 구하려는 값은 숫자가 아닌 제곱의 갯수이다.
dp[10] + 1 [1^1] = dp[10] + 1
dp[7] + 4 [2^2] = dp[7] + 1

dp[2] + 9 [3^2] = dp[2] + 1

private static int bottom_up2(int N) {

  for(int i = 2; i <= N; i++) {
      dp[i] = i;
      for(int j = 1; j * j<= i; j++) {
          dp[i] = Math.min(dp[i], dp[i - j*j] + 1);
      }
  }

  return dp[N];
}

N을 입력받아 dp배열을 초기화한다
이 때 초기화는 N + 1로 한다.
이유는 인덱스가 0부터 시작하기 때문이고, 문제에서 1부터 시작하기 때문에
```
static Integer[] dp;
```

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

int N = Integer.parseInt(br.readLine());

dp = new Integer[N + 1];

- 초기값을 설정한다
```java
dp[0] = 0;
dp[1] = 1;

bottom-up으로 dp값을 초기화한다.

private static int bottom_up2(int N) {

  for(int i = 2; i <= N; i++) {
      dp[i] = i;
      for(int j = 1; j * j<= i; j++) {
          dp[i] = Math.min(dp[i], dp[i - j*j] + 1);
      }
  }

  return dp[N];
}

bottom-up 메서드를 호출하여 출력한다.
```
System.out.println(bottom_up2(N));
```

전체코드


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    static Integer[] dp;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());

        dp = new Integer[N + 1];

        dp[0] = 0;
        dp[1] = 1;

        System.out.println(bottom_up2(N));
    }

    private static int bottom_up(int N) {

        for(int i = 2; i <= N; i++) {
            int min = Integer.MAX_VALUE;

            for(int j = 1; j <= i / 2; j++) {

                if(j * j == i) {
                    min = 1;
                    break;
                } else {
                    min = Math.min(min, dp[i - j]  + dp[j]);
                }
            }

            dp[i] = min;
        }

        return dp[N];
    }

    private static int bottom_up2(int N) {

        for(int i = 2; i <= N; i++) {
            dp[i] = i;
            for(int j = 1; j * j<= i; j++) {
                dp[i] = Math.min(dp[i], dp[i - j*j] + 1);
            }
        }

        return dp[N];
    }


}

[백준] 11054번: 가장 긴 바이토닉 수열 - Java, 자바

Wed, 30 Aug 2023 13:59:40 GMT

문제접근

이 문제는 어떤한 값 기분으로 왼쪽은 증가하는 수열 [LIS] 오른쪽으로는 감소하는 수열[LDS]이란걸 알 수 있다.
그렇다면 이 문제 같은경우는 어떻게 풀면될까.. 하고 생각해보면
어떠한 수열의 값 N을 기준으로 왼쪽으로는 LIS를 오른쪽으로는 LDS를 진행해준 후 두 개의 배열의 값을 합친 값 중
가장 큰 값을 출력하면 되지 않을까란 생각이 들 수 있다.
말 그대로 N을 기준으로 N - 1 부터 시작하여 0까지는 LIS를 통해 LIS_DP를 초기화하고,
N + 1 부터 시작하여 length - 1까지는 LDS를 통해 LDS_DP를 초기화하여 두 개의 배열의 합을 구하면 된다.
여기서 하나더, 이전에 LDS문제는 비교할 때 (number[N] < number[j]) 가 성립할 때 였는데 이때는 0 부터 시작하여 N까지 였기 때문에 N 기준 앞 쪽의 수가 더 컸어야 했지만, 여기서는 반대로 N부터 시작하여 Length - 1 까지 순회하기 때문에 N이 더 커야 한다는 것을 명심하자. (number[N] > number[j]) 여기서 조심해야 하는 것은 LIS,LDS 2번을 하게 되면 자기자신 N이 2번 들어가기 때문에 두 개의 합한 값에 -1을 반드시 해주어야한다.

전체코드


import java.awt.im.InputContext;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    static int[] numbers;

    static Integer[] lis_dp;
    static Integer[] lds_dp;
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());

        numbers = new int[N];

        lis_dp = new Integer[N];
        lds_dp = new Integer[N];

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        for(int i = 0; i < N; i++) {
            numbers[i] = Integer.parseInt(st.nextToken());
        }

        for(int i = 0; i < N; i++) {
            recur_lis(i);
        }

        for(int i = N - 1; i >= 0; i--) {
            recur_lds(i);
        }

        int max = Integer.MIN_VALUE;

        for(int i = 0; i < N; i++) {

            max = Math.max(max, recur_lds(i) + recur_lis(i) - 1);
        }

        System.out.println(max);
    }


    static int recur_lis(int N) {

        if(lis_dp[N] == null) {
            lis_dp[N] = 1;

            for(int i = N - 1; i >= 0; i--) {

                if (numbers[N] > numbers[i]) {
                    lis_dp[N] = Math.max(lis_dp[N], recur_lis(i) + 1);
                }
            }
        }


        return lis_dp[N];
    }


    static int recur_lds(int N) {

        if(lds_dp[N] == null) {
            lds_dp[N] = 1;

            for(int i = N + 1; i < lds_dp.length; i++) {
                if(numbers[N] > numbers[i])  {
                    lds_dp[N] = Math.max(lds_dp[N], recur_lds(i) + 1);
                }
            }
        }

        return lds_dp[N];
    }
}

정리

LIS 와 LDS를 알고 조합 할 수 있었다면 쉽게 해결할 수 있었을 것이다. LIS, LDS를 하되, 모두 N에서 시작하기 때문에 N의 값(1)이 중복되기 때문에 답에서 -1을 해주는 것이 중요했다.

[백준] 1912번: 연속합 - Java, 자바

Wed, 30 Aug 2023 13:49:27 GMT

문제접근

이 문제는 손으로 써보면 쉽게 해결할 수 있는 문제이다.
이 문제의 핵심은 연속된 몇 개의 수를 합하여 가장 큰 합을 구하는 것이다.
맨 처음 이 문제를 풀 떄 수열로 헷갈려서 문제를 틀렸는데, 잘 읽어보면 연속된 몇 개의 수에 답이 있다.
0부터 N까지 수를 합하면서 현재 [자기자신] 과 [이 전까지 합한 수 + 자기자신]을 비교하여 큰 값을 dp에 저장하면 된다.
예를들어서 예제 입력
10 -4 3 1 5 6 -35 12 21 -1

idx[0] = 10;
- idx[0] 이전 값을 비교할 것이 없기 때문에 자기자신 10이 가장 크다.
- dp[0] = 10;
idx[1] = -4; [이전 값 = 10]+ [자기자신 = -4] = [6];
- idx[1]은 -4 이지만 이전 값 10을 합치면 6으로 자기자신보다 크다.
- dp[1] = dp[0] + idx[1] = 6;
idx[2] = 3;
- idx[2]는 비교할 것 없이 이전 값과 자신을 합한 값이 크다.
- dp[2] = dp[1] + idx[2] = 9;
idx[3] = 1;
- idx[3]도 동일하다
- dp[3] = dp[2] + idx[3] = 10;
idx[4] = 5;
- idx[4]도 동일하다
- dp[4] = dp[3] + idx[4] = 15;
idx[5] = 6;
- idx[5] 도 동일하다
- dp[5] = dp[4] + idx[5] = 21;
idx[6] = -35;
- idx[6]은 음수인데, 자기자신 보다는 자기자신의 값 + 이전 합한 값을 합친 값이 더 크다.
- 즉, dp[6] = dp[5] + idx[6] = -14;
idx[7] = 12;
- idx[7]은 이전값 + 자기자신 보다 자기자신의 수가 더 크다는 것을 한눈에 알 수 있다.
- 여기에서는 이 전까지 합한 값을 버리게 되며, dp[7]에는 idx[7] 자기자신만 들어가게 된다.
- dp[7] = idx[7] = 12;
idx[8] = 21;
- idx[8]에서는 이전 값 dp[7]과 자기자신을 합한 값이 크다는것을 알 수 있다.
- dp[8] = dp[7] + idx[8] = 33;
idx[9] = -1;
- idx[9] 도 dp[8]과 자기자신을 합한 값이 더 크다.
- dp[9] = dp[8] + idx[9] = 32;

이제 dp[]의 값을 모아보면 아래와 같다.
[10, 6, 9, 10, 15, 21, -14, 12, 33, 32]
여기서 가장 큰 수는 33이다. 33 = dp[8] 은 idx[7], idx[8]을 합친 값이란걸 알 수 있다.
이것을 코드로 보자면

전체코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    static Integer[] dp;
    static int[] numbers;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        dp = new Integer[N];
        numbers = new int[N];

        for(int i = 0; i < N; i++) {
            numbers[i] = Integer.parseInt(st.nextToken());
        }

        dp[0] = numbers[0];


        recur(N - 1);



        int max = Integer.MIN_VALUE;

        for(int i = 0; i < N; i++) {
            max = Math.max(max, dp[i]);
        }

        System.out.println(max);


    }


    static int recur(int N) {

        if(dp[N] == null) {
            dp[N] = Math.max(recur(N - 1) + numbers[N], numbers[N]);
        }

        return dp[N];
    }
}

코드 상세

top-down

위에서 아래로 진행하며 자기자신의 값과 |이전 dp[]의 값 + 자기자신| 을 비교하여 더 큰 값을 dp[]에 넣는다.

recur(N - 1);

static int recur(int N) {

    if(dp[N] == null) {
        dp[N] = Math.max(recur(N - 1) + numbers[N], numbers[N]);
    }

    return dp[N];
}

N을 입력받아 dp[], numbers[]을 초기화한다.

다음으로 입력받는 수열을 numbers 배열에 저장한다.

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

int N = Integer.parseInt(br.readLine());

StringTokenizer st = new StringTokenizer(br.readLine(), " ");

dp = new Integer[N]; numbers = new int[N];

for(int i = 0; i < N; i++) { numbers[i] = Integer.parseInt(st.nextToken()); }

- dp[0]의 값을 초기화해준다.
  - dp[0]의 값은 이전 값과 비교할 값이 없기 때문에 number[0]의 값을 갖는다.
```java
dp[0] = numbers[0];

N - 1 부터 재귀를 호출하여 dp배열을 초기화한다.
```
recur(N - 1);
```

static int recur(int N) {

if(dp[N] == null) {
    dp[N] = Math.max(recur(N - 1) + numbers[N], numbers[N]);
}   

return dp[N];

}

- dp배열 중 가장 큰 값을 출력한다
```java
int max = Integer.MIN_VALUE;

for(int i = 0; i < N; i++) {
    max = Math.max(max, dp[i]);
}

System.out.println(max);

[백준] 11722번: 가장 긴 감소하는 부분 수열 - Java, 자바

Wed, 30 Aug 2023 13:46:33 GMT

문제접근

LIS와 반대로 LDS 의 문제이다. 이 문제 또한 DP로 풀 수 있다.
LIS와는 반대로 감소하는 수열이기 떄문에 N에 대한 값을 비교할 때는 비교하는 N의 값이 이 전 값보다 작을 때 조건을 만족하게 된다.
LIS를 풀었었다면 쉽게 LDS문제도 풀 수 있다.
코드로 보자면 아래와 같다.

전체코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    static Integer[] dp;
    static int[] number;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());

        dp = new Integer[N + 1];
        number = new int[N + 1];

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        for(int i = 1; i <= N;i ++) {
            number[i] = Integer.parseInt(st.nextToken());
        }

//        for(int i = N; i >= 0; i--) {
//            recur_lds(i);
//        }
        bottom_up(N);

        int max = Integer.MIN_VALUE;

        for(int i = 1; i <= N; i++) {
            max = Math.max(dp[i], max);
        }

        System.out.println(max);
    }

    static int recur_lds(int N) {

        if(dp[N] == null) {

            dp[N] = 1;
            for(int i = N - 1; i >= 0; i--) {

                if(number[N] < number[i]) {
                    dp[N] = Math.max(dp[N], recur_lds(i) + 1);
                }
            }
        }


        return dp[N];
    }

    static void bottom_up(int N) {
        for(int i = 1; i <= N; i++) {
            dp[i] = 1;

            for(int j = 0; j < i; j++) {

                if(number[i] < number[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }
    }
}

코드상세

top-down

N을 입력받고 입력받은 N으로 배열을 초기화한다.
- dp 배열은 수열의 길이를 저장하는 배열이고
- number 배열은 다음으로 입력받는 수열의 정보를 저장한다.
  - N + 1로 초기화한 이유는 (1 <= N <= 1000)에 이해를 돕기위해
  - 인덱스0이 아닌 시작을 1로 잡았기 때문에
```
static Integer[] dp;
static int[] number;
```

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

int N = Integer.parseInt(br.readLine());

dp = new Integer[N + 1]; number = new int[N + 1];

- 다음으로 입력받은 수열을 number 배열에 저장한다.
```java
StringTokenizer st = new StringTokenizer(br.readLine(), " ");

for(int i = 1; i <= N;i ++) {
    number[i] = Integer.parseInt(st.nextToken());
}

재귀함수를 호출하여 dp배열을 초기화 한다.

for(int i = N; i >= 0; i--) {
   recur_lds(i);
}

재귀함수에서는 dp[N]의 값이 아직 초기화 되지 않았다면 먼저 dp[N]의 값을 1로 초기화한다.
- 1로 초기화하는 이유는 수열의 길이를 저장하는 dp배열에 기본적으로 자기자신이 포함되기 때문에 1로 초기화한다.
다음으로는 위에서 아래로 for-loop를 돌면서 값을 비교한다.
- 이 떄 입력받은 number[N]의 값이 비교하려는 for-loop의 number[i]의 값보다 작다면
- dp[N]에 dp[N]과 dp[i] + 1의 값을 비교하여더 큰값을 저장한다.
  - dp[i] + 1의 값은 다른말로 recur_lds(i) + 1 과 같다.
    - 그 이유는 dp[i]에 대하여 for-loop는 위에서 아래로 진행 중인데 아직 dp[i]에 해당하는 값은
    - 초기화 되지 않았기 때문에 재귀를 통해 초기화를 해준다.
```
static int recur_lds(int N) {
```
  if(dp[N] == null) {
```
dp[N] = 1;
for(int i = N - 1; i >= 0; i--) {

    if(number[N] < number[i]) {
        dp[N] = Math.max(dp[N], recur_lds(i) + 1);
    }
}
```
  }

return dp[N];

}

- dp 배열을 순회하며 큰 값을 출력한다.
```java
int max = Integer.MIN_VALUE;

for(int i = 1; i <= N; i++) {
    max = Math.max(dp[i], max);
}

System.out.println(max);

bottom-up

Bottom-up도 top-down과 비슷하지만 다른게 있다면 아래에서 부터 순회를 시작하여 dp 배열을 채우고
2중 for-loop를 사용한다는 점이다.
헷갈릴수도 있는데 비교의 기준이 되는 number[N]의 값이 비교하려는 number[j]의 값 보다 작을 때 조건이 성립한다.
예를들어, N = 4 일때 0,1,2,3을 비교하게 되는데 N = 4일때의 값은 20이고, 0,1,2,3 의 값은 각각 [10, 30, 10, 20]이다. 이 문제는 감소하는 수열로써 그대로 보이는 것 기준으로 왼쪽으로 갈 수록 수가 커야하고, 오른쪽으로 갈 수록 수가 작아져야 하기 때문에 number[N]의 값이 비교하려는 number[j]보다 작아야하는 것이다.

N을 입력받아 배열을 초기화한다.

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

int N = Integer.parseInt(br.readLine());

dp = new Integer[N + 1]; number = new int[N + 1];

- 다음으로 입력받는 값으로 number 배열을 초기화한다.
```java
StringTokenizer st = new StringTokenizer(br.readLine(), " ");

for(int i = 1; i <= N;i ++) {
    number[i] = Integer.parseInt(st.nextToken());
}

dp 배열의 값을 초기화한다.
이때는 아래서 부터 위로 값을 채워나간다.
- 2중 for-loop를 사용하는데, 기본적으로 자기자신이 수열에 포함되기 때문에
- dp[i]의 값을 1로 초기화한다.
- 2번째 for-loop에서는 i보다 작을 때 까지 loop를 돌면서
  - i보다 작은 이유는 예를들어 i= 3 일때 1,2; 즉, 이 전값과 비교하여
  - 더 큰 값이 있을경우 조건에 있는 로직을 실행하여 dp[i]를 초기화한다.
- 비교하려는 number[j]보다 작다면 dp[i]의 값과 dp[j] + 1값을 비교하여 더 큰 값을 저장한다.
  - +1인 이유는 dp[j]에 대한 값이 i에 속해지기 때문에 i값을 카운팅하기 위해 +1을 해주는 것이다.
```
static void bottom_up(int N) {
for(int i = 1; i <= N; i++) {
 dp[i] = 1;

 for(int j = 0; j < i; j++) {

     if(number[i] < number[j]) {
         dp[i] = Math.max(dp[i], dp[j] + 1);
     }
 }
}
}
```
dp배열을 순회하며 큰 값을 출력한다.
```
int max = Integer.MIN_VALUE;
```

for(int i = 1; i <= N; i++) { max = Math.max(dp[i], max); }

System.out.println(max);

```

정리

이 문제는 그대로 보이는 것 기준으로 왼쪽으로 갈 수록 수가 커져야 하고, 오른쪽으로 갈 수록 수가 작아지는 것만 인식한다면 생각보다 쉽게 풀 수 있다.

[백준] 11055번: 가장 큰 증가하는 부분 수열 - Java, 자바

Wed, 30 Aug 2023 13:12:09 GMT

문제접근

이 문제에서는 dp의 값으로는 해당 배열의 부분 수열의 합이 들어간다.
비교하려는 arr[N] 에 대하여 N - 1부터 arr[N]과 비교하여 값이 더 작을경우
dp[N] 에 dp[N] 과 dp[N - 1] + arr[N] 를 비교하여 더 큰 값을 dp[N] 에 할당한다. 예를들어, 처음 dp배열의 초기값은 입력받은 값들이 들어갈 것이다. 왜냐하면 수열의 합이 기본적으로 자기자신을 포함하기 때문이다.
다음으로는 for문을 돌면서 N 보다 작은 N-1 ~ 0 까지 순회하며 입력받은 arr값들을 비교한다. 만약 N과 비교하여 이전값들이 더 작다면 dp[N]에 dp[N]과 dp[해당 루프 값 (j)] + arr[N] 을 더해 더 큰 값을 dp[N]에 저장한다.

예제입력을 보면 dp배열의 초기값으로 dp[0] = 1; dp[1] = 100; dp[2] = 2; dp[3] = 50; dp[4] = 60; dp[5] = 3; dp[6] = 5; dp[7] = 6; dp[8] = 7; dp[9] = 8; 이 들어가게 된다.

다음으로 한 예시로 만약 N = 5 일 때를 기준으로 bottom-up으로 for문을 돌면서 값을 구해보자.

for(int i = 0; i < N(5); i++) {
    dp[i] = number[i];
    for(int j = 0; j < i; j++) {
        dp[i] = Math.max(dp[i], dp[j] + number[i]);
    }
}

i=0 (1)
- i가 0일때는 처음 초기값 설정 이후 내부 for문은 타지않는다. 따라서
- dp[0] = 1;
i=1 (100)
- i=1 일때는 내부 for문을 타게되고, dp[0] + number[1] 과 dp[1] 중에 더 큰값을 저장하게 된다. 각각의 값은 101 과 100이다.
- dp[1] = 101;
i=2 (2)
- i=2 일때는 내부 for문으로는 0,1을 순회하며, number[1]은 조건에 맞지 않아 패스하게 되며, dp[0] + number[2] 과 dp[2]를 비교하게 된다.
- dp[2] = 3;
i=3 (50)
- i=3 일때는 0~2를 순회하며, 조건에 맞는 0과 2를 비교하게 된다. 각각 dp[0] + number[3] 과, dp[2] + number[3]을 비교하게 되며 각각의 값은 51과 53이다.
- dp[3] = 53;
i=4 (60)
- i=4 일때는 0~3를 순회하며, 조건에 맞는 0,2,3 을 비교하게 된다. 각각 dp[0] + number[4] 과, dp[2] + number[4], dp[3] + number[4]을 비교하게 되며 각각의 값은 51과 53, 113이다.
- dp[4] = 113;

dp[0] = 1; dp[1] = 101; dp[2] = 3; dp[3] = 53; dp[4] = 113; dp[5] = 6; dp[6] = 11; dp[7] = 17; dp[8] = 24; dp[9] = 32;

전체코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    static int[] number;
    static Integer[] dp;
    static int N;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());
        number = new int[N];
        dp = new Integer[N];

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        for(int i = 0; i < N; i++) {
            number[i] = Integer.parseInt(st.nextToken());
        }

        dp[0] = number[0];
        bottom_up_lis();

//        for(int i = 1; i < N; i++) {
//            recur_lis(i);
//        }

        int max = Integer.MIN_VALUE;

        for(int i = 0; i < N; i++) {

            if(max < dp[i]) {
                max = dp[i];
            }
        }

        System.out.println(max);
    }

    private static int recur_lis(int N) {

        if(dp[N] == null) {
            dp[N] = number[N];

            for(int i = N - 1; i >= 0; i--) {

                if(number[N] > number[i]) {
                    dp[N] = Math.max(dp[N], number[N] + recur_lis(i));;
                }
            }
        }

        return dp[N];
    }


    private static void bottom_up_lis() {

        for(int i = 1; i < N; i++) {
            dp[i] = number[i];

            for(int j = 0; j < i; j++) {
                if(number[i] > number[j]) {
                    dp[i] = Math.max(dp[j] + number[i], dp[i]);
                }
            }
        }
    }
}

[백준] 11053번: 가장 긴 증가하는 부분 수열 - Java, 자바

Wed, 30 Aug 2023 12:53:35 GMT

문제접근

이 문제는 다른 말로는 LIS(최장 증가 부분 수열)라고 부른다고 한다.
주어진 수열에서 오름차순으로 구성 가능한 원소들을 선택하여 최대 길이를 찾아 내는 것.
아래에서 풀 문제는 시간 복잡도가 O(N^2) 이다.

먼저 예제 출력을 갖고 살펴보면
기본적으로 수열을 갖고 있지 않아도 1이 할당된다.[자기 자신]
idx[0] = 10; 일때는 수열이 없기 때문에 값이 1이된다. idx[1] = 20; 일때는 앞에 값 {10, 20}으로 수열의 값이 2가 된다.
idx[2] = 10; 일 때는 앞에 값은 10보다 큰 20이기 때문에 수열의 값이 1이된다.
idx[3] = 30; 일 때는 idx[0]의 값 10, idx[1]의 값 20, 그리고 자신까지 해서 총 3이된다. {10, 20, 30}
idx[4] = 20; 일 때는 idx[0]의 값 그리고 자기자신 까지 해서 총 2의 값을 가진다. {10, 20}
idx[5] = 50; 일 때는 idx[0], idx[1], idx[3]과 자기 자신까지 해서 총 4가 된다. {10, 20, 30, 50}
그렇다면 어떻게 풀면 될까?
각 값에 대하여 이전 값과 비교하여 작다면 수열의 값을 늘려주면 된다.
즉, for loop에서 i가 3일 때 3 아래 값 0,1,2 와 비교하여 값이 수열에 해당한다면 값을 증가시켜주면 된다.

top-down

dp[] 은 기본적으로 idx의 해당하는 수열의 갯수를 저장하고 있다.
dp[]에서 기본적으로 모든 값은 1[자기자신]값을 갖고있다.
N의 값에 대하여 for loop를 도는데, 초기값은 N, i를 감소시키면서 N-1,N-2 ... 0 까지
N값과 비교하며 N보다 작다면 dp[N] 에 dp[N]과 재귀함수(i) + 1과 비교하여 큰 값을 dp[N]에 저장한다.
여기서 +1을 해주는 이유는 예를들어서,
N의 값이 비교하는 값보다 큰데, 비교하는 값 dp[i]에 대하여 dp[i]의 값은 dp[N]에 합쳐지는것 뿐만 아니라 arr[i]의 값은
arr[N]에 속해지는 수열이기에 + 1을 해주는 것이다.

N을 입력받는다.
- N을 입력받고 dp 배열과 number 배열을 초기화 해준다.
  - 여기서 dp배열은 수열의 값을 저장한다.
```
static Integer dp[];
static int[] number;
```

BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.parseInt(br.readLine());

dp = new Integer[N]; number = new int[N];

- 다음으로 입력받는 수열을 number 배열에 저장한다.
```java
for(int i = 0; i < N; i++) {
    number[i] = Integer.parseInt(st.nextToken());
}

초기값을 설정한다
```
dp[0] = 1;
```
for loop를 돌면서 dp[] 값을 초기화한다.
```
for(int i = 0; i < N; i++) {
  recur(i);
}
```
재귀함수에서는 dp[N]이 초기화 되지 않았을 경우 dp값을 초기화 해준다.
- 여기서는 dp[N]의 값의 초기값은 1로 설정해준다.
- for loop를 돌면서 N - 1 부터 시작하여 0까지 number 값을 비교한다.
- dp[N] 에는 dp[N] 값과 재귀함수(i) + 1 과 비교하여 큰 값을 dp[N]에 저장한다.

private static int recur(int N) {

    if(dp[N] == null) {

        dp[N] = 1;

        for(int i = N - 1; i >= 0; i--) {

            if(number[N] > number[i]) {
                dp[N] = Math.max(dp[N], recur(i) + 1);
            }
        }
    }

    return dp[N];
}

dp[] loop를 돌면서 max값을 출력한다.
```
int max = Integer.MIN_VALUE;
```

for(int i = 0; i < N; i++) { if (max < dp[i]) { max = dp[i]; } }

System.out.println(max);



### bottom-up
top-down과 동일한데 값을 설정할 때 for loop를 통해 dp[]을 초기화한다.
top-down과는 다른건 dp값을 초기화 할 때 조건이 하나 더 붙는다.   
조건이라기보다 top-down에서 Math.max로 비교하는 값이 조건으로 추가되는 것이다.   
기본적으로 number[i] 값이 비교하려는 number[j] 보다 커야한다. 그래야만 수열이 성립하기 때문이다.   
다음으로는 Math.max에서 dp[i] 값과 recur(N) + 1 값을 비교하는것을 여기에서는    
number[i] 에 해당하는 dp[i] 와 number[j]에 해당하는 dp[j] 에서 만약 number[i]가 더 큼에도 불구하고    
dp[i]가 dp[j] 보다 작을 경우 dp[i]에 dp[j] + 1을 초기화한다.   
여기서 + 1을 하는 이유는 number[i]가 number[j]보다 크기 때문에 number[j]가 number[i]의 수열에 포함되고, 자기자신 number[j] 도    
number[i]의 수열에 포함되기 때문에 + 1을 해주는 것이다.   


- N을 입력받는다.
```java
static Integer dp[];
static int[] number;

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

int N = Integer.parseInt(br.readLine());

dp = new Integer[N];
number = new int[N];

수열을 입력받아 number[] 을 초기화한다.

StringTokenizer st = new StringTokenizer(br.readLine(), " ");

for(int i = 0; i < N; i++) { number[i] = Integer.parseInt(st.nextToken()); }

- dp 초기값을 설정해준다.
```java
dp[0] = 1;

초기값 다음 1 부터 시작하여 N-1 까지 순회하며 dp값을 초기화한다.
- top-down과 동일하게 초기값은 dp[i]의 값은 1로 초기화해준다.
- 2중 for loop에서는 0부터 시작하여 i전 까지 돌면서 number[i]와 비교해준다.
- 여기서는 조건이 number[i]가 number[j] 보다 큰데도, dp[]의 값이 dp[j] 보다 작을경우
- dp[i]에 dp[j] + 1로 초기화 해준다.
```
for(int i = 1; i < N; i++) {

dp[i] = 1;

for(int j = 0; j < i; j++) {

  if(number[i] > number[j] && dp[i] <= dp[j]) {
      dp[i] = dp[j] + 1;
  }
}
}
```
dp를 순회하며 max값을 출력한다.
```
int max = Integer.MIN_VALUE;
```

for(int i = 0; i < N; i++) { if(max < dp[i]) { max = dp[i]; } }

System.out.println(max);


### 전체코드
```java
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static Integer dp [];
    static int number [];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        dp = new Integer[N];
        number = new int[N];

        for(int i = 0; i < N; i++) {
            number[i] = Integer.parseInt(st.nextToken());
        }

        //초기값
        dp[0] = 1;

        for(int i = 0; i < N; i++) {
            recur(i);
        }

        int max = Integer.MIN_VALUE;

        for(int i = 0; i < N; i++) {
            if (max < dp[i]) {
                max = dp[i];
            }
        }

        System.out.println(max);

    }

    private static int recur(int N) {

        if(dp[N] == null) {

            dp[N] = 1;

            for(int i = N - 1; i >= 0; i--) {

                if(number[N] > number[i]) {
                    dp[N] = Math.max(dp[N], recur(i) + 1);
                }
            }
        }

        return dp[N];
    }
}

전체코드 (bottom-up)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main2 {

    static Integer dp[];
    static int[] number;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());

        dp = new Integer[N];
        number = new int[N];


        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        for(int i = 0; i < N; i++) {
            number[i] = Integer.parseInt(st.nextToken());
        }

        dp[0] = 1;

        for(int i = 1; i < N; i++) {

            dp[i] = 1;

            for(int j = 0; j < i; j++) {

                if(number[i] > number[j] && dp[i] <= dp[j]) {
                    dp[i] = dp[j] + 1;
                }
            }
        }

        int max = Integer.MIN_VALUE;

        for(int i = 0; i < N; i++) {
            if(max < dp[i]) {
                max = dp[i];
            }
        }

        System.out.println(max);
    }
}

[백준] 9465번: 스티커 - Java, 자바

Wed, 30 Aug 2023 11:42:58 GMT

문제접근

2가지 방법으로 풀어보려고 한다.

top-down 방식 [Main.java] 이렇게 불러야 할지 모르겠지만 top-down 방식으로 풀어보도록 하겠다.
먼저 어떠한 값 (row, col)에 마지막에 도달하기 위해서는 아래 그림과 같은 접근만 가능하다.

그림에서 같이 값(row, col)에 대하여 접근할 수 있는 방법은 row = 0 일 때는 (row + 1, col - 2)와 (row + 1, col -1)에서 접근이 가능하다.
다음으로 row = 1일때는 (row - 1, col -2), (row - 1, col - 1)에서 접근이 가능하다.
문제에서는 최대값을 구하는 것이기에 접근할 수 있는 두 값 중 큰 것에서 마지막 값 (row, col)에 접근하면 되는 것이다. Math.max((row + 1, col - 2), (row + 1, col - 1)) [규칙 부분]
top-down 방식은 재귀를 통해 마지막까지 접근해 다시 역으로 올라오는 것이다. 다시말해 재귀의 종료시점은 배열이라면 첫 번째 값 [0]에 해당할 것이다. [초기화 부분]
다음으로 중요한 것은 예외이다. 위에서 보인 규칙에 따르면 현재 값의 (col -1)과 (col - 2) 값을 비교한다. 해당 문제를 풀기위해 배열을 사용할텐데, col <=1 이라면 배열에 벗어나 버려 오류가 발생한다 [예외 부분]
위의 조건들을 합치면 문제를 해결할 수 있다.

케이스 T를 입력받는다. 이 후에 입력받는 배열값을 나누기 위해 StringTokenizer를 선언한다.
- static 영역에는 메모이제이션에 사용할 배열과, 입력받는 스티커 정보를 저장할 배열을 선언한다.
```
static int[][] stickers;
static Integer[][] dp;
```

BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st;

int T = Integer.parseInt(br.readLine());

- 테스트 케이스만큼 돌면서 for문 안에서는 배열의 가로 길이 N을 입력받는다. 
  - 입력받은 N 으로 크기 [2][N + 1] 배열을 dp, stickers 배열을 초기화한다.  
    - 여기서 N + 1인 이유는 인덱스는 0 부터 시작하기 때문에 쉽게 이해하기 위해 1크기를 더 더했다.
  - 입력받은 스티커 정보에서 첫 번째 값 [0][1] 과 [1][1]의 값을 가지고 dp 배열의 초기값을 넣어준다.
```java
for(int i = 0; i < T; i++) {
    int N = Integer.parseInt(br.readLine());

    stickers = new int[2][N + 1];

    for(int j = 0; j < 2; j++) {
        st = new StringTokenizer(br.readLine(), " ");
        for(int k = 1; k <= N; k++) {
            stickers[j][k] = Integer.parseInt(st.nextToken());
        }
    }

    dp = new Integer[2][N + 1];

    dp[0][1] = stickers[0][1];
    dp[1][1] = stickers[1][1];

    System.out.println(Math.max(recur(0, N), recur(1, N)));
}

다음으로 재귀로 호출할 메서드이다.
- 메서드의 인자로는 2개의 정보를 받는다.
  - 하나는 row, 다른 하나는 col이다.
- 재귀의 종료 조건으로 col == 1 일때 stickers[row][col]을 리턴한다.
  - col == 1 인 이유는 col가 1에 도달했다는 건 오른쪽에서 시작하여 왼쪽 끝에 도달하였다는 말이기 때문이다.
- 다음으로는 메모이제이션 배열 dp가 초기화되지 않았다면 [dp[row][col] == null] 초기화를 해준다.
- (여기서 dp 배열의 값은 큰 값으로 갈 수록 이전 값의 누적 합이 저장된다.)
  - 이 때 조건으로는 col == 2 일 때는 뒤로 한칸밖에 없기 때문에 따로 최대값을 비교하지않고 (col -1) 값만 호출하여 현재 stickers[row][col] 값에 더해서 초기화 해준다.
    - 쉽게 생각하여 현재 (row, col) 값에 도달하기 위해서는 (row - 1, col -1), (row -1, col - 2) 둘 중에서 와야하는데, col == 2 인 상태에서 (col -2)를 배열을 넘어가기 때문이다.
  - col > 2 라면 그림에서 봤듯이 col -2, col - 1 중에 큰 값을 찾은 후 현재 값 stickers[row][col]과 더하여 dp[row][col]를 초기화해준다.
    - 여기서 1 - row 인 이유는 row 값은 0 또는 1 인데, 만약 현재 값이 0이라면 1에서 도달한 것이기에 1 - 0 => 1 이 되고, 현재 값이 1이라면 0 에서 도달한 것이기에 1 - 1 => 0 이 된다.
      - 즉, 쉽게 표현하기 위하여 1 - row로 짧게 쓴 것이다.
- 마지막에는 모두 초기화 된 메모이제이션에서 값만 꺼내어 return 한다.

메서드를 호출했던 부분에서는 마지막 값 dp[0][N] 과 dp[1][N] 중에서 큰 값을 출력한다.

private static int recur(int row, int col) {

  if (col == 1) {
      return stickers[row][col];
  }

  if (dp[row][col] == null) {
      if (col == 2) {
          dp[row][col] = recur(1 - row, col - 1) + stickers[row][col];
      } else {
          dp[row][col] = Math.max(recur(1 - row, col - 1), recur(1 - row, col - 2)) + stickers[row][col];
      }
  }

  return dp[row][col];
}

bottom-up 방식 위와는 다르게 for문을 통해 모든 값을 설정하고 마지막에 Math.max를 통해 dp[0][N], dp[1][N] 중 큰 값을 출력하는 것은 동일하다.
규칙은 위에서 설명했기에 생략한다.

T를 입력받는다.
여기서는 dp 배열을 Integer가 아닌 int 배열로 선언한다.
```
static int dp[][], stickers[][];
```

BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st;

int T = Integer.parseInt(br.readLine());

- test case t 만큼 for문을 돈다.
  - 여기서도 동일하게 n을 입력받고, 그 크기만큼 stickers, dp 배열을 초기화한다.
  - 다음으로 스티커 배열을 입력받아 초기화 시켜준다.
  - 초기값 dp[0][1], dp[1][1] 도 stickers 배열에서 가져와 초기화한다.
  - 여기서는 재귀를 사용하지않고, col == 2 부터 시작해 dp 배열의 값을 초기화한다.  
    - 여기서도 col == 2 일때 위에처럼 범위를 벗어나는게 아닌가 라고 생각할 수 있는데, 그래서 dp배열을 Integer가 아닌, int로 한 이유도 있다.
      - 원래라면 [0][0], [0][1] 에 값을  0으로 초기화 시켜줬어야 했지만, int 배열 초기값이 0 이기 때문에 따로 초기화 하지 않은 것이다.
  - 동일한 규칙을 이용해 (col - 2), (col - 1) 중 큰 값과 현재 값(stickers[0][j] or stickers[1][j])을 더하여 dp값을 초기화한다.
  - 마지막도 동일하게 dp[0][N], dp[1][N] 중 큰 값을 출력한다.

```java
for(int i = 0; i < T; i++) {
    int N = Integer.parseInt(br.readLine());

    stickers = new int[2][N + 1];
    dp = new int[2][N + 1];


    for(int j = 0; j < 2; j++) {
        st = new StringTokenizer(br.readLine(), " ");
        for(int k = 1; k <= N; k++) {
            stickers[j][k] = Integer.parseInt(st.nextToken());
        }
    }

    dp[0][1] = stickers[0][1];
    dp[1][1] = stickers[1][1];

    for(int j = 2; j <= N; j++) {
        dp[0][j] = Math.max(dp[1][j - 1], dp[1][j - 2]) + stickers[0][j];
        dp[1][j] = Math.max(dp[0][j - 1], dp[0][j - 2]) + stickers[1][j];
    }

    System.out.println(Math.max(dp[0][N], dp[1][N]));
}

전체코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    static int[][] stickers;
    static Integer[][] dp;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int T = Integer.parseInt(br.readLine());

        for(int i = 0; i < T; i++) {
            int N = Integer.parseInt(br.readLine());

            stickers = new int[2][N + 1];

            for(int j = 0; j < 2; j++) {
                st = new StringTokenizer(br.readLine(), " ");
                for(int k = 1; k <= N; k++) {
                    stickers[j][k] = Integer.parseInt(st.nextToken());
                }
            }

            dp = new Integer[2][N + 1];

            dp[0][1] = stickers[0][1];
            dp[1][1] = stickers[1][1];

            System.out.println(Math.max(recur(0, N), recur(1, N)));
        }
    }

    private static int recur(int row, int col) {

        if (col == 1) {
            return stickers[row][col];
        }

        if (dp[row][col] == null) {
            if (col == 2) {
                dp[row][col] = recur(1 - row, col - 1) + stickers[row][col];
            } else {
                dp[row][col] = Math.max(recur(1 - row, col - 1), recur(1 - row, col - 2)) + stickers[row][col];
            }
        }

        return dp[row][col];
    }
}

[백준] 2156번: 포도주 시식 - Java, 자바

Wed, 30 Aug 2023 11:15:16 GMT

문제접근

이 문제는 간단하게 보자면, N에 도달하기 위한 몇 가지 조건들 중에서 가장 큰 수를 뽑는 것 이다. 여기서는 몇가지 규칙이 있는데

마지막 N번 째 포도주를 마실 필요가 없다.
연속으로 놓여진 3잔을 모두 마실 수 없다.

마지막 N번 째 포도주를 마실 필요가 없다는 이유는, 문제의 마지막 부분에 가각의 잔에 순서대로 놓여진 포도주를 마시는 방법을 소개할 때 알 수 있다.

이 규칙들을 가지고 N에 도달하기 위한 몇 가지 조건들을 세워보자면 아래와 같다. 여기서 말하는 "N에 도달하기 위한"이 문제에서는 반드시 N에 도달할 필요는 없다. [N - 1 까지만 도달해도 된다.]

N번 째 포도주와, N-1번 째 포도주를 마시고, N - 3 까지의 누적 최대합을 더하는 것
N번 째 포도주를 마시고, N - 2 까지의 누적 최대합을 더하는 것
N번 째 포도주를 마시지 않고, N -1 까지의 누적 최대합을 더하는 것

규칙들을 코드로 나타내 보자면

wines[N] + wines[N -1] + dp[N -3]
wines[N] + dp[N -2]
dp[N - 1]

이렇게 나눈 이유는 첫 번째로는 연속으로 놓여진 3잔을 모두 마실수 없다. 그렇다면 최대한으로 마실 수 있는 잔의 수는 2잔인데, 만약 N을 마신다면 N - 1을 마신 후, N - 2는 못 마실것이다. 그말은 N - 3 잔 부터는 다시 마실 수 있다는 뜻이되고, N을 마신 후 N - 1을 마시지 않는다면 N - 2부터 다시 마실 수 있다는 것이다. 위의 말대로 만들어진 규칙이 1번 2번이 된다.
마지막으로 N을 마시지 않은경우 N - 1 까지의 최대값을 구한게 규칙이 될 것이다.

여기서 의문이 들 수 있는데, 그렇다면 N을 마시지 않고, N -1 을 마시고 한번 건너 뛴 N - 3 의 최대값을 더하면 되지 않을까? [wines[N - 1] + dp[N - 3]] 라는 생각이 들 수 있다.
여기서 생각을 해보면 dp에는 N - 3 까지 오면서 마실 수 있는 최대값을 선택하면서 왔을 것이다. 그런데 이 선택에 있어서 wines[N - 3]을 마셨을 수도, 마시지 않았을 수도 있다. 그렇기 때문에 N -2 를 건너뛰고 N -1 을 마시는 것은 최대가 되지 않을수도 있는 것이다. 따라서 dp[N - 1] 이란 규칙이 나온것이다. dp[N - 1]는 N - 1까지 오면서 선택할 수 있는 최대값을 선택하면서 왔기 때문이다.

전체코드

package date_2023_08_18.DP_2156;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {


    static Integer dp[];
    static int glass[];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());

        dp = new Integer[N + 1];
        glass = new int[N + 1];

        for(int i = 1; i <= N; i++) {
            glass[i] = Integer.parseInt(br.readLine());
        }

        //초기값 세팅
        dp[0] = 0;
        dp[1] = glass[1];


    }

    private static int recur(int N) {

        if(N == 1) {
            return dp[N];
        }

        if(dp[N] == null) {
            dp[N] = Math.max(Math.max(recur(N - 2), recur(N - 3) + glass[N - 1]) + glass[N], recur(N - 1));
        }

        return dp[N];
    }
}

정리

이 문제도 생각해보면 N에 도달하기 위한 규칙을 찾고, 그 규칙들 중 가장 큰 값을 찾는 문제였다. 간단하게 생각하자면, 규칙 중 최대값을 찾아 dp배열에 넣으면 끝.

[백준] 11057번: 오르막 수 - Java, 자바

Wed, 30 Aug 2023 10:42:15 GMT

문제접근

이 문제는 이 전 쉬운 계단수와 비슷한 문제이다. 다른점이 있다면 이 문제에서는 0으로 시작할 수 있다는 것이다. 쉬운계단 수

이 문제는 손으로 직접 적어보면 쉽게 이해가 가능하다.
이 문제에서는 0으로 시작하는 숫자 또한 수로 인정하고 있다.
1자리를 예를 들면 0 ~ 9 까지 총 10가지가 가능 할 것이다.

다음으로 2자리를 예시로 들면, 2자리는 2번째 자리 즉 10의 자리가 0 일때 첫 번째 자리 1의 자리는 0 ~ 9 까지 가능하다. [인접한 수가 같아도 오름차순으로 쳐주기 때문에]
10의 자리 | 1의자리
0 | 0 ~ 9

이어서 2번 째 자리가 1일 때는 첫 번쨰 자리는 1 ~ 9 까지,
10의 자리 | 1의자리
1 | 1 ~ 9

2번 째 자리가 2일때는 첫 번째 자리는 2 ~9 까지.... 2번 째 자리가 8일 때는 첫 번째 자리는 8 ~9 까지 2번 째 자리가 9일 때는 첫 번째 자리는 9 까지 가능하다.
10의 자리 | 1의자리
9 | 9 ~ 9

위의 규칙을 보자면 2번 째 자리의 값이 T 라면 첫 번째 자리의 값은 T ~ 9 까지 인것을 확인할 수 있다.
즉, 입력받은 N 번째 자리의 값이 T 일 때 N - 1번째 자리 값은 T ~ 9 까지이다.

전체코드 (top-down)

public class Main {

    static Long dp[][];
    static int mod = 10_007;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());

        dp = new Long[N + 1][10];


        //초기값 설정
        for(int i = 0; i <= 9; i++) {
            dp[1][i] = 1L;
        }


        long result = 0;

        for(int i = 0; i <= 9; i++) {
            result += recur(N, i);

        }
            System.out.println(result % mod);

    }

    static long recur(int digit, int val) {

        if (digit == 1) {
            return dp[digit][val];
        }

        if(dp[digit][val] == null) {
//            if (val == 9) {
//                dp[digit][val] = recur(digit - 1, 9) % mod;
//            } else {
//                long result = 0;
//                for(int i = val; i <= 9; i++) {
//                    result += recur(digit - 1, i);
//                }
//                dp[digit][val] = result  % mod;
//            }
            long result = 0;
            for(int i = val; i <= 9; i++) {
                result += recur(digit - 1, i);
            }

            dp[digit][val] = result % mod;
        }

        return dp[digit][val];
    }
}

코드 상세

N을 입력받는다.
- 입력받은 N + 1 크기의 이차원배열 생성
- N + 1인 이유는 인덱스가 0 부터 시작하기 때문에
- 두 번째 값이 10인 이유는 0~9까지 이기때문에
```
static Long dp[][];
static int mod = 10007;
```

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

int N = Integer.parseInt(br.readLine());

dp = new Long[N + 1][10];

- 배열의 초기값을 설정한다.
  - 1자리 일 때 각각의 수는 1개만 가능하기 때문에
```jpaql
for(int i = 0; i <= 9; i++) {
    dp[1][i] = 1L;
}

재귀함수를 만든다.
- 해당 함수에서는 digit [자릿수] 가 1 일 경우 dp[digit][val]를 리턴한다.
- 배열 값이 초기화가 되어있지않다면 [== null] 값을 초기화 한다.
- 위에서 얘기하였듯이 N번째 자리 val에 대하여 N - 1 자리 값은 val ~ 9 까지 이다.
  - 따라서 인자로 받은 val를 for의 초기값으로 설정하고 9 까지 for문을 돌면서 값을 저장한다.
- 값을 저장할 때는 mod만큼 나누어 저장한다. 여기서는 모듈러 연산이 사용된다.
```
static long recur(int digit, int val) {
if (digit == 1) {
    return dp[digit][val];
}

if(dp[digit][val] == null) {
    long result = 0;
    for(int i = val; i <= 9; i++) {
        result += recur(digit - 1, i);
    }

    dp[digit][val] = result % mod;
}

return dp[digit][val];
}
```
마지막으로 N번쨰 자리 0~ 9 까지 for문을 돌면서 결과를 구한다.
- 0 ~ 9 까지 인 이유는 조건에 나와있다.
```
long result = 0;
```

for(int i = 0; i <= 9; i++) { result += recur(N, i);

} System.out.println(result% mod);

```

정리

이 문제에서는 손으로 적어보면서 쉽게 풀 수 있었을 것이다. 별 다른 예외없이 가장 앞부터 0~9를 채우고 자릿수를 하나씩 줄여가며 범위를 줄여나가면 쉽게 해결 할 수 있었을 것이다.

[백준] 2193번: 이친수 - Java, 자바

Tue, 29 Aug 2023 07:44:28 GMT

문제접근

먼저 자릿수에 대한 개념을 잡기 위해서 이전 글을 참고하고 오면 이해하기 쉽습니다. 이전 글

이 전에 풀던DP와 같은 풀이로 푼다. 자릿수에 해당하는 자릿값으로 문제를 푸는데 dp[digit][val]
여기서 자릿값은 0 or 1, 2개만 가능하다.

다음 조건으로는 시작이 0 으로 시작하지 않는다는 점.
1이 연속으로 두 번 나타나지 않는다는 점.
이 조건들을 조합해보면 아래와같은 재귀함수를 만들 수 있다.

digit[자릿수] 가 1일때는 digit[digit][val]를 반환한다. [종료시점]
dp[digit][val] == null 일 때
- val이 1일때는 뒤에 올 수 있는 수는 0밖에 없으므로 recur(digit - 1, 0);
- val이 0일때는 뒤에 0 or 1이 올수 있기 때문에 recur(digit - 1, 0) + recur(digit -1 , 1) 이 된다.
  코드로 보면 아래와 같다.

전체코드 (top-down)

package date_2023_08_16.DP_2193;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    static Long dp[][];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());

        dp = new Long[N + 1][2];

        dp[1][0] = dp[1][1] = 1L;

        System.out.println(recur(N, 1));
    }

    static Long recur(int digit, int val) {

        if(digit == 1) {
            return dp[digit][val];
        }

        if(dp[digit][val] == null) {
            if(val == 1) {
                dp[digit][val] = recur(digit - 1, 0);
            } else {
                dp[digit][val] = recur(digit - 1, 0) + recur(digit - 1, 1);
            }
        }

        return dp[digit][val];
    }
}

코드 상세

N을 입력받는다.
- 입력받은 N으로 배열을 생성한다.
- 이 때 이차원 배열은 Long을 사용한다. 2^90이어 값이 넘어갈 수 있기 때문에..?
- N + 1 인 이유는 인덱스가 0 부터 시작하기 때문이고, 두 번째 크기가 2인 이유는 0 or 1 두개 만 들어가기 때문에.
```
static Long dp[][];
```

BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.parseInt(br.readLine()); dp = new Long[N + 1][2];

- 초기값을 설정한다.
```java
dp[1][0] = dp[1][1] = 1L;

재귀함수를 선언한다.
- 종료조건은 digit == 1 일때
- 아직 배열의 값이 초기화되지 않았다면
  - val == 1 일때는 뒷 값으로 0 밖에 오지 못함.
  - val == 0 일때는 뒷 값으로 0, 1 둘다 가능.
```
static Long recur(int digit, int val) {
```
  if(digit == 1) {
```
return dp[digit][val];
```
  }
  
  if(dp[digit][val] == null) {
```
if(val == 1) {
    dp[digit][val] = recur(digit - 1, 0);
} else {
    dp[digit][val] = recur(digit - 1, 0) + recur(digit - 1, 1);
}
```
  }
  
  return dp[digit][val]; } ```
재귀함수를 호출한다.
- N,1 만 호출하는 이유는 첫번 째 값이 1밖에 오지 못하기 때문이다.
```
System.out.println(recur(N, 1));
```

bottom-up

이제는 bottom-up으로 풀어보도록 하자. 어떠한 자릿수 N에 올 수 있는 수는 0 or 1 일 것이다. 그렇다면 N - 1에는 어떻게 와야하는가? N에서 0 일때는 1 or 0 둘 다 올 수 있지만 1일 경우는 0밖에 오지 못한다는 것을 알 수 있다.

if (val == 0) {
    dp[digit][val] = dp[digit - 1][0] + dp[digit -1][1];
} else {
//val == 1
    dp[digit][val] = dp[digit - 1][0];
}

bottom-up 전체코드


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    static Long dp[][];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());

        dp = new Long[N + 1][2];

        dp[1][0] = dp[1][1] = 1L;

        bottom_up(N);

            //1만 하는 이유는 N 자리 즉, 가장 앞자리에는 0이 올수 없기 때문에.
        System.out.println(dp[N][1]);
    }


    static void bottom_up(int N) {

        for(int i = 2; i <= N; i++) {
            for(int j = 0; j <= 1; j++) {

                if (j == 0) {
                    dp[i][j] = dp[i - 1][0] + dp[i - 1][1];
                } else if (j == 1){
                    dp[i][j] = dp[i - 1][0];
                }
            }
        }
    }

}

여담

이친수를 적다보면 규칙이 하나보이는데,

dp[1] = 1; dp[2] = 10; dp[3] = 100, 101; dp[4] = 1000, 1010, 1001; dp[5] = 10000, 10100, 10010, 10001, 10101;

dp[N]에 대하여 dp[N -1] 수 뒤에 0을 붙인 값 + dp[N]에 대하여 dp[N - 2] 수 뒤에 01 을 붙인 값을 더한게 dp[N]에 된다는 것이다..

dp[3]을 먼저 보면 dp[1] = 1에 01 을 붙인 [101]과 dp[2]에 0을 붙인 [100]이 곧 dp[3]이 된다. 다시, dp[4] 에서 dp[2]에 01을 붙인 [1001], dp[3]에 0을 붙인 [1000, 1010] 이 곧 dp[4]가 된다. 즉, dp[N] = dp[N -1] + dp[N -2]; 가 성립한다.
이렇게 1차원배열로도 문제를 풀 수 있다.

정리

이 문제는 풀 수 있는 방법이 여러가지였다. 저는 이전에 자릿수에 대해 문제를 풀었기에 2차원배열로 문제를 해결하였습니다. N자리에 들어갈 수 있는 값 [0,1]을 갖고 조건을 기준으로 이 전 dp[]값을 가지고 현재 dp[]을 구하는 것이었습니다.

[백준] 10844번: 쉬운 계단수 - Java, 자바

Tue, 29 Aug 2023 07:08:22 GMT

문제 접근

이 문제는 풀지못하여 좋아하는 이방인님 블로그를 참고하여 제 생각을 정리하였습니다.

출처: https://st-lab.tistory.com/134

몇 가지 조건을 알아보도록 하자. 길이가 3인 계단 수에 대해 구한다면 123, 345 등등이 사용될 것이다.
여기서 123을 살펴보면 3번째 자리의 값은 1, 두 번째 자리는 2, 첫번 째 자리는 3이 될것이다.
다른 조건으로는 인접한 모든 자리의 차이가 1이라는 것인데, 이것을 살펴보면 만약 0일 경우
다음으로는 1 밖에 오지못할 것이다. [-1이 올 수 없기 때문에] 다음으로는 9 다음으로는 8밖에 못 올것이다. [10이 못오기 때문에]
예를 들어 10 다음으로는 101, 89 다음으로는 898 밖에 올 수 없다는 말이다.
나머지 수 2~8 까지는 +1,-1 값을 가질 수 있다.
윗 그림은 제가 기억하기 위해 남겨놓습니다...

여기서는 2차원배열을 사용해야 하는데, 2차원 배열을 사용하는 이유는 [N번쨰 자리]의 [자릿값]을 표현하기 위해서 이다.
여기서 N번째 자리는 입력을 받을 것이고 해당 N번 째 자리에 들어가는 값들은 0 ~ 9 까지 일 것이다.
따라서 배열로 표현하면 [Long[N + 1][10]]이다.
여기서 N + 1 인 이유는 인덱스는 0부터 시작이고, 자연수는 1부터 시작이기 떄문이다.
10또한 같은 이유로 9가 아닌 10의 크기를 갖는 것이다.

여기서 헷갈릴 수 있는데, 2차원 배열에서 첫 번째 배열은 자릿수에 해당한다. 아래에서 예를 들어보자
만약 10123 이란 숫자가 있다고 가정할 때
숫자: 1 0 1 2 3
자리: 5번째자리 4번째자리 3.. 2.. 1
이렇게 표현이 가능할텐데, 배열같은 경우 왼쪽에서 오른쪽으로 읽는데, 여기서는 다르게
인덱스를 마치 N번째 자리에 해당하는 값이라고 생각하면 쉽게 이해할 수 있다. 다시말해,
10123일 때
숫자: 1 0 1 2 3
인덱스: 5 4 3 2 1
자리: 5 4 3 2 1
이런식으로 값이 들어가게 된다.

다음으로 1자리만 주어진다면 1 ~9 가 가능하며, 계단 수는 각각 1이 된다.
[1][1] ~ [1][9] = 1;

이제 조건을 가지고 재귀함수를 만든다면 아래와 같을 것이다.
재귀함수는 2가지 인수를 갖는데, 하나는 자릿수에 해당하는 digit과 해당 자리에 할당되어있는 자릿값 val이다. 위에 보았듯이 1자리만 주어졌을 때 1이 모두 할당되었으니 재귀의 종료시점은 digit이 1일 때이다.

private static long recur(int digit, int val) {

    if(digit == 1) {
        return dp[digit][val];
    }
}

다음으로는 0과 9에 대한 조건이다. 자리수 N에 대하여 0일 때 뒤에는 1밖에 오지못한다는 점과
9일 때 뒤로는 8밖에 못오는 점이다.
위에서 설명했듯이 이차원배열의 첫 번째 배열은 N번 째 자리를 나타내는 것이다.
예를들어서
숫자: 1 0 1
자리: 3 2 1
인덱스: 3 2 1
따라서 digit - 1를 이해하자면 2째 자리가 0 일때 다음 첫 째 자리로는 1 만 올 수 있기 때문에
digit - 1, 1이 오게되는 것이다.

if(val == 0) {
    dp[digit][val] = recur(digit - 1, 1) % mod;
} else if (val == 9){
    dp[digit][val]=recur(digit-1, 8) % mod;
}

0,9를 제외한 수는 +1, -1를 가질 수 있다.

} else {
    dp[digit][val] = (recur(digit - 1, val - 1) + recur(digit - 1, val + 1)) % mod;
}

참고한 블로그에서 모듈러연산을 사용하였는데, 모듈러연산에 대해 짧게 설명하자면
% 연산에 대한 나머지 값이 같다는 것이다.
3 % 10 과 13 % 10의 결과 값이 같다는 것이다.
%연산에 대해서 몫은 중요하지 않고, 나머지가 같은 값이 나온다는 것을 설명한다.
A % B 에 대해서 A에 B를 여러번 더해도 같은 결과가 나온다는 것이다.
3 % 10, 13 % 10, 23 % 10 ...,
이것을 가지고 값이 long이 넘어갈 수도 있기 때문에 dp[][]에 저장을 할 때 % mod 만큼하여 저장한다.
결과에서도 % mod한 값을 출력하기 때문이다.
mod값이 10,000일 경우 10,007 % 10,000 에서의 결과는 7이고
7 % 10,000 에서의 결과도 7로 동일하기 때문이다.

전체코드 top-down [재귀]


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    static Long[][] dp;

    static long mod = 1_000_000_000;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());

        //배열 생성
        dp = new Long[N + 1][10];

        //초기값 설정
        for(int i = 0; i < 10; i++) {
            dp[1][i] = 1L;
        }

        long result = 0;
        // N에 도달하기 위한 1 ~9 까지의 수를 구한다.
        for(int i = 1; i <= 9; i++) {
            result += recur(N, i);
        }

        System.out.println(result % mod);

    }

    private static long recur(int digit, int val) {

        if(digit == 1) {
            return dp[digit][val];
        }

        if(dp[digit][val] == null) {

            if(val == 0) {
                dp[digit][val] = recur(digit - 1, 1) % mod;
            } else if (val == 9) {
                dp[digit][val] = recur(digit - 1, 8) % mod;
            } else {
                dp[digit][val] = (recur(digit - 1, val - 1) + recur(digit - 1, val + 1)) % mod;
            }
        }

        return dp[digit][val];
    }
}

bottom-up

다른 문제로 top-down으로 해결했던 문제를 bottom-up으로 다시 풀어보려 한다.
bottom-up 방식은 아래에서 부터 위로 올라가는 방식으로 초기값 이후 ~ N까지 진행하며 값을 채운다. 따라서, bottom-up 같은경우 이 전 값을 이용하여 현재 dp[] 을 채운다. 다시말해,
N = 3 일때 N < 3 일때의 값을 가지고 N = 3을 채운 다는 것이다.
생각해보면 위의 값은 채워지지 않았기 때문에 이 전값을 사용하는것은 당연한걸지도..?

위에서 볼 수 있듯이 초기값은 1자리 일 경우 1 ~ 9 의 값은 1만 갖는다.

for(int i = 1; i < 10; i++) {
    dp[1][i] = 1;
}

그리고 조건으로는 만약 현재 자리값의 수가 0 일 때는 1에서 밖에 오지 못 한것이고, 9일때는 8에서 밖에 오지 못한것이다. 그 이외의 숫자 2~8은 다음 자릿수의 +1, -1에서 온 것이다.

if(val == 0) {
    dp[digit][val] = dp[digit - 1][1] % mod;
} else if (val == 9) {
    dp[digit][val] = dp[digit - 1][8] % mod;
} else {
    dp[i][j] = (dp[i - 1][j + 1] + dp[i -1][j - 1]) % mod;
}

전체코드 bottom-up

package date_2023_08_15.DP_10844;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    static Long[][] dp;

    static long mod = 1_000_000_000;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());

        //배열 생성
        dp = new Long[N + 1][10];

        //초기값 설정
        for(int i = 0; i < 10; i++) {
            dp[1][i] = 1L;
        }

        long result = 0;
        bottom_up(N);

        for(int i = 1; i <= 9; i++) {
            result += dp[N][i];
        }

        System.out.println(result % mod);

    }


    static void bottom_up(int N) {

        for(int i = 2; i <= N; i++) {

            for(int j = 0; j < 10; j++) {
                if(j == 0) {
                    dp[i][j] = dp[i - 1][1] % mod;
                } else if (j == 9) {
                    dp[i][j] = dp[i - 1][8] % mod;
                } else {
                    dp[i][j] = (dp[i - 1][j + 1] + dp[i -1][j - 1]) % mod;
                }
            }
        }
    }
}

정리

이 문제는 풀면서 처음으로 나온 이차원 배열이다. 여기서 이차원 배열의 개념은 어떠한 N의 자리에 대하여 1~9까지의 값 이었다. 어떠한 N의 자리 / 1 ~ 9 까지의 경우의 수 아직 어떨 때 2차원 배열을 써야하는지 개념이 잡히지 않았지만, 대략 이렇게 이해하고 있다.
이 문제의 경우 예외 조건을 찾는것 또한 중요하다. 곰곰히 생각해보면 어떠한 수 X에 대하여 도달할 수 있는 경우의 수를 찾는 문제였다. 예를 들어, 2자리 3 [2][3] 에 도달하려면 [1][2] 또는 [1][4] 에서 [2][3]에 도달할 수 있는 그런 느낌.. 이랄까.. 거기에 몇 가지 예외를 추가하여 푼 문제 같다.

틀려도 일단 기록하자

docker 공부 시작하기 [spring-boot] run 과 start의 차이와 attach, detach에 대해서- (3)

📙종료된 컨테이너 다시 실행하기

📗 attach, detach

docker 공부 시작하기 [spring-boot] 도커파일에 작성되는 명령어 알아보기- (2)

📕명령어 비교하기

📙 RUN, CMD, ENTRYPOINT

📒RUN

📒CMD

📒ENTRYPOINT

📒 CMD, ENTRYPOINT 차이

📙 COPY, ADD

📙ENV, ARG

📙EXPOSE

📙추가적인 테스트

📒 EXPOSE와 같은 포트 바인딩해보기

📒 -P 옵션과 -p 같이 사용하기

📒 그렇다면 -p 옵션에서 다른 포트 바인딩 시엔??

📙VOLUME, BIND MOUNT

📒VOLUME

📒VOLUME 생성하기

📒컨테이너에 VOLUME 마운트하기

📒VOLUME 삭제

📒BIND MOUNT

출처

docker 공부 시작하기 [spring-boot] 도커 파일로 컨테이너 실행하기- (1)

📕 시작

📕프로젝트 구성

📙실행과정

📕Dockerfile

📒Dockerfile 말고 다른이름은 안되나요??

📒Dockerfile의 위치는??

📙작성된 Dockerfile

📙하나씩 알아보기

📒FROM

📗실행해보기

📒CMD

📗어떻게 해야할까?

📒COPY

📗그러면 어떻게 해야 할까??

📒추가적으로

📒WORKDIR

📒ARG

📕시행착오

📒ERROR: failed to solve: no build stage in current context

📗해결법

📒starting 무한로딩

📗해결법

참고

[spring-vue] 웹소켓으로 채팅 구현하기 (5) - vue 화면 설명

📘vue.config.js

📘AXIOS 사용 시

📘STOMP

📗Client 객체 생성

📗subscribe 하기

📗publish 하기

📗disconnect하기

[spring-vue] 웹소켓으로 채팅 구현하기 (4) - DB 추가 및 엔티티 추가

📗구현

📘엔티티 설정

📘테스트 데이터 추가

📘API 추가

📘시나리오1

📘시나리오2

정리

[spring-vue] 웹소켓으로 채팅 구현하기 (3) - STOMP

📕STOMP

📗개요

📗사용이유

📗구현

📘시나리오1

📘시나리오2

📘시나리오 테스트

정리

출처:

[spring-vue]웹소켓으로 채팅 구현하기 (2) - 프로젝트 생성 및 스프링웹소켓

📗프로젝트 생성

📗spring-websocket

📘postman으로 테스트 하기

📘session객체 저장하기