Sevity Blog

현재 만들어 보고 있는 online judge 프로젝트의 서비스 구성은 다음과 같다.(관련 있는 2개만 표시. 실제로는 7개)

인증 서비스 (Backend): 사용자의 회원 가입, 로그인, 로그아웃, 세션 관리 등을 담당
인증 서비스 (Frontend): 사용자 인터페이스를 제공 (로그인 폼, 회원가입 폼 등)

한가지 알아두면 좋은점은 Spring Boot의 경우 /login, /logout endpoint의 경우 직접 정의하지 않아도 자동으로 처리한다는 점이다.(이점 때문에 디버깅시 많이 헷갈렸다ㅠ)

세션은 서버에서 브라우저로 set-cookie 헤더를 통해서 세션아이디를 부여한다.

아래처럼 브라우저 개발자 도구에서 확인가능하다(애플리케이션탭 > 쿠키섹션)

서버의 세션과 브라우저(클라이언트)의 쿠키 개념

세션을 서버에서 생성하고 세션id를 set-cookie를 통해서 브라우저(클라이언트)로 전달한다.

이때 쿠키는 브라우저를 종료해도 유지되는 지속쿠키를 쓰고 만료시점을 정의할수도 있고, 세션쿠키를 쓰면 브라우저 종료시 자동으로 쿠키도 삭제된다.

서버의 세션의 경우 지속시간을 application.properties에 다음과 같이 지정할 수 있다.

server.servlet.session.timeout=30m

현재 내가 테스트중인 프로젝트에서는 /login 성공시 세션쿠키가 발급되며, 세션 타임아웃의 효과는 확인이 안되었다.

일단은 이정도에서 더 깊이 안파고 넘어가기로 한다.

트러블슈팅

http에서 포트가 서로다른 서비스(MSA)간 연동하기

아래 크롬 설명에 따르면 https를 쓰고 secure 옵션을 주어야 SameSite=None으로 지정하면서 포트가 달라도 쿠키저장이 된다는것 같다.(관련글, 관련글2)

set-cookie로 응답을 제대로 했음에도 브라우저에 쿠키저장이 안될때

클라이언트에서 서버로 요청할때 credential을 보내줘야 했다(이것땜에 한참헤맴 ㅠ)

      const response = await axios.post('https://sevity.com:9991/login', `username=${username}&password=${password}`, {
        headers: {
          'Content-Type': 'application/x-www-form-urlencoded',
        },
        withCredentials: true,  // 여기, 이 줄 없으면 브라우저에 쿠키저장 안된다!!
      });

getSession(true)의 안전성

HttpSession session = request.getSession(false); 를 하면 존재하는 세션정보를 가져오고, false자리에 true를 넣으면 없으면 생성하라는 의미인데, 이렇게 하면 (내가만든세션), (SpringSecurity에 의해 아직 없지만 생성될 세션) 이렇게 두벌이 될까봐 우려했는데, 나중에 확인해보니 그렇지는 않았다. 따라서 항상 true로 호출해도 무방한 것 같다.

단 여기를 보면 멀티스레드 환경에서 레이스 컨디션에 의해 중복세션과 중복쿠키가 생성되는 경우는 있는 것 같다. 해결책은 아래처럼 동기화블록내에 생성과 처리를 묶어주면 되긴할듯(현재 내 구현에서는 그렇게 까지 하진 않았다)

synchronized (request) {
    HttpSession session = request.getSession(true);
    // ... 세션 사용 코드 ...
}

TMI

/login에서 반환되는 response.data 값과 SESSION쿠키의 값은 동일하나, SESSION쿠키의 경우 base64로 인코딩 되어 있다.

//response.data: c8545bb7-c90b-4d69-9128-08efd0a73866
//SESSION(쿠키): Yzg1NDViYjctYzkwYi00ZDY5LTkxMjgtMDhlZmQwYTczODY2

let encodedSessionId = 'Yzg1NDViYjctYzkwYi00ZDY5LTkxMjgtMDhlZmQwYTczODY2';
let decodedSessionId = atob(encodedSessionId);
console.log(decodedSessionId);  // 출력: c8545bb7-c90b-4d69-9128-08efd0a73866

Mypy

Mypy는 Python 코드에 대해 정적 타입 검사를 수행하는 도구입니다.

