생각해보기 에라토스테네스의 체 대량의 소수를 한꺼번에 판별하고자 할 때 사용 loose upper-bound : O(NlogN) proper upper-bound : O(Nlog(logN)) 2이상 N이하인 범위 내 모든 소수를 구할 때, 에라토스테네스의 체를 이용할 수 있다. 이때, 2이상 √N이하인 소수의 배수들을 해당 범위 내에서 제외시키는 방식으로 구할 수 있다. 또한 소수의 배수들을 제외시킬 때, 해당 소수의 제곱부터 시작하면 된다. 이 이유는 아래에서 설명한다. loose upper-bound 2이상 N이하의 모든 자연수에 대해, 소수의 배수들을 제외하는 연산의 횟수를 계산해보자. 먼저 근사화를 통해 해당 범위 내 모든 소수의 배수가 아닌 모든 자연수의 배수를 제외시키는 상황을 가정한다. 예를..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/132266 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 생각해보기 시도해본 방법 1. shift 연산 → queue 구현 2. 방문 체크 자료구조 : 배열 → Map 객체 3. 인접 리스트 자료구조 : 2차원 배열 → Map 객체 index를 알고 있으면 배열 또한 탐색을 O(1)로 수행할 수 있으므로 차이가 없었다. 그러나 2, 3의 경우 길이 없는 지역에 대해 (key, value)를 할당하지 않으므로 특정 조건 하에(길이 없는 지역이 많을..

생각해보기 포화 이진 트리는 노드의 개수가 2^n - 1개이다. 더미 노드는 주어진 수를 변경하면 안되므로 이진수로 변환된 문자열의 앞에 추가된다. 부모 노드가 0인데 자식 노드가 1인 경우, 이진 트리가 될 수 없다. 부모 노드와 자식 노드가 모두 0인 경우는 가능 더미 노드의 개수 파악하기 더미 노드의 개수를 찾는 과정을 반복한다. 이를 통해 규칙성을 파악하고 식으로 나타내보자. 주어진 수 1 2 3 4 5 6 7 8 9 A 1 10 11 100 101 110 111 1000 1001 B 1 2 2 3 3 3 3 4 4 C 1 10 10 11 11 11 11 100 100 D 1 2 2 2 2 2 2 3 3 A : 주어진 수에 대한 이진수 변환 B : A의 길이 C : B에 대한 이진수 변환 D : ..

문제 설명 자연수 x를 y로 변환하려고 합니다. 사용할 수 있는 연산은 다음과 같습니다. x에 n을 더합니다 x에 2를 곱합니다. x에 3을 곱합니다. 자연수 x, y, n이 매개변수로 주어질 때, x를 y로 변환하기 위해 필요한 최소 연산 횟수를 return하도록 solution 함수를 완성해주세요. 이때 x를 y로 만들 수 없다면 -1을 return 해주세요. 제한사항 1 ≤ x ≤ y ≤ 1,000,000 1 ≤ n

풀이 1) recursion /** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */ /** * @param {TreeNode} root * @return {boolean} */ var isSymmetric = function(root) { return isSame(root.left, root.right); }; var isSame = function (leftr..

생각해보기 처음에는 아스키 코드를 통해 a ~ z까지 다 바꾸면서 비교하는 방식으로 했었다. 그러나 문제 조건을 활용하면 연산 횟수를 줄일 수 있다. 조건 1 - words라는 배열 안에 있는 단어로만 변환 가능하다는 점 조건 2 - 한 번의 변환 과정에서 하나의 알파벳만 바꿀 수 있다는 점 다른 알파벳의 수를 count해서 count가 1이면 변환 가능한 단어임을 알 수 있다. 조건 1에 의해 words 배열 안에 있는 단어들에 한정하여 비교를 진행하면 된다. DFS를 통해 탐색할 때, visited를 초기화하여 다른 경우의 수에 대해서도 탐색을 가능하게 한다. 또한 count를 갱신하면서 최소 횟수를 찾는다. 풀이) function solution(begin, target, words) { let a..

생각해보기 인접 리스트로만 풀다보니 인접 행렬에 대해 미숙했다. 인접 리스트와 인접 행렬에 대한 구현과 탐색을 다시 숙지하자. 네트워크의 개수 = 부분 그래프의 개수 임의의 정점 x에 대해 BFS 또는 DFS로 탐색하였을 때, 방문하지 않은 노드들은 임의의 정점 x와 같은 그래프에 속해 있지 않다. 따라서 방문하지 않은 노드들에 대해 BFS 또는 DFS 탐색을 다시 수행한다. 조건문 안에서 BFS 또는 DFS 함수가 호출된 횟수가 곧 네트워크의 개수이다. 풀이) function solution(n, computers) { let answer = 0; let visited = Array.from({ length: n }, () => false); // BFS function bfs(x) { let queu..

https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 생각해보기 인접 행렬과 인접 리스트의 구현과 탐색 방법 인접 행렬의 경우, 인수로 넘겨진 노드를 기준으로 해서 각각의 다른 노드들이 연결되어 있는지 확인하며 탐색 인접 리스트의 경우, 인수로 넘겨진 노드에 해당하는 인덱스에 연결된 노드의 정보들이 있음 DFS와 BFS의 노드 탐색 순서 DFS 재귀 호출이나 스택으로 구현 함수 호출이 되면서 방문 체크 BFS 큐..