상권's
TIL 13 (2021.10.19) 본문
O(1) – 상수 시간 : 문제를 해결하는데 오직 한 단계만 처리함.
O(log n) – 로그 시간 : 문제를 해결하는데 필요한 단계들이 연산마다 특정 요인에 의해 줄어듬.
=> 주로 입력 크기에 따라 처리 시간이 증가하는 정렬알고리즘에서 많이 사용된다.
O(n) – 직선적 시간 : 문제를 해결하기 위한 단계의 수와 입력값 n이 1:1 관계를 가짐.
O(n log n) : 문제를 해결하기 위한 단계의 수가 N*(log2N) 번만큼의 수행시간을 가진다. (선형로그형)
=> 주로 입력 크기에 따라 처리 시간이 증가하는 정렬알고리즘에서 많이 사용된다.
O(n^2) – 2차 시간 : 문제를 해결하기 위한 단계의 수는 입력값 n의 제곱.
=> 반복문이 2번 있는 케이스
O(C^n) – 지수 시간 : 문제를 해결하기 위한 단계의 수는 주어진 상수값 C 의 n 제곱.
시간복잡도를 구하는 요령
각 문제의 시간복잡도 유형을 빨리 파악할 수 있도록 아래 예를 통해 빠르게 알아 볼수 있다.
- 하나의 루프를 사용하여 단일 요소 집합을 반복 하는 경우 : O (n)
- 컬렉션의 절반 이상 을 반복 하는 경우 : O (n / 2) -> O (n)
- 두 개의 다른 루프를 사용하여 두 개의 개별 콜렉션을 반복 할 경우 : O (n + m) -> O (n)
- 두 개의 중첩 루프를 사용하여 단일 컬렉션을 반복하는 경우 : O (n²)
- 두 개의 중첩 루프를 사용하여 두 개의 다른 콜렉션을 반복 할 경우 : O (n * m) -> O (n²)
- 컬렉션 정렬을 사용하는 경우 : O(n*log(n))
- 2021.10.19 오늘의 코플릿-
두 수를 입력받아 거듭제곱을 리턴해야 합니다.
Math.pow, 거듭제곱 연산자 사용은 금지됩니다.
시간복잡도 O(logN)을 만족해야 합니다. 나머지를 구하는 이유는 계산 결과가 컴퓨터로 나타낼 수 있는 수의 범위를 넘을 수 있기 때문입니다. 하지만 모든 연산이 끝난 뒤에 그 결과를 94,906,249로 나누려고 해서는 안 됩니다.
연산 중간에도 이 범위를 넘을 수 있기 때문에, 연산을 할 때마다 나머지를 구하고 그 결과에 연산을 이어가시기 바랍니다.
// while을 사용해서 exponent가 0이 될 때까지 곱한다.
// 리턴할 때 94,906,249로 나눠서 나머지 값을 리턴한다.
// exponent가 0이 될 때까지 while 반복문을 통해서
// result = result * base
// exponent = exponent - 1 실행
// return할 때 % 94906249 를 한다.첫 수도코드 => base를 exponent만큼 곱해주기만 하면 되는 문제로 간단하게 생각을 했습니다.
그런데 역시나 한 번에 모든 테스트 코드를 통과할 수 없었습니다. 항상 문제에 시간복잡도를 충족하라는 주의사항이 붙어있었는데, 사실 코드를 짜고 자시고 해야지 시간복잡도를 충족하지만, 대게 그 정도도 못하다가 오늘 자세하게 알아보게 되었습니다.
첫 수도코드를 진행했을 경우 O(n)로 진행이 되었을 것입니다. O(log n) 이 연산 시간이 짧다는 건 알겠지만 코드 구현이 어려웠습니다. 그래서 레프런스의 도움이 받았습니다.
// 짝수의 경우에는 2로 나눈 후, 그 값을 재귀한 것을 변수에 담고, 이 변수를 두개 곱하고 94906249 나머지 값을 구한다.
// 홀수의 경우에는 parseInt(홀수 / 2) 하면 소수점 자리는 안 나오기 때문에 한 번 더 곱해주고 94906249 구한다.
코드 구현이 원활해지면 시간복잡도를 충족시키기 위해 노력할 것 입니다.
REST API에 대해 이해할 수 있다.
REST API는 Representational State Transfer API로, 웹에서 사용되는 데이터나 자원(Resource)을 HTTP URI로 표현하고, HTTP 프로토콜을 통해 요청과 응답을 정의하는 방식을 말합니다.
레오나르드 리차드슨은 REST API를 잘 적용하기 위해 성숙도 모델(4단계)을 만들었습니다.
실제로 엄밀하게 3단계까지 지키기 어렵기 때문에 2단계까지만 적용해도 좋은 API 디자인이라고 볼 수 있고, 이런 경우 HTTP API 라고도 부릅니다.
REST 성숙도 모델 - 0단계
0단계에서는 단순히 HTTP 프로토콜을 사용
0단계는 좋은 REST API를 작성하기 위한 기본 단계입니다.
단순히 HTTP 프로토콜을 사용하는 것이 REST API의 출발점
REST 성숙도 모델 - 1단계
1단계에서는 개별 리소스와의 통신 준수
REST API는 웹에서 사용되는 모든 데이터나 자원(Resource)을 HTTP URI로 표현 =>
자원은 개별 리소스에 맞는 엔드포인트(Endpoint)를 사용해서 요청 & 받은 자원에 대한 정보를 응답으로 전달
어떤 리소스를 변화시키는지 혹은 어떤 응답이 제공되는지에 따라 각기 다른 엔드포인트를 사용하기 때문에, 적절한 엔드포인트를 작성하는 것이 중요합니다. 엔드포인트 작성 시에는 동사, HTTP 메소드, 혹은 어떤 행위에 대한 단어 사용은 지양하고, 리소스에 집중해 명사 형태의 단어로 작성하는 것이 바람직 방법입니다.
1단계에서는 요청하는 리소스가 무엇인지에 따라 각기 다른 엔드포인트로 구분해서 사용.
=> 0단계에서는 모든 요청에서 엔드포인트로 /appointment를 사용
=> 1단계에서는 요청하는 게 무엇인지에 따라 엔드포인트를 변경
=>
1. 예약 가능 시간 확인에서는 '/doctors/허준' 엔드포인트를 사용해서 '허준'의 예약 가능한 시간(자원)을 받음
2. 특정 시간에 예약에서는 앞선 요청에서 받은 자원 중, 예약을 원하는 시간 대의 id를 이용해서 /slots/123을 엔드포인트로 작성
=> 예약을 통해서 리소스를 변화시키기 때문에 실제 변경 시킬 리소스를 엔드포인트로 작성.
3. 응답으로 리소스를 전달할 때에도 사용한 리소스에 대한 정보와 함께 리소스 사용에 대한 성공/실패 여부를 반환
REST 성숙도 모델 - 2단계
2단계에서는 CRUD에 맞게 적절한 HTTP 메소드를 사용
메소드 사용 규칙
GET 메소드 같은 경우는 서버의 데이터를 변화시키지 않는 요청에 사용해야 합니다.
POST는 요청마다 새로운 리소스를 생성하고 PUT 은 요청마다 같은 리소스를 반환합니다.
이렇게 매 요청마다 같은 리소스를 반환하는 특징을 멱등(idempotent)하다고 합니다. 그렇기 때문에 멱등성을 가지는 메소드 PUT과 그렇지 않은 POST는 구분하여 사용해야 합니다.
0단계와 1단계에서는 모든 요청을 POST 진행
=> 예약 가능 시간 확인은 조회(READ) GET 메소드를 사용
=> GET 메소드는 body를 가지지 않기 때문에 query parameter를 사용하여 필요한 리소스를 전달
/doctors/허준/slots?date=2022-08-10
=> 특정 시간에 예약하는 것은 예약은 생성(CREATE) POST 메소드를 사용
POST에 대한 응답도 중요!
=> 이 경우 응답은 새롭게 생성된 리소스를 보내주기 때문에, 응답 코드도 201 Created 로 명확하게 작성
=> 관련 리소스를 클라이언트가 Location 헤더에 작성된 URI를 통해 확인 가능해야 함
REST 성숙도 모델의 2단계까지 적용을 하면 대체적으로 잘 작성된 API라고 여겨짐
물론 로이 필딩은 앞서 이야기한 바와 같이 3단계까지 만족하지 못한다면 REST API가 아니기 때문에 HTTP API라고 불러야 한다고 주장 => 3단계까지 적용한 경우는 드물기 때문에, 꼭 3단계까지 적용해야 하는 건 아님
REST 성숙도 모델 - 3단계
HATEOAS(Hypertext As The Engine Of Application State)라는 약어로 표현되는 하이퍼미디어 컨트롤 적용
3단계의 요청은 2단계와 동일하지만, 응답에는 리소스의 URI를 포함한 링크 요소를 삽입하여 작성
=> 링크 요소는 응답을 받은 다음에 할 수 있는 다양한 액션들을 위해 많은 하이퍼미디어 컨트롤을 포함
예약 가능 시간을 확인한 후에는 그 시간대에 예약을 할 수 있는 링크를 삽입,
특정 시간에 예약을 완료하고 나서는 그 예약을 다시 확인할 수 있도록 링크를 작성
=> 응답 내에 새로운 링크를 넣어 새로운 기능에 접근할 수 있도록 하는 것이 3단계의 중요 포인트
=> 이러한 링크들은 조금 더 쉽고, 효율적으로 리소스와 기능에 접근할 수 있게 하는 트리거가 될 수 있음
Open API와 API Key에 대해 이해할 수 있다.
- Open API 누구나 해당 기관이나 API에서 제공하는 이용 수칙만 준수하면 이용할 수 있는 API
- API Key 해당 API에 접근할 수 있는 권한으로, 데이터를 요청할 때 API Key를 같이 전달해서 원하는 응답을 받을 수 있음
'~2022 작성 글 > TIL' 카테고리의 다른 글
| TIL 15(멱집합&WindowLocalStorage) (2021.10.21) (0) | 2021.10.21 |
|---|---|
| TIL 14 (2021.10.20) (0) | 2021.10.20 |
| TIL 12 (Redux, sort(), HTTP, 멱등성)(2021.10.18) (0) | 2021.10.18 |
| TIL 11 (2021.10.17) (0) | 2021.10.17 |
| TIL 10 코드 리뷰 (2021.10.08) (0) | 2021.10.16 |
