🎆

문제더보기전체 쿼리의 수(구간의 최대 수)가 100 이하라는 전제로 모든 구간에 대한 BFS를 진행함으로서 이 문제를 해결할 수 있다.UnionFind로 풀이하다 실패했는데, 구간의 순서가 구간의 포함 여부에 영향을 미치므로 모든 구간의 포함 관계가 갱신되었을때 각각의 포함된 구간에 대한 UnionFind를 다시 수행해줘야 이 문제를 풀이할 수 있다. 그러므로 단순한 BFS로 문제를 재구성했다. 결국 완전탐색으로 풀이해야하므로 2 a b에 대한 입력이 왔을때 a 구간에서부터 시작해서 이동할 수 있는 모든 구간에 대해 탐색하면서 이동할 수 있는 구간을 기준으로 다시 BFS를 진행하여 결국 b 구간이 나오는지에 대한 여부만 확인하면 된다.구간의 수를 N이라 하고, 2 a b라는 쿼리가 오는 경우를 M이라 할..

문제더보기풀이왼쪽에서 부터 선택할 경우 선택할 수 있는 원소의 개수는 ⌊|S|/2⌋, 오른쪽부터 선택할 경우 선택할 수 있는 원소의 개수는  ⌈|S|/2⌉로 정해져 있다.한 방향을 선택하게 된다면 해당 방향의 원소 전체의 GCD를 선택하고 남은 원소들에서 다시 방향을 선택하는 태스크를 진행하게 된다.그러므로 왼쪽을 선택하는 경우, 오른쪽을 선택하는 경우에 대한 모든 경우의 수를 구해 최댓값을 구하면 풀리는 문제다. 배열의 크기는 2*10^5이고, a그러므로 전체 배열에 대해 gcd 연산을 하게 되는 이 알고리즘은 O(N log min(a, b))이다.#include #include #include using namespace std;int N, arr[200001], ans;int gcd(int a, i..

시간을 줄일 수 있는 방법중 하나로 설명되는 전처리이다.전처리라는 단어의 의미와 같이 입력받은 데이터에 대해 선제적으로 처리하여 완전탐색을 피할 수 있도록 하는 방법이다. 문제 1) 괄호 쌍 만들어주기단순 모든 경우의 수를 탐색하면 모든 인덱스를 탐색하면서 여는 괄호가 두개인 시작점을 찾고, 닫는 괄호가 두개인 끝 점을 전부 찾아서 해야된다. 이는 (((()))), (())(())와 같은 경우가 최악의 경우로 생각할 수 있는데, ((을 잡고 ))을 찾기위해 모든 인덱스를 탐색하는 과정에서 시간복잡도는 O(N^2)가 나오게 된다. sol1) 누적합 응용 전처리누적합의 대상을 특정 인덱스 오른쪽의 ))의 개수로 한다. ( ( ) ) ( ( ) ) ( ( ) ) 와 같은 예시가 있다고 하자.인덱스의 역순으로 ..

기본 개념1차 수직선 상에 n개의 선분이 주어졌을 때, x = k 직선과 만나는 서로 다른 선분의 수는 몇 개인지를 판단하는 프로그램을 작성해보세요.단, 주어지는 x 좌표는 모두 다름을 가정해도 좋습니다. 문제를 가시적으로 나타내면 2개라는 것을 쉽게 알 수 있다. 이 가시성을 컴퓨터 알고리즘으로 쉽게 나타내기 위해서는 다음과 같이 시작점에 +1, 끝 점에 -1을 하는 방법이 있다.K를 기준으로 그보다 왼쪽에 있는 점들을 생각하여 만약 끝 점이 k보다 작다면 k와 겹치지 않으므로 시작점의 값 +1 + 끝점의 값 -1을 하므로 0이된다.K를 기준으로 그보다 시작점이 오른쪽에 있는 점 또한 마찬가지이며 만약 겹치는 점이 생길 경우 시작점이 +1이므로 겹치는 구간 +1를 할 수 있다.이렇게 된다면 특정한 구간..

문제더보기마야 문자를 해독하는 일은 예상 외로 어려운 일이다. 현재에도 뜻이 완전히 밝혀진 마야 문자는 거의 없는 실정이며, 그나마 해독에 진척이 시작된 지는 30여 년도 되지 않았다.마야 문자는 소리를 나타내는 여러 종류의 그림글자로 구성되는데, 이 글자들이 여러 위치에서 결합함으로써 단어를 형성한다.마야 문자 해독을 어렵게 하는 요인 중 하나는 바로 단어를 읽는 순서이다. 마야 문자를 쓰는 고대인들은 단어를 기록할 때 특정한 규칙 대신, 그들이 보기에 좋게 보이도록 단어를 이루는 글자들을 아무렇게나 배열했다. 그렇기 때문에 고고학자들이 마야 기록에서 단어를 이루는 각 그림글자들의 발음을 알아내더라도 그 단어를 실제로 발음하는 방법은 정확히 알 수 없는 셈이다.고고학자들은 W라는 특정 단어를 발굴 기록..

