알고리즘

동적 프로그래밍(Dynamic Programming) 주어진 문제를 여러 개의 하위 문제(subproblem)로 나누어 푼 다음, 그것을 결합하여 해결하는 알고리즘 특징 메모리 공간을 약간 더 사용하여 연삭 속도를 비약적으로 증가 하위문제들의 수가 기하급수적으로 늘어날 경우 유리한 알고리즘 문제조건 큰 문제를 작은 문제로 나눌 수 있다. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다. 메모라이제이션(Memorization)을 사용하여 작은 문제에서 구한 정답을 저장 동적 프로그래밍 vs 분할 정복 공통점 문제를 잘게 쪼게어 작은 단위로 분할 차이점 동적 프로그래밍 SubProblem는 중복되어 상위 문제 해결시 사용 Memorization 사용 상향식 접근(bottom up) 분할 정..

이번엔 이진탐색의 심화인 upper bound, lower bound에 대해 배워보겠습니다. 이진탐색에 대하여 정확히 알고싶으신 분, 결정값에 모르시는 분, 리턴 값에 lo를 쓰는 지에 대하여 모르시는 분에게 적합할 것 같습니다. 이진 탐색의 기본 원리는 다음과 같습니다. - L[mid] == target ▶ return mid - L[mid] target ▶ lo = mid +1 하지만 이것만으로 이진탐색 문제들을 풀 수 없습니다. Lower bound와 Upper bound에 대하여 알아 보겠습니다. lo는 가능한 값들 중 최소값, hi는 가능한 값들 중 최대값을 의미합니다. Lower bound 해당 값 이상의 값이 처음 나오는 인덱스 ..

이진 탐색에 들어가기 앞서, 순차 탐색과 무엇이 다른지 확인해보겠습니다. 순차 탐색(Sequential Search) 출처 : https://velog.io/@yujo/JS%EC%84%A0%ED%98%95-%ED%83%90%EC%83%89Linear-Search 특징 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법 데이터가 정렬되어 있지 않아도 사용 가능 최악의 경우 시간복잡도 O(N) 코드 def sequential_search(n,target,arr): for i in range(n): if arr[i] == target: return i +1 print('생성할 원소 개수를 입력한 뒤 찾을 문자열 입력') n, target = input().split(..

정렬이란? 데이터를 특정한 기준에 따라서 순서대로 나열하는 것 정렬을 통하여 이진 탐색(Binary Search) 가능 정렬 알고리즘 종류 : 선택 정렬, 삽입 정렬, 퀵 정렬, 계수 정렬 선택 정렬(Selection Sort) 선택 정렬 가장 작은 데이터를 선택해 맨 앞의 데이터와 바꾸고, 그다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정 시간 복잡도 - O(n^2) 코드 arr = [7,5,9,0,3,1,6,2,4,8] for i in range(len(array)): min_idx = i if arr[min_idx] > arr[i]: min_idx= i arr[i], arr[min_idx] = arr[min_idx], arr[i] print(arr) 삽입 정렬(Insertion So..

탐색 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정 그래프, 트리 등의 자료구조 안에서 탐색을 하는 문제를 자주 다룸 대표적인 알고리즘 - DFS(깊이우선 탐색),BFS(너비우선 탐색) 자료구조란? 데이터를 표현하고 관리하고 처리하기 위한 구조 대표적인 자료구조인 스택과 큐는 다음 두 핵심 함수로 구성됨 삽입(Push) : 데이터를 삽입한다. 삭제(Pop) : 데이터를 삭제한다. 스택(Stack) FILO, LIFO 구조 append() : 리스트의 가장 뒤쪽에 데이터 삽입 pop() : 리스트의 가장 뒤쪽에서 데이터 꺼냄 큐(Queue) FIFO 구조 collections 모듈에서 제공하는 deque 자료구조 활용 append() : 데큐의 가장 뒤쪽에 데이터 삽입 popleft() : 데큐의 가..

구현 머릿속의 알고리즘 -> 소스코드 유형 완전탐색(브루트 포스) - 모든 경우의 수 계산 시뮬레이션 - 문제에서 제시한 알고리즘 차례대로 수행 메모리 사용량 데이터의 개수 메모리 사용량 1,000 약 4KB 1,000,000 약 4MB 10,000,000 약 40MB 수행시간 1초당 연산량 Python 3 20,000,000 pypy 3 100,000,000 체크리스트 어떤 알고리즘을 채택했는가? 완전탐색(브루트 포스) 시뮬레이션 알고리즘을 어떻게 구현하였는가? 백준 문제 3190번- 뱀 시뮬레이션을 이용하여 구현 뱀의 머리가 갈 위치에 보드의 끝이거나 뱀의 몸통이 있는지 확인 사과에 도착할 경우 사과 집합에서 제거 if (nx,ny) in apples: d_set= set() d_set.add((nx..

# 그리디 개념 그리디(greedy) : 탐욕 ## 현재 상황에서 가장 좋은것만 고르는 것 - 매 순간 가장 좋아 보이는 것 선택 ex) 거스름돈 - 가장 큰 화폐단위부터 거스르기 ## 해당 해법이 정당한지 검토 ex) 거스름돈 - 큰 단위의 동전은 작은 단위의 배수이므로 다른 해가 나올 수 없음 ### 체크리스트 - [X] 현재 상황에서 가장 좋은 것만 고르는가? - [X] 해당 해법이 정당한가? 출처 HTML 삽입 미리보기할 수 없는 소스