알고리즘/programmers(46)
-
[JS] 2 x n 타일링 - 이거 왜 피보나치인지 알려드림!
일단 제목부터 스포인데요.사실 이번 문제는 코드가 중요하지 않습니다.어떻게 거기까지 생각이 미치냐가 더 중요한 것 같아요.자 같이 한번 생각해보죠! 문제 요약 직사각형의 가로의 길이 n이 매개변수로 주어질 때, 이 직사각형을 채우는 방법의 수를 return 하는 solution 함수를 완성해주세요. 제한사항 가로의 길이 n은 60,000이하의 자연수 입니다. 경우의 수가 많아 질 수 있으므로, 경우의 수를 1,000,000,007으로 나눈 나머지를 return해주세요. 정답 코드 function solution(n) { const memo = [1, 2, ...Array(n - 1).fill(0)]; for (let i = 2; i < n; i++) { memo[i] = (memo[i - 1] + mem..
2022.07.23 -
[JS] 배달
그래프 문제입니다. 간선 별로 가중치가 다르게 설계되어있네요. 최솟값을 묻는 문제이니, 우리 많이 당해봤잖아요? 그쵸? BFS를 써서 문제를 풀어봅시다! 문제 요약 N은 마을의 수, K는 배달까지 걸리는 최대 시간입니다. 1번 마을에서 출발해서 K 시간 이하로 갈 수 있는 모든 마을의 수를 return해주세요! 입출력 예 N road K result 5 [[1,2,1],[2,3,3],[5,2,2],[1,4,2],[5,3,1],[5,4,2]] 3 4 6 [[1,2,1],[1,3,2],[2,3,2],[3,4,3],[3,5,2],[3,5,3],[5,6,1]] 4 4 접근 방법 일단 BFS를 설계하기 위해서는 큐를 만들어줘야합니다. 이번 문제에서는 간선의 방향이 중요하지 않습니다. 만약 1번 마을에서 시작하는 ..
2022.07.22 -
[JS] 괄호 회전하기
큐 문제입니다. 큐 안에 커스텀 함수 하나만 만들어주면 인생 편해지더라구요. 같이 풀어보시죠! 문제 요약 대괄호, 중괄호, 그리고 소괄호로 이루어진 문자열 s가 매개변수로 주어집니다. 이 s를 왼쪽으로 x (0 ≤ x < (s의 길이)) 칸만큼 회전시켰을 때 s가 올바른 괄호 문자열이 되게 하는 x의 개수를 return 하도록 solution 함수를 완성해주세요. s length "[](){}" 3 "}]()[{" 2 "[)(]" 0 "}}}" 0 접근법 위에 설명한 대로 큐를 이용해볼 겁니다. 일단 s 요소 그대로 큐에 다 넣어줍니다. 반복문 안에서 일단 다 올바른 괄호인지 체크해주고, dequeue한 값을 다시 enqueue 해주면 되겠군요. 다 올바른 괄호인지 체크해주는 부분이 핵심로직입니다. 정답..
2022.07.21 -
[JS] 후보키 - every를 아시나요?
안녕하세요. 오늘 다뤄볼껀 2019 카카오 블라인드 채용 기출문제인 후보키입니다. 카카오 문제는 역시 장황하네요. 자 다들 잘 푸셨나요? 같이 한번 보죠 문제 요약 아래와 같은 학생들의 인적사항이 주어졌을 때, 후보 키의 최대 개수를 구하라. 유일성과 최소성을 만족하는 키를 모두 구하시오. relation result [["100","ryan","music","2"],["200","apeach","math","2"],["300","tube","computer","3"],["400","con","computer","4"],["500","muzi","music","3"],["600","apeach","music","2"]] 2 접근방법 일단 입력이 2중 배열로 되어있네요. 사실 어떤 칼럼을 키로 정했다면 나..
2022.07.20 -
[JS] 게임맵 최단거리 - 미뤄뒀던 BFS에 대해
이 문제는 정말 정석적인 재귀함수 문제입니다. 뭔가 계속 관성적으로 dfs를 쓰다보니 (사실 bfs는 큐를 사용하기 때문에 생각하기 싫은 것도 있었어요.) 효율성 테스트가 통과가 안되더라구요. 일단 같이 한번 풀어봐요! 문제 요약 게임을 하려고 합니다. [0, 0]에서 좌표의 끝지점까지 가는 최소 거리를 구해주세요! 문제 해석 전 처음에 dfs를 사용했습니다. 항상 dfs 사용할 때 return 값때문에 뭔가 잘 생각이 팍 안나는 편인데 다른 분들 코드에서 영감을 얻어서 solution 함수 안에 구현해줬는데요. 일단 dfs 코드 먼저 보시죠. 정답 코드(DFS) function check (row, col, maxRow, maxCol) { if (row < 0 || col < 0 || row === m..
2022.07.19 -
[JS] 소수찾기 - 부제: 이거 외되.......? (진짜 모름)
여러분들 정말 자바스크립트의 기묘한 걸 찾아냈습니다. 혹시 왜이런지 아시는 분 있으면 알려주시면 너무 좋을 것 같아요. 오늘 풀어볼 문제는 프로그래머스 Level 2의 소수 찾기 입니다. 일단 같이 한번 볼까요? 문제 요약 numbers return "17" 3 "011" 2 한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다. 각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요. 제한사항 numbers는 길이 1 이상 7 이하인 문자열입니다. numbers는 0~9까지 숫자만으로 이루어져 있습니다. "013"은 0,..
2022.07.18