Out Of Memory

자바 애플리케이션 환경인 WAS 기반에서 수행된 서비스들에 대해서는 흔히 JVM Heep 메모리 관련 오류들을 흔하게 접할수 있다.
OOME(Out Of Memory Error)는 JVM의 메모리가 부족하여 발생한 에러로 그 종류/원인은 다양하다.

Java.lang.OutOfMemoryError: Java heap space

Java의 Heap Memory 공간이 부족하여 발생한다. 공간 부족의 원인으로는 Heap Memory의 크기가 작아서 발생하는 경우와 애플리케이션 로직의 문제로 발생하는 경우가 있다.

해당 오류를 해결하기 위한 가장 쉬운 방법으로는 -Xmx 옵션을 사용하여 Heap Memory의 크기를 증가시키는 방법이 있지만 이는 GC Time의 증가를 동반하기 때문에 충분한 사전 테스트가 필요하다.

OOME가 발생한 시점에 생성된 Heap Dump 분석을 기반으로 쓸데없이 많은 Memory를 사용하거나 Memory Leak을 유발하는 로직을 찾아내어 수정해야 한다.

Java.lang.OutOfMemoryError : PermGen space

Java Heep Memory 영역 중 Permanent 영역은 Class Method와 관련된 각종 Meta Data 등을 저장하는 용도로 사용된다. 따라서 JVM 기동시 로딩되는 Class 또는 String의 수가 많다면 Java.lang.OutOfMemoryError : PermGen space의 원인이 됩니다. 또한 Classloader Leak에 의해 OOME가 발생될 수 있다.

Permanent 영역은 Heap 영역과는 달리 일반 비즈니스 프로그램으로 핸들링 할 수 없기때문에 JVM Option 튜닝으로도 해결이 되지 않는다면 WAS 혹은 JDK 버그를 의심해봐야 한다.

PermGen 영역은 Class를 로딩하고 해제하지 않으면 누수가 일어나며 PermGen 영역에 OutOfMemory가 발생할 수 있다. Class Loading 현황을 분석하려면 컨텍스트 메뉴에서 Java Basics > Class Loader Explorer를 선택해서 확인 할 수 있다.

AOP(Aspect Oriented Programing)

AOP는 관점 지향 프로그래밍이다.

쉽게 말해서 AOP는 애플리케이션 전체에 걸쳐 사용되는 기능을 재사용 하도록 지원하는 것이다.

관점 지향 프로그래밍이라는 단어가 AOP를 이해하는데 더 어려움을 일으킨다.

쉽게 설명하면 프로젝트 구조를 바라 보는 관점을 바꿔 보자는 것이다.

(제 3자의 관점)

(핵심기능에서 바라본 관점)

(부가기능에서 바라본 관점)

부가적 기능의 관점엑서 보면 각각의 서비스는 before와 after 메소드를 공통으로 사용하고 있다.

기존의 OOP에서 바라보던 관점을 다르게하여 부가기능적인 측면에서 보았을때 공통된 요소를 추출하자는 것이 관점 지향 프로그래밍이다.

• OOP : 비지니스 로직의 모듈화
  • 모듈화의 핵심 단위는 비지니스 로직
• AOP : 인프라 혹은 부가기능의 모듈화
  • 대표적 예 : 로깅, 트랜잭션, 보안 등
  • 각각의 모듈들의 주 목적 외에 필요한 부가적인 기능들

AOP는 새로운 개념은 아니다!

결국은 공통된 기능을 재사용하는 기법

기존 OOP같은 경우 상속이나 위임을 통해 처리하지만 자바의 경우 다중 상속을 지원하지 않을뿐더러 상속이나 위임으로 처리하기에는 깔끔하게 모듈화가 어렵다고 한다.

그래서 이러한 문제를 해결하기 위해 AOP가 등장하게 되었고 AOP의 큰 장점은 2가지가 있다.

1. 어플리케이션 전체에 흩어진 공통 기능이 하나의 장소에서 관리된다는 점
2. 다른 서비스 모듈들이 본인의 목적에만 충실하고 그외 사항들은 신경쓰지 않아도 된다는 점

AOP용어

타겟(Target)

부가기능을 부여할 대상을 말한다.
위에 그림에선 공통된 기능을 가진 Service들을 얘기한다.

