코딩하는 eroke

어느덧 경력이 2년이 되었으나 아직도 REST에 대해 명확히 설명하지 못하는 부끄러운 단계여서,,

유튜브채널 naver d2에서  '그런 REST API로 괜찮은가' 테크강의와 위키백과를 보며 REST에 대해 정리해보았다. 

 REST 

 정의 

Representational State Transfer 표현적인 상태전송

a way of providing interoperability between computer systems on the Internet.

컴퓨터 시스템간의 상호운용성을 제공하는 방법

< 분산 하이퍼미디어 시스템 (ex: 웹)을 위한 아키텍쳐 스타일 (제약조건의 집합) >

사실 정의만 봐서는 잘 와닿지 않는다.

 배경 

1. WEB의 등장 (1991)

• 표현형식 : HTML (정보를 하이퍼텍스트로 연결)
• 식별자 : URI
• 전송방법 : HTTP (프로토콜)

HTTP 명세가 추가되며 기존의 웹을 망가뜨리지 않고 HTTP를 반영할 방법에 대해 고민하게 됨

HTTP Object Model 등장 > 나중에 REST 라는 이름으로 발표 (2000)

(Roy T. Fielding - "Architectural Styles and the Design of Network-based Software Architectures")

2. API 등장

XML-RPC (MS) > SOAP (Salesforce) > REST (Flickr)  > 점점 규칙이 적고 간결해짐

MS의 REST API 가이드라인 (2016)

• URI 형식 : https://{serviceRoot}/{collection}/{id} 
• 메소드지원 : GET, PUT, DELETE, POST, HEAD, PATCH, OPTIONS
• 버저닝 : Major.minor 버전정보는 URI 에 포함

 REST API 

REST 아키텍쳐 스타일(제약조건의 집합)을 모두 따르는  API 

RESTful : Fielding 의 REST 원리를 따르는 시스템

REST 제약조건

1. 인터페이스 일관성 (Uniform Interface) : 일관적인 인터페이스로 분리되어야 한다
   • For 독립적 진화 : 서버와 클라이언트는 각각 독립적으로 진화함 > 서버 기능이 변경되어도 클라이언트 업데이트 할 필요 없음 > HTTP, HTML 명세가 변경되어도 웹은 잘 동작함
   • Uniform Interface 제약조건 (4개)
     • 1) identification of resources : 리소스는 URI로 식별되어야함
     • 2) manipulation of resources through representations : 표현을 통해 리소스를 제작해야함 > 리소스를 생성/수정/삭제할 때 메시지에 표현을 담아 전송해야하는 것
     • 3) self-descriptive messages : 메시지에 설명이 있어야함 > 확장가능한 커뮤니케이션 = 서버/클라이언트가 변경되어도 오고가는 메시지는 언제나 해석가능함 > 현재 HTTP 요청/응답메시지에는 설명 없음
     • 4) hypermedia as the engine of application state (HATEOAS) : 애플리케이션 상태는 하이퍼링크를 통해 전이되어야함 (Late binding) > 전이가 완료된 후에 다음으로 전이될 상태가 결정됨 = 링크는 동적으로 변경될 수 있어야함
     • 오늘날 REST API는 대체로 3,4 번은 못 지키고 있음
2. 무상태(Stateless) : 각 요청 간 클라이언트의 콘텍스트가 서버에 저장되어서는 안 된다
3. 캐시 처리 가능(Cacheable): WWW에서와 같이 클라이언트는 응답을 캐싱할 수 있어야 한다.
   잘 관리되는 캐싱은 클라이언트-서버 간 상호작용을 부분적으로 또는 완전하게 제거하여 scalability와 성능을 향상시킨다.
4. 계층화(Layered System): 클라이언트는 보통 대상 서버에 직접 연결되었는지, 또는 중간 서버를 통해 연결되었는지를 알 수 없다. 중간 서버는 로드 밸런싱 기능이나 공유 캐시 기능을 제공함으로써 시스템 규모 확장성을 향상시키는 데 유용하다.
5. Code on demand (optional) : 서버가 클라이언트가 실행시킬 수 있는 로직을 전송하여 기능을 확장시킬 수 있다. (ex. 자바 애플릿, 자바스크립트)
6. 클라이언트/서버 구조 : 아키텍처를 단순화시키고 작은 단위로 분리(decouple)함으로써 클라이언트-서버의 각 파트가 독립적으로 개선될 수 있도록 해준다