이는 TypeScript의 컴파일러와 유사한 역할을 수행하며, 코드에서 타입 오류를 찾아내는 데 도움이 됩니다​.

예제:
먼저 mypy를 설치합니다:

pip install mypy

다음은 mypy를 사용한 Python 코드 예제입니다:(name에 대해 str이라는 어노테이션을 했음에 주목. python 3.5기능)

# 파일명: example.py

def greeting(name: str) -> str:
    return "Hello, " + name

age: int = "25"  # 이 줄은 타입 오류를 발생시킵니다.

print(greeting("Alice"))

터미널에서 mypy를 사용하여 코드를 검사합니다:

mypy example.py

이 명령을 실행하면, mypy는 age: int = "25"라인에서 타입 오류를 발견하고 이를 알려줍니다.

Pytype:

Pytype은 또 다른 Python 정적 타입 검사 도구.

어노테이션이 없어도 추론을 기반으로 동작함.

예를들어 아래와 같이 어노테이션이 없는 코드에 대해서 pytype을 수행하면

def multiply_numbers(a, b):
    return a * b

result = multiply_numbers(5, '3')
print(result)

아래처럼 런타임전 경고를 확인할 수 있음(런타임에서는  Python은 문자열 '3'을 5번 반복하여 '33333'을 생성하고 오류로 판단하지 않음)