애스펙트(Aspect)

객체지향 모듈을 오브젝트라 부르는것과 같게 부가기능 모듈을 애스펙트라 부르며, 핵심기능에 부가되어 의미를 갖는 특별한 모듈이라 생각하면 된다.

어드바이스(Advice)

실질적으로 부가기능을 담은 구현체
어드바이스는 타겟 오브젝트에 종속되지 않기 때문에 순수하게 부가기능에만 집중 할 수 있다.
어드바이스는 애스펙트가 무엇을 언제할지를 정의한다.

포인트컷(PointCut)

부가기능이 적용될 대상(메소드)를 선정하는 방법을 얘기한다.
즉, 어드바이스를 적용할 조인포인트를 선별하는 기능을 정의한 모듈을 얘기한다.

조인포인트(JoinPoint)

어드바이스가 적용될 수 있는 위치를 얘기한다.
Spring에서는 메소드 조인포인트만 제공하고 있다.
따라서 Spring 내에서 조인포인트라 하면 메소드를 가르킨다고 생각하면 된다.

프록시(Proxy)

타겟을 감싸서 타겟의 요청을 대신 받아주는 랩핑(Wrapping)오브젝트이다.
클라이언트에서 타겟을 호출하게 되면 타겟이 아닌 타겟을 감싸고 있는 프록시가 호출되어, 타깃 메소드 실행전에 선처리, 메소드 실행 후, 후처리를 하도록 구성되어 있다.

인트로덕션 (Introduction)

타겟 클래스에 코드 변경없이 신규 메소드나 멤버변수를 추가하는 기능을 얘기한다.

위빙 (Weaving)

지정된 객체에 애스팩트를 적용해서 새로운 프록시 객체를 생성하는 과정을 얘기한다.
예를 들면 A라는 객체에 트랜잭션 애스팩트가 지정되어 있다면, A라는 객체가 실행되기전 커넥션을 오픈하고 실행이 끝나면 커넥션을 종료하는 기능이 추가된 프록시 객체가 생성되고, 이 프록시 객체가 앞으로 A 객체가 호출되는 시점에서 사용된다. 이때의 프록시객체가 생성되는 과정을 위빙이라 생각하면 된다.
Spring AOP는 런타임에서 프록시 객체가 생성 된다.

실습(어노테이션)

1
2
3
4
5
6
7
8
9

@SpringBootApplication
@EnableAspectAutoProxy
public class SomeApplication {

    public static void main(String[] args) {

        ApplicationContext ctx = SpringApplication.run(Application.class, args);
    }
}

• @SpringBootApplication 또는 @Configuration을 명시한 클래스에 @EnableAspectAutoProxy를 명시하면 Spring AOP를 사용하기 위한 첫 준비가 끝난다.
• @EnableAspectAutoProxy은 XML 기반의 ApplicationContext 설정에서의 <aop:aspectj-autoproxy />와 동일한 기능을 한다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

@Component
@Aspect
@Order(Ordered.LOWEST_PRECEDENCE)
public class SomeAspect {

    @Around("execution(* com.blogcode.board.BoardService.getBoards(..))")
    public Object calculatePerformanceTime(ProceedingJoinPoint proceedingJoinPoint) {
        Object result = null;
        try {
            long start = System.currentTimeMillis();
            result = proceedingJoinPoint.proceed();
            long end = System.currentTimeMillis();

            System.out.println("수행 시간 : "+ (end - start));
        } catch (Throwable throwable) {
            System.out.println("exception! ");
        }
        return result;
    }
}

• 스프링 빈에 @Aspect를 명시하면 해당 빈이 Aspect로 작동한다.
• 클래스 레벨에 @Order를 명시하여 @Aspect 빈 간의 작동 순서를 정할 수 있다. int 타입의 정수로 순서를 정할 수 있는데 값이 낮을수록 우선순위가 높다. 기본값은 가장 낮은 우선순위를 가지는 Ordered.LOWEST_PRECEDENCE이다.
• @Aspect가 명시된 빈에는 어드바이스(Advice)라 불리는 메써드를 작성할 수 있다. 대상 스프링 빈의 메써드의 호출에 끼어드는 시점과 방법에 따라 @Before, @After, @AfterReturning, @AfterThrowing, @Around 등을 명시할 수 있다.

