CS4 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을 반환.. 2024. 8. 29. 알고리즘 복잡도 알고리즘 복잡도에 대해서 정리해보았습니다.알고리즘의 복잡도는 시간 복잡도와 공간 복잡도로 나뉩니다. 시간 복잡도 & 공간 복잡도최근에는 하드웨어 메모리 용량이 커졌기 때문에, 알고리즘의 성능 측정에서는 시간 복잡도가 좀 더 우선시 됩니다. 시간 복잡도시간 단위가 아닌, 알고리즘에 필요한 단계 수만을 고려합니다.데이터가 증가할수록 단계 수가 어떻게 변하는지를 말해줍니다. 공간 복잡도프로그램을 실행시켰을 때 필요로 하는 자원 공간의 양입니다.정적으로 선언된 변수, 재귀 함수와 같이 동적으로 공간을 계속해서 필요로 하는 경우도 포함합니다. 빅 오 표기법빅 오 표기법은 자료 구조와 알고리즘의 효율성을 간결하고 일관된 언어로 설명하기 위해 등장했습니다.절대적인 실행 시간과 필요한 자원 공간의 양을 파악하는 것은 .. 2024. 8. 27. [네트워크] HTTP Methods 차이점 정리 HTTP 메서드HTTP 프로토콜에서 사용되는 요청 메서드로, 자원에 대해 서버가 수행할 동작을 지정합니다.총 9가지가 있으며 REST API를 설계할 때 주로 사용되는 메서드는 5가지입니다. 주요 메서드 5가지GET : 서버로부터 자원을 요청하는 동작POST : 서버로 데이터를 전송하여 자원을 생성하거나 업데이트 하는 동작PUT : 서버에 자원을 생성하거나 기존 자원을 대체하는 동작PATCH : 서버 자원의 일부만 수정하는 동작DELETE : 서버에서 자원을 삭제하는 동작 GET vs POST1. GET목적서버로부터 자원을 요청하는 동작데이터 전송 방식요청 본문을 사용하지 않고, 요청 URI에 Path Variable 이나 Query String 을 사용할 것을 권장합니다.보안데이터가 URL에 포함되므로.. 2024. 8. 6. [자료구조] 해시 테이블 해시 테이블이란?키(key)와 값(value)의 쌍으로 데이터를 저장하는 자료구조입니다.해시 테이블에서 삽입, 삭제, 탐색 시 평균적인 시간복잡도는 O(1) 입니다. 어떤 값을 찾더라도 한 단계만 소요된다는 의미입니다.사용 사례검색이나 저장이 빈번할 때 사용하면 좋은데, 특히 캐시를 구현할 때 해시 테이블을 사용할 수 있습니다.캐시는 이전에 계산된 결과를 임시로 저장하는 장소입니다. 캐시의 접근 시간에 비해 원래 데이터를 접근하는 시간이 오래 걸리는 경우나 값을 다시 계산하는 시간을 절약하고 싶은 경우에 사용됩니다. 작동 원리해시 테이블 내부에서는 index와 value로 이루어진 배열 구조를 사용하고 있습니다.키(key)를 해시 함수를 사용하여 배열의 인덱스로 변환한 후, 해당 인덱스에 값(value).. 2024. 7. 11. 이전 1 다음
