Major- (863) 썸네일형 리스트형 [알고리즘] 1-4. 퀵 정렬 [재귀 함수 이용] 1. 퀵정렬 : 기준값[pivot]을 선정해 해당 값보다 작은 데이터와 큰 데이터로 분류하는 것을 반복해 정렬 -> 기준값을 선택하는 함수가 시간 복잡도에 영향을 미치며, 평균적으로 시간복잡도는 O(nlogn)이다. -> 퀵이라는 이름에서 알 수 있듯이 평균적인 상황에서 최고의 성능을 나타낸다. [컴퓨터로 가장 많이 구현된 정렬 알고리즘 중 하나] (1) 구현 과정 -> 기준값 pivot을 중심으로 데이터를 2개의 집합으로 나누는 것을 반복해 정렬 데이터를 분할하는 pivot 설정 [방법에 따라 다르지만 여기서는 가장 오른쪽 끝 값으로 설정] 기준값을 기준으로 2개의 집합으로 분리하는 과정 start 데이터 start를 오른쪽으로 1칸 이동 [우측 shift 연산] end 데이터.. [알고리즘] 1-3. 삽입 정렬 # 1. 삽입 정렬 : 이미 정렬된 데이터 범위에 정렬된 데이터 범위에 정렬되지 않은 데이터를 적절한 위치에 삽입시켜 정렬 -> 시간복잡도는 O(n^2)으로 느리지만, 구현하기 쉽다. (1) 구현 과정 -> 선택 데이터를 현재 정렬된 데이터 범위 내에서 적절한 위치에 삽입 현재 index에 있는 데이터 값 선택 현재 선택한 데이터가 정렬된 데이터 범위에 삽입될 위치를 탐색 삽입 위치부터 index에 있는 위치까지 shift 연산 수행 삽입 위치에 현재 선택한 데이터를 삽입하고 index++ 연산 수행 전체 데이터의 크기만큼 index가 커질 때까지, 즉 선택할 데이터가 없을 때까지 반복 -> 삽입 위치를 찾는 탐색 과정에서 정렬되었을 경우 이진 탐색을 사용해 시간 복잡도를 단축 시킬 수 있다. 문제 18. .. [알고리즘] 1-2. 선택 정렬 # 1. 선택 정렬 : 대상 데이터에서 최대나 최소 데이터를 데이터가 나열된 순으로 선택해 정렬 -> 구현 방법이 복잡함에도 불구하고, 시간 복잡도 또한 O(n^2)로 효율적이지 않아 사용하지 않는다. (1) 구현 원리 : 최솟값 또는 최댓값을 찾고, 남은 정렬 부분의 가장 앞의 데이터와 swap해 정렬 남은 정렬 부분에서 최솟값 또는 최댓값을 찾는다. 남은 정렬 부분에서 가장 앞의 데이터와 선택된 데이터를 swap 가장 앞의 데이터 위치를 변경해 (index++) 한 후 남은 정렬 부분의 범위를 축소 전체 데이터 크기만큼 index가 커질 때까지 == 남은 정렬 부분이 없을 때까지 반복 문제 17. 내림차순으로 자릿수 정렬하기 # 수가 주어지면 그 수의 각 자릿수를 내림차순으로 정렬하시오. 입력 첫 번째 .. [알고리즘] 문제 풀이 순서 정리 1단계. 문제 분석하기 -> 내용과 조건을 살피고, 어떤 알고리즘을 사용할지 결정 연산 횟수 = 시간 복잡도 * 데이터의 크기 -> 연산 횟수를 이용해 조건에 부합한지 확인 2단계 .손으로 풀어보기 -> 손으로 그림을 그리면서, 문제를 푸는 과정을 구상 3단계. 슈도코드 작성하기 -> 구상한 문제 풀이 과정을 코드로 어떻게 구현할지 계획을 세운다. 4단계. 코드 구현하기 -> 슈도코드로 설계한 프로그램을 실제 코드로 구현 [알고리즘] 1-1. 버블 정렬 # 1. 버블 정렬 -두 인접한 데이터의 크기를 비교해 정렬 -간단하게 구현 가능하지만, 시간 복잡도가 O(n^2)로 느리다. -루프를 돌면서 인접한 데이터간 swap 연산으로 정렬 비교 연산이 필요한 루프 범위 설정 인접한 데이터 값 비교 swap 조건에 부합하면 swap 연산 수행 루프 범위 끝날 때까지 비교와 swap연산 반복 정렬된 영역을 빼고 나머지 실행 비교 대상이 없을 때까지 해당 과정 반복 문제 15. 수 정렬하기1 [백준 온라인 저지 2750번] N개의 수가 주어졌을 때 이를 오름차순 정렬하는 프로그램을 작성하시오. 입력 1 번째 줄에 수의 개수 N(1 [알고리즘] 1. 정렬 1. 정렬 알고리즘 버블 정렬 데이터를 인접 요소끼리 비교해, swap 연산을 수행하면서 정렬 선택 정렬 대상에서 크거나 작은 데이터를 찾고, 선택을 반복하면서 정렬 삽입 정렬 대상을 선택해 정렬된 영역에서 선택 데이터의 위치를 찾아 삽입하면서 정렬 퀵 정렬 pivot 값을 선정해 해당 값을 기준으로 정렬 병합 정렬 이미 정렬된 부분들을 효율적으로 병합해 전체를 정렬 기수 정렬 데이터의 자릿수를 바탕으로 비교해 정렬 2. 정렬 알고리즘 구현 (1) 버블 정렬 : 루프를 돌면서 인접한 데이터간 swap 연산으로 정렬 N(정렬할 수 개수) A(정렬할 배열 선언) for(i : 0 ~ N - 1) { for(j : 0 ~ N - 1 - i) { 현재 A 배열의 값보다 1칸 오른쪽 배열의 값이 더 작으면 두 수.. [기술면접 대비] DB 내용 정리 (회복전까지) 1. 데이터베이스 시스템 개념 데이터베이스의 목적 : 파일시스템의 고질적인 문제인 중복을 해결하고, 공유를 목적으로 사용하는 시스템 -> 많은 트랜잭션을 동시에 수행해도 일관성과 고립성의 문제가 생기지 않도록 해야 함 -데이터 처리 기능 : CRUD Create, Read, Update, Delete -트랜잭션 속성 : ACID Atomicity, Consistency, Isolation, Durability (1) 데이터베이스 유형별 구축 난이도 -> 검색과 변경 빈도에 따른 데이터베이스 유형 구분 데이터베이스는 데이터의 검색과 변경 작업을 주로 수행하는데, 이러한 검색과 변경의 빈도에 따라 시스템 구축의 난이도가 결정 검색 빈도 변경 빈도 구축 난이도 특징 적다 적다 1단계 검색이 많지 않아 DB 구.. [Ch.07 - Recursive] 03. 팩토리얼 3. 팩토리얼 자연수 N이 입력되면 N!를 구하는 프로그램을 작성하세요. 예를 들어 5! = 5*4*3*2*1=120입니다. 입력설명 첫 번째 줄에 자연수 N(1 이전 1 ··· 56 57 58 59 60 61 62 ··· 108 다음
