본문 바로가기

Algorithm28

[JS] 백준 2565번 전깃줄 문제 링크 https://www.acmicpc.net/problem/2565 풀이 전략 문제의 요지는 서로 교차하지 않기 위해 없애야하는 전깃줄의 최소 개수를 구하는 것이다. 그리디 풀이 방식으로 가장 많이 교차하고 있는 전깃줄을 없애가며 풀 수 있지만dp로 풀기 위해서는 이를 반대로 생각할줄 알아야했다. 전깃줄이 꼬이지 않게 하려면 오른쪽에 있는 전깃줄들의 번호가 오름차순이어야한다. 다시말해, 우리는 우리가 없애야하는 전깃줄을 최소로 하기 위해서, 전체 전봇대중 가장 긴 증가하는 부분수열(LIS)을 찾으면 된다. 이게 왜 가능하냐면, 만약 전깃줄이 꼬여있을 때 오른쪽 전깃줄의 전기선은 오름차순으로 가다가 중간중간 낮아지는 부분들이 있을 것이다. 이 부분의 전깃줄만 제거한다면, 우리가 원하는 최소의 갯수.. 2022. 11. 21.
[JS] 백준 10814번 나이순 정렬 문제 링크 https://www.acmicpc.net/problem/10814 풀이 전략 온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 작성하시오. => stable하게 정렬해야 한다. => 대표적인 stable sort 알고리즘인 counting sort(계수정렬)을 이용하였습니다. 코드 const fs = require("fs"); const input = fs.readFileSync("/dev/stdin").toString().trim().split("\n"); // counting sort. const n = input.shift(); solution(input.. 2022. 7. 12.
[JS] 백준 1300번 K번째 수 문제 링크 https://www.acmicpc.net/problem/1300 풀이 전략 B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 B의 인덱스는 1부터 시작한다. 코드 const fs = require("fs"); const [n, k] = fs .readFileSync("/dev/stdin") .toString() .trim() .split(/\s/) .map(Number); solution(n, k); function solution(n, k) { let lt = 1; let rt = n * n; // k의 최대값은 n * n이기 때문에 rt는 n * n while (lt = k) rt = mid - 1; // 순서를 확인하여 k보다 크거나 같다면 rt를 mid보다 작게한 else .. 2022. 7. 8.
[JS] 백준 2110번 공유기 설치 문제 링크 https://www.acmicpc.net/problem/2110 풀이 전략 C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하시오. 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 한 줄에 하나씩 주어진다. 코드 const fs = require("fs"); const input = fs .readFileSync("/dev/stdin") .toString() .trim() .split(/\s/) .map(Number); const n =.. 2022. 7. 6.
[JS] 2019카카오 : 실패율 프로그래머스 LEVEL1 문제 링크 https://programmers.co.kr/learn/courses/30/lessons/42889 풀이 전략 실패율은 다음과 같이 정의한다. - 스테이지에 도달했으나 아직 클리어하지 못한 플레이어의 수 / 스테이지에 도달한 플레이어 수 실패율이 높은 스테이지부터 내림차순으로 스테이지의 번호가 담겨있는 배열을 return 하도록 solution 함수를 완성하라. tages에는 1 이상 N + 1 이하의 자연수가 담겨있다. - 각 자연수는 사용자가 현재 도전 중인 스테이지의 번호를 나타낸다. - 단, N + 1 은 마지막 스테이지(N 번째 스테이지) 까지 클리어 한 사용자를 나타낸다. 코드 function solution(N, stages) { const answer = []; const ar.. 2022. 6. 30.
[JS] 2020카카오 : 키패드 누르기 프로그래머스 LEVEL1 문제 링크 https://programmers.co.kr/learn/courses/30/lessons/67256 풀이 전략 엄지손가락은 상하좌우 4가지 방향으로만 이동할 수 있으며 키패드 이동 한 칸은 거리로 1에 해당합니다. 왼쪽 열의 3개의 숫자 1, 4, 7을 입력할 때는 왼손 엄지손가락을 사용합니다. 오른쪽 열의 3개의 숫자 3, 6, 9를 입력할 때는 오른손 엄지손가락을 사용합니다. 가운데 열의 4개의 숫자 2, 5, 8, 0을 입력할 때는 두 엄지손가락의 현재 키패드의 위치에서 더 가까운 엄지손가락을 사용합니다.4-1. 만약 두 엄지손가락의 거리가 같다면, 오른손잡이는 오른손 엄지손가락, 왼손잡이는 왼손 엄지손가락을 사용합니다. 코드 const keypad = [ ["1", "2", "3"],.. 2022. 6. 26.
[JS] 2021Dev-Matching : 로또의 최고 순위와 최저 순위 프로그래머스 LEVEL1 문제 링크 https://programmers.co.kr/learn/courses/30/lessons/77484 풀이 전략 순서와 상관없이, 구매한 로또에 당첨 번호와 일치하는 번호가 있으면 맞힌 걸로 인정됩니다. 코드 function solution(lottos, win_nums) { var answer = []; let zero = 0; let correct = 0; for(const num of lottos){ if(num === 0) zero++; for(const win of win_nums){ if(num === win) correct++; } } let best = 7 - (zero+correct); let worst = 7 - correct; if(best >= 7) best = 6 if(.. 2022. 6. 24.
[JS] 2022카카오 : 신고 결과 받기 프로그래머스 LEVEL2 문제 링크 https://programmers.co.kr/learn/courses/30/lessons/92334 풀이 전략 각 유저는 한 번에 한 명의 유저를 신고할 수 있습니다. - 신고 횟수에 제한은 없습니다. - 서로 다른 유저를 계속해서 신고할 수 있습니다. - 한 유저를 여러 번 신고할 수도 있지만, 동일한 유저에 대한 신고 횟수는 1회로 처리됩니다. k번 이상 신고된 유저는 게시판 이용이 정지되며, 해당 유저를 신고한 모든 유저에게 정지 사실을 메일로 발송합니다. 유저가 신고한 모든 내용을 취합하여 마지막에 한꺼번에 게시판 이용 정지를 시키면서 정지 메일을 발송합니다. 자기 자신을 신고하는 경우는 없습니다. 코드 function solution(id_list, report, k) { const.. 2022. 6. 23.
[JS] 2020카카오 : 수식 최대화 프로그래머스 LEVEL2 문제 링크 https://programmers.co.kr/learn/courses/30/lessons/67257 풀이 전략 단, 연산자의 우선순위를 새로 정의할 때, 같은 순위의 연산자는 없어야 합니다. 수식에 포함된 연산자가 2개라면 정의할 수 있는 연산자 우선순위 조합은 2! = 2가지이며, 연산자가 3개라면 3! = 6가지 조합이 가능합니다. 만약 계산된 결과가 음수라면 해당 숫자의 절댓값으로 변환하여 제출하며 제출한 숫자가 가장 큰 참가자를 우승자로 선정하며, 우승자가 제출한 숫자를 우승상금으로 지급하게 됩니다. "-56+100"처럼 피연산자가 음수인 수식도 입력으로 주어지지 않습니다. 같은 연산자끼리는 앞에 있는 것의 우선순위가 더 높습니다. 코드 function solution(expressi.. 2022. 6. 22.

티스토리툴바