알고리즘
-
투포인터TodayILearned 2022. 4. 22. 00:30
급 문제 풀다가 투포인터가 예전에도 헷갈렸던 기억에 구글링 해가면서 기억을 더듬어봤는데 전혀 기억이 안나..! 이래서 무슨 망각 곡선 이런게 있는거군. 정말 살에 와닿는 그래프다. 왜 구글링 페이지들이 다 초면인가 하니, 예전엔 파이썬 알고리즘 책으로 공부했었어서 더 생경하게 느껴지는지도. 투포인터를 치면 블로그에서는 보통 배열 내 요소들의 합에 대한 것을 예시로 들어서 그 예에만 한정된 문제인 줄 알았는데, 알고보니 투포인터는 그런 용도로만 사용되는 기법은 아니었다. 예를들어, 배열 내 요소들끼리 비교를 하려면 순차적으로 모든 요소들을 하나씩 비교해야 한다. 어쩌면 for문을 이중으로 돌려서 O(n^2)의 시간복잡도를 만들면서 문제를 풀이 할 수도 있다. 반면 투포인터를 이용하면 O(n)의 시간복잡도를..
-
[알고리즘] JS 조합, 순열 재귀함수 이해하기TodayILearned/알고리즘 2021. 8. 23. 03:18
순열과 조합, javascript 재귀함수 이해하기 완전탐색 문제풀이를 위해 조합과 순열을 공부했는데, 코드의 흐름이 이해가 잘 가지 않았다. 이전에 재귀함수를 학습할 때도 어렵다고 느꼈는데, forEach문까지 합쳐져서 더 헷갈렸던 것 같다. 재귀함수 + 반복문 어택으로 자꾸 스택의 흐름을 놓치게돼서 헷갈렸는데, 직접 그려보고, 디버거에 쌓이는 호출스택과 비교하면서 보니 코드가 이해되기 시작했다. 우선 조합과 순열에 대해서는 인터넷에 많은 자료가 있기 때문에 이 글에서는 최소한의 설명만 하고, 코드의 진행 방향에 대해서 설명하려고한다. 조합 const getCombinations = function (arr, selectNumber) { const results = []; if (selectNumber..
-
위장 해쉬로 풀기 자바스크립트TodayILearned/알고리즘 2021. 8. 16. 10:47
바로 전에 올린 '완주하지못한 선수' 2021.08.16 - [TodayILearned/알고리즘] - 완주하지 못한 선수 해쉬로 풀기 자바스크립트 와 비슷한 맥락의 문제이고, 다만 경우의 수가 합쳐져서 점화식 때문에 헷갈리게되는 문제이다. 또 문제가 대놓고 해쉬충돌이 있을테니 처리하라고 예고까지 해준다. (그 전 위장문제도 그랬음) function solution(clothes) { let key; const hashTable = {}; for (let i = 0; i < clothes.length; i++) { key = clothes[i][1]; if (!hashTable[key]) { hashTable[key] = 1; } else { hashTable[key] = hashTable[key] + 1..
-
완주하지 못한 선수 해쉬로 풀기 자바스크립트TodayILearned/알고리즘 2021. 8. 16. 10:41
해쉬문제니까 해쉬로 풀었다. 해당 문제를 이중 for문을 이용해서 푸는 방법도 있지만, 그렇게하면 시간복잡도가 n^2으로 늘어나기도하고 일단 그건 해시 풀이가 아니어서.. 어떤 주제로 문제가 주어지면 최대한 그 주제에 익숙해지기 위해서 해당 주제로 풀려고한다... function solution(participant, completion) { const HashTable = {}; let key; // Add : 해쉬충돌까지 고려했다. for (key of participant) { if (!HashTable[key]) { HashTable[key] = 1; } else { HashTable[key] = HashTable[key] + 1; } } // Search for (key of completion..
-
Intersection of Two Arrays II 자바스크립트TodayILearned/알고리즘 2021. 8. 16. 10:18
이번 알고리즘 스터디 때 이진탐색을 주제로 한 문제로 선정했다. 다만 풀면서 이렇게 푸는것 보다 해시로 푸는게 더 나았을 거라는 생각을 떨칠 수 없었다고... 그래도 이진탐색에 익숙해지려고 이진탐색을 적용해 풀었다. const intersect = function (nums1, nums2) { const answer = []; let sortedArray = nums1; let justArray = nums2; if (nums1.length > nums2.length) { sortedArray; justArray; } else { sortedArray = nums2; justArray = nums1; } sortedArray.sort((a, b) => a - b); for (let i = 0; i < j..
-
프로그래머스 최댓값과 최솟값TodayILearned/알고리즘 2021. 6. 14. 11:40
최댓값과 최솟값 난이도 : 하 문자열 코드 def solution(s): answer = '' a = s.split() lst = list(map(int,a)) m = max(lst) n = min(lst) answer = str(n) + ' ' + str(m) return answer 풀이 map, min과 max 내장함수를 이용했다. str을 형변환해서 int로 바꾸어 비교한 다음 다시 str로 변경하여 answer에 담았다.
-
프로그래머스 짝지어제거하기TodayILearned/알고리즘 2021. 6. 14. 01:23
짝지어 제거하기 종류 : 스택/큐 난이도 : 하 코드 def solution(s): answer = [] lst = list(s) for i in range(0,len(lst)): answer.append(lst[i]) while(len(answer) >= 2): if(answer[-1] == answer[-2]): answer.pop() answer.pop(-1) break if answer: return 0 else: return 1 return answer 풀이 주어진 문자열(s)를 list함수를 이용해 배열로 만든다. 배열의 길이만큼 answer에 문자를 하나씩 push(append)한다. 만약 answer의 길이가 2 이상이고, 문자열 두개를 비교했을 때 같다면, 순서대로 pop한다. 단 무한반..
-
[알고리즘] 1436 파이썬TodayILearned/알고리즘 2021. 3. 18. 20:20
주요개념: 브루트포스법 브루트포스법은 문자열 검색하는 방법 중 하나이다. 모든 문자열을 비교하여 조건에 부합하는 값을 도출하는것이 목표이다. 해당 문제에서는 최소 종말수인 666부터 시작하여 667,668,669..1666...2666....9666까지 비교한다 비교하면서 종말수의 조건에 부합하는 숫자를 찾는다. 몇번째 종말수인지 카운트한다. while True : > 특정조건을 만족할 경우(break 문에 걸리는 경우) 를 제외하고 무제한으로 실행된다. int형태로는 if~in 구문을 쓸 수 없기 때문에, str형태로 변환시켜준 후 진행한다. n = int(input()) count = 0 six_n = 666 while True: if '666' in str(six_n): # if in 은 strin..