(포인트컷 표현식)

• @Before (이전)
  • 어드바이스 타겟 메소드가 호출되기 전에 어드바이스 기능을 수행
• @After (이후)
  • 타겟 메소드의 결과에 관계없이(즉 성공, 예외 관계없이) 타겟 메소드가 완료 되면 어드바이스 기능을 수행
• @AfterReturning (정상적 반환 이후)
  • 타겟 메소드가 성공적으로 결과값을 반환 후에 어드바이스 기능을 수행
• @AfterThrowing (예외 발생 이후)
  • 타겟 메소드가 수행 중 예외를 던지게 되면 어드바이스 기능을 수행
• @Around (메소드 실행 전후)
  • 어드바이스가 타겟 메소드를 감싸서 타겟 메소드 호출전과 후에 어드바이스 기능을 수행

제약조건

테이블에 올바른 데이터만 입력 받고 잘못된 데이터는 들어오지 못하도록 칼럼마다 정하는 규칙

해당 조건과 맞지 않는 데이터가 들어오면 걸러내기 때문에 데이터의 정확성이 올라간다.

종류는 총 5가지이다.

NOT NULL

컬럼 생성시 지정하지 않으면 default로 Null이 허용가능하게 되어 있다.
따라서 해당 컬럼값을 입력하지 않고 튜플을 삽입시 Null이 들어가게 되는데
이를 방지하기 위해서는 Not Null을 기술해 주면 된다.

UNIQUE

유일한 값만 들어가도록 하고 싶을 때 사용한다.

즉, 중복이 허용되지 않도록 데이터를 넣어야하는 경우 사용한다.

Primary Key

기본키이다.
기본키란 해당 테이블을 대표하는 컬럼으로 Primary key로 지정된 컬럼은 Null값을 가지지 못하며,
중복된 값을 가질 수 없다.

즉, 이 primary key에 의해 튜플들은 중복되지 않고 구분될 수 있게 된다.
따라서 UNIQUE와 NOT NULL을 동시에 정의한 것과 효과가 같아진다.

Foreign Key

외래키를 의미하는 제약조건이다.
외래키는 참조 무결성을 위해 사용되는데 이 외래키로 지정된 컬럼은 반드시 다른 테이블의 “Primary key(기본키)”와 참조 관계를 가지게 되고
외래키로 지정된 컬럼은 참조관계를 가진 테이블의 기본키에 있는 값만을 가질 수 있다.

즉, Null 값은 허용하되, 참조하고 있는 테이블의 기본키에 있는 값만 입력될 수 있다.

CHECK

입력될 수 있는 데이터의 종류를 제한할 수 있다.

ex) coin CHAR(1) CHECK(coin IN(‘P’,’N’,’D’))

MySQL은 CHECK 제약조건을 지원하지 않는다고 한다.

마무리

PRIMARY KEYY 빼고 제약조건은 여러 칼럼에 중복으로 설정될 수 있고,

하나의 칼럼에도 여러개의 제약 조건들이 중복으로 설정될 수있음.

신발사이즈 추천 서비스 ShoesFit

설명

ShoesFit은 집단지성을 이용한 신발 사이즈 추천 서비스 입니다.

자신이 가지고 있는 두개의 신발을 이용하여 원하는 신발의 브랜드와 이름을 입력하면 다른사람들의 입력한 정보를 토대로 신발사이즈를 추천해줍니다.

입력한 두개의 신발은 연관 관계를 만들어 저장함으로 다른사람들의 검색의 도움을 주는 정보가 됩니다.

기술 설명

Spring Boot를 이용하여 신발 추천 알고리즘 및 API를 개발하였습니다.

MyBatis 대신 JPA를 사용하였습니다.

JavaScript와 jQuery를 이용하여 자동완성 기능을 만들었으며 Ajax를 이용하여 API를 호출하여 사용하였습니다.

Travis CI를 이용하여 자동 빌드와 CodeDeploy를 이용한 자동 빌드, Nginx를 이용한 무중단 배포까지 하였습니다.

freenom에서 무료 도메인을 받아 aws 네임서버를 이용하여 도메인 연결을 하였습니다.

