코딩테스트8 220121 LeetCode - Palidrome 풀이 (JS) LeetCode 풀이 Palidrome (Easy) /** * @param {number} x * @return {boolean} */ const isPalindrome = function(x) { const reversed = String(x).split('').reverse().join('') const regex = new RegExp(reversed, 'g') return regex.test(x) } Palidrome Linked List (Medium) head 가 조건이 있는 연결리스트로 구현되어있어 일단 연결리스트부터 코드로 작성하였다. 직접 작성한 답안 /** * @param {ListNode} head * @return {boolean} */ var isPalindrome = functi.. 2022. 1. 21. 220120 LeetCode - Two Sums 풀이 (JS) LeetCode 풀이 Two Sums (Easy) 코테준비를 위해 풀이를 시작했다. 프로그래머스를 선택하지 않은 이유는, 나름 코딩테스트 초급수준인데 level2 부터는 구현하기 꽤 어려웠기 때문이다. /** * @param {number[]} nums * @param {number} target * @return {number[]} */ var twoSum = function(nums, target) { let test = [] const queue = [...nums] let firstIdx = 0 while (queue.length > 1) { for (let i = firstIdx; i < nums.length; i++) { if (i === firstIdx) continue // console... 2022. 1. 20. 220109 최단 경로 알고리즘 개념 최단 경로 알고리즘 개념 가장 빠른 길찾기 최단 경로 Shortest path 알고리즘은 말 그대로 가장 짧은 경로를 찾는 알고리즘이다. 그래서 "길 찾기" 문제 라고도 한다. 최단 경로 알고리즘 유형에는 다양한 종류가 있는데, 상황에 맞는 효율적인 알고리즘이 이미 정립되어있다. '한 지점에서 다른 특정 지점까지의 최단 경로를 구해야 하는 경우', '모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우' 등이 다양한 사례가 존재한다. 이런 사례에 맞는 알고리즘을 알고있다면 문제를 좀 더 쉽게 풀 수 있다. 최단 경로 문제는 보통 그래프를 이용해 표현하는데, 각 지점은 그래프에서 '노드'*로 표현되고, 지점간 연결된 *도로는 '간선' 으로 표현된다. 또한 실제 코딩 테스트에서는 최단 경로.. 2022. 1. 16. 211227 다이나믹 프로그래밍 다이나믹 프로그래밍 피보나치 수열 피보나치 수열 구하는 과정 메모이제이션 (Memoization) 기법 결론 다이나믹 프로그래밍 한 번 계산한 문제는 다시 계산하지 않도록 하는 알고리즘 중복되는 연산 줄이기 프로그래밍에서 다이나믹 이란, '프로그램이 실행되는 도중에' 라는 의미이다. 자료구조에서 동적 할당(Dynamic Allocation) 은 프로그램 실행 중에 프로그램 실행에 필요한 메모리를 할당하는 기법이다. 그러나 '다이나믹 프로그램' 에서는 이런 의미는 아니라는 것을 기억하자. 피보나치 수열 이전 두 항의 합을 현재의 항으로 설정하는 특징이 있는 수열 $n$ 번째 피보나치 수 = $(n - 1)$ 번째 피보나치 수 + $(n - 2)$ 번째 피보나치 수 단, 1 번째.. 2022. 1. 16. 211110 구현 개념 구현 개념 구현시 고려해야할 메모리 제약 사항 리스트의 크기 제약 채점 환경 구현 문제에 접근하는 방법 예시 문제 구현 개념 코딩 테스트에서 구현Implementation 이란 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정이다. 구현 문제 유형은 모든 범위의 코딩 테스트 문제 유형을 포함하는 개념이다. 그러므로 알고리즘 교재에서는 대부분 구현을 별도의 유형으로 다루지 않는다. 우리는 알고리즘 문제를 해결할 때, 문제를 읽고 문제풀이 방법을 고민한다. 고민 끝에 문제에 대한 정확한 풀이 방법을 우리가 원하는 프로그래밍 언어로 정확히 구현했을 때 비로소 정답 처리를 받을 수 있다. 이를 위해 프로그래밍 언어의 문법을 정확히 알고 있어야 하며, 문제의 요구사항에 어긋나지 않는 답안 코드를 실수 없이 작성해야.. 2022. 1. 16. 211203 그리디 알고리즘 그리디 탐욕법. 단순하지만 강력한 문제 해결 방법 현재 상황에서 지금 당장 좋은 것만 고르는 방법 그리디 알고리즘은 매 순간 가장 좋아보이는 것만 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다. 그리디 알고리즘 문제는 출제의 폭이 매우 넓기 때문에, 많은 유형을 풀어보며 훈련을 해야한다. 특정 알고리즘 (다익스트라) 같은 특이 케이스를 제외하고는 단순 암기를 통해 모든 문제를 대처하기 어렵다는 점을 이해해야한다. 보통 코딩 테스트에서 출제되는 그리디 알고리즘 유형의 문제는 창의력, 즉 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구한다. 다시말해 특정한 문제를 만났을 때 단순히 현재 상황에서 가장 좋아보이는 것만 선택해도 문제를 풀 수 있는지를 파악할 수 있어야한.. 2021. 12. 3. 211202 DFS, BFS 개념 그래프 인접 행렬 (Adjacency Matrix) 방식 인접 리스트 (Adjacency List) 방식 두 방식의 차이점 DFS (깊이 우선 탐색: Depth-First Search) DFS 의 동작 과정 DFS 예제 BFS (너비 우선 탐색: Breath First Search) DFS 의 동작 과정 BFS 예제 결론 그래프 그래프를 탐색하기 위한 대표적인 두 가지 알고리즘 노드(Node)(정점(Vertex) 이라고도 부른다) 와 간선(Edge) 로 이루어진 자료구조 그래프 탐색이란, 하나의 노드를 시작으로 다수의 노드를 방문하는 것을 말한다. 두 노드가 간선으로 연결되어있다면 '두 노드는 인접하다(Adjacent)' 라고 표현한다. 프로그래밍에서 그래프는 크게 2가지 방식으로 표현할 .. 2021. 12. 2. Leetcode solution 해답 시리즈 dev.to/seanpgallivan/series/11116 About DEV — DEV Community About DEV (dev.to) dev.to 2021. 3. 15. 이전 1 다음
