이진 힙 자료구조 - 전에 함.
DFS & BFS
그래프 알고리즘으로, 문제를 풀 때 상당히 많이 사용한다.
경로를 찾는 문제 시, 상황에 맞게 DFS와 BFS를 활용하게 된다.
DFS
루트 노드 혹은 임의 노드에서 다음 브랜치로 넘어가기 전에, 해당 브랜치를 모두 탐색하는 방법
스택 or 재귀함수를 통해 구현한다.
- 모든 경로를 방문해야 할 경우 사용에 적합
시간 복잡도
- 인접 행렬 : O(V^2)
- 인접 리스트 : O(V+E)
V는 접점, E는 간선을 뜻한다
BFS
루트 노드 또는 임의 노드에서 인접한 노드부터 먼저 탐색하는 방법
큐를 통해 구현한다. (해당 노드의 주변부터 탐색해야하기 때문)
- 최소 비용(즉, 모든 곳을 탐색하는 것보다 최소 비용이 우선일 때)에 적합
시간 복잡도
- 인접 행렬 : O(V^2)
- 인접 리스트 : O(V+E)
1. REST란?
Representational State Transfe라는 용어의 약자이다.
자원을 URI로 표시하고 해당 자원의 상태를 주고 받는 것을 의미한다.
REST의 구성 요소는
- 자원(Resource): URI
- 행위(Verb): HTTP METHOD
- 표현(Representations)
로 이루어져 있다.
즉 Rest는 URI를 통해 자원을 표시하고, HTTP METHO를 이용하여 해당 자원의 행위를 정해주며
그 결과를 받는 것을 말한다.
2. REST의 특징
- Uniform Interface (유니폼 인터페이스)
HTTP 표준만 따른다면 어떤 언어 혹은 어떤 플랫폼에서 사용하여도 사용이 가능한 인터페이스 스타일이다.
안드로이드 플랫폼, IOS 플랫폼 등 특정 언어나 플랫폼에 종속되지 않고 사용이 가능하다. - Stateless (상태 정보 유지 안함)
Rest는 상태 정보를 유지하지 않는다.
서버는 각각의 요청을 완전히 다른 것으로 인식하고 처리를 한다.
이전 요청이 다음 요청 처리에 연관이 되면 안된다. - Cacheable (캐시 가능)
HTTP의 기존 웹 표준을 그대로 사용하기 때문에 HTTP가 가진 캐싱 기능 적용이 가능하다. - Self-descriptiveness (자체 표현 구조)
Rest API 메시지만 보고도 쉽게 이해할 수 있는 자체 표현 구조로 되어있다. - Client-Server
Rest 서버는 API 제공을 하고 클라이언트는 사용자 인증에 관련된 일들을 직접 관리한다.
자원이 있는 쪽을 Server라고 하고 자원을 요청하는 쪽이 Client가 된다.
서로간의 의존성이 줄어들기 때문에 역할이 확실하게 구분되어 개발해야할 내용들이 명확해진다. - Layerd System (계층화)
클라이언트는 Rest API 서버만 호출한다.
Rest 서버는 다중 계층으로 구성될수 있으면 로드 밸런싱, 암호화, 사용자 인증 등을 추가하여 구조상의
유연성을 둘 수 있다.
3. REST API란?
Rest 기반의 규칙들을 지켜서 설계된 API를 Rest API 혹은 Restful API이라고 한다.
4. REST API 설계 규칙
- URI는 정보의 자원을 표현해야한다.
자원의 이름은 동사보다는 명사를 사용한다.
URI는 자원을 표현하는데 중점을 두어야 하기 때문에 행위에 대한 표현이 들어가면 안된다.
(URI에 HTTP METHOD와 행위에대한 동사 표현이 들어가면 안된다.)- GET /users/321
- 자원에 대한 행위는 HTTP METHOD로 표현한다. (GET, POST, PUT DELETE)
URI에 자원의 행위에 대한 표현이 들어가지 않는 대신 HTTP METHOD를 통해 대신한다.- GET /users/321 321 ID를 가진 유저 정보를 가져오기
- DELETE /users/321 321 ID를 가진 유저 정보를 삭제하기
- POST /users 유저를 생성하기
- 슬래시 (/)는 계층 관계를 나타내는데 사용한다.
- URI 마지막은 슬래시(/)를 사용하면 안된다.
- 하이픈 (-)은 URI의 가독성을 높이는데 사용한다.
불가피하게 긴 URI를 사용하게 될 경우 하이픈을 이용하여 가독성을 높인다. - 언더바(_) 혹은 밑줄은 URI에 사용하지 않는다.
밑줄은 보기 어렵거나 밑줄 때문에 문자가 가려지기도 한다.
그래서 대신 언더바를 사용하지 않고 하이픈을 이용한다. - URI는 경로에는 소문자가 적합하다.
URI 경로에는 대문자 사용을 피해야한다.
대소문자에 따라 각자 다른 리소스로 인식하기 때문이다.
RFC3986(URI 문법 형식)은 URI 스키마와 호스트를 제외하고는 대소문자를 구별하도록 규정하기 때문이다. - 파일 확장자는 URI에 포함하지 않는다.
REST API에서는 메시지 바디 내용의 포맷을 나타내기 위한 파일 확장자를 URI 안에 포함시키지 않는다.
Accept header를 사용한다. - 리소스 간의 관계를 표현하는 방법GET : /users/{userid}/devices
5. RESTFUL API란?
위에서 설명했던 REST를 REST답게 쓰기 위한 방법이지만 누군가가 공식적으로 발표한 것이 아니고
그저 개발자들이 비공식적으로 의견을 제시한 것이라 명확한 정의는 없다고 한다.
하지만 RESTFUL의 목적은 이해하기 쉽고 사용하기 쉬운 REST API를 만드는 것이다.
CRUDHTTP METHODURI
| user들을 표시 | GET | /users |
| user 하나만 표시 | GET | /users/:id |
| user를 생성 | POST | /users |
| user를 수정 | PUT | /users:id |
| user를 삭제 | DELETE | /users:id |
- Restful 하지 못한 경우
- CRUD 기능을 전부 POST METHOD로만 처리하는 API
- URI에 자원과 id외 정보가 들어가는 경우
- PUT /users/update-nickname [X]
- PUT /users/:id/nickname [O]
데드락(DeadLock)
프로세스가 자원을 얻지 못해서 다음 처리를 하지 못하는 상태
'교착 상태'라고도 부름
시스템적으로 한정된 자원을 여러 곳에서 사용하려고 할 때 발생
- 데드락이 일어나는 경우
프로세스1과 2가 자원1,2를 모두 얻어야 한다고 가정해보자
t1 : 프로세스1이 자원1을 얻음 / 프로세스2가 자원2를 얻음
t2 : 프로세스1은 자원2를 기다림 / 프로세스2는 자원1을 기다림
현재 서로 원하는 자원이 상대방에 할당되어 있어서 두 프로세스는 무한정 wait 상태에 빠짐
→ 이것이 바로 DeadLock!!!!!!
(주로 발생하는 경우)
멀티 프로그래밍 환경에서 한정된 자원을 얻기 위해 서로 경쟁하는 상황 발생
한 프로세스가 자원을 요청했을 때, 동시에 그 자원을 사용할 수 없는 상황이 발생할 수 있음. 이때 프로세스는 대기 상태로 들어감
대기 상태로 들어간 프로세스들이 실행 상태로 변경될 수 없을 때 '교착 상태' 발생
데드락(DeadLock) 발생 조건
4가지 모두 성립해야 데드락 발생
(하나라도 성립하지 않으면 데드락 문제 해결 가능)
- 상호 배제(Mutual exclusion)
자원은 한번에 한 프로세스만 사용할 수 있음
- 점유 대기(Hold and wait)
최소한 하나의 자원을 점유하고 있으면서 다른 프로세스에 할당되어 사용하고 있는 자원을 추가로 점유하기 위해 대기하는 프로세스가 존재해야 함
- 비선점(No preemption)
다른 프로세스에 할당된 자원은 사용이 끝날 때까지 강제로 빼앗을 수 없음
- 순환 대기(Circular wait)
프로세스의 집합에서 순환 형태로 자원을 대기하고 있어야 함
데드락(DeadLock) 처리
교착 상태를 예방 & 회피
- 예방(prevention)
교착 상태 발생 조건 중 하나를 제거하면서 해결한다 (자원 낭비 엄청 심함)
- 상호배제 부정 : 여러 프로세스가 공유 자원 사용
- 점유대기 부정 : 프로세스 실행전 모든 자원을 할당
- 비선점 부정 : 자원 점유 중인 프로세스가 다른 자원을 요구할 때 가진 자원 반납
- 순환대기 부정 : 자원에 고유번호 할당 후 순서대로 자원 요구
- 회피(avoidance)
교착 상태 발생 시 피해나가는 방법
은행원 알고리즘(Banker's Algorithm)
- 은행에서 모든 고객의 요구가 충족되도록 현금을 할당하는데서 유래함
- 프로세스가 자원을 요구할 때, 시스템은 자원을 할당한 후에도 안정 상태로 남아있게 되는지 사전에 검사하여 교착 상태 회피
- 안정 상태면 자원 할당, 아니면 다른 프로세스들이 자원 해지까지 대기
교착 상태를 탐지 & 회복
교착 상태가 되도록 허용한 다음 회복시키는 방법
- 탐지(Detection)
자원 할당 그래프를 통해 교착 상태를 탐지함
자원 요청 시, 탐지 알고리즘을 실행시켜 그에 대한 오버헤드 발생함
- 회복(Recovery)
교착 상태 일으킨 프로세스를 종료하거나, 할당된 자원을 해제시켜 회복시키는 방법
프로세스 종료 방법- 교착 상태의 프로세스를 모두 중지
- 교착 상태가 제거될 때까지 하나씩 프로세스 중지
- 교착 상태의 프로세스가 점유하고 있는 자원을 선점해 다른 프로세스에게 할당 (해당 프로세스 일시정지 시킴)
- 우선 순위가 낮은 프로세스나 수행 횟수 적은 프로세스 위주로 프로세스 자원 선점
주요 질문
-
데드락(교착 상태)가 뭔가요? 발생 조건에 대해 말해보세요.
-
회피 기법인 은행원 알고리즘이 뭔지 설명해보세요.
-
기아상태를 설명하는 식사하는 철학자 문제에 대해 설명해보세요.
교착 상태 해결책
- n명이 앉을 수 있는 테이블에서 철학자를 n-1명만 앉힘
- 한 철학자가 젓가락 두개를 모두 집을 수 있는 상황에서만 젓가락 집도록 허용
- 누군가는 왼쪽 젓가락을 먼저 집지 않고 오른쪽 젓가락을 먼저 집도록 허용
CAP 이론
1. 일관성(Consistency)
일관성은 동시성 또는 동일성이라고도 하며 다중 클라이언트에서 같은 시간에 조회하는 데이터는 항상 동일한 데이터임을 보증하는 것을 의미한다. 이것은 관계형 데이터베이스가 지원하는 가장 기본적인 기능이지만 일관성을 지원하지 않는 NoSQL 을 사용한다면 데이터의 일관성이 느슨하게 처리되어 동일한 데이터가 나타나지 않을 수 있다. 느슨하게 처리된다는 것은 데이터의 변경을 시간의 흐름에 따라 여러 노드에 전파하는 것을 말한다. 이러한 방법을 최종적으로 일관성이 유지된다고 하여 최종 일관성 또는 궁극적 일관성을 지원한다고 한다.
각 NoSQL 들은 분산 노드 간의 데이터 동기화를 위해서 두 가지 방법을 사용한다. 첫번째로 데이터의 저장 결과를 클라이언트로 응답하기 전에 모든 노드에 데이터를 저장하는 동기식 방법이 있다. 그만큼 느린 응답시간을 보이지만 데이터의 정합성을 보장한다. 두번째로 메모리나 임시 파일에 기록하고 클라이언트에 먼저 응답한 다음, 특정 이벤트 또는 프로세스를 사용하여 노드로 데이터를 동기화하는 비동기식 방법이 있다. 빠른 응답시간을 보인다는 장점이 있지만, 쓰기 노드에 장애가 발생하였을 경우 데이터가 손실될 수 있다.
2. 가용성(Availability)
가용성이란 모든 클라이언트의 읽기와 쓰기 요청에 대하여 항상 응답이 가능해야 함을 보증하는 것이며 내고장성이라고도 한다. 내고장성을 가진 NoSQL 은 클러스터 내에서 몇 개의 노드가 망가지더라도 정상적인 서비스가 가능하다.
몇몇 NoSQL 은 가용성을 보장하기 위해 데이터 복제(Replication)을 사용한다. 동일한 데이터를 다중 노드에 중복 저장하여 그 중 몇 대의 노드가 고장나도 데이터가 유실되지 않도록 하는 방법이다. 데이터 중복 저장 방법에는 동일한 데이터를 가진 저장소를 하나 더 생성하는 Master-Slave 복제 방법과 데이터 단위로 중복 저장하는 Peer-to-Peer 복제 방법이 있다.
3. 네트워크 분할 허용성(Partition tolerance)
분할 허용성이란 지역적으로 분할된 네트워크 환경에서 동작하는 시스템에서 두 지역 간의 네트워크가 단절되거나 네트워크 데이터의 유실이 일어나더라도 각 지역 내의 시스템은 정상적으로 동작해야 함을 의미한다.
Annotation
어노테이션이란 본래 주석이란 뜻으로, 인터페이스를 기반으로 한 문법이다. 주석과는 그 역할이 다르지만 주석처럼 코드에 달아 클래스에 특별한 의미를 부여하거나 기능을 주입할 수 있다. 또 해석되는 시점을 정할 수도 있다.(Retention Policy) 어노테이션에는 크게 세 가지 종류가 존재한다. JDK 에 내장되어 있는 built-in annotation과 어노테이션에 대한 정보를 나타내기 위한 어노테이션인 Meta annotation 그리고 개발자가 직접 만들어 내는 Custom Annotation이 있다. built-in annotation 은 상속받아서 메소드를 오버라이드 할 때 나타나는 @Override 어노테이션이 그 대표적인 예이다. 어노테이션의 동작 대상을 결정하는 Meta-Annotation 에도 여러 가지가 존재한다.