let’sencrypt의 certbot을 이용하여 빠르게 ssl을 적용하였습니다.

기술 요약

• SpringBoot
• JavaScript
• jQuery
• JPA
• AWS EC2(Amazon Linux)
• AWS RDS(Maria DB)
• AWS CodeDeploy
• AWS S3
• AWS Rout 53
• Travis CI
• Nginx
• certbot

사용방법

1. 가지고 있는 신발 두개의 브랜드와 이름 사이즈를 입력하세요.
2. 사이즈를 알고 싶은 신발의 브랜드와 이름을 입력하세요.
3. 두신발 검색 버튼을 눌러서 검색해주세요.

주의사항

• 브랜드와 이름이 같은 신발은 입력하실 수 없습니다.
• 찾으시는 신발이 자동완성에 있으면 자동완성에 있는 단어를 입력해주세요. ex)에어맥스가 자동완성 리스트에 있으면 airmax(X) 에어맥스(O)

향후계획

• CSS 추가(ㅜㅜ)
• JS 기능 추가 및 완벽하게 (간단하게만 해놓은 상태)
• API 보완 및 기능 확대
• 진짜 서비스

JPA란

JPA는 여러 ORM 전문가가 참여한 EJB 3.0 스펙 작업에서 기존 EJB ORM이던 Entity Bean을 JPA라고 바꾸고 JavaSE, JavaEE를 위한 영속성(persistence) 관리와 ORM을 위한 표준 기술이다. JPA는 ORM 표준 기술로 Hibernate, OpenJPA, EclipseLink, TopLink Essentials과 같은 구현체가 있고 이에 표준 인터페이스가 바로 JPA이다.

ORM 이란

ORM(Object Relational Mapping)이란, Object(객체)와 Relation(관계형 데이터베이스) 간의 불일치 문제를 해결하기 위한 도구다.

흔히 알고 있는 ibatis나 mybatis는 ORM이 아니다. SQL 구문을 Mapping 하여 실행하는 sql mapper이다.

장단점

장점

객체지향적으로 데이터를 관리할 수 있기 때문에 비즈니스 로직에 집중 할 수 있으며, 객체지향 개발이 가능하다.
테이블 생성, 변경, 관리가 쉽다. (JPA를 잘 이해하고 있는 경우)
로직을 쿼리에 집중하기 보다는 객체자체에 집중 할 수 있다.
빠른 개발이 가능하다.

단점

어렵다. 장점을 더 극대화 하기 위해서 알아야 할게 많다.
잘 이해하고 사용하지 않으면 데이터 손실이 있을 수 있다. (persistence context)
성능상 문제가 있을 수 있다.(이 문제 또한 잘 이해해야 해결이 가능하다.)

어노테이션 정리

@Entity

JPA에서 Entity라는 것은 데이터베이스에 저장하기 위해서 유저가 정의한 클래스다. 일반적으로 RDBMS에서 Table의 정의 비슷한 것이다. Table의 이름이나 컬럼들에 대한 정보를 가진다.

@Id

일반적으로 키(primary key)를 가지는 변수에 선언한다. @GeneratedValue 어노테이션은 해당 Id 값을 어떻게 자동으로 생성할지 전략을 선택할 수 있다.

@Table

@Table을 이용하면 별도의 이름을 가진 데이터베이스 테이블과 매핑할 수 있다. 기본적으로 @Entity로 선언된 클래스의 이름은 실제 데이터베이스의 테이블 명과 일치하는 것을 매핑한다. 따라서 @Entity의 클래스명과 데이터베이스의 테이블명이 다르면 @Table(name=”XXX”) 같은 형식으로 작성하면 이름을 다르게 해서 매핑이 가능하다.

@Column

@Column에서 지정한 멤버 변수와 데이터베이스의 컬럼명을 다르게 주고 싶다면 @Column(name=”XXX”) 같은 형식으로 작성해주면 된다. 그렇지 않으면 기본적으로 멤버 변수명과 일치하는 데이터베이스의 컬럼을 매핑 한다.

그외의 어노테이션들이나 사용법들은 추후에 더 포스팅 하도록 하겠습니당

Filter, Iterceptor, AOP의 차이점 및 정리

스프링으로 웹 개발을 하다보면 Filter, Interceptor, AOP를 이용해 전/후 처리를 할 수 있다,

