CS/알고리즘|자료구조12 스터디 발표 준비 - 단일연결리스트(Singly Linked List) 단일 연결 리스트 정의 단일 연결 리스트와 Array 비교 검색, 삽입, 제거, 순회 LinkedList 데이터를 저장하는 자료구조 index로 접근하는 array와 달리 LinkedList는 인덱스 없이 그냥 다수의 data element 즉, node로 구성 → 데이터에 접근할 index는 없기 때문에 첫번째 element부터 차례로 탐색 각각의 node는 문자열, 숫자와 같은 하나의 data element를 저장한다. + 다음 node를 가리키는 정보 역시 저장. 다음 노드가 없는 마지막 노드는 null을 가리킨다. 중간 node는 일일이 추적하지 않는다. head만 알고 있을 것이다. 구성 head → linked list의 시작 node tail → 마지막 node length → 작업 용이를 .. 2022. 3. 29. [알고리즘] 탐색 알고리즘 발표용 정리 검색 JS에서는 배열에 담긴 element를 조사하기 위한 다양한 방법이 있다. 그 중 하나가 indexOf를 이용한 검색 (없으면 -1 반환) 내장함수 원리에 대한 공부 어떻게 활용할 수 있을지 공부 목표 탐색 알고리즘(Searching Algorithm)은 무엇인가 배열에 대한 선형 탐색(linear search) 수행 정렬된 배열에 대한 이진 탐색(binary search) 수행 naive한 String 탐색 알고리즘 구현 KMP String 탐색 알고리즘이라 불리는 것 구현 선형 탐색(Linear Search) indexOf Array - arr.indexOf(searchElement[, fromIndex]) 배열에서 지정된 요소를 찾을 수 있는 첫 번째 인덱스를 반환하고 존재하지 않으면 -1을 .. 2022. 1. 29. [알고리즘] 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. 이전 1 2 다음
