분류 전체보기
-
16713번 Generic Queries알고리즘 2023. 1. 21. 10:15
문제 설명 주어진 수열에서 XOR 연산을 하는 query를 여러 개 수행한 결과값들을 다시 XOR연산을 한 값을 구하는 문제입니다. 문제 풀이 선행 지식 XOR Python에서 XOR 연산은 "^"를 통해 이루어진다. XOR 연산의 결과 값 0 ^ 0 = 0 0 ^ 1 = 1 1 ^ 0 = 1 1 ^ 1 = 0 a1^a2^a3^a4 = A라고 할 경우 A^a1 = a2^a3^a4이다. 풀이 개념 이번 문제는 XOR의 개념을 생각하는 데에 오래 걸린 것 같습니다.. 수열의 길이 N과 쿼리의 개수가 모두 10^6로 큰 수 입니다. 그러므로 한 쿼리마다 XOR 연산을 하는 것은 비효율적이므로 누적합을 통해 이용해보도록 하겠습니다. 여기서 헷깔렸던 점은 수열의 홀수번째부터 시작하는 누적합과 짝수번째부터 시작하는..
-
1304번 지역알고리즘 2023. 1. 20. 18:27
문제 설명 이번 문제는 1~N의 도시에서 1->2, 2->3, i->i+1, N-1->N으로 가는 고속 도로가 있고 문제에서 일반 도로가 주어질 경우, 아래 조건을 만족하도록 지역을 나눌 경우 지역의 개수의 최대값을 구하는 문제입니다. 조건 지역 A의 어떤 도시에서 지역 B의 어떤 도시로 넘어갈 수 있는 경로가 있다면, B에 속해 있는 어떤 도시에서 A에 속해 있는 어떤 도시로 가는 경로는 없어야 합니다. 모든 지역의 도시 개수는 같아야 한다. 문제 풀이 아이디어 1 문제의 조건을 다시 생각해보기 위의 조건에 만족하도록 지역을 나눌 경우를 생각해보겠습니다. 모든 도시는 이미 자기보다 +1이 되는 도시로 향하는 도로가 하나씩 있다. 그렇다는 말은, 1에서 3으로 2에서 8로 X에서 Y(X E인 경우만 생각..
-
24453번 디버깅알고리즘 2023. 1. 20. 17:29
문제 설명 이 번 문제는 자동으로 생성된 코드에 오류가 반드시 존재할 때, 이 오류를 자동으로 고쳐주는 커맨드를 누르기 위해 필요한 전제 조건을 만족하여 커맨드를 누를경우 해결되는 오류의 개수를 최대로 하는 문제입니다. 전제 조건 작성된 코드에서 오류가 없는 연속된 X줄이 존재 사용자는 오류를 Y개 이상을 찾아 해결한 뒤에 커맨드를 누르고 싶다 문제 풀이 아이디어 이번 문제는 Y와 관련된 전제 조건을 마지막에 생각하는 것이 핵심인 것 같습니다. X에 관련된 조건과 문제의 답을 연관 시켜보면, 연속된 X줄에서 찾게되는 오류의 개수를 최소로 해야한다는 것을 알 수 있습니다. 그 이유는 이 개수가 최소여야지만, 에디터가 해결할 오류의 개수를 최대로 할 수 있기 때문입니다. 따라서, 연속된 X줄 중에서 나올 수..
-
jest + React testing library + msw 테스트 초기 설정프론트엔드 2023. 1. 11. 15:24
이번 프로젝트를 시작하면서 TDD를 도입해보고자 미리 연습을 해보고 싶어서 이번 포스팅을 작성하게 되었습니다. 프로젝트는 Create React App typescript에 패키지 매니저는 yarn berry를 사용하고 있습니다. 해당 프로젝트 설정은 밑의 링크를 확인해주세요! https://blog.beomseok.dev/52 CRA + typescript + yarn berry 오늘의 포스팅은 yarn berry 패키지 매니저를 이용한 프로젝트 설정 방법을 살펴보도록 하겠습니다. yarn berry를 사용한 이유는 npm, yarn classic의 단점을 보완하고 pnp 방식을 이용해 배포할 경우 패키 blog.beomseok.dev 목차 1. msw란? 2. 설치 방법 3. 초기 설정 4. 예제 1..
-
CRA + typescript + yarn berry프론트엔드 2023. 1. 11. 14:21
오늘의 포스팅은 yarn berry 패키지 매니저를 이용한 프로젝트 설정 방법을 살펴보도록 하겠습니다. yarn berry를 사용한 이유는 npm, yarn classic의 단점을 보완하고 pnp 방식을 이용해 배포할 경우 패키지를 install하는 시간을 줄여 build 시간을 단축시켜주기 때문입니다. 1. yarn 설치 npm install --global yarn yarn --version // 1.22.17 npm을 이용해 yarn을 global 설치를 합니다. 그 다음, 버전 체크를 통해 yarn 실제로 잘 설치 됐는지 확인합니다. 2. yarn을 이용해 typescript CRA 프로젝트 설치 yarn create react-app --template typescript 패키지 매니저를 yar..
-
14570번 나무 위의 구술알고리즘 2023. 1. 3. 15:25
문제 설명 이번 문제는 트리에 구술을 밑의 규칙대로 떨어뜨릴 경우, k번째 구술이 멈추게 될 노드의 위치를 찾는 문제입니다. 규칙 현재 구슬이 놓인 노드의 자식이 없다면 그 자리에서 멈춘다. 1을 만족하지 않으며, 만일 현재 구슬이 놓인 노드의 자식 노드가 한 개라면 해당 자식 노드로 떨어진다. 1, 2를 만족하지 않으며, 만일 현재 구슬이 놓인 노드의 자식 노드가 두 개라면, 현재 노드의 왼쪽 서브트리에 담긴 모든 구슬의 수 오 -> 왼 -> 오... 로 반복된다는 것을 알 수 있다. 즉, k가 홀수일 경우에는 왼쪽으로 짝수일 경우에는 오른쪽으로 구술이 떨어지게 된다. 노드의 레벨마다 k를 2로 나눈 몫으로 교체해야 되는데, 이 때 k가 홀수일 경우에는 추가적으로 1을 더해주어야 한다. 그 이유는 N이..
-
1980번 햄버거 사랑알고리즘 2023. 1. 3. 15:00
문제 설명 두 개의 햄버거를 먹는 속도와 총 시간이 주어진다. 어떤 햄버거도 먹고 있지 않을 경우 콜라를 마신다. 이럴 경우 콜라를 마시는 시간을 최소한으로 하고, 햄버거를 최대한 많이 먹을 경우의 햄버거 개수를 구하는 문제이다. 문제 풀이 이번 문제는 1부터 주어진 시간 t까지 for문을 돌면서, 콜라를 가장 적게 마신 시간 중에서 햄버거를 가장 많이 먹은 개수를 구할 수 있도록 했습니다. 1. 햄버거를 먹는 시간이 적은 시간을 기준으로 주어진 시간내에 최대 먹을 수 있는 개수를 range로 for문을 돌도록했습니다. 2. 해당 시간의 햄버거를 먹었을 때 다른 햄버거를 먹는 개수와 콜라를 마신 시간을 계산해줍니다. 콜라는 현재까지의 최소 콜라 시간과 비교해줍니다. 3. 현재까지의 최소 콜라 시간과 비교..
-
14941번 호기심알고리즘 2023. 1. 3. 14:48
문제 설명 이번 문제는 어떤 범위에 있는 소수가 주어졌을 경우 순서대로 3*A1 - A2 + 3*A3 ... 에 대한 수식에 대입했을 때 나오는 답을 구하는 문제입니다. 문제 풀이 나의 풀이 ※이번 문제는 시간 초과, 틀렸습니다. 등 여러 이유들로 문제를 풀지 못해 먼저 문제를 푸신 분의 설명을 듣고 풀게 되었습니다ㅠ 1. 처음에는 우선 소수를 구한 뒤 주어진 범위에 있는 소수들을 수식에 각각 대입해서 문제를 푸는 식으로 했습니다. -> 시간 초과 2. 소수를 구하는 시간 복잡도를 줄이고 같은 방식으로 문제를 풀었습니다. -> 시간초과 문제를 읽어보니, 질문의 수는 n개이고, 문제의 이름처럼 호기심이 많은 질문자는 질문을 매우 많이 한다고 합니다... 그래서 시간 복잡도를 줄일 방법을 찾아봤지만, 도저히..