자료구조-알고리즘
1.자료구조,알고리즘 시리즈 시작
https://www.algodale.com/data-structures/코테준비를 어떻게 하면 좋을까 항상 막막하다. 그리고 루틴하게 가져가지 않으면 항상 어디까지 진행했지 하고 그냥 무작위로 풀게되는데, 알고달레라는 사이트에서 알고리즘, 자료구조를 보기좋게
2.[재귀][leetcode]39.combination sum
알고리즘재귀유형조합문제candidates = 서로다른 정수들target = 타겟 정수return = 더해서 타겟정수가 나오는 모든 유니크한 candidate 조합.예제문제풀이이 문제는 nCr의 n과 r이 정해져있지 않는 조합이다. 보통의 조합이라면n개의 요소에서 r개를
3.[재귀]JavaScript로 순열과 조합 구현하기 (재귀 + 백트래킹)
프론트엔드 개발을 하다 보면, 순열(Permutation)과 조합(Combination)을 다뤄야 할 일이 종종 있습니다. 면접 준비나 알고리즘 문제 해결에 특히 자주 등장하죠. 이 글에서는 조합과 순열의 개념 차이부터, JavaScript로 재귀 + 백트래킹을 활용한 구현 방법까지 정리해보겠습니다. 조합 (Combination) > 서로 다른 n...
4.[leetcode]Product of Array Except Self
nums 배열answer 배열answeri가 모든 num요소들의 numsi를 제외한 모든 값의 곱이 들어간다.모두 32비트정수에 맞는다. (int 범위에 맞다는 뜻인거같다.)풀고보니 나눗셈이 안된다..왜냐면 0이 있는 경우도 있다.올바른 방법은 왼쪽 곱, 오른쪽 곱을
5.[leetcode]Top K Frequent Elements
https://leetcode.com/problems/top-k-frequent-elements/코드를 좀더 다듬어 보자면...freqMap.entries() 를 이용해서 Array.from을 대체할수있다. 빈도수 세기 (for 루프 + Map)→ O(n)Ma
6.[leetcode]198. House Robber
7.[leetcode]128. Longest Consecutive Sequence
이것도 최적의 알고리즘을 사용해야한다. 우선 처음 푼 방법은 시간복잡도:2중for문+sortn^2 + nlogn => n^2. 공간복잡도:nums는 초기화했고, 기타 변수들만 사용을 했다(maxCount,current,count)=> O(1)하지만 이문제는 O(n)의
8.[leetcode]15. 3Sum
문제배열안의 요소 중 모두 더했을때 0이되는 3개 요소의 조합을 구하기.중복되는 조합이면 안된다. 이 때 중복은 index의 중복을 말하는 듯.https://leetcode.com/problems/3sum/submissions/1677996513/
9.[leetcode]70. Climbing Stairs
공간복잡도 O(1)시간복잡도 2^ndp 활용공간복잡도 O(n)시간복잡도 O(n)슬라이딩 윈도우 기법공간복잡도 O(1)시간복잡도 O(n)
10.[leetcode]98. Validate Binary Search Tree
이 문제는, BST로 탐색이 가능한지를 판별하는 문제이다. 유효한 BST는 이렇게 정의가 된다. 1\. 노드의 좌측 서브 트리에는 노드의 키보다 작은 키를 가진 노드만 있다. 2\. 노드의 우측 서브 트리에는 노드의 키보다 큰 키를 가진 노드만 있다. 3\. 좌 우측
11.[leetcode]53. Maximum Subarray
문제링크: https://leetcode.com/problems/maximum-subarray/연속된 부분 배열 중 합이 가장 큰 것을 찾는 문제. 매 순간 현재 위치까지의 최대 부분합을 유지하면서 전체 최대값을 업데이트 해 나가는 방식.카데인 알고리즘 (Ka
12.[leetcode]191. Number of 1 Bits
문제:n이 주어졌을 때, 2진법으로 표현했을 때, 1의 개수를 리턴하기. 2진법을 구할때, 나머지가 1일때마다 count++ 해주고, 마지막에 2나 1이 남으면 count ++ 하고 break 해주면 된다.시간복잡도 O(n)공간복잡도 O(1)
13.[leetcode] 39. Combination Sum
여기서 문제가 생겼다. 중복이 생긴다는 것이다. 어떻게 중복을 제거하면 좋을까?Set을 이용한다.순서를 둔다. idx를 dfs에 넘겨주어서, 순서대로 작동하게 한다. 내가 선택한 방법은 idx까지 넘겨 순서가 있게 작동하는 방법이다. 시간복잡도: O(N^(targe
14.[leetcode]91. Decode Ways
은선님, 알겠어요. 딱 핵심만 간결하게 쓰는 블로그 글 초안 만들어드릴게요.문자열이 주어졌을 때, 각 숫자를 알파벳(A=1, B=2, … Z=26)으로 디코딩할 수 있는 경우의 수를 구하는 문제다.1글자씩 혹은 2글자씩 끊어 디코딩 가능하다.'0'은 단독으로 디코딩 불
15.[leetcode]322. Coin Change
이 문제는, 모든 금액의 총합을 도달하기 까지 소요되는 가장 적은 개수의 동전 수를 구하는 문제이다. https://leetcode.com/problems/coin-change/
16.[leetcode]79. Word Search
https://leetcode.com/problems/word-search/description/m\*n 그리드 스타일의 보드가 주어지고word가 주어지면만약 그리드에 word가 있으면 true를 반환해라. 근접한 셀을 순서대로 구조화하여 단어가 만들어질 수
17.[leetcode]153. Find Minimum in Rotated Sorted Array
https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/description/\~~문제 파악이 조금 어려운 문제이다. 내가 파악한 대로면A ir = (A i(r-1) + 1)%(length+1)이
18.[leetcode]21. Merge Two Sorted Lists
두개의 정렬된 링크드 리스트 list1, list2를 받았을 때, 두개의 리스트를 하나의 정렬된 리스트로 반환하기. splicing을 통해서 만들어져야한다. 이게 무슨말이지? 싶다면 연결리스트를 배워야한다. https://www.algodale.com/data-stru
19.[leetcode]70. Climbing Stairs
특정 지점까지 얼마나 많은 개수의 길이 존재할까갈 수 있는 방법은 1 혹은 2칸씩 오를 수 있다. dp로 풀기. 점화식은 이렇다. dpn = dn-1 + dn-2시간복잡도: O(n)공간복잡도: O(n)메모리 아끼기dp배열 없이 변수로만 작성하기시간복잡도: O(n)공간복
20.[leetcode]49. Group Anagrams
https://leetcode.com/problems/group-anagrams/description/시간복잡도 : O(n \* klogk) 공간복잡도 :O(n · k)2.문자 빈도수 기반 키 만들기 알파벳이 26뿐이므로 각 단어마다 알파벳 개수를 세서 카운
21.[leetcode]208. Implement Trie (Prefix Tree)
https://leetcode.com/problems/implement-trie-prefix-tree/submissions/1717889324/트라이 클래스를 구현해보는 문제이다. 트라이에 대한 설명은 알고달레에서 참고했다. https://www.al
22.[leetcode] 139. Word Break
내가 풀어보고싶은데 또 안풀린다. 결국 백트레킹인가?만약 현재까지 초기화한 word에 대해서 dict에 존재한다면뭔가에 true를 저장을 한다. 근데 현재까지 진행하고나서, 그 뒤에 dict에 존재하는 것이 없다면?그땐 어떻게 해야할까. 일단, true라고 표시했던 지