boolean possible(int p1, int p2) { // 패턴 첫번째와 패턴 두번째가 서로 인접 가능한지
if(p1 == p2) return false; // 동일한 패턴은 인접할 수 없다.
int[][] patterns = { {1, 4}, {3, 4}, {4, 1}, {4, 3} }; // 인접할 수 없는 패턴
for (int i = 0; i < patterns.length; i++)
if(p1 == patterns[i][0] && p2 == patterns[i][1])
return false;
return true;
}
2. 계산 방법
c열에 p 패턴으로 돌을 놓을 때,
0열~ c열까지의 점수의 최댓값을 구하는 함수이다.
3. 재귀적 해법
scoreColumn(int c, int p)
c열에 p패턴으로 돌이 놓일 때, c열의 점수의 합
c값의 범위는 0 1 2... n-1
p값의 범위는 1, 2, 3, 4
int column(int c, int p){
switch(p){
case 1: return a[0][c];
case 2: return a[1][c];
case 3: return a[2][c];
case 4: return a[0][c] + a[2][c];
}
return 0;
}
sum(int c, int previous)
c-1열에 previous 패턴으로 돌이 놓여있을 때,
c열부터 마지막 열까지 점수의 합 중 최대
previous 패턴으로 놓여있을 때 c열에 올 수 있는 패턴들에 대해서
sum(c+1, c열이 올 수 있는 패턴) 메서드를 재귀 호출하여 구현한다.
점수 = (위 메서드의 리턴 값) + (현재 열의 점수)
점수의 최댓값을 리턴한다.
int sum (int c, int previous) {
if(c >= a[0].length) return 0; // 종료조건
int max = Integer.MIN_VALUE;
for (int p = 1; p <= 4; p++){
if(c == 0 || possible(previous, p)){ // c 현재열이 0이면 이전 패턴과는 상관없다.
int score = column(c, p) + sum (c + 1, p);
if(score > max)
max = score;
}
}
return max;
}
4. 동적 프로그래밍으로 구현
int[][] dp = new int [4+1][a.length] // 행에는 이전 열의 패턴이 들어간다.
int sum (int c, int previous) {
if(c >= a[0].length) return 0; // 종료조건
if(dp[previous][c] != 0) return dp[previous][c]; // 이미 계산한 적이 있으면
int max = Integer.MIN_VALUE;
for (int p = 1; p <= 4; p++){
if(c == 0 || possible(previous, p)){ // c 현재열이 0이면 이전 패턴과는 상관없다.
int score = column(c, p) + sum (c + 1, p);
if(score > max)
max = score;
}
}
return dp[previous][c] = max;
}
백준 9465번 스티커 설명
1. 문제 설명
2행 n열로 배치된 스티커를 뗄 때 스티커의 점수의 합이 최대가 되도록 스티커를 뗀다.
뗀 스티커의 왼쪽, 오른쪽, 위, 아래에 있는 스티커는 뗄 수 없다.
즉, 2 * n개의 스티커 중에서 점수의 합이 최대가 되면서 서로 변을 공유하지 않는 스티커 집합을 구해야 한다.
2. 문제 풀이
조약돌 문제와는 다른 점은 패턴은 3가지로 0행 스티커를 뗀 패턴, 1행 스티커를 뗀 패턴, 떼지 않은 패턴이다.
* 인접할 수 있는/없는 패턴
이전 열에서 아무것도 떼지 않았을 경우: 어떤 패턴이든 올 수 있다.
이전 열에서 0행이나 1행 스티커를 뗀 경우: 같은 행에 있는 스티커는 뗄 수 없다.
* 계속 아무것도 떼지 않을 경우
점수의 합이 0이 될 수 있다.
그렇기 때문에 dp를 -1로 초기화를 해주어야 한다.
마찬가지로, dp에 저장이 되어있는지 아닌지 확인할 때는 -1을 기준으로 검사해주어야 한다.
static int[][] dp;
static int sum(int[][] a, int c, int previous) {
if (c >= a[0].length)
return 0; // 종료조건
if (dp[c][previous] != -1)
return dp[c][previous];
int max = 0;
for (int r = 0; r <= 2; r++) {
if (r == 0 || r != previous) {
int ans = a[r][c] + sum(a, index + 1, r);
if (ans > max)
max = ans;
}
}
return dp[c][previous] = max;
}
처음엔 백준 12279번과 1927번을 int 배열과 ArrayList<Integer>로 풀었는데 시간초과가 떴다. 문제가 있는 것 같아서 찾아보다가 우선순위 큐로 풀어야한다는 것을 배웠다. 우선순위 큐 말고 다른 방식으로 풀면 왜 시간초과가 뜨는지는 잘 모르겠다. 단순 java가 시간을 많이 잡아먹는게 문제인가
REpresentation State Transfer (자원을 이름으로 구분해 해당 자원의 상태를 주고받는 것)
REST는 웹에 존재하는 자원(이미지, 동영상, 데이터)에 대해서 고유한 URI를 부여하고 활용하는 방법론을 의미한다.
하나의 URI는 하나의 고유한 Resource를 대표하도록 설계된다는 개념
웹의 장점을 최대한 활용할 수 있는 네트워크 기반의 아키텍처 (웹의 기존 기술과 HTTP 프로토콜을 그대로 활용하기 때문에 웹의 장점을 최대한 활용 가능)
www(World Wide Web)과 같은 분산 시스템을 위한 소프트웨어 아키텍쳐
1-1. REST의 3요소
* Resource (자원) URI는 정보의 자원을 표현해야 한다.
* Method (행위) HTTP Method
* Representation of Resource (표현)
HTTP 의도에 맞게 활용된다는 것은,
1. URI는 정보의 자원을 표현해야 한다.
2. 자원에 대한 행위는 HTTP Method(GET 생성, POST 조회, PUT 수정, DELETE 삭제)로 표현하는 것을 말한다. 즉, URI로 주어나 목적어를 만들고 HTTP Method로 동사를 만든다는 개념.
URI를 불분명한 자원으로 표현하거나 혹은 동사처럼 사용하거나, HTTP Method 중 GET을 쓰면서 수정도 하고 삭제도 하는 것은 RESTful하지 않다.
1-2. HTTP와 REST
REST는 결국 URI를 이용해서 제어할 자원을 명시하고, HTTP를 이용해서 제어 명령을 내린다.
HTTP에 여러 Method가 있지만 REST에서는 CRUD에 해당하는 4가지 Method만 사용한다.
* C reate = POST
* R ead = GET
* U pdate = UPDATE
* D elete = DELETE
Resource를 URI로 정해준 뒤에 HTTP Method를 이용해서 CRUD를 구현하고 Message를 JSON(혹은 XML)로 표현하여 HTTP Body에 실어 보내면 된다.
2. REST의 설계 목표
* 컴포넌트들 간의 상호연동성 확보
- 리눅스의 파이프가 상이한 프로세스들을 연동하는 것처럼, REST API는 복수의 컴포넌트들을 결합함으로써 작업을 더 효율적으로 수행하게 한다.
* 범용 인터페이스 제공
- REST 모델을 위한 HTTP와 URI는 표준이므로 어디서든 사용 가능한 범용 인터페이스를 제공한다. 개발자는 비즈니스 로직만 고민하면 된다.
* 각 컴포넌트들의 독립적인 배포
* 지연감소, 보안 강화, 레거시 시스템을 인캡슐레이션 하는 중간 컴포넌트로의 역할
REST의 목표를 가지고 작업을 수행할 시, 백엔드와 프런트엔드의 영역을 효율적으로 분리할 수 있어 규모 확장에 있어 장점이 생기고 독립적으로 배포되어 버전 관리를 할 수 있다.
자원과 직접적인 통신을 하고 있는 백엔드가 분리되어 있기 때문에 접근하는 것에 있어서나 자원을 캡슐화해서 보낼 수 있어 보안이 강화된다는 장점이 있다.
3. REST의 6가지 특성/제약
1. Stateless (무상태성)
* 상태가 없다는 것은 사용자나 클라이언트의 Context를 서버 쪽에 유지하지 않는다는 의미
* HTTP Session과 같은 Context 저장소에 상태 정보를 저장하지 않는다는 것이다.
* 상태 정보를 저장하지 않으면 각 API 서버는 들어오는 메시지로만 처리하면 되고, Session과 같은 Context 정보를 신경 쓸 필요가 없다. -> 서비스의 자유도가 높아지고 서버에서 불필요한 정보를 관리하지 않아 구현이 단순해진다.
2. Client - Server (클라이언트 - 서버 구조)
* 클라이언트와 서버가 서로 분리되어야 한다.
* 예를 들어, 개발자가 모바일 어플의 Client 단을 수정할 때 Server 단의 데이터 베이스 디자인에 영향을 끼치지 않고 수정할 수 있어야 한다. (거꾸로도 마찬가지)
* 역할이 구분되면 개발자 관점에서 클라이언트와 서버에서 개발해야 할 내용들이 명확해지고 의존성이 줄어든다.
3. Layered System (계층형 구조)
* MVD 모델에서 Model, View, Controller 가 각각 역할을 담당하고 서로 상호작용하듯이, REST API에서도 아키텍처의 서로 다른 계층이 협업을 하여 확장성과 유연성을 증가시킨다.
* 클라이언트 입장에서는 대상 서버에 직접 연결되었는지, 중간 서버를 통해 연결되었는지 알 수 없다. 즉, REST API 서버만 호출한다. 그러나 서버는 다중 계층으로 구성될 수 있다.
* 순수 비즈니스 로직을 수행하는 API 서버와 그 앞단에 사용자 인증(Authentication), 암호화(SSL), 로드밸런싱 등을 하는 계층을 추가해서 구조상의 유연성을 둘 수 있다.
4. Cacheable (캐시 처리 가능)
* REST는 HTTP라는 기존의 웹 표준을 그대로 사용하기 때문에, 웹에서 사용하는 기존의 인프라를 활용 가능하다. 때문에 HTTP 프로토콜 기반의 로드밸런서, SSL, Cache 등을 사용할 수 있다.
* HTTP가 가진 캐싱 기능을 적용할 수 있다. HTTP 프로토콜 표준에서 사용하는 Last-Modified 태그나 E-Tag를 이용하면 캐싱 구현이 가능하다.
* 무상태성 API는 많은 양의 입출력 호출을 다루다 보면 Request가 폭증할 수 있다. 때문에 REST API는 Cacheable Data의 저장공간을 확충하도록 설계되어야 한다.
* 즉, 데이터가 Cacheable 할 때, 그 Response는 그 데이터가 언제까지 저장될 수 있다는 것을 지시해야 한다. 이를 통해 API와 인터렉션 수를 드라마틱하게 줄일 수 있다. 또, 내부 서버 사용을 줄여서 빠르고 효율적인 애플리케이션을 만들도록 하는 도구들을 API 사용자들에게 제공한다.
* Cache를 사용하면 REST 컴포넌트가 위치한 서버에 Transation을 발생시키지 않는다. 때문에 전체 응답 시간과 성능, 그리고 서버의 자원 사용률을 비약적으로 향상할 수 있다.
5. Uniform Interface (인터페이스 일관성)
* 서버로부터 클라이언트를 분리하는 것의 핵심은 느슨한 결합으로 애플리케이션의 독립적인 개발을 가능하게 하는 Uniform Interface를 갖는 것이다.
* REST는 HTTP 표준에 따르는 것이라면, 안드로이드든 iOS든, 특정 언어나 기술에 종속되지 않고 모든 플랫폼에 사용이 가능하며, URI로 지정한 리소스에 대한 조작이 가능한 아키텍처 스타일을 의미한다.
이는 REST 개념이 대두된 배경과도 연관된다.
1. 어플리케이션 복잡도 증가에 따른 어플리케이션 분리 및 통합이 중요해졌다.
2. 모바일과 같은 다양한 클라이언트의 등장으로 Backend 하나로 다양한 Device를 대응하기 위해 REST의 필요성이 늘어났다.
6. Self-descriptiveness (자체 표현 구조)
* 동사(Method) + 명사(URI)로 이루어져 있어 어떤 메서드에서 무슨 행위를 하는지 알 수 있으며, 메시지 포맷 역시 JSON를 이용해서 직관적으로 이해가 가능한 구조
댓글 개