반응형 [알고리즘] 5. 동적 계획법 Index 1. 다이나믹 프로그래밍 2. 추천문제 3. 참고자료1. 다이나믹 프로그래밍Dynamic Programming- 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법- 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않음- 점화식 : 인접한 항들 사이의 관계식- Memoization: 한 번 계산한 결과를 메모리 공간에 메모하는 기법(=Caching), - Top-down(메모이제이션) 방식과 Bottom-up 방식이 존재- Bottom-up 방식을 사용시 결과 저장용 리스트는 DP 테이블 이용- 분할 정복은 부분 문제의 중복이 없음 (조건)1) Optimal Substructure(최적 부분 구조)- 큰 문제를 작은 문제로 나눌 수 있으며 작은.. 2023. 10. 5. [알고리즘] 4. 그리디 && 구현 Index 1. 그리디 2. 구현 3. 추천 문제 4. 참고자료1. 그리디Greedy Algorithm- 현재 상황에서 지금 당장 좋은 것만 고르는 방법- 정당성 분석, 반복적 선택시 최적의해 보존되는지 검토 (Exam)- 거스름 돈: 가장 큰 동전의 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없음 2. 구현Implementation- 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정(problem->thinking->solution)- 2차원 공간을 다룰 경우 Matirx(행렬)을 사용- 시뮬레이션 및 완전 탐색의 경우 2차원 공간에서의 방향 벡터가 활용dx = [0, -1, 0, 1]dy = [1, 0, -1, 0]for i in range(4): nx =.. 2023. 10. 5. [알고리즘] 3. 정렬 Index 1. 정렬 2. 버블 정렬 3. 삽입 정렬 4. 선택 정렬 5. 퀵 정렬 6. 병합 정렬 7. 계수 정렬 8. 추천 문제 9. 참고자료1. 정렬정렬(Sort)- 데이터를 특정한 기준에 따라 순서대로 나열하는 것 2. 버블 정렬버블 정렬(Bubble Sort) def bubble_sort(arr: list): for i in range(len(arr)): for j in range(len(arr)-1): if (arr[j] > arr[j+1]: arr[j], arr[j+1] = arr[j+1], arr[j] return arr3. 삽입 정렬삽입 정렬(Insertion Sort)- 처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입- .. 2023. 10. 5. [알고리즘] 2. 코딩테스트를 위한 파이썬 라이브러리 Index 1. 내장 함수 2. itertools 3. heapq 4. bisect 5. collections/math 6. 참고자료1. 내장 함수 내장 함수- 기본 입출력 함수부터 정렬 함수까지 기본적인 함수들을 제공- sum(list), min(list), max(list), eval(문자열 수식), sorted(list, reverse=True, key=lambda x: x[1]) 2. itertoolsitertools- 반복되는 형태의 데이터를 처리하기 위한 기능 제공- 순열과 조합 기능 제공- 순열: 서로 다른 n개에서 서로 다른 r개를 선택하여 일렬로 나열하는 것- 조합: 서로 다른 n개에서 순서에 상관 없이 서로 다른 r개를 선택하는 것# 순열import itertools import pe.. 2023. 10. 5. [알고리즘] 1. 코딩테스트를 위한 파이썬 문법 및 환경설정 Index 1. 코딩 테스트 2. 환경설정 3. 기본 문법 4. 자료형 && 자료구조 5. 주의할 점 6. 참고자료1. 코딩 테스트코딩 테스트- 기업/기관에서 직원이나 연수생을 선발하기 위한 목적으로 시행 되는 시험- 문제 해결 역량을 평가 복잡도(Complexity)- 시간 복잡도: 특정한 크기의 입력에 대하여 알고리즘의 수행 시간 분석- 공간 복잡도: 특정한 크기의 입력에 대하여 알고리즘의 메모리 사용량 분석- 연산 횟수가 5억이상인 경우 Clang은 1~3초, Python은 5~15초 문제 해결 과정1. 지문 읽기 및 요구사항 분석2. 문제 해결 아이디어 찾기 3. 소스코드 설계 및 코딩 2. 환경설정VSCode- https://code.visualstudio.com/download Pyth.. 2023. 10. 5. 이전 1 ··· 4 5 6 7 다음 반응형
