반응형 [알고리즘] 7. 그래프 탐색 Index 1. 스택과 큐 2. 재귀 3. 유클리드 호제법 4. DFS 5. BFS 6. 추천 문제 7. 참고자료- Search란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정- 그래프 탐색 알고리즘으로 DFS/BFS가 있음 1. 스택과 큐Stack- FILO(First In Last Out)의 자료구조- 입구와 출구가 동일stack = []# 삽입stack.append(val)# 삭제stack.pop()# 최상단 원소 확인print(stack[-1])Queue- FIFO(First In First Out)의 자료구조- 입구와 출구가 양쪽으로 나있는 터널 형태queue = []# 삽입queue.append(val)# 삭제queue.pop(0)# 최하단/최상단 원소 확인queue[0]queue[-1.. 2024. 7. 19. [알고리즘] 6. 이진 탐색 Index 1. 순차 탐색 2. 이진 탐색 3. 이진 탐색 라이브러리 4. 파라메트릭 서치 5. 추천 문제 6. 참고자료1. 순차 탐색순차 탐색(Sequential Search)- 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법 2. 이진 탐색이진 탐색(Binary Search)- 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법- O(log N) (재귀적 구현)def binary_search(arr, target, start, end): if start > end: return None mid = (start + end) // 2 if arr[mid] == target: return mid elif arr[mid] > target: re.. 2024. 7. 19. [알고리즘] 5. 동적 계획법 Index 1. 다이나믹 프로그래밍 2. 추천문제 3. 참고자료1. 다이나믹 프로그래밍Dynamic Programming- 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법- 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않음- 점화식 : 인접한 항들 사이의 관계식- Memoization: 한 번 계산한 결과를 메모리 공간에 메모하는 기법(=Caching), - Top-down(메모이제이션) 방식과 Bottom-up 방식이 존재- Bottom-up 방식을 사용시 결과 저장용 리스트는 DP 테이블 이용- 분할 정복은 부분 문제의 중복이 없음 (조건)1) Optimal Substructure(최적 부분 구조)- 큰 문제를 작은 문제로 나눌 수 있으며 작은.. 2024. 7. 19. [알고리즘] 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 =.. 2024. 7. 19. [알고리즘] 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)- 처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입- .. 2024. 7. 19. [알고리즘] 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.. 2024. 7. 19. [알고리즘] 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 Pyt.. 2024. 7. 19. [기본 규칙] Python 프로젝트 구조 기본 프로젝트 구조project_name/├── project_name/│ ├── __init__.py│ ├── module1.py│ ├── module2.py│ └── ...├── tests/│ ├── __init__.py│ ├── test_module1.py│ ├── test_module2.py│ └── ...├── docs/│ └── ...├── scripts/│ └── ...├── .gitignore├── requirements.txt├── setup.py└── README.md디렉토리 및 파일 설명프로젝트 루트 디렉토리 (project_name/): 프로젝트 전체를 포함하는 최상위 디렉토리입니다.패키지 디렉토리 (project_name/): 실제 코드가 포함된.. 2024. 7. 19. [기본 규칙] Python 코딩컨벤션 공통 규칙1. 들여쓰기는 공백 4칸을 사용. tab 사용 불가2. 각 줄의 최대 길이는 79자로 제한. 길어질 경우 \ 또는 괄호를 사용하여 다음줄로 나눔3. 모듈 레벨 함수 및 클래스 정의는 두줄 간격으로 작성4. 괄호, 중괄호, 대괄호 내부에는 공백 사용 금지5. 쉼표, 콜론, 세미콜론 앞에 공백 사용 금지. 뒤에는 공백 사용6. 주석은 한 줄의 경우 #을 사용하고 코드와 두칸의 공백을 둠. 여러 줄의 경우 """을 사용7. docstring 작성시 """을 사용 변수 및 함수1. 변수 및 함수명은 영어소문자 및 밑줄(_)로 구성된 snake_case로 작성2. 상수는 영어대문자 및 밑줄(_)로 작성. 모듈 수준에서만 작성.3. 연산자 앞뒤에 공백 사용4. 문자열의 경우 쌍따옴표(")를 사용5. 함수.. 2024. 7. 19. [환경설정] Python 환경설정 Windowspython 사용법(버전 고정)1. python 다운로드- 버전, LTS과 CPU 확인 후 Windows installer 다운- 다운로드후 custom install을 하여 모든 유저에게 허용되도록 체크하여 설치 2. powershell에서 버전확인python --versionconda 사용법(버전 변경 가능)1. miniconda 설치- 실행 파일 다운로드하여 설치- 설치 후 환경변수(Path)에 추가 2. 가상환경 생성 및 삭제# 가상환경 생성conda create --name python=# 가상환경 삭제conda env remove --name 3. 가상환경 실행conda activate 4. 버전확인python --version MacOSpython 사용법(버전 고정)1. ter.. 2024. 7. 19. 이전 1 2 3 4 다음 반응형
