CS23 [알고리즘] Sliding Window Pattern 심화 sliding window pattern을 이해하기 위한 좋은 예제 function minSubArrayLenSol(nums, sum) { let total = 0; // 들어온 sum과 비교할 window 내 값들의 합을 담아줄 total let start = 0; // window의 시작 index let end = 0; // window의 끝 index let minLen = Infinity; // return 해 줄 가장 짧은 window 길이. 어떤 길이여도 가장 처음 길이가 min이 되도록 Infinity로 입력 while (start < nums.length) { // window가 nums array를 벗어날 때까지 if (total < sum && end < nums.length) { /.. 2022. 1. 16. [알고리즘] 문제해결패턴 지난 시간 문제 해결을 위한 일반적인 접근 방법에 관한 내용에 이어서 일반적인(general) 패턴에 관한 내용. 대표적으로 4가지를 이야기해 볼 수 있다. 1. Frequency counters Python에서 Counter 함수를 생각하면 된다. Python에서도 따로 내장함수로 만들어 뒀고, 강의에서도 일반적인 패턴으로 소개하는 것으로 보아 String 관련 문제에서 정말 많이 쓰이는 것 같다. String, Array 등 내의 각 element 개수를 세는데 이용하자. JavaScript 코드 function frequencyCounter(str) { let counterObject = {}; for (let val of str) { counterObject[val] = (counterObject.. 2022. 1. 15. [자료구조] 시간복잡도 문제 풀기 http://www.kyobobook.co.kr/product/detailViewKor.laf?mallGb=KOR&ejkGb=KOR&barcode=9788966263080 예제 12 void permutation(String str) { permutation(str, ""); } void permutation(String str, String prefix) { if (str.length() == 0) { System.out.println(prefix); } else { for (int i = 0; i < str.length(); i++) { String rem = str.substring(0, i) + str.substring(i + 1); permutation(rem, prefix + str.charA.. 2022. 1. 2. [Python|알고리즘] Sequential Search def seqsearch(n, S, x):#n은 list의 length-1(list의 최종 index는 길이보다 1이 작으므로), S list 안에 x가 존재하는지 확인하는 코드 location = 1#반환하는 주소는 컴퓨터 언어 말고 일상적인 숫자로 반환할 것임 while (location n: location = 0#x가 S list 안에 없으면 없다는 의미에서 위치는 0으로 반환 return location#위치 index 반환 나는 참 이렇게 지역변수를 통해서 지혜롭게 짜는 거에 약한 거 같다. 뭔가 나에게 저런식으로 location이라고 써있지 않고 그냥 a 이런식으로 자기 마음대로 쓴 코드들은 보면 '저걸 왜 넣었지?' 하면서 거기에 꽂혀서 뇌정지가 와버린다..ㅠㅠ 쓸데없어 보이는(?) 추가적.. 2021. 10. 16. [CS/알고리즘] 백트래킹/Backtracking 재귀 함수 너무 약하다.. BOJ 15649번, 지난번 itertools 때 permutations도 그렇고 구현을 못한다... 머릿 속에 그려지지 않는다랄까... 어떻게 공부해야할지 모르겠다. 강의들을 계속 보고 따라쳐볼까 DFS(Depth-First Search, 깊이우선탐색) 방식을 기반으로 불필요한 경우를 배제하며 원하는 해답에 도달할 때까지 탐색하는 전략이다. 이론 자체는 단순한데 구현하는게 참 쉽지가 않다. https://jamesu.dev/posts/2020/04/13/baekjoon-problem-solving-15649/ 백준 문제 풀이: 15649 - N과 M (1) Dev Blog by James Minsu Jeon jamesu.dev 이 블로그 글을 보면 잘 정리가 되어 있는 듯 한.. 2021. 10. 15. [CS/알고리즘] Recursion 조건 1 - 적어도 하나의 Base Case, 즉, 순환되지 않고 종료되는 Case가 있어야한다. 조건 2 - 모든 Case는 결국 Base Case로 수렴해야 한다. 암시적(implicit) 매개변수를 쓰지 말고 명시적(explicit) 매개변수를 써라 예를 들어 순환 함수를 사용할 수 있는데 함수 내에서 그냥 for문을 돌렸다고 치자 def func(n, data, target): ~~ for i in range(n): ~~ 이런 식으로 그런데 이때 data가 list인데 시작점이 어디인지 명시가 안되어 있다. 우리끼리 그냥 암시적(implicit)으로 index 0인 값부터 시작한다는 것을 알 뿐 그런데 recursion 함수를 짤 때는 def func_recur(start, end, data, t.. 2021. 10. 8. [CS/자료구조] ChainHash, maxLoadFactor(λ_max) 오늘 공부한 재밌는 개념 체이닝(Chaining) https://www.boostcourse.org/cs204/lecture/625974/?isDesc=false 자바로 구현하고 배우는 자료구조 부스트코스 무료 강의 www.boostcourse.org 우선 해쉬 테이블에 값에 따른 주소를 반환하기 위해서 1. Hashcode로 돌린다. 2. 나온 정수가 있다면(int a 가정) 양수로 바꿔준다 8바이트의 경우 -> a & ox7FFFFFFF 를 통해(index 값은 음수를 가질 수 없다) 3. %tablesize를 통해 나머지 반환해서 그것을 index로 지정! 하지만 같은 index 값이 나올 때 해쉬 충돌이 발생한다. +1, 제곱수 더하기, 이중 해쉬등의 해결 방법이 있지만 Chain hash를 이용.. 2021. 10. 8. [CS/자료구조] Array를 이용한 스택과 큐의 시간 복잡도 https://www.boostcourse.org/cs204/lecture/625951/?isDesc=false 자바로 구현하고 배우는 자료구조 부스트코스 무료 강의 www.boostcourse.org 배열(array)에서 스택과 큐를 구현할 때 시간 복잡도는 어떻게 될까? array를 통한 스택(Stack) 구현은 강의에서 만든 addLast, removeLast 메소드(맨뒤 추가, 맨뒤 삭제)를 이용하면 결국 둘 다 O(1)의 시간복잡도가 나와서 구현 가능하다. addFirst, removeFirst 조합으로 하면 각각 시간복잡도가 O(n)이기 때문에 절대 안된다. -> Array로 Stack 구현 가능! 하지만 큐(Queue)의 경우 addLast, removeFirst의 조합이나 addFirst,.. 2021. 10. 7. [CS/자료구조] 고려해야 할 경계조건 5가지 경계 조건 Boundary Conditions - Empty data structure - Single element in the data structure - Adding / removing beginning of data structure - Adding / removing end of the data structure - Working in the middle 어떤 자료 구조든 아래의 경계 조건에서 문제가 생기진 않을지 생각해봐야 합니다. 1. 자료 구조가 비어있는 경우 2. 자료 구조에 단 하나의 요소가 들어있을 때 3. 자료 구조의 첫 번째 요소를 제거하거나 추가할 때 4. 자료 구조의 마지막 요소를 제거하거나 추가할 때 5. 자료 구조의 중간 부분을 처리할 때 출처: https://www.bo.. 2021. 10. 6. [CS/알고리즘] 빅 오 표기법 여태 그냥 O(N), O(N^2)이런거만 알았지 O가 무슨 의미인지 몰랐는데 오늘 수업을 통해 알게 되었다. https://www.boostcourse.org/cs204 자바로 구현하고 배우는 자료구조 부스트코스 무료 강의 www.boostcourse.org 알고리즘 공부는 하고 싶고 어떤 강의를 들어야 좋을지 고민하던 중 부스트코스로 자바1을 다 듣고 자료구조 강의를 듣는 중이다. 빅 오 표기법에서는 알고리즘 간의 관계를 다음과 같이 표현 - O (빅 오 복잡도) : 비교 대상인 다른 알고리즘과 같거나 더 빠르다. - θ (세타 복잡도) : 비교 대상인 다른 알고리즘과 같다. - Ω (빅 오메가 복잡도) : 비교 대상인 다른 알고리즘과 같거나 느리다. - o (리틀 오 복잡도) : 비교 대상인 다른 알.. 2021. 10. 5. 이전 1 2 3 다음