$ pytype example.py
Computing dependencies
Analyzing 1 sources with 0 local dependencies
ninja: Entering directory `/Users/user/.pytype'
[1/1] check example
FAILED: /Users/user/.pytype/pyi/example.pyi 
pytype-single --imports_info /Users/user/.pytype/imports/example.imports --module-name example -V 3.8 -o /Users/user/.pytype/pyi/example.pyi --analyze-annotated --nofail --quick /Users/user/example.py
File "/Users/user/example.py", line 4, in <module>: unsupported operand type(s) for *: 'int' and 'str' [unsupported-operands]
  Function multiply_numbers was called with the wrong arguments (1:15)

For more details, see https://google.github.io/pytype/errors.html#unsupported-operands.
ninja: build stopped: subcommand failed.

Mypy vs Pytype

Mypy

Mypy는 Dropbox에서 개발되었으며, Python의 첫 번째 정적 타입 검사 시스템으로 간주됩니다.

이 도구는 2012년부터 개발이 시작되었으며, 아직도 활발하게 개발이 진행되고 있습니다​.
Mypy는 standalone으로 실행되거나, 커맨드 라인이나 편집기 또는 IDE의 linter 통합의 일부로 작동할 수 있습니다.
Mypy는 타입 어노테이션을 포함하지 않은 코드에 대해 대부분의 코드 검사를 수행하지 않으며, 이는 점진적으로 코드 기반을 주석 처리하고 있는 경우 Mypy가 시간을 낭비하지 않도록 하기 위함입니다.

Pytype

Pytype는 Google에서 개발되었으며, Mypy와 달리 타입 설명자 대신 추론을 사용합니다. 즉, Pytype는 코드 흐름을 분석하여 타입을 결정하려고 시도하며, 타입 어노테이션에 엄격하게 의존하지 않습니다​1.
Pytype는 가능한 한 관대하게 행동하며, 런타임에서 작동하고 어떤 어노테이션도 모순되지 않는 연산이 있으면 Pytype는 그것에 대해 불평하지 않습니다.
pytype의 reveal_type(expr)을 사용해서 런타임 전에 type()과 비슷한 기능을 활용하여 디버깅/개발 가능

TypeScript vs ECMAScript

ECMAScript (ES):

ECMAScript는 JavaScript 언어의 표준 사양입니다.
ECMAScript는 JavaScript의 기본 구조와 규칙을 설정하며, JavaScript 엔진이 이 표준을 따라 구현되어야 합니다.
ECMA International이라는 표준화 기구가 관리하며, 시간이 지남에 따라 여러 버전의 ECMAScript 사양이 발표되었습니다 (예: ES3, ES5, ES6/ES2015 등).

TypeScript

TypeScript는 Microsoft에서 개발한 JavaScript의 상위 집합(superset) 언어입니다.
TypeScript는 JavaScript의 모든 기능을 포함하며, 그 위에 정적 타입 체크와 인터페이스, 제네릭, 데코레이터 등과 같은 추가 기능을 제공합니다.
정적 타입 체크는 코드의 오류를 런타임 전에 찾아내고, 코드의 가독성과 유지 관리성을 향상시킵니다.
TypeScript는 개발 시간에 TypeScript 코드를 JavaScript 코드로 변환(트랜스파일)하여 실행할 수 있도록 합니다. 이는 TypeScript 컴파일러를 사용하여 수행됩니다.

비교:

타입 시스템: TypeScript는 정적 타입 시스템을 제공하는 반면, ECMAScript(JavaScript)는 동적 타입 시스템을 사용합니다.
추가 기능: TypeScript는 ECMAScript의 기능에 추가적인 기능을 제공하여, 큰 프로젝트의 관리와 유지 보수를 돕습니다.
호환성: TypeScript는 JavaScript와 완벽하게 호환되며, TypeScript 코드는 JavaScript 코드로 변환될 수 있습니다.
표준화: ECMAScript는 국제 표준이며, TypeScript는 Microsoft에 의해 관리되는 오픈 소스 프로젝트입니다.

코드 샘플

// javascript
function add(a, b) {
    return a + b;
}

const result = add(5, '10');  // Output: '510' (문자열 연결)


//typescript
function add(a: number, b: number): number {
    return a + b;
}

const result = add(5, '10');  // Type Error: Argument of type 'string' is not assignable to parameter of type 'number'.

위의 TypeScript 코드에서 add 함수는 두 개의 숫자 타입 매개변수를 받아야 하며, 숫자 타입의 값을 반환해야 한다는 것을 명시적으로 지정합니다. 따라서, 문자열을 매개변수로 전달하려고 하면 컴파일 타임에 타입 에러가 발생합니다.

이 예제는 TypeScript의 정적 타이핑이 코드의 안정성을 어떻게 향상시키는지 보여줍니다. TypeScript는 개발자에게 잠재적인 문제를 미리 알려주어, 런타임 에러를 줄이고 코드의 품질을 향상시킵니다.

도입배경

2000년대 초반에는 웹 개발에서 주로 쿠키를 사용하여 클라이언트 측 데이터를 저장하곤 했습니다. 그러나 쿠키는 몇 가지 제약 사항과 문제점이 있었습니다. 예를 들어, 쿠키는 작은 용량의 데이터만 저장할 수 있고, 모든 HTTP 요청에 자동으로 포함되어 네트워크 부하를 초래할 수 있습니다.

이러한 문제를 해결하기 위해 HTML5 명세의 일부로 Local Storage와 Session Storage가 도입되었습니다. 이 기술은 2009년에 W3C에 의해 표준화되었고, 대부분의 현대 웹 브라우저에서 지원됩니다

.

Local Storage와 Session Storage의 주요 특징:

클라이언트 측 저장: 이들은 클라이언트 측에서만 접근 가능하며, 서버로 전송되지 않습니다. 이로 인해 네트워크 부하가 줄어듭니다.

용량: 일반적으로 5~10MB의 데이터를 저장할 수 있어, 쿠키보다 훨씬 더 많은 정보를 저장할 수 있습니다.

API: JavaScript를 통해 간단하게 데이터를 저장하고 검색할 수 있는 API가 제공됩니다.

Session Storage는 탭이나 창이 닫힐 때까지 데이터를 유지하며, Local Storage는 영구적으로 데이터를 저장합니다.

Local Storage는 도메인, 프로토콜, 그리고 포트까지 모두 일치해야만 데이터에 접근할 수 있기 때문에, 포트가 다른 두 서비스에서는 Local Storage를 공유할 수 없습니다. 

코드 샘플

// Local Storage에 정보 저장
localStorage.setItem('isLoggedIn', 'true');

//Local Storage에서 정보 불러오기
const storedIsLoggedIn = localStorage.getItem('isLoggedIn');

브라우저에서 확인

크롬에서 F12를 누르고 애플리케이션탭 > 왼쪽탭에서 로컬 스토리지를 보면 다음처럼 내용 확인이 가능하다.

Q. 설계 디자인 문제의 경우 초기에 질문할 것들은?

• 기능적 요구사항
• 비기능적 요구사항
  • 성능, 확장성, 안정성, 보안
  • 비용최적화
  • 트래픽패턴
• 제약사항
  • 벤드위스, 시스템사양, 외부시스템 디펜던시
• 프로세스
  • 스케일아웃등 의사결정시 데이터 포인트 필요(응답시간, 에러율, CPU/메모리/IO사용율, 대기중인요청, 스레드개수등)
  • 메트릭측정
  • 필드테스트전 로드테스트(환경구축 필요)

Q. 과부하처리

• 웹서버/WAS
  • 정적컨텐츠면 CDN(Content Delivery Network) 고려
  • 커넥션풀
  • 로드밸런싱(리버스 프록시)
  • Scale up, Scale out
  • Auto Scaling
• DB
  • 쿼리최적화/인덱싱
  • 머터리얼뷰(정규화 수준 낮추기)
  • Master/Slave분리
  • 샤딩, 분산트렌젝션(2단계 커밋)
  • NoSQL도입(쓰기작업이 많거나, 주문서등 비정형 데이터 저장)
  • 이벤트소싱(CQRS)
•  캐시적용(Redis등)
  • 읽는경우: Look aside. Cache에 있으면 Cache에서 가져오고 없으면 DB에서 읽고 Cache에 업데이트
  • 쓰는경우:
    • Write Through. 항상 cache에 저장하고 DB에도 저장
    • Write Back. Cache에 저장하고 주기적으로 모아서 DB에 배치 업데이트
  • 일관성보완: 캐시만료timeout, 쓰기시 캐시무효화
  • 가용성보완: 캐시복제

•  
  • Redis의 한계: 싱글스레드. 
    • keys대신 scan사용
• 비동기 처리
  • 대기열 시스템을 통한 고객 경험 개선
•  코드최적화
  • 지연로딩(이미지등), 디바운싱(마지막 요청만 처리)
• 전송방식 변경
  • gRPC
• 외부 디펜던시가 있다면
  • 스로틀링(rate limit포함, 요청수 제한), 서킷브레이크(close, open, half-open)
    • 푸시/풀(전자는 리소스헤비)
    • failover=fallback(다른 결제 시스템)
  • 분리된 Queue에 요청을 저장하고, 백그라운드로 처리. 시스템 복구시 순차적 처리
  • 회로차단기로 막혔을때의 요청을 DLQ(Dead Letter Queue)에 넣고 모니터링 후 원래큐로 돌리거나 후처리.

Q. 장애대층

• 네트워크 실패 문제
  • 다중 AZ, 서킷브레이크(외부 서비스면)
• 단일 실패지점
  • 데이터 복제, 로드밸런싱, 자동장애복구(클라우드), 장애격리(MSA)
  • 다중 AZ

Q. 무중단 DB마이그레이션(RDB > NoSQL기준)

• 데이터 동기화
  • 이미 존재하는 RDB데이터를 NoSQL로 복사(배치, ETL)
• 더블 Writing (RDB, NoSQL)
• 읽기연산을 NoSQL로 전환
• 쓰기연산 전환, RDB중단(feature flag사용)
• 경우에 따라 일부 사용자 또는 서비스만 전환(카나리테스트)
• 중간중간에 일관성확인/모니터링/롤백계획도 수립하면서 해야함

Q. Monolithic에서 MSA로 전환

• 도메인 분석을 통해 몇개 서비스로 나눌지 결정
• 비즈니스영향력이 작고 기술적으로 단순한 도메인 부터 이전
• DB분리 > 서비스간 API설계 > 통계는 별도 ETL구축
• 단점: API는 DB Join보다 비싸고 느림. 대안: 모듈식(펑션콜/공유메모리/로컬큐)

Q. 도메인주도설계(DDD)

• DB스키마 부터 설계하고 CRUD > 비즈니스로직 구현 순서가 아님
• 비즈니스부터 고민. 바운디드 컨텍스트(용어 정의)
• 애그리게이트(대출계좌, 대출자, 대출상품을 묶어 대출로 애그리게이트)
• 이벤트(대출신청, 승인, 상환)
• 서비스(복잡한 비즈니스로직 예를들어 대출 신용평가)

Q. NoSQL vs 스팍/하둡 vs Kafka

• NoSQL: 실시간성
• 스팍/하둡: 배치(하둡은 디스크액세스때문에 느리고, 스팍은 실시간성이 있으나 데이터 저장/관리 기능없음)
• Kafka: 배치보다는 실시간성에 강점. 하지만 메시지가 저장되므로 배치에도 사용가능.

 인과관계 추론

• RCT(Randomized Controlled Trial). 즉 A/B테스트는 랜덤하게 나누는게 중요하며 인과관계를 과학적으로 보여준다(나머지기업은 인과관계추론이 완전하게 안됨) 좋지만 인공실험이 필요.
• RD(Regression Discontinuity): 회귀불연속설계법. 경계선에 집중

• 집군분석(Cluster Analysis):

• 패널데이터분석: 평행 트렌드 가정이 성립해야함.

생성 패턴 (Creational Patterns)
생성 패턴은 객체 생성과 관련된 문제를 해결합니다.

싱글턴 패턴 (Singleton Pattern): 클래스의 인스턴스가 하나만 생성되도록 보장.
팩토리 메서드 패턴 (Factory Method Pattern): 객체 생성을 서브클래스에 위임.
빌더 패턴 (Builder Pattern): 복잡한 객체를 단계별로 생성합니다.

• 생성자의 인수가 너무 길고 복잡할때 이를 보완.
• method chaining 과 함께 사용

프로토타입 패턴 (Prototype Pattern): 기존 객체를 복제하여 새 객체를 생성합니다.

• python deepcopy()

구조 패턴 (Structural Patterns)

구조 패턴은 클래스나 객체의 구성을 단순화하고 확장성을 높입니다.

어댑터 패턴 (Adapter Pattern): 호환되지 않는 인터페이스를 변환하여 함께 작동하게 합니다.

• 바꾸기 힘든 레거시를 품은 새로운 클래스 만들어서 기존 구조와 통합

브리지 패턴 (Bridge Pattern): 구현부에서 추상화를 분리하여 독립적으로 변화할 수 있게 합니다.

• 잘 안쓰는듯? abstract 와 interface 사이에 다르를 놓는것 같은데..

컴포지트 패턴 (Composite Pattern): 객체들을 트리 구조로 구성하여 부분-전체 계층을 표현합니다.

• 단일요소와 집합요소를 모두 같은 부모를 상속 받도록 해서 복잡한 트리구조도 단일 개체로 표현가능
• Folder와 File이 모두 Unit이라는 부모를 상속받도록 하는 것 생각

데코레이터 패턴 (Decorator Pattern): 객체에 동적으로 새로운 책임을 추가합니다.
퍼사드 패턴 (Facade Pattern): 복잡한 시스템에 대한 간단한 인터페이스를 제공합니다.

• 이건 그냥 복잡한 단계를 하나의 API로 묶어서 단순화 하는 개념.

플라이웨이트 패턴 (Flyweight Pattern): 공유를 통해 대량의 객체를 효율적으로 지원합니다.
프록시 패턴 (Proxy Pattern): 다른 객체에 대한 대리자나 플레이스홀더 역할을 합니다.

• 준비시간이 오래걸리는 프린터 앞에 버퍼프린터 대리자로 모아서 처리하는거 생각하면 됨

행동 패턴 (Behavioral Patterns)
행동 패턴은 객체 간의 책임과 알고리즘을 관리합니다.

책임 연쇄 패턴 (Chain of Responsibility Pattern): 요청을 객체의 체인을 통해 전달합니다.
명령 패턴 (Command Pattern): 요청을 객체로 캡슐화합니다.

• 행동도 객체화 할수 있다는 것(포토샵 액션 리스트 생각)

해석자 패턴 (Interpreter Pattern): 문법 규칙을 클래스로 표현합니다.

• 컴파일러 비슷한일 할때, 클래스로 처리

반복자 패턴 (Iterator Pattern): 컬렉션의 요소를 순회하는 방법을 제공합니다.
중재자 패턴 (Mediator Pattern): 객체 간의 상호작용을 캡슐화하여 객체들이 직접 참조하지 않도록 합니다.
메멘토 패턴 (Memento Pattern): 객체의 상태를 캡쳐하고 복원합니다.
감시자 패턴 (Observer Pattern): 객체 간의 일대다 의존성을 정의합니다.

• 구독하면 알림보내는거 생각하면됨. 이벤트일 필요없고 콜백도 가능

상태 패턴 (State Pattern): 객체의 내부 상태에 따라 행동을 변경합니다.

• 상태를 객체로 표현하여, 조건문처리를 단순화 한다.

전략 패턴 (Strategy Pattern): 알고리즘을 캡슐화하여 상호 교체 가능하게 합니다.

• 암것도 아님. 추상화를 통해 sum()등의 행동을 갈아 끼울 수 있다는 것.

템플릿 메서드 패턴 (Template Method Pattern): 알고리즘의 구조를 정의합니다.
방문자 패턴 (Visitor Pattern): 객체 구조에 새로운 연산을 추가합니다.

• 데이터와 행동을 클래스 분리. 이렇게 하면 행동의 추가 확장이 편해짐(sum, avg등)

주 역할

웹서버/캐시/로드밸런서/리버스프록시

SSL Termination

클라이언트와는 https통신을 하면서 백단 서버들과는 http(gRPC포함)통신을 하여, 복호화 부담을 줄이는 기능

실전꿀팁

여기가면 실제로 많이 사용되는 Nginx설정을 보고 적용할 수 있다.

일반적으로 셔플 알고리즘을 떠올리면 다음과 같은 naive solution을 생각하기 쉽다.

void LnNumber::ShuffleArray(long* arr, long count)
{
      for (int i=0;i<count;i++)
      {
            long toInx = rand() % count;
            {//swap
                  long temp = arr[i];
                  arr[toInx] = arr[i];
                  arr[i] = temp;
            }
      }
}

하지만 위 코드는 순진해보이는 겉모습과 다르게 엄청난 바이어스를 포함하고 있는데,

카드 3장의 모든 순열은 3!(=3 x 2 x 1) = 6이지만 위의 toInx를 보면 3 x 3 x 3 = 27로 6으로 나눠떨어지지 않는 경우의 수를 가지고 있다!

따라서 아래처럼 덜 직관적이지만 n!에 맞춘 경우의 수를 가진 코드로 수정해줘야 한다.

이 코드를 Fisher-Yates shuffle이라고 한다.

void LnNumber::ShuffleArray(long* arr, long count) {
    for (int i = count - 1; i > 0; i--) {
        long toInx = rand() % (i + 1); // 0부터 i까지의 랜덤한 인덱스(i포함)
        // swap
        long temp = arr[i];
        arr[i] = arr[toInx];
        arr[toInx] = temp;
    }
}

이코드의 toInx를 보면 카드3장의 예시에서 3 x 2 x 1 = 6 = 3!의 경우의 수를 가진다.

sort

가장 기본적인 sort는 Array.sort()또는 Collections.sort()를 쓰면 된다. (char[] 같은건 전자만 가능한듯?)

struct node 같은걸 쓰면서 특정 필드에 대해 소팅하고 싶으면 다음 기법을 쓰자.

class Tweet {
    Long time;
    int tweetId;
}
List<Tweet> feed;
...

//time에 대해서 sort하고 싶을때
feed.sort((t1, t2) -> t1.time.compareTo(t2.time));  
//역순을 원하면 t1, t2를 바꿔준다.
feed.sort((t1, t2) -> t2.time.compareTo(t1.time));

//약간 올드하게 아래처럼도 가능
Collections.sort(feed, new Comparator<Tweet>() {
    @Override
    public int compare(Tweet t1, Tweet t2) {
        return t1.time.compareTo(t2.time);
    }
});

여러 필드에 대해서 복잡하게 정렬해야하면 아래 방법 사용

feed.sort(Comparator.comparing((Tweet t) -> t.time)
                   .thenComparing(Comparator.comparing((Tweet t) -> t.tweetId).reversed()));

LIS(Longest Increasing Subsequence)는 가장 긴 증가하는 부분 수열을 찾는 알고리즘이다.

즉, 주어진 수열에서 일부 숫자를 제거하여 만든 부분 수열 중에서, 오름차순으로 정렬된 가장 긴 수열을 찾는 문제.
예를 들어, 수열 [10, 20, 10, 30, 20, 40]이 있다면, LIS는 [10, 20, 30, 40]이 된다.

예시 백준 문제는 여기 있다.

DP를 연습할때 가장 먼저 나오는 문제이지만, 의외로 2가지 실수하기 쉬운 포인트와. 한가지 인사이트를 제공한다.

2가지 실수하기 쉬운 포인트

아래는 이문제에 대한 정답코드인데, 아래 주석으로 여기라고 되어 있는 부분을 풀때마다 실수했다.

#include <stdio.h>
#include <algorithm>
using namespace std;

// dp[3] = 5 ; 인덱스 3까지 가장 긴 증가하는 부분수열의 길이는 5이다.
int dp[1001]; 
int A[1001];

int main(void)
{
	int N; scanf("%d", &N);
	for (int i = 0; i < N; i++) scanf("%d", A + i),dp[i]=1;  // 여기. dp[i]=1초기화 부분!
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < i; j++) {
			if (A[i] > A[j]) 
				dp[i] = max(dp[i], dp[j] + 1);
		}
	}
	int ans = 1;
	for (int i = 0; i < N; i++) ans = max(ans, dp[i]);  // 여기. dp[n-1]아니어도 답이 될 수 있음!
	printf("%d\n", ans);
	return 0;
}

한가지 인사이트

이 문제는 놀랍게도 recursive+memoization보다 iterative 방식이 더 생각하기 편하고,

편한 recursive+memoization을 떠올리면 dp[ix][cur_val] 형태가 돼서 냅색DP형태가 나오는데 문제 범위에 따라 메모리초과 오류가 발생하여 해결이 어렵다.

아래는 편한 recursive버전이다.

#include <bits/stdc++.h>
using namespace std;
int dp[1001][1001];
int in[1001];
int n;
int dfs(int ix, int cur_max_val){
    if(ix>=n) return 0;
    if(dp[ix][cur_max_val]) return dp[ix][cur_max_val];
    
    //포함
    int r1 = -1;
    if(cur_max_val < in[ix])
        r1= 1 + dfs(ix+1, in[ix]);
    
    //불포함
    int r2 = dfs(ix+1, cur_max_val);

    return dp[ix][cur_max_val] = max(r1,r2);
}
int main() {
    scanf("%d", &n);
    for(int i=0;i<n;i++) scanf("%d", in+i);
    printf("%d\n", dfs(0, 0));

    return 0;
}

자세히 들여다 보면, dp[n]을 1로 초기화 하는 부분도 필요없고, 마지막에 정렬하는 부분도 필요없어서 실수 확률이 확연히 줄어든다.

하지만 위 코드를 dp[ix]로 1차원만 사용하도록 변경하는건 쉽지 않다.

아래처럼 할 수 있긴한데, dfs함수내에 iterative한 부분이 들어 있어 완전한 DFS라고 부를 수 있을지 약간 애매하다.

#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);++i) 
#define REP(i,n) FOR(i,0,n) 
typedef vector<int> VI;

int dp[1001];
int in[1001];
int N;
int go(int n)
{
         if(n==0) return 1;
         if(dp[n]) return dp[n];
 
         int maxR=1;
         REP(i,n){
            if(in[n] >in[i])
                maxR = max(maxR, go(i)+1);                 
         }
         return dp[n] = maxR;
}
 
int main()
{
        scanf("%d\n", &N);
        REP(i, N)scanf("%d",&in[i]); 
        int r=0;
        REP(i,N) r=max(r,go(i));
        cout << r <<endl;
        return 0;
}

실제 시퀀스를 출력하는 방법

아래처럼 prev배열하나를 추가하면 어렵지 않게 구현가능하다.

#include <stdio.h>
#include <algorithm>
using namespace std;

// dp[3] = 5 ; 인덱스 3까지 가장 긴 증가하는 부분수열의 길이는 5이다.
int dp[1001];
int A[1001];
int prv[1001];

int main(void)
{
    fill(prv, prv + 1001, -1);
    int N;
    scanf("%d", &N);
    for (int i = 0; i < N; i++)scanf("%d", A + i), dp[i] = 1; // 여기. dp[i]=1초기화 부분!
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < i; j++)
        {
            if (A[i] > A[j])
                if (dp[j] + 1 > dp[i])
                {
                    dp[i] = dp[j] + 1;
                    prv[i] = j;
                }
        }
    }
    int ans = 1;
    int end_ix = 0;
    for (int i = 0; i < N; i++)
    {
        if (ans < dp[i])
        {
            ans = dp[i];
            end_ix = i;
        }
    }
    printf("%d\n", ans);
    vector<int> v;
    v.push_back(A[end_ix]);
    while (prv[end_ix] != -1)
    {
        end_ix = prv[end_ix];
        v.push_back(A[end_ix]);
    }
    reverse(v.begin(), v.end());
    for (auto e : v)
        printf("%d ", e);

    return 0;
}