문제 링크 Find Peak Element - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 문제 유형 이진 탐색 (Binary Search) 문제 풀이 이 문제는 완전 탐색을 통해 배열 내의 가장 큰 값을 찾고, 전/후 값을 비교해 peak elements인지 확인하는 방법이 있다. 이 경우, 시간 복잡도는 O(n)이다. 이 문제는 O(log n)의 시간복잡도를 갖도록 구현해야 하므로 이진 탐색을 이용하여 peak elements를 찾는다면 O(log n)의 ..
문제 링크 Sort Colors - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 문제 유형 정렬, 브루트 포스, in-place sort algorithm 문제 풀이 이 문제는 아래의 다양한 방식으로 접근할 수 있다. 정렬 메서드 sort() 사용하기 javascript 엔진 v8에서는 삽입 정렬과 병합 정렬을 합친 TimSort를 사용해 정렬 메서드를 구현한다고 한다. 따라서, sort() 메서드를 사용해 정렬을 하였을 때, O(nlogn)의 시간 복잡도를 ..
문제 링크 Minimum Size Subarray Sum - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 문제 유형 배열 (Array), 투 포인터 (Two Pointer) 문제 풀이 해당 문제는 배열 내의 어떤 부분 배열의 원소의 전체 합이 target값과 같거나 큰 부분 배열의 최소 길이를 출력해야 한다. 이는 투 포인터의 개념을 이용하여 해결하면 된다. 투 포인터는 1차원 배열을 순차적으로 접근할 때, 2개의 포인터를 사용하여 문제를 처리한다. 따라서, ..
문제 링크 Find Pivot Index - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 문제 유형 배열 (Array) 문제 풀이 처음에는 브루트 포스로 현재 피봇의 양옆의 값들의 합을 비교하는 방법이 떠올랐다. 그러나 이렇게 되면 양옆의 값을 더할 때 O(n)의 시간복잡도를 갖게 되고, 이것이 n개 만큼 반복되어 결국 O(n^2)의 시간복잡도를 갖게 되므로 다른 방법으로 접근해야 한다. 이 문제는 배열 접근 방법 중 하나인 sliding 기법을 사용하면 된다..
문제 링크 Move Zeroes - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 문제 유형 배열 (Array) 문제 풀이 이 문제는 0을 옮긴다고 생각하기 보다 0이 아닌 숫자를 옮기는 방식으로 접근하면 된다. 배열을 순회하면서 현재 요소가 0이 아닌 숫자이면 idx 인덱스의 0과 스왑하고 idx를 한칸 옮긴다. 코드 var moveZeroes = function(nums) { let idx = 0; // 요소의 값이 0인 인덱스를 저장한다. for (let ..
문제 링크 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 유형 조합 (Lv.2) 문제 풀이 orders course result ["ABCFG", "AC", "CDE", "ACDE", "BCFG", "ACDEH"] [2, 3, 4] ["AC", "ACDE", "BCFG", "CDE"] ["XYZ", "XWY", "WXA"] [2,3,4] ["WX", "XY"] 이 문제는 다음과 같은 방식으로 접근했다. 각 손님들이 주문한 단품메뉴 조합에서 코스요리를 구성할 단품메뉴의 수만큼 뽑아서 만든 조합을 만든다. 각 코스요리 후보 조합을 정렬한다. 테스트 케이..
문제 링크 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 문제 유형 DFS/ BFS 문제 풀이 공통) 각 정점과 연결된 정점의 번호를 2차원 배열 graph에 담는다. (정점이 여러 개인 경우에 정점 번호가 작은 것부터 먼저 방문해야하므로 연결된 정점의 번호를 오름차순으로 정렬했다.) [[], [2, 3, 4], [1, 4], [1, 4], [1, 2, 3], []] => 1번과 연결된 정점: 2, 3, 4 / 2번과 연결된 정점: 1, 4... stack, queue에..
문제 링크 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 문제 유형 다이나믹 프로그래밍 문제 풀이 반복문을 통해 (N - 2)층부터 0층까지 차례로 정수들을 방문한다. 현재 위치의 값 = (바로 아래층의 연결된 값중 최댓값) + (현재 위치의 값) 0층에 저장된 최대 경로에 있는 수의 합을 출력한다. 코드 const fs = require("fs"); const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt"; const input = fs.readFileSync(filePath).toString()...