결론적으로 REST로 인해 웹의 독립적 진화가 가능해짐

• HTTP에 지속적으로 영향을 줌
  • Host 헤더 추가 / 길이제한 다루는 방법 명시 (ex. 414 URI Too Long) / URI의 리소스 정의가 추상적으로 바뀜
• REST API를 개발/ HTTP API를 개발/ (현재상태) 개발한 것을 그냥 REST API 라고 부르는것 

현재 REST API를 구현하기 힘든 이유

WEB = 사람이 보는 것 ,  Media type = html, 하이퍼링크, self-descriptive (html 명세)

HTTP = 기계가 해석, Media type = Json, 하이퍼링크 X, non self-descriptive (key-val 정의 없음)

> Self-descriptive 해결하기 위한 노력 

• json에 미디어타입을 정의한 뒤 미디어타입 문서를 만들어 self description 정의 > IANA에 등록 (모든 미디어타입)
  • 단점 : 매번 미디어타입 정의 필요
• json에 명세한 문서 링크를 추가해 Profile 작성 
  • 단점 : 클라이언트가 Link 헤더(RFC 5988)와 profile (RFC 6906)을 알아야함.
  • Content negotiation 할 수 없음

> HATEOAS 해결하기 위한 노력 : data, 헤더 모두 활용

• data(json 본문)에 다양한 방법으로 하이퍼링크 표현 
  • 단점 : 링크를 표현하는 법을 직접 정의해야함
• HTTP 헤더로 링크 표현 (Link, Location 등) 
  • 정의된 relation만 활용하면 표현에 한계가 있음

 정리 

• 오늘날 대부분의 REST API는 사실 REST 를 따르지 않음 (self-descriptive, HATEOAS 불만족)
• REST는 진화하는 웹 어플리케이션을 위한 것이다.
• REST를 따를지는 API 설계자들이 스스로 판단해 결정해야한다.

 Reference

- Naver D2 : 그런  REST API로 괜찮은가

- 위키백과 : REST​

문제

이진탐색의 가장 기본적인 문제이다. 하지만 나는 다 까먹어서 다시 공부했다...

가지고있는 k개의 랜선을 잘라 같은 길이로 n개를 만들 수 있는 최대 길이를 출력하는 문제이다.

풀이

k, n = map(int, input().split())
lan = []

for i in range(k):
    lan.append(int(input()))

lan.sort()  # 이분탐색을 위해 정렬
s = 1
e = max(lan)