문제파이선 프로세스 내에서 쉘을 이용하는 작업을 하는 경우 Subprocess를 사용해서 쉘 작업의 output을 파이선 프로세스에 쉽게 넘길 수 있다. 하지만 Subprocess는 별도의 쉘을 띄워서 작업하므로 쉘 작업이 환경변수를 요하는 작업일 경우에 module not found와 같은 오류가 뜨거나 제대로 작동하지 않는 모습을 보인다. 해결  env는 Subprocess 실행시 환경변수를 지정할 수 있는 인자가 있다.   다음과 같이 env를 지정해서 할 수 있다. 나는 많은 환경변수를 관리하고 적용해야 하는 문제가 있었으므로 (코드가 더러워져서..) export PATH=""export LIB_PATH=""python ~~~.py와 같은 형식으로 shell script를 만들어 직접 환경변수를 ..

서론흔하게 nonblocking-async한 동작을 만들기 위해서는 멀티쓰레딩/멀티프로세싱 과 같은 기법을 사용하게 된다.하지만 python에서는 Global Interpreter Lock 이라는 동일 시점에 하나의 스레드만 사용하도록 하는 인터프리팅 기법이 사용되기 때문에 멀티스레딩으로 다음과 같은 동작을 기대하기 힘들다.그러므로 파이썬 공식 홈페이지에서도 멀티프로세싱을 사용해 비동기적인 작동을 하도록 하는 것을 추천한다. 하지만 프로세스는 스레드와 달리 별도의 메모리 공간을 차지하게되므로, 공유자원을 사용할 경우 난관에 봉착한다. 몰라서 그냥 멀티스레딩으로 작업했는데 알고보니까 Manager라는 객체로 여러 프로세스간의 공유 메모리를 사용할 수 있다고 한다.Manager의 사용법은 공식 홈페이지에 가..

사용 스택front - vite+reactback - Springsession control - redisserver - AWS EC2 문제AWS EC2에 회원관리 기능을 가진 Spring boot 기반 Rest API를 올리고, 프론트에서 요청을 보낼 경우 계속해서 JSESSIONID 쿠키의 값이 계속 바뀌는 현상이 생겼다. 세션이 계속해서 갱신되면서 세션 관리를 레디스로 하기 때문에 레디스에 갱신된 session id로 계속해서 값이 들어가게 되었다.  프론트, 백을 전부 로컬호스트에서 하는 경우에는 이러한 현상이 생기지 않았지만 다른 서버에 프론트와 백을 두게 되면 이러한 문제가 생기게 되었다.  해결Cookie의 SameSite 가 기본적으로 lax로 설정되어 있기 때문에 발생한 오류였다.현재의 ..

문제더보기색을 표현하는 기본 요소를 이용하여 표시할 수 있는 모든 색 중에서 대표적인 색을 고리 모양으로 연결하여 나타낸 것을 색상환이라고 한다. 미국의 화가 먼셀(Munsell)이 교육용으로 고안한 20색상환이 널리 알려져 있다. 아래 그림은 먼셀의 20색상환을 보여준다. 그림 1. 먼셀의 20색상환색상환에서 인접한 두 색은 비슷하여 언뜻 보면 구별하기 어렵다. 위 그림의 20색상환에서 다홍은 빨강과 인접하고 또 주황과도 인접하다. 풀색은 연두, 녹색과 인접하다. 시각적 대비 효과를 얻기 위하여 인접한 두 색을 동시에 사용하지 않기로 한다.주어진 색상환에서 시각적 대비 효과를 얻기 위하여 서로 이웃하지 않은 색들을 선택하는 경우의 수를 생각해 보자.  먼셀의 20색상환에서 시각적 대비 효과를 얻을 수 ..

문제기다란 종이에 알파벳 대문자로만 이루어진 문자열이 한 줄로 쓰여 있다. 예를 들어 아래 그림과 같이 종이에 “ABAACA”가 쓰여 있다고 가정하자. 이제 이 종이를 한 번만 접을 것이다. 종이는 서로 이웃한 문자 사이에서만 접을 수 있다. 예를 들어 아래 그림과 같이 위 종이를 4번째 문자와 5번째 문자 사이에서 접을 수 있다. 이때 서로 맞닿은 문자 쌍 중에서, 서로 같은 문자가 맞닿은 쌍의 개수가 이 접기의 점수가 된다. 예를 들어 앞에서의 접기의 점수는 1점이 된다. 하지만 아래 그림과 같이 3번째 문자와 4번째 문자 사이에서 종이를 접으면 점수는 2$점이 된다. 이제 여러분은 알파벳 대문자로만 이루어진 문자열 𝑆$ S $가 주어질 때, 다음과 같은 질문 𝑄개에 답해야 한다. 𝑙 𝑟$: ..