반응형 [알고리즘] 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. [자료구조] 연결 리스트 연결리스트 정의- 연결리스트는 데이터와 포인터를 가지고 있는 노드를 한 줄로 연결하여 데이터를 저장하는 자료구조- 포인터는 다음이나 이전의 노드와 연결을 담당- 연속된 메모리 구조가 아닌 파편화된 메모리에서 유용하게 사용- 접근 시간 복잡도: O(N)- 탐색 시간 복잡도: O(N)- 삽입/삭제 시간 복잡도: O(1)연결리스트 종류- Single Linked List: 각 노드에 자료 공간과 한 개의 포인터 공간이 있고 각 노드의 포인터는 다음 노드를 가리킴- Doubly Linked List: 노드에 앞 노드의 메모리 주소를 보관하는 포인터를 추가해 앞의 노드와 뒤의 노드 모두 연결- Circular Linked List: Single Linked List의 마지막 노드의 포인터가 NULL이 아닌 헤드를.. 2024. 7. 19. [자료구조] 배열 배열이란?- 같은 자료형의 값들의 묶음으로 연속적인 메모리를 사용- 조회시 인덱스를 이용여 속도가 빠름- 메모리 공간을 사전 할당하므로 공간 이상의 값을 저장시 메모리 재할당 필요- 접근 시간 복잡도: O(1)- 탐색 시간 복잡도: O(N)- 삽입/삭제 시간 복잡도: O(N)배열 ADT배열 구조배열 조회배열 추가배열 삭제 void insert()void remove() 프로그램 언어별 메서드- C: 동일한 자료형의 묶음/* 배열 선언 및 초기화 */type arr[size];type arr[size] = {val1, ...};/* 2차원 배열 선언 및 초기화 */type arr[size][size];type arr[size][size] = {{val1, ...}, {val2, ...}};/* 동적배열 할.. 2024. 7. 19. [목차] 알고리즘 1. 알고리즘 개요1.1 알고리즘 정의1.2 시간복잡도와 공간복잡도: Ο-표기, Ω-표기, Θ-표기1.3 주요 함수2. 정렬2.1 삽입 정렬(Insertion Sort)2.2 선택 정렬(Selection Sort)2.3 버블 정렬(Bubble Sort)2.4 퀵 정렬(Quick Sort)2.5 병합 정렬(Merge Sort)2.6 계수 정렬(Counting Sort)2.7 기수 정렬(Radix Sort)2.8 힙 정렬(Heap Sort)3. 수학3.1 소수 판별: 에라토스테네스의 체3.2 최대공약수: 유클리드 호제법3.3 행렬 연산3.4 순열과 조합3.5 4. 동적계획법 5. 그리디 6. 시뮬레이션 7. 탐색5.1 선형 탐색(Linear Search)5.2 이분 탐색(Binary Search)5.3 BF.. 2024. 7. 19. [코딩테스트] 해시 해시 unordered_map 다루기#include int main(int argc, char** argv) { /* 생성 및 초기화 */ unordered_map dict1 = {{"key1": val1}, {"key2": val2}, {"key3": val3}}; /* 삽입 */ dict1["key"] = val; dict1.insert({"key": val}); dict1.insert(make_pair("key", val)); /* 삭제 */ dict1.erase("key"); /* 탐색 */ dict1.find("key"); /* 조회 */ for (auto it = dict1.begin(); it != dict.. 2024. 7. 9. [코딩테스트] 큐 큐- FIFO(First In First Out): 먼저 들어간 데이터가 먼저 나오는 구조- 작업 대기열이나 이벤트 처리에 사용 queue 다루기#include int main(int argc, char** argv) { /* queue 생성 및 초기화 */ queue q; /* 삽입 */ q.push(val); /* 삭제 */ q.pop(); /* 조회 */ while (!q.empty()) { std::cout 문제 추천- 기능 개발(Lv2)- 카드 뭉치(Lv1)+) - 다리를 지나는 트럭(Lv2) 2024. 7. 9. [코딩테스트] 스택 스택- FILO(First In Last Out): 먼저 들어간 데이터가 나중에 나오는 구조- 함수 호출시 메모리의 스택에 사용 stack 다루기#include int main(int argc, char** argv) { /* stack 선언 및 초기화 */ stack s; /* 추가 및 삭제 */ s.push(val); s.pop(); /* 조회 */ while (!s.empty()) { std::cout 문제 추천- 괄호 회전하기(Lv2)- 짝지어 제거하기(Lv2)- 주식 가격(Lv2)- 크레인 인형 뽑기 게임(Lv1)- 표 편집(Lv3)+)- 같은 숫자는 싫어(Lv1)- 올바른 괄호(Lv2)- 컨트롤 제트(Lv0) 2024. 7. 9. [코딩테스트] 배열 / 연결리스트 배열- 배열: 같은 타입의 원소들을 효율적으로 관리하기 위한 기본 자료형- 연속된 메모리를 이용한 자료구조- 탐색: O(1), 맨 뒤 삽입: O(1), 맨 앞/중간 삽입: O(N)- 배열 선택시 고려할점: 할당 가능한 메모리 크기 확인/중간 데이터 삽입 횟수 확인 배열 다루기#include int main(int argc, char** argv) { /** 배열 선언 및 초기화 * 배열 선언: type arr_name[size]; * 배열 초기화(기본값은 0): type arr_name[size] = {val1, ...}; */ int arr1[] = {1, 2, 3, 4, 5}; int arr2[5] = {1, 3, 4}; // 나머지는 0 int.. 2024. 7. 9. [코딩테스트] 특징 및 소개 코딩테스트 코딩테스트 사이트- 프로그래머스: 네이버, 카카오 등 IT 기업들의 코딩테스트 사이트- 백준 온라인 저지- solved.ac: 백준 온라인 저지를 단계별로 분류- SW Expert Academy: 삼성 코딩테스트 사이트- Softeer: 현대 자동차그룹 코딩테스트 사이트이론시간복잡도- Time Complexity는 알고리즘의 성능을 나타내는 지표로 입력 크기에 따른 연산횟수의 추이를 활용- 점근표기법인 Big-O Notation을 사용공간복잡도 C++ 필수 문법자료형- 정수형(short, int, long long): short는 2bytes; int는 4bytes; long long은 8bytes- 실수형(float, double): float는 4bytes; double은 8bytes- .. 2024. 7. 9. 이전 1 2 다음 반응형
