꾸꾸리

1. 투 포인터 알고리즘 투 포인터 알고리즘은 리스트에 순차적으로 접근할 때 두 개의 점의 위치를 기록하면서 처리하는 방법이다. 두 개의 점을 시작점과 끝점으로 이용하게 되면 데이터의 범위를 표현 가능하며, 메모리와 시간 효율성을 높일 수 있다. 2. 투 포인터의 동작방식 그렇다면 투 포인터가 어떤 식으로 동작하는지 알아보자. 다음과 같은 수열이 존재하였을 때, 연속된 부분수열의 합이 5인 경우의 개수(count)를 구해보자. 이 경우, 투 포인터를 이용한다면 다음과 같은 방법으로 문제를 해결할 수 있다. 시작점과 끝점이 0번 index를 가리킨다.(첫 번째 원소의 index) 현재 부분합이 5라면, count를 1 증가시킨다. 현재 부분합이 5보다 작다면 end를 1 증가시킨다. 현재 부분합이 5보다 ..

1. CCW 알고리즘 이란 점 A, B, C 세 점이 존재하였을 때, 이 세 점의 방향관계를 구하는 알고리즘이다. A, B, C를 연결하였을 때, 반시계 방향일 경우 양수를, 시계 방향일 경우 음수를, 직선일 경우 0을 반환한다. 이 세점의 방향관계를 구하기 위해서 세 점을 두 개의 벡터로 표현하고, 외적을 통하여 그 값이 음수인지 양수인지 0인지를 확인하는 과정이 필요하다. 그럼 우선 외적에 대해 알아보자. 2. 외적 두 벡터 A와 B에 모두 수직인 벡터 A X B를 A, B의 외적이라고 정의한다. 외적의 크기는 |A||B|sinθ이고, 두 벡터가 만드는 평행사변형의 넓이와 같다. 두 벡터의 외적의 방향은 오른손의 법칙을 따른다. 교환법칙이 성립하지 않는다. ( A X B != B X A) A X B ..

1.비트마스킹(BitMasking)이란 비트(bit, binary digit)란 컴퓨터의 최소 연산 단위로, 하나의 bit가 표현할 수 있는 경우는 0과 1로 두 가지이다. 주로 1은 켜져있고, 0은 꺼져있다고 표현한다. 비트 마스킹이란, 정수를 이진수로 표현하여, 비트 연산을 통해 문제를 해결하는 알고리즘 테크닉이다. 5개의 전구의 상태(켜짐/꺼짐)를 표현할 때 다음과 같은 방식들을 이용할 수 있다. 우선 다음과 같이 리스트 자료형으로 표현할 수 있다. 1 lights = [True,True,False,False,False] cs 두번째로 비트마스킹을 이용하여 다음과 같이 2진수의 정수로 표현할 수도 있다. (Python에서 2진수를 표현할때 다음과 같이 앞에 0b를 붙인다.) 1 lights=0b11..