본문 바로가기

CS

(6)

투 포인터 알고리즘 정의투 포인터(Two Pointer) 알고리즘이란, 배열이나 컬렉션에서 두 개의 포인터를 이용하여 범위를 조절해가며 특정한 조건을 만족하는 부분을 찾는 기법이다.특히 정렬된 배열이나 컬렉션과 관련된 문제에서 효과적으로 사용된다.핵심 아이디어는 배열의 서로 다른 두 부분을 동시에 반복하는 것이다.일반적으로 시간 복잡도는 O(n), 공간 복잡도는 O(1)이 된다.런타임을 최적화하고 공간을 절약하고 싶을 때 사용한다.고려해야 할 점포인터의 초기 위치 설정포인터를 어디서 시작하고 어떤 인덱스를 비교할 것인가?포인터의 이동 방향과 조건같은 방향으로 이동할 것인가, 다른 방향으로 이동할 것인가?포인터를 언제 움직일 것인가?포인터의 중지 조건포인터를 언제 멈출 것인가?일반적으로 배열의 반복이 끝날 때나 두 포인터가 ..

세션 기반 인증 vs 토큰 기반 인증, 그리고 쿠키🍪 세션? 토큰? 쿠키? 인증 방식에 대해 이야기할 때 헷갈리는 개념들을 정리해보고자 합니다. HTTP는 무상태!우선 HTTP 프로토콜이 무상태(stateless)라는 것을 이해해야 합니다.HTTP 프로토콜로 웹을 통해 통신해야 할 때, 우리가 보내는 각각의 요청은 독립적입니다.요청이 끝나면 서버는 클라이언트의 정보를 잊어버리고, 요청을 보낼 때마다 클라이언트가 누군지 알려줘야 합니다. 서버에게 요청을 보낼 때 클라이언트가 누군지 알려주는 방식으로 대표적으로 세션과 토큰이 있는 것입니다.세션 인증 방식과 토큰 인증 방식의 로그인 방법에 대해 이야기 해보겠습니다. 세션(session)세션 인증 방식으로 로그인을 하는 과정은 다음과 같습니다.클라이언트는 사용자 인증 정보(예를 들면 유저명, 비밀번호)를 담아서 ..

Boyer-Moore 과반수 투표 알고리즘 Boyer-Moore 과반수 투표 알고리즘 (Boyer-Moore majority vote algorithm)주어진 후보자 목록에서 과반수를 차지하는 후보를 찾는 알고리즘이다.배열 내 과반수에 해당하는 원소가 항상 존재한다고 가정하면, 결과값은 항상 과반수 원소가 된다.핵심 아이디어는 주어진 후보자 목록에 두 가지의 서로 다른 후보를 지정하고, 이들을 서로 상쇄시켜가며 최종 후보를 결정하는 것이다.시간 복잡도는 O(N), 공간 복잡도는 O(1) 이다. 동작 방식 입력 시퀀스 요소 m과 카운터 c를 0으로 초기화한다.입력 시퀀스에서 각각의 요소 x에 대해서c == 0 이면 m = x, c = 1 대입한다.m == x 이면 c = c + 1 대입한다.m != x 이면 c = c -1 대입한다.m을 반환한다...

알고리즘 복잡도 시간 복잡도 & 공간 복잡도 알고리즘의 복잡도는 시간 복잡도와 공간 복잡도로 나뉜다. 최근에는 하드웨어 메모리 용량이 커졌기 때문에, 알고리즘 성능 측정에서는 시간 복잡도가 좀 더 우선시된다. 1. 시간 복잡도알고리즘에 필요한 단계 수만 고려한다.데이터가 증가할수록 단계 수가 어떻게 변하는지를 말해준다.2. 공간복잡도프로그램을 실행시켰을 때 필요로 하는 자원 공간의 양이다.정적으로 선언된 변수, 재귀함수와 같이 동적으로 공간을 계속해서 필요로 하는 경우도 포함한다. 빅 오 표기법자료구조와 알고리즘의 효율성을 간결하고 일관된 언어로 설명하기 위해 등장했다.절대적인 실행 시간과 필요한 자원 공간의 양을 파악하기란 어려우므로, 빅 오 표기법으로 알고리즘의 효율성을 정량화할 수 있다.입력 크기 N에 따라 연산이..

[네트워크] HTTP Methods 차이점 정리 HTTP 메서드HTTP 프로토콜에서 사용되는 요청 메서드로, 자원에 대해 서버가 수행할 동작을 지정합니다.총 9가지가 있으며 REST API를 설계할 때 주로 사용되는 메서드는 5가지입니다. 주요 메서드 5가지GET : 서버로부터 자원을 요청하는 동작POST : 서버로 데이터를 전송하여 자원을 생성하거나 업데이트 하는 동작PUT : 서버에 자원을 생성하거나 기존 자원을 대체하는 동작PATCH : 서버 자원의 일부만 수정하는 동작DELETE : 서버에서 자원을 삭제하는 동작 GET vs POST1. GET목적서버로부터 자원을 요청하는 동작데이터 전송 방식요청 본문을 사용하지 않고, 요청 URI에 Path Variable 이나 Query String 을 사용할 것을 권장합니다.보안데이터가 URL에 포함되므로..

[자료구조] 해시 테이블 해시 테이블이란?키(key)와 값(value)의 쌍으로 데이터를 저장하는 자료구조.해시 테이블에서 삽입/삭제/탐색 시 평균적인 시간복잡도는 O(1)로, 어떤 값을 찾더라도 한 단계만 소요된다.사용 사례검색이나 저장이 빈번할 때 사용하면 좋은데, 특히 캐시를 구현할 때 해시 테이블을 사용할 수 있다.캐시는 이전에 계산된 결과를 임시로 저장하는 장소로, 캐시의 접근 시간에 비해 원래 데이터를 접근하는 시간이 오래 걸리는 경우나 값을 다시 계산하는 시간을 절약하고 싶은 경우에 사용된다.작동 원리해시 테이블 내부에서는 index와 value로 이루어진 배열 구조를 사용한다.키(key)를 해시 함수를 사용하여 배열의 인덱스로 변환한 후 해당 인덱스에 값(value)을 저장한다. 해시 함수해시 테이블에서의 해시 함..

이전 1 다음

티스토리툴바