이것저것

메모리 상에 원소를 연속하게 배치한 자료구조. 시간복잡도 O(1)으로 k번째 원소의 위치를 바로 계산 (확인 및 변경 등) 할 수 있다.타 자료구조와는 다르게 추가적으로 소모되는 메모리의 양이 거의 없다.메모리 상에 데이터들이 붙어있으므로 Cache hit rate가 높다.Cache hit rate란 캐시 적중률을 의미하며 명령이나 자료를 찾기 위해 캐시 메모리에 접근했을 때 자료가 존재하면 적중 Hit 되었다 하고 없다면 실패했다고 한다. 적중률은 적중횟수/총 접근횟수 이며 컴퓨터의 성능을 나타내는 척도로 사용된다.메모리 상 연속한 구간을 잡아야 하므로 할당에 다소 제약이 존재한다. 기능원소를 확인/변경 : O(1)배열 끝에 원소를 추가 : O(1)배열 끝 원소를 제거 : O(1)임의의 위치에 원소를 ..

시간복잡도 컴퓨터는 1초에 대략 3-5억 개의 연산을 처리할 수 있다. 따라서 시간 제한이 1초라고 한다면 3-5억 번의 연산 안에 답을 내고 종료되는 프로그램을 짜야 한다는 뜻으로 이해하면 된다. 입력의 범위를 보고 문제에서 요구하는 시간복잡도를 대략적으로 유추가 가능하다.N의 크기허용 시간복잡도N O(N!)N   25O(2^N)N   100O(N^4)N   500O(N^3)N   3000O(N^2logN)N   5000O(N^2) N   1,000,000O(NlogN)N   10,000,000O(N)그 이상O(logN), O(1) 문제 1N 이하의 자연수 중 3의 배수이거나 5의 배수인 수를 모두 합한 값을 반환하는 프로그램을 작성하라. N은 5만 이하의 자연수이다.var n = int.Parse(C..

알고리즘을 공부하는 목적?코딩 테스트의 출제 의도 파악을 분명히 함'최적화'에 대한 이해개인 프로젝트의 퀄리티를 높임포트폴리오의 어필 방향을 확실히 함종류빅오 표기법 Big-O notation - 시간복잡도, 공간복잡도완전 탐색 Brute-force search탐욕적 기법 Greedy Algorithm분할 정복 Divide and conquer동적 계획법 Dynamic programming이진 탐색 Binary search파라메트릭 탐색 Parametric search깊이 우선 탐색 Depth-First search (DFS)너비 우선 탐색 Breadth-First search (BFS)백트래킹 Backtracking비트마스킹 Bit masking구간합 배열 Prefix sum에라토스테네스의 체 Siev..

자료구조를 공부하는 목적?알고리즘 학습에 선행함 종류리스트 List배열 Array연결 리스트 Linked list스택 Stack큐 Queue덱 Double Ended Queue (Dequeue)그래프 Graph트리 Tree이진 검색 트리 Binary search tree우선순위 큐 Priority queue (PQ)유니온 파인드 Union-Find (Disjoint-set)세그먼트 트리 Segment tree (ST)최소 스패닝 트리 Minimum spanning tree (MST)머지 소트 트리 Merge sort tree퍼시스턴트 세그먼트 트리 Persistent segment tree