백준 11689번 문제인 GCD(n, k) = 1 문제는 정확히 오일러 피를 묻는 문제이다. 오일러 피 공식만 코드로 구현하면 끝나는데 난이도가 골드1로 꽤 높은 편이다. 주어지는 수의 범위가 10의 12승으로 매우 커서 오일러 피의 원리를 모르고 단순히 탐색으로 문제를 풀면 시간초과가 발생하기때문에 그런것 같다.  1. 오일러 피 함수란?오일러 피 함수란 자연수 n에 대해 n과 서로소(공약수가 1뿐인 수)인 n이하의 자연수 개수를 구하는 함수이다. ex) n=12 일때n 이하의 자연수중 n과 서로소인 수 : 1, 5, 7, 1112에 대한 오일러 피 함수 결과 = 4  2. 오일러 피 함수의 원리와 사용법먼저 오일러 피 함수를 구현한 코드를 보면 아래와 같다.function eulerPhi(n) { ..

정수론 유클리드 호제법 문제풀이 중 백준 칵테일 문제를 풀게되었다. 유클리드 호제법을 알고 최대공약수를 구하는 과정 자체는 간단하지만 문제 풀이가 간단하지 않아서... 글로 정리해보려 한다. 글 작성에 앞서 문제를 푸는 아이디어를 얻기위해 여러 게시글과 백준 질문 게시판, ChatGPT의 도움을 받았다.문제에서 상황설명이 꽤 길게 작성되어있는데 그것때문에 더욱 헷갈린 것 같다. 문제 내용을 정리하면 칵테일들중 특정 두개의 비율을 몇개 알려줄테니 전체의 비율을 구해라 이다. 이 점을 기억하고 풀이하면 도움이 될 것 같다. • 문제 : 백준 1033번 - 칵테일더보기1033번: 칵테일문제를 풀기 위해 아래와 같은 요소들을 고려하였다.최대공약수, 최소공배수를 구할때 유클리드 호제법을 활용했다.입력에서 주어지는..

소수란 1보다 큰 자연수중 1과 자기자신만을 약수로 가지는 수 이다. 즉 1과 자기 자신 외의 어떤 수로도 나누어떨어지지 않는다.소수를 구하는 가장 간단한 방법은 1부터 자기자신까지 모든 수로 나누어 보는것이다. 그때 나누어떨어지는 수가 있으면 소수가 아닌것이다.하지만 이러한 완전탐색방식을 사용하면 O(N)의 시간복잡도로 꽤 긴시간이 걸리게 된다.수학적 원리를 이용한 알고리즘을 활용하면 소수를 탐색하는 시간을 줄일 수 있다.   1. 소수 탐색의 기본 조건프로그래밍으로 소수를 탐색하면 반복문을 활용하게 된다. 반복문으로 특정 범위에서 소스를 탐색하기에 앞서 기본적으로 고려해야할 조건이 있다.1은 소수가 아니다.2는 소수이며 2의 배수는 모두 소수가 아니다. (2가 약수이므로)소수를 탐색하기에 앞서 두 조..

더보기11003번: 최솟값 찾기문제를 풀기 위해 아래와 같은 요소들을 고려하였다.L이 1이면 범위가 1이므로 최솟값은 자기자신이 된다. L이 1일경우 숫자배열을 그대로 반환한다.문제의 시간제한은 2.4초 이고 주어지는 숫자의 개수는 최대 5,000,000개 이다. 최솟값을 찾기위해 단순히 정렬을 이용하면 O(n log n)의 시간복잡도로 시간초과가 발생한다. Deque를 사용하여 최솟값을 관리하여 O(n)의 시간복잡도로 줄일 수 있다.특정 범위의 최솟값을 찾아야 하므로 슬라이딩 윈도우를 사용한다.슬라이딩 윈도우는 뒤의 값을 추가하고 앞의 값을 제거하면서 범위를 유지한 채 나아가는 기법이다. 이는 최솟값을 관리하는 Deque에서도 사용해야하는 값의 범위이므로 Deque에는 최솟값 자체를 집어넣는 것이 아닌..

투 포인터를 사용해야 하는 문제는 모든 경우의 수를 확인하는 방법(브루트포스)을 사용하면 시간초과가 발생한다. 특정 범위 혹은 특정한 두 값에 대해 문제에서 주어진 조건과 매치를 하는 경우 투 포인터 기법을 활용하여 수행 시간(시간복잡도)을 단축시킬 수 있다.  1. 투포인터란?투 포인터 알고리즘은 배열 혹은 리스트를 순회하면서 두 개의 포인터를 사용해 문제를 해결하는 기법이다.주로 연속적인 구간을 찾거나, 특정 조건을 만족하는 두 요소를 탐색할때 사용된다. 두 개의 포인터 활용배열에서 두개의 포인터를 가지고 특정 조건을 탐색한다. 두 포인터를 합하는 등 단순히 활용할수도 있으며 두 포인터 사이값을 활용하여 특정 조건에 맞는지 검사할 수 도 있다.정렬된 배열에서 주로 사용투 포인터는 좌우 포인터를 이동시..

더보기3190번: 뱀문제를 풀기 위해 아래와 같은 요소들을 고려하였다.뱀의 머리 위치에 따라 뱀의 길이가 증가하거나 게임이 종료되므로 queue의 형태로 뱀 배열을 관리했다.readline과 join을 통해 하나의 문자열로 입력되는 값을 처리하기 위해 split, slice, reduce, map등을 활용했다.뱀의 이동에는 enqueue와 dequeue가 사용되었다.경과한 시간 변수를 관리하고 이를 방향전환 정보와 매칭해서 사용했으며 방향은 상하좌우 배열로 따로 관리했다. 1. 소스코드더보기const readline = require("readline");const solution = (data) => { let boardSize = Number(data.split("\n")[0]); let ..

더보기더보기더보기더보기코딩테스트 연습 - 여행경로 | 프로그래머스 스쿨 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr문제를 풀기위해 아래와 같은 요소들을 고려하였다.tickets에 sort를 먼저 적용하여 가장 빠르게 나오는 답변이 알파벳 순이 될 수 있도록 했다.조합을 생성하여 가장 적합한 결과를 찾아야하므로 DFS를 활용했다.더보기더보기더보기더보기function solution(tickets) { tickets.sort(); let result = []; let visited = Array(tickets.length).fill(false); function dfs(airport..

더보기13458번: 시험 감독문제를 풀기위해 아래와 같은 요소들을 고려하였다.프로그래머스와 달리 백준은 입력값을 직접 처리해주어야 한다. (readline or fs)총감독관 혼자 감독할 수 있는 경우와 부감독관이 필요한 경우로 나누어서 계산했다. 1. 소스코드더보기const readline = require("readline");function solution(data) { const [n, ai, count] = data.split("\n"); const st = ai.split(" ").map(Number); const [b, c] = count.split(" ").map(Number); let total = 0; for (let i = 0; i { inpu..