res = 0
while s <= e:
    total = 0
    mid = (s + e) // 2

    for x in lan:
        if x >= mid: total += (x // mid)

    if total < n:
        e = mid - 1
    else:
        res = mid
        s = mid + 1

print(res)

현타...ㅎㅎ 알고리즘도 종종 풀어줘야 잊지 않는거 같다...

공부할게 넘 많아~~~~

문제 (2019 KAKAO BLIND RECRUITMENT)

record 문자열배열을 입력받을 때 사용자가 들어오고 나간 이력을 출력하는 문제이다.

닉네임은 변경할 수 있고 최종적으로 변경된 닉네임으로 결과를 출력한다.

풀이

def solution(record):
    dic={}
    res=[]
    id=[]
    
    for i in range(len(record)):
        s = record[i].split()

        if s[0]=='Enter':
            res.append(s[1]+'님이 들어왔습니다.')
            dic[s[1]]=s[2] #id별 이름저장
            id.append(s[1])

        elif s[0]=='Leave':
            res.append(s[1]+'님이 나갔습니다.')
            id.append(s[1])

        elif s[0]=='Change':
            dic[s[1]] = s[2] #이름변경

    for j in range(len(res)):
        tmp=dic[id[j]]
        res[j]=res[j].replace(id[j],tmp)
        
    return res

딕셔너리로 id당 바뀌는 닉네임을 관리하고 사용자가 채팅방에 들어오고 나갈때마다 

'id님이 들어왔습니다/나갔습니다' 로 저장해서 마지막에 id 부분을 최종 닉네임으로 바꿨다.

저 replace() 부분을,,, 좀더 좋은 방법으로 쓸 수 있을 것 같긴한데..

어쨌든 한번에 성공했더니 기분은 좋균 ㅎㅎ

이번주는 구현 위주로 풀고 담주부터 진짜진짜 알고리즘 공부해야지;;

문제

방번호에 필요한 세트 수 를 출력하면 된다. 한 세트는 0~9의 숫자이고 6, 9는 서로 뒤집어 사용할 수 있다.

풀이

import collections

n=input()
d=collections.defaultdict(int)

for x in n:
    x=int(x)
    if x!=6 and x!=9: d[x]+=1
    else:
        if d[6]>d[9]:d[9]+=1
        else: d[6]+=1

res = list(d.values())
res.sort(reverse=True)
print(res[0])

default 딕셔너리를 사용해 구현하였다. 

6, 9 가 아닌 경우는 세트 값을 추가하고 6 혹은 9일 경우엔 적은 수를 더해가며 세트를 추가했다.

딕셔너리의 values 를 리스트화 시켜 정렬 후 가장 큰 값 (세트)을 출력했다.

문제

단지번호붙이기 (BOJ2667) 문제와 비슷한 문제이다.

그런데 DFS 재귀로 풀었더니 예제 코드는 정답으로 출력되지만 제출 시 런타임 에러 (RecursionError)가 발생했다.

RecursionError 관련해서는 아래 링크로 확인해보면 발생 이유와 대응 방법에 대해 나온다.

그래서 재귀방식 대신 큐를 사용해 BFS로 다시 풀었더니 이번엔 시간초과가 나왔다;; (개빡취네)

질문검색 탭을 보니 나랑 똑같은 문제로 틀린 사람이 있었다. (https://www.acmicpc.net/board/view/78364)

다행히 어느 천재님이 아래 내용으로 댓글을 달아주셨다.

BFS는 큐에서 뺀 다음이 아닌, 큐에 넣을 때 방문 체크를 해야 중복 방문이 일어나지 않습니다. 
BFS 문제에서 시간 초과나 메모리 초과가 나면 이것부터 의심해 보시면 됩니다.

소름돋게 내 코드도 큐에서 뺀 다음에 visit 처리하고 있었다...

존잘님의 방법대로 코드를 수정했더니 바로 정답처리 되었다. (감사합니다..)

풀이 (Python)

from collections import deque

dx = [1,0,-1,0]
dy = [0,1,0,-1]

if __name__ == '__main__':
    t = int(input())

    for _ in range(t):
        dq = deque()
        m,n,k = map(int, input().split())
        v = [[0]*n for _ in range(m)]
        arr = [[0]*n for _ in range(m)]
        cnt=0

        for _ in range(k):
            a,b = map(int,input().split())
            arr[a][b]=1

        for i in range(m):
            for j in range(n):
                if v[i][j]==0 and arr[i][j]==1:
                    cnt+=1
                    dq.append([i,j])
                    v[i][j]=1
                    while dq:
                        cx, cy = dq.popleft()
                        #v[cx][cy] = 1 <<문제의 기존 visit 처리
                        for k in range(4):
                            nx = cx + dx[k]
                            ny = cy + dy[k]
                            if (0 <= nx < m and 0 <= ny < n and v[nx][ny] == 0 and arr[nx][ny] == 1):
                                dq.append([nx,ny])
                                v[nx][ny]=1
        print(cnt)

문제

유명한  dfs 문제이다. (그림 출처 : 백준사이트)

n을 입력받은 뒤 첫 번째 그림처럼 n*n 배열이 주어지는데

1이 상하좌우로 이어지는 영역을 하나의 단지로 구분한다.

한 단지 영역내의 1들은 각 단지의 집의 개수이다.

두번재 그림을 보면 3단지가 있고 각각 집의 개수는 7,8,9개씩 이다.

단지의 개수와 집의 개수를 오름차순으로 정렬해 출력하면 되는 문제이다.

예전에 C++로 풀었던 문제여서 이번엔 파이썬으로 풀어봤는데

계속 이맞왜틀 ㅡㅡ 상태였는데 집개수가 0인 경우를 출력을 안했었다는걸 알게됨;

풀이1 (python)

dx = [1,0,-1,0]
dy = [0,1,0,-1]

cnt=0
def dfs(x,y):
    global cnt
    v[x][y]=1
    cnt+=1 #집 count
    for i in range(4):
        nx = x+dx[i]
        ny = y+dy[i]
        if(0<=nx<n and 0<=ny<n and v[nx][ny]==0 and arr[nx][ny]==1):
            dfs(nx,ny)

if __name__ == '__main__':
    n = int(input())
    v = [[0]*n for _ in range(n)]
    arr = []
    dan = [] #단지수

    for _ in range(n):
        arr.append(list(map(int,input())))

    for i in range(n):
        for j in range(n):
            if arr[i][j]==1 and v[i][j]==0:
                dfs(i,j)
                dan.append(cnt)
                cnt=0

    dan.sort()
    print(len(dan)) #단지 수
    if len(dan)==0:print(0)
    for d in dan:print(d) #집 수

풀이2 (C++)

#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
int N, M, A[25][25], visit[25][25],ny,nx;
int dan_cnt =1, cnt = 1;
int dx[] = { 0,0,1,-1 }, dy[] = { 1,-1,0,0 };

vector<int>dan;
vector<pair<int, int>>pos;
queue<pair<int, int>>q;

void BFS(int y, int x, int dan_cnt) {
	q.push({ y,x });
	visit[y][x] = dan_cnt;
	cnt = 1;
	while (!q.empty()) {
		int cy = q.front().first;
		int cx = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++) {
			int ny = cy + dy[i];
			int nx = cx + dx[i];
			if (A[ny][nx]!=1||visit[ny][nx] !=0|| ny < 0 || nx < 0 || ny >= N || nx >= N)continue;

			visit[ny][nx] = dan_cnt;
			q.push({ ny,nx });
			cnt++;
		}
	}
}

int main() {//플러드필,연결요소
	/*ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);*/
	
	//memset(visit, -1, sizeof(visit));
	
	scanf("%d", &N);
	for (int y = 0; y < N; y++) {
		for (int x = 0; x < N; x++) {
			scanf("%1d", &A[y][x]);
			if (A[y][x] == 1)  pos.push_back({ y,x });
		}
	}

	for (int i = 0; i < pos.size(); i++) {
		int y = pos[i].first;
		int x = pos[i].second;
		if (visit[y][x] == 0) { BFS(y, x, dan_cnt++); dan.push_back(cnt); }
	}

	sort(dan.begin(),dan.end());
	printf("%d\n", dan_cnt-1);
	for (int i = 0; i < dan.size(); i++) {
		printf("%d\n", dan[i]);
	}
	return 0;
}

C++ 코드는 2년 전 코드여서인지 내가 짰는데도 낯선느낌이다..ㅎ ;;

문제

어제 풀었던 DFS와 BFS 문제와 거의 똑같은 문제이다. DFS로 단순하게 풀었다.

풀이1 (Python)

cnt = 0
def dfs(c):
    global cnt
    v[c]=1
    for i in range(1,n+1):
        if g[c][i]==1 and v[i]==0:
            cnt += 1
            dfs(i)

if __name__ == '__main__':
    n = int(input())
    pair = int(input())

    g = [[0] * (n + 1) for _ in range(n + 1)]
    v = [0] * (n + 1)

    for _ in range(pair):
        a,b = map(int,input().split())
        g[a][b] = g[b][a] = 1

    dfs(1)
    print(cnt)

풀이2 (C++)

#include <iostream>
using namespace std;
int N, link, com[101][101], visit[101], a, b,cnt;

void DFS(int n) {
	cnt++;
	visit[n] = 1;
	for (int i = 1; i <= N; i++) {
		if (com[n][i] && !visit[i])DFS(i);
	}
}

int main() {
	cin >> N;
	cin >> link;
	for (int i = 0; i < link; i++) {
		cin >> a >> b;
		com[a][b] = com[b][a] = 1;
	}
	DFS(1);
	cout << cnt - 1;
	return 0;
}

3년 전에 C++로 풀었던 문제들을 파이썬으로 다시 풀어보았다.

문제

정점의 개수(N), 간선의 개수(M), 시작정점(V)을 입력받고 간선의 수만큼 연결된 정점들의 번호를 입력받아 

시작정점부터 각각 DFS, BFS로 수행한 결과를 출력하면 된다.

DFS는 재귀함수로, BFS는 큐를 사용해 풀었다. 

풀이1 (Python)

from collections import deque

def dfs(v):
    dv[v]=1
    print(v,end=' ')
    for i in range(1, n+1):
        if dv[i]==0 and g[v][i]==1:
            dfs(i)

if __name__ == '__main__':
    n,m,v=map(int,input().split())
    g = [[0]*(n+1) for _ in range(n+1)]
    dv=[0]*(n+1) #dfs visit
    bv=[0]*(n+1) #bfs visit
    q = deque()

    for _ in range(m):
        x,y=map(int,input().split())
        g[x][y] = g[y][x] = 1  #간선연결

    #DFS
    dfs(v)
    print()
    #BFS
    q.append(v)
    bv[v] = 1
    while q:
        v = q.popleft()
        print(v, end=' ')
        for i in range(1, n + 1):
            if bv[i] == 0 and g[v][i] == 1:
                q.append(i)
                bv[i] = 1

풀이2 (C++)

//DFS와 BFS
#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <memory.h>
using namespace std;

int N, M, V,V1,V2;
//stack<int>S;
queue <int> q;
int visit[1001];
int graph[1001][1001];

void dfs(int V) {
	cout << V << " ";
	for (int i = 1; i <= N; i++) {
		if (!visit[i] && graph[V][i]) {
			visit[i] = true;
			dfs(i);
		}
	}
}

void bfs(int V) {
	q.push(V);
	visit[V] = 1;
	while (!q.empty()) {
		V = q.front();
		q.pop();
		cout << V << " ";

		for(int i=1;i<=N;i++)
			if (!visit[i] && graph[V][i]) {
				visit[i] = 1;
				q.push(i);
			}
	}
}

int main() {
	cin >> N >> M >> V;
	for (int i = 0; i < M; i++) {
		cin >> V1>> V2;
		graph[V1][V2] = 1;
		graph[V2][V1] = 1;
	}

	visit[V] = 1;
	dfs(V);
	cout << endl;

	memset(visit, false, sizeof(visit));
	bfs(V);
	cout << endl;
	
	return 0;
}

갈 길이 멀다... ㅎㅎ 

문제

오랜만에 푼 SQL,,

SEX_UPON_INTAKE 컬럼에 'Neutered' 또는 'Spayed' 단어가 들어 있으면 중성화 한 동물로 'O'를 출력, 

중성화 하지 않은 동물은 'X'를 출력하면 되는 문제이다.

실행결과를 아래처럼 나오게 하면 된다.

풀이

SELECT ANIMAL_ID, NAME, 
    CASE WHEN (SEX_UPON_INTAKE LIKE '%Neutered%' 
            OR SEX_UPON_INTAKE LIKE '%Spayed%') 
            THEN 'O' ELSE 'X' END AS 중성화
 FROM ANIMAL_INS
 ORDER BY ANIMAL_ID

SELECT에 CASE 문을 사용하고 컬럼 별칭을 붙여 출력했다.

끝!

오랜만에 그리디 ! 

문제

끊어진 기타줄 N개와 M개의 기타 브랜드들이 주어지고 

각 M개의 기타줄을 6개 패키지로 구매할때와 낱개로 구매할때 1개 가격이 주어진다.

모든 브랜드들을 고려해 가장 저렴하게 구매할 수 있는 가격을 출력하면 된다!

처음에 한 브랜드만 선택해야 한다 생각하고 구현했다가 틀리고,

패키지로만 구매하는 경우를 고려하지 않아 또 틀렸다!

풀이

if __name__ == '__main__':
    N, M = map(int, input().split()) # N=끊어진줄, M=브랜드
    minp = mins = 7000
    ps = N // 6 #패키지
    p = N % 6   #낱개

    for i in range(M):
        pak, sol = map(int,input().split())
        minp = min(minp,pak) 
        mins = min(mins,sol)
        tmp = min(minp*ps+mins*p, mins*N, minp*(ps+1))

    print(tmp)

결과