알고리즘 (54) 썸네일형 리스트형 2020 KAKAO BLIND RECUITMENT 괄호 변환 이 문제에 적힌 그대로 구현하는게 중요하다. 간단한 조건도 잘 체크하자. 먼저 '(', ')'로만 이루어진 문자열이 있을 경우 '('의 개수와 ')'의 개수가 같으면 이를 균형잡힌 괄호 문자열이라 한다. 그러면 일단 여기서 체크할 부분은 빈 문자열은 균형잡힌 괄호 문자열이 아니다. 균형잡힌 괄호 문자열을 판별하는 함수를 작성해보자. 함수 이름은 checkIsBalancedString이 좋은 것 같다. 만약 균형잡힌 문자열이라면 true, 아니라면 false를 반환한다. function checkIsBalancedString(s) { if (s === "") return false // 빈 문자열은 균형잡힌 문자열이 아니다. let left = 0 // 왼쪽 괄호의 개수 let right = 0 // 오른.. JavaScript Data Structure And Algorithm | 재귀 재귀 소개 수학과 언어학, 예술에서 재귀는 자신에 대해 정의한 것이 발생하는 것을 나타낸다. 컴퓨터 과학 분야에서는 재귀함수는 자기 자신을 호출하는 함수이다. 재귀 함수는 '분할 정복' 방식을 통해 복잡한 문제를 해결한다. 재귀의 규칙 재귀함수를 잘못 작성하는 경우 심각한 문제를 일으킨다. 프로그램이 어느 한곳에 빠져서 종료되지 않기 때문이다. 무한 재귀 호출은 스택 오버플로(stack overflow)를 초래한다. 스택 오버플로는 프로그램의 콜 스택 개수가 제한된 양의 주소 공간(메모리)을 초과할 때를 나타낸다. 재귀 함수를 올바르게 구현하기 위해서는 스택 오버플로를 피하기 위한 특정 규칙을 따라야 한다. 기저 조건 재귀에는 기저 조건(종료 조건)이 존재한다. 재귀 메소드는 자기 자신을 호출하기 때문에.. LeetCode 787. Cheapest Flights Within K Stops 먼저 Map을 사용하여 인접리스트를 만들어줍니다. 인접리스트를 잘 채워준 이후에 큐를 선언하고 출발지부터 넣어줍니다. while 문을 돌면서 queue를 거리순으로 정렬하고 가장 거리가 가까운 것 부터 방문해나갑니다. 방문했던 곳에서는 방문했던 곳에서부터 더 방문할 수 있는 수를 확인해서 현재 방문할 수 있는 개수 - 1 보다 더 많이 방문할 수 있다면 continue를 해줍니다. 모든 간선을 사용하거나 도착지에 도착하면 while 문이 종료됩니다. const findCheapestPrice = function(_, flights, src, dst, K) { const adjacencyList = new Map(); for(const [start, end, cost] of flights) { if(adj.. LeetCode 93. Restore IP Addresses IP 주소로 가능한 모든 경우의 수를 구해야 한다. -> 백트래킹 일단 길이가 4보다 작거나 12보다 크면 IP 주소를 만들수조차 없으므로 빈 배열을 반환하게 했다. 또한 조건에서 string에 속할 수 있는 것은 숫자뿐이므로 문자열 -> 숫자 변환은 parseInt(x) 또는 Number(x)를 이용한다. backtracking 함수에서 탈출조건은 배열의 현재 길이가 4일 때 join으로 합쳐서 정답 배열에 푸쉬한 후 탈출하기로 했다. 또한 탈출조건으로 현재 배열이 3개이고 남은 문자열의 길이가 3이상이라면 적절한 IP 주소를 만들 수 없으므로 제거하는 베이스케이스를 추가했다. 그 후에는 전형적인 백트래킹을 활용했다. 풀이는 아래와 같다. const restoreIpAddresses = (s) => {.. Leetcode 45. Jump Game II a처음에는 재귀를 이용한 완전 탐색으로 접근했다. /** * @param {number[]} nums * @return {number} */ const jump = function(nums) { const endIndex = nums.length - 1 let ans = Infinity function travel(position, count) { if (position > endIndex) { return } if (position === endIndex) { ans = Math.min(ans, count) return } const jumpRange = nums[position] for (let i = 1; i = nums.length - 1) return 0 if (memo[idx]) return .. 43. Multiply Strings 문제를 읽고 생각을 별로 안하고 답을 내면 아래와 같은 답을 제출한다. const multiply = function(num1, num2) { return String(parseInt(num1) * parseInt(num2)) }; 이렇게 내면 무조건 틀리는데 이유는 정말 큰 수를 곱하면 overflow가 나기 때문이다. 따라서 배열에 저장하면서 "잘" 곱해줘야한다. 잘 곱해준다는 의미는 아래와 같이 배열에 저장하면서 곱하는 것을 의미한다. const multiply = function(num1, num2) { if (num1 === "0" || num2 === "0") return "0" // 0이면 무조건 0리턴 const n = num1.length, m = num2.length // 배열 길이 저.. 2022 KAKAO TECH INTERNSHIP | 코딩 테스트 공부 문제를 읽으면서 그리디 알고리즘의 냄새가 났다. 주어진 모든 문제들을 풀 수 있는 알고력과 코딩력을 얻는 최단 시간을 구하는 문제이다. 해결해야하는 문제는 (초기 알고력, 초기 코딩력) 상태에서 시작해 (목표 알고력, 목표 코딩력) 상태에 도달하는 최단시간을 구하는 문제이다. 이때, 목표 알고력을 넘는 알고력이나 목표 코딩력을 넘는 코딩력은 구현 방법에 따라 시간초과나 세그먼트 폴트와 같이 예상치 못한 런타임 오류를 일으킬 수 있다고 한다.(해설) 이 문제는 2차원 동적계획법 DP로 풀이가 가능하다. DP를 아래와 같이 정의한다. dp[i[j]: 알고력 i , 코딩력 j 상태에 도달하는데 필요한 최단 시간 이렇게 DP배열을 정의하면 문제에서 요구하는 답은 dp[목표 알고력][목표 코딩력]이다. dp[초기.. 2022 KAKAO TECH INTERNSHIP | 두 큐 합 같게 만들기 문제는 두 큐가 주어졌을 때 enqueue, dequeue 연산만으로 두 큐의 합이 정확히 반씩 나눠지도록 연산을 수행하는 것인데, 최소로 수행해야한다고 한다. queue1의 합을 L, queue2의 합을 R이라고 했을 때, L과 R을 같게 만들기 위해서는 탐욕법을 사용하여 해결 할 수 있다. - L > R 이라면, q1의 원소를 q2으로 넘긴다. - L R인 상황에서 먼저 L을 증가시키고 R을 감소시키는 방법이 최적인 경우가 있다고 가정해보자. 이 경우 L = R을 만들기 위해서 언젠가 L을 감소시키고 R을 증가시켜야 하고 결국 q1의 원소를 q2로 넘겨주는 동작은 반드시 필요하다. 이 때 직접 큐 자료구조를 사용하지 않고 단순히 배열을 큐로 사용.. 이전 1 2 3 4 ··· 7 다음
