코딩테스트

🙌문제설명양의 정수 `n`이 주어집니다. 이 숫자를 `k`진수로 바꿨을 때, 변환된 수 안에 아래 조건에 맞는 소수(Prime number)가 몇 개인지 알아보려 합니다.`0P0`처럼 소수 양쪽에 0이 있는 경우`P0`처럼 소수 오른쪽에만 0이 있고 왼쪽에는 아무것도 없는 경우`0P`처럼 소수 왼쪽에만 0이 있고 오른쪽에는 아무것도 없는 경우`P`처럼 소수 양쪽에 아무것도 없는 경우단, `P`는 각 자릿수에 0을 포함하지 않는 소수입니다.예를 들어, 101은 `P`가 될 수 없습니다.예를 들어, 437674을 3진수로 바꾸면 `211`0`2`01010`11`입니다. 여기서 찾을 수 있는 조건에 맞는 소수는 왼쪽부터 순서대로 211, 2, 11이 있으며, 총 3개입니다. (211, 2, 11을 `k`진법..

그래프노드 Node(정점 Vertex), 간선 Edge그래프 탐색 : 하나의 노드를 시작으로 다수의 노드를 방문하는것.두 노드가 간선으로 연결되어 있다면, 두 노드는 인접하다고 표현한다.인접 행렬 Adjacency Matrix : 2차원 배열로 연결 관계 표현인접 리스트 Adjacency List : 연결 리스트로 연결 관계 표현예제 5-6. 인접 행렬자바스크립트에서 무한대 숫자를 의미하는 `Infinity`를 이용해 연결되어있지 않다고 표시한다.const INF = Infinity;const graph = [ [0,7,5], [7,0,INF], [5,INF,0]]console.log(graph);0,7,5 노드가 연결된 노드들을 표현한다. 예제 5-7. 인접 리스트[노드, 거리] 형식c..

DFS/BFS 이전에 자료구조 기초를 자바스크립트로 구현하는 방법스택, 큐삽입 push, 삭제pop 함수가 핵심적으로 사용된다.이외에도 오버플로, 언더플로를 고민해야한다오버플로 : 특정한 자료구조가 수용할 수 있는 데이터의 크기를 이미 가득 찬 상태에서 삽입 연산을 수행할때 발생언더플로 : 데이터가 들어있지 않은 상태에서 삭제 연산을 수행할때 발생 스택 Stack선입후출 구조. 출입구가 하나라고 생각하면 된다.예제 5-1const stack = [];stack.push(5);stack.push(2);stack.push(3);stack.push(7);stack.pop();stack.push(1);stach.push(4);stack.pop();console.log(stack);//[5,2,3,1]consol..

🙌문제설명N개의 수로 이루어진 수열 A1, A2, ..., AN이 주어진다. 또, 수와 수 사이에 끼워넣을 수 있는 N-1개의 연산자가 주어진다. 연산자는 덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷)으로만 이루어져 있다.우리는 수와 수 사이에 연산자를 하나씩 넣어서, 수식을 하나 만들 수 있다. 이때, 주어진 수의 순서를 바꾸면 안 된다.예를 들어, 6개의 수로 이루어진 수열이 1, 2, 3, 4, 5, 6이고, 주어진 연산자가 덧셈(+) 2개, 뺄셈(-) 1개, 곱셈(×) 1개, 나눗셈(÷) 1개인 경우에는 총 60가지의 식을 만들 수 있다. 예를 들어, 아래와 같은 식을 만들 수 있다.1+2+3-4×5÷61÷2+3+4-5×61+2÷3×4-5+61÷2×3-4+5+6식의 계산은 연산자 우선 순위를..

🙌문제설명어떤 나라에는 1번부터 N번까지의 도시와 M개의 단방향 도로가 존재한다. 모든 도로의 거리는 1이다.이 때 특정한 도시 X로부터 출발하여 도달할 수 있는 모든 도시 중에서, 최단 거리가 정확히 K인 모든 도시들의 번호를 출력하는 프로그램을 작성하시오. 또한 출발 도시 X에서 출발 도시 X로 가는 최단 거리는 항상 0이라고 가정한다.예를 들어 N=4, K=2, X=1일 때 다음과 같이 그래프가 구성되어 있다고 가정하자.이 때 1번 도시에서 출발하여 도달할 수 있는 도시 중에서, 최단 거리가 2인 도시는 4번 도시 뿐이다.  2번과 3번 도시의 경우, 최단 거리가 1이기 때문에 출력하지 않는다. 입력첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (..

개념 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정 `피지컬`을 요구하는 문제 완전탐색 : 모든 경우의 수를 주저 없이 다 계산하는 해결방법 시뮬레이션 : 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행 ❓자바스크립트 메모리 제약 사항 일반적으로 컴퓨터는 1초에 `10억(10^8)`번 연산의 연산이 가능하다. C++이나 파이썬은 기준이 정해져 있지만, 자바스크립트는 대략 `10^7`번 정도를 기준으로 계산하라는 이야기가 있다. 공식적으로는 정의되어있지 않고, 언어 자체의 특성보다는 브라우저나 실행 환경의 성능에 따라 다를 수 있다고 한다. 정확한 "1초에 몇 번"의 연산으로는 일반적으로 표현되지 않는 대신에, 브라우저나 실행 환경에서의 실제 성능 측정을 통해 어떤 연산이 더 효율적인지 판단하는..

개념 탐욕법 현재 상황에서 지금 당장 좋은 것만 고르는 방법 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다 다익스트라 알고리즘 - 엄밀히 말하면 그리디 알고리즘으로 분류 암기가 필요 없음 해법이 정당한지 검증이 필요 그리디와 정렬 알고리즘과 짝을 이뤄 자주 출제됨 ❓문제를 만났는데 바로 문제 유형을 파악할 수 없는 경우 그리디 알고리즘을 의심하고 해법을 고민 그리디로 해결할 수 없다면 → 다이나믹 프로그래밍이나 그래프 알고리즘으로 해결할 수 있는지 고민 예제 3-1 거스름돈 const COIN_TYPES = [500,100,50,10]; let n = 1260; let cnt = 0; for(const coin of COIN_TYPES) { cnt += Math.floor(n/coin); n..

🙌문제설명 점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다. 예를 들어, 4번 학생은 3번 학생이나 5번 학생에게만 체육복을 빌려줄 수 있습니다. 체육복이 없으면 수업을 들을 수 없기 때문에 체육복을 적절히 빌려 최대한 많은 학생이 체육수업을 들어야 합니다. 전체 학생의 수 n, 체육복을 도난당한 학생들의 번호가 담긴 배열 lost, 여벌의 체육복을 가져온 학생들의 번호가 담긴 배열 reserve가 매개변수로 주어질 때, 체육수업을 들을 수 있는 학생의 최댓값을 return 하도록 solution 함수를..

🙌문제설명 0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요. 예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다. 0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요. 제한사항 numbers의 길이는 1 이상 100,000 이하입니다. numbers의 원소는 0 이상 1,000 이하입니다. 정답이 너무 클 수 있으니 문자열로 바꾸어 return 합니다. ☑️나의 풀이 function solution(numb..