셋 다 비슷한 기능을 가지고 있지만 시점이나 적용하는 방식이 다르다.

Filter

말그대로 요청과 응답을 거른뒤 정제하는 역할을 한다.

서블릿 필터는 DispatcherServlet 이전에 실행이 되는데 필터가 동작하도록 지정된 자원의 앞단에서 요청내용을 변경하거나, 여러가지 체크를 수행할 수 있다.

또한 자원의 처리가 끝난 후 응답내용에 대해서도 변경하는 처리를 할 수가 있다.

보통 web.xml에 등록하고, 일반적으로 인코딩 변환 처리, XSS방어 등의 요청에 대한 처리로 사용된다.

Filter 메서드

init() - 필터 인스턴스 초기화

doFilter() - 전/후 처리

destroy() - 필터 인스턴스 종료

Interceptor

필터는 스프링과 무관하게 지정된 자원에 대해 동작한다.

스프링은 DistpatcherServlet으로부터 시작되므로 필터는 스프링 컨텍스트 외부에 존재하게 된다.

하지만 인터셉터는 스프링의 DistpatcherServlet이 컨트롤러를 호출하기 전, 후로 끼어들기 때문에 스프링 컨텍스트 내부에 존재하게된다.

그리고 스프링 내의 모든 객체(bean) 접근이 가능하다.

인터셉터는 여러 개를 사용할 수 있고 로그인 체크, 권한체크, 프로그램 실행시간 계산작업 로그확인, 업로드 파일처리등에 사용된다.

Interceptor 메서드

preHandler() - 컨트롤러 메서드가 실행되기 전

postHanler() - 컨트롤러 메서드 실행직 후 view페이지 렌더링 되기 전

afterCompletion() - view페이지가 렌더링 되고 난 후

AOP

객체 지향의 프로그래밍을 했을 때 중복을 줄일 수 없는 부분을 줄이기 위해 종단면(관점)에서 바라보고 처리한다.

주로 ‘로깅’, ‘트랜잭션’, ‘에러 처리’등 비즈니스단의 메서드에서 조금 더 세밀하게 조정하고 싶을 때 사용합니다.

Interceptor나 Filter와는 달리 메소드 전후의 지점에 자유롭게 설정이 가능하다.

Interceptor와 Filter는 주소로 대상을 구분해서 걸러내야하는 반면, AOP는 주소, 파라미터, 애노테이션 등 다양한 방법으로 대상을 지정할 수 있다.

AOP의 포인트컷

@Before: 대상 메서드의 수행 전

@After: 대상 메서드의 수행 후

@After-returning: 대상 메서드의 정상적인 수행 후

@After-throwing: 예외발생 후

@Around: 대상 메서드의 수행 전/후

정리

Dispatcher-Servlet 이란

Servlet Container에서 HTTP프로토콜을 통해 들어오는 모든 요청을 프레젠테이션 계층의 제일앞에 둬서 중앙집중식으로 처리해주는 프론트 컨트롤러(Front Controller)

클라이언트로부터 어떠한 요청이 오면 Tomcat(톰캣)과 같은 서블릿컨테이너가 요청을 받는데,
이때 제일 앞에서 서버로 들어오는 모든 요청을 처리하는 프론트 컨트롤러를 Spring에서 정의하였고,
이를 DispatcherServlet이라고 한다.

그래서 공통처리 작업을 DispatcherServlet이 처리한 후, 적절한 세부 컨트롤러로 작업을 위임한다.

Dispatcher-Servlet의 처리과정

먼저 DispatcherServlet이 요청을 받으면 그 요청을 처리할 수 있는 Handler의 이름을 HandlerMapping에게 물어본다.

HandlerMapping은 요청 URL을 보고 Handler를 판단하고, 또한 Handler 실행 전에 전처리, 후처리로 실행해야 할 인터셉터 목록을 결정한다.

DispatcherServlet은 제어권을 Handler로 전달한다.

Handler는 응답에 필요한 서비스를 호출하고 응답에서 렌더링해야 하는 View Name을 판단해서 DispatcherServlet에 전송한다.

DispatcherServlet은 논리적인 View Name을 ViewResolver에 전달해서 응답에 필요한 View를 생성할 수 있도록 한다.

