본문 바로가기

⌨️ Algorithm/Python13

[Algorithm] Week 7. 다이나믹 프로그래밍 다이나믹 프로그래밍 중복되는 연산을 줄이자 어떤 문제는 메모리 공간을 약간 더 사용하면 연산 속도를 비약적으로 증가시킬 수 있는 방법이 있음. 대표적인 방법이 다이나믹 프로그래밍 ex) 피보나치 수열 재귀함수를 통해 구현한 피보나치 수열 fibo(x) 함수에서 x가 커지면 수행 시간이 기하급수적으로 늘어남. 시간복잡도: O(2^n) def fibo(x): if x == 1 or x == 2: return 1 return fibo(x - 1) + fibo(x - 2) print(fibo(4)) ==> 이때 사용해야 할 방법? 다이나믹 프로그래밍 다이나믹 프로그래밍 조건 큰 문제를 작은 문제로 나눌 수 있다. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다. 메모이제이션(캐싱) 기법을 사용.. 2023. 2. 14.
[Algorithm] Week 6. 이진 탐색 범위를 반씩 좁혀가는 탐색 순차 탐색 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법 def sequential_search(n, target, array): for i in range(n): if array[i] == target: return i + 1; print("생성할 원소 개수를 입력한 다음 한칸 띄고 찾을 문자열을 입력하세요") input_data = input().split() n = int(input_data[0]) target = input_data[1] print("앞서 적은 원소 개수만큼 문자열을 입력하세요. 구분은 띄어쓰기 한 칸으로 합니다.") array = input().split() # 순차 탐색 수행 결과 출력 print(seq.. 2023. 2. 7.
[Python 문법] sum(), count(), map(), zip() 함수 정리 문법 정리 sum() sum(덧셈할 것, 처음에 더할 것) 만약 여기서 처음에 더할 것을 [ ] (빈 리스트) 로 준다면? (두번째 인자의 default값이 0이므로 만약 두번째 인자를 [ ] 로 주지 않으면 error발생함.) array = [[1, 2, 3], [4, 5, 6], [7, 8, 9], [10, 11, 12]] print(sum(array, [])) [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12] 즉 두번째 인자에 [ ] 를 줌으로써, 리스트 연산을 명확하게 알려주는 것! [ (두번째 인자) ] + [1, 2, 3] + [4, 5, 6] + [7, 8, 9] + [10, 11, 12] = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12] cou.. 2023. 2. 5.
[Algorithm] Week 5. 정렬 정렬 정렬? 데이터를 특정한 기준에 따라서 순서대로 나열하는 것. 선택 정렬 "가장 작은 것을 선택한다." ==> 선택 정렬! 데이터가 무작위로 여러 개 있을 때, 이 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그다음 작은 데이터를 선택하여 앞에서 두 번째 데이터와 바꾸는 과정을 반복하는 것. array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8] for i in range(len(array)): min_index = i for j in range(i + 1, len(array)): if array[min_index] > array[j]: min_index = j array[i], array[min_index] = array[min_index], array[i] # .. 2023. 1. 31.
[Algorithm] Week 4. DFS/BFS 알고리즘 스터디 코드와 규칙 정리: https://github.com/5jisoo/Algorithm-Study GitHub - 5jisoo/Algorithm-Study: [2023 Winter ~ ] Algorithm Study ✏️ 알고리즘 스터디를 위한 저장소입니다. [2023 Winter ~ ] Algorithm Study ✏️ 알고리즘 스터디를 위한 저장소입니다. - GitHub - 5jisoo/Algorithm-Study: [2023 Winter ~ ] Algorithm Study ✏️ 알고리즘 스터디를 위한 저장소입니다. github.com 교재: 이것이 취업을 위한 코딩 테스트다 with 파이썬 DFS/BFS 그래프 탐색을 위한 대표적인 알고리즘. 탐색: 많은 양의 데이터 중에서 원하는 데이.. 2023. 1. 24.
[Python] itertools 라이브러리 공식문서 참고하기: https://docs.python.org/ko/3/library/itertools.html#itertools.combinations itertools — Functions creating iterators for efficient looping This module implements a number of iterator building blocks inspired by constructs from APL, Haskell, and SML. Each has been recast in a form suitable for Python. The module standardizes a core set... docs.python.org itertools 효율적인 루핑을 위한 이터레이터를 만드는.. 2023. 1. 19.
[Algorithm] Week 3. 구현 알고리즘 스터디 코드와 규칙 정리: https://github.com/5jisoo/Algorithm-Study GitHub - 5jisoo/Algorithm-Study: [2023 Winter ~ ] Algorithm Study ✏️ 알고리즘 스터디를 위한 저장소입니다. [2023 Winter ~ ] Algorithm Study ✏️ 알고리즘 스터디를 위한 저장소입니다. - GitHub - 5jisoo/Algorithm-Study: [2023 Winter ~ ] Algorithm Study ✏️ 알고리즘 스터디를 위한 저장소입니다. github.com 교재: 이것이 취업을 위한 코딩 테스트다 with 파이썬 구현 피지컬로 승부하기 구현 = 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정 생각해낸 풀이과정.. 2023. 1. 17.