그 후 해당 View에 Model과 컨트롤러를 전달해서 응답을 생성한다.

이렇게 생성한 응답을 클라이언트에게 반환한다.

단어 변환

문제 설명

두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다.

1. 한 번에 한 개의 알파벳만 바꿀 수 있습니다.
2. words에 있는 단어로만 변환할 수 있습니다.
   예를 들어 begin이 hit, target가 cog, words가 [hot,dot,dog,lot,log,cog]라면 hit -> hot -> dot -> dog -> cog와 같이 4단계를 거쳐 변환할 수 있습니다.

두 개의 단어 begin, target과 단어의 집합 words가 매개변수로 주어질 때, 최소 몇 단계의 과정을 거쳐 begin을 target으로 변환할 수 있는지 return 하도록 solution 함수를 작성해주세요.

제한사항

• 각 단어는 알파벳 소문자로만 이루어져 있습니다.
• 각 단어의 길이는 3 이상 10 이하이며 모든 단어의 길이는 같습니다.
• words에는 3개 이상 50개 이하의 단어가 있으며 중복되는 단어는 없습니다.
• begin과 target은 같지 않습니다.
• 변환할 수 없는 경우에는 0를 return 합니다.

  소스 코드

  자바

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51

  import java.util.*; class Solution { public int solution(String begin, String target, String[] words) { int[] countarray = new int[words.length]; //words배열 안의 단어까지 도달하는 카운트를 저장하는 배열 boolean[][] array = new boolean[words.length][words.length]; //각 단어에서 단어로 변환 될수 있는지를 나타내기 위한 배열 int targetindex=-1; //최종으로 변환되어야 하는 단어의 인덱스를 저장하기 위한 변수 Queue<Integer> queue = new LinkedList<Integer>(); for(int i=0; i<words.length;i++){ //시작 단어에서 변환 가능한 단어들을 찾기위한 반복문 int count =0; for(int j=0;j<begin.length();j++){ if(count==2)break; if(words[i].charAt(j)!=begin.charAt(j)){ count++; } } if(count==1){ //변환이 가능하면 큐에 집어 넣고 도달하는 카운트를 1로 저장 queue.offer(i); countarray[i]++; } if(words[i].equals(target)){ //단어가 최종 단어이면 인덱스를 저장 targetindex=i; } } if(targetindex==-1) return 0; //배열안에 최종 단어가 존재하지 않으면 0을 반환 for(int i=0; i<words.length;i++){ //단어에서 다른 단어로 변환이 가능 하는지 확인하는 반복문 for(int j=i+1;j<words.length;j++){ int count =0; for(int k=0;k<begin.length();k++){ if(count==2)break; if(words[i].charAt(k)!=words[j].charAt(k))count++; } if(count==1){ //i단어에서 j단어로 변환이 가능하면 array[i][j]를 true로 array[i][j]=true; array[j][i]=true;//방향성이 없기때문에 array[j][i]도 true로 } } } while(!queue.isEmpty()){ //BFS시작 int index = queue.poll(); for(int i=0; i<words.length;i++){ if(countarray[i]==0 &&array[index][i]){ countarray[i]=countarray[index]+1; queue.offer(i); } } } return countarray[targetindex]; } }

소스코드 설명

단어간 변화 할수 있는지 charAt함수를 이용하여 한글자씩 비교 하였고 한개만 다른 경우에는 변화 할 수 있다 생각하여 배열에 양방향으로 true를 주었습니다.

배열을 만들고 큐를 이용하여 반복문을 돌려 BFS를 구현하였습니다. 이미 탐색한 문자열은 countarray를 이용하여 체크하며 해당 문자열이 몇번째로 탐색 되었는지 카운트를 입력하였으며

countarryay[targetindex]를 이용하여 목표 문자열은 몇번째로 탐색 되었는지 결과값을 리턴하였습니다.

도둑질

문제 설명

도둑이 어느 마을을 털 계획을 하고 있습니다. 이 마을의 모든 집들은 아래 그림과 같이 동그랗게 배치되어 있습니다.

각 집들은 서로 인접한 집들과 방범장치가 연결되어 있기 때문에 인접한 두 집을 털면 경보가 울립니다.

각 집에 있는 돈이 담긴 배열 money가 주어질 때, 도둑이 훔칠 수 있는 돈의 최댓값을 return 하도록 solution 함수를 작성하세요.

제한사항

이 마을에 있는 집은 3개 이상 1,000,000개 이하입니다.

money 배열의 각 원소는 0 이상 1,000 이하인 정수입니다.

입출력 예

소스 코드

자바

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
    public int solution(int[] money) {
        int answer = 0;
        int length = money.length;
        int[] dp =new int[length-1];
        int[] dp2= new int[length];
        
        dp[0]=money[0];
        dp[1]=money[0];
        dp2[0]=0;
        dp2[1]=money[1];
        for(int i=2;i<length-1;i++){
            dp[i]=Math.max(dp[i-2]+money[i],dp[i-1]);
        }
        for(int i=2;i<length;i++){
            dp2[i]=Math.max(dp2[i-2]+money[i],dp2[i-1]);
        }
        
        return Math.max(dp[length-2],dp2[length-1]);
    }
}

소스코드 설명

값을 저장할 dp배열을 2개를 만들었습니다. 한개는 처음 집을 훔치는 경우이며 다른 한개는 처음 집을 훔치지 않는 경우 입니다.

dp배열은 처음 집을 훔치기때문에 인접한 마지막 집은 훔칠수 없으므로 반복문은 length-1 전까지만 돌렸습니다.

dp[0]과 dp[1]은 0번째 집부터 1번째 집까지 가장 많이 훔칠수 있는 금액인데 0번집을 훔치기때문에 1번째 집은 훔칠수없게되고 dp[1]까지의 가장큰 금액은 첫번째 집을 훔친 경우이므로 dp[0],dp[1]에는 0번 집의 돈을 넣어 줬습니다.

반복문을 돌면서 두번째 전의 최대 돈에 현재 번째 집의 돈을 합친것과 이전의 최대 돈을 비교하여 dp배열을 채웁니다.

dp2의 경우는 0번째 집에서는 돈을 훔치지 않는 경우이며 0을 넣어주고 dp2[1]에는 1번째 집의 돈을 넣어주고 똑같은 방법으로 반복을 시킵니다.

dp2는 첫번째 집에서는 돈을 훔치지 않으므로 반복문은 length까지 돌렸습니다.

dp와 dp2의 마지막 값을 비교하여 더 큰값을 출력 하여 정답을 구하였습니다.

정수 삼각형

문제 설명

위와 같은 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾아보려고 합니다. 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능합니다. 예를 들어 3에서는 그 아래칸의 8 또는 1로만 이동이 가능합니다.

삼각형의 정보가 담긴 배열 triangle이 매개변수로 주어질 때, 거쳐간 숫자의 최댓값을 return 하도록 solution 함수를 완성하세요.

제한사항

삼각형의 높이는 1 이상 500 이하입니다.

삼각형을 이루고 있는 숫자는 0 이상 9,999 이하의 정수입니다.

입출력 예

출처

소스 코드

자바

1
2
3
4
5
6
7
8
9
10
11
12

class Solution {
    int answer=0;
    public int solution(int[][] triangle) {
        
        for(int i =triangle.length-2;i>=0;i--){
            for(int j=0;j<triangle[i].length;j++){
                triangle[i][j]=triangle[i+1][j]>triangle[i+1][j+1]?triangle[i][j]+triangle[i+1][j]: triangle[i][j]+ triangle[i+1][j+1];
            }
        }
        return triangle[0][0];
    }  
}

소스코드 설명

처음에는 재귀함수를 통하여 모든 결과를 더하고 맨마지막 행에 도달했을 때 점수가 최대값보다 크면 최대값을 갱신하는 방법을 이용하였습니다.

문제가 원하는 방법이 아니듯 시간 초과로 실패 하였고 다른 방법을 생각하였습니다.

갈수 있는 길은 [i][j]일 경우 [i+1][j] or [i+1][j+1]이기 때문에 반대로 올라가는 방법을 생각하게 되었고

[i][j]에 [i+1][j] 과 [i+1][j+1] 더 큰값을 더해주면서 삼각형 맨 위까지 반복문을 돌리게 되면 triangle[0][0]에는 최대 값이 저장 됩니다.