Java/Java 알고리즘 (37) 썸네일형 리스트형 [알고리즘] 2. 자료구조 배열과 리스트 Array 데이터 접근이 주 업무일 경우 ArrayList 데이터 추가 및 삭제가 주 업무일 경우 LinkedList 데이터 수정이 주 업무일 경우 구간 합 투 포인터 슬라이딩 윈도우 스택과 큐 Stack [LIFO] 나중에 들어온 게 먼저 나간다. Queue [FIFO] 선형 큐 나가면 끝 환형 큐 [원형 큐] 나가면 다시 처음으로 삽입 [계속 돈다] 연결리스트 큐 PriorityQueue [우선순위 큐] [알고리즘] 1-6. 기수 정렬 [구간 합 이용] (+ 우선순위 큐 이용) 1. 기수 정렬 : 값을 비교하지 않는 정렬로, 값을 놓고 비교할 자릿수를 정한 후 해당 자릿수만 비교 -> 시간 복잡도가 O(kn)으로, 데이터의 자릿수에 영향을 받는다. -> 시간 복잡도가 가장 짧은 정렬로, 데이터의 개수가 많을 경우 사용된다. (1) 구현 과정 : 값의 자릿수를 나타내는 큐인, 10개의 큐를 이용한 정렬 일의 자릿수 기준으로 배열 원소를 큐에 넣는다. 0번째 큐부터 9번째 큐까지 pop을 진행한다. 십의 자릿수 기준으로 같은 과정 반복 마지막 자릿수를 기준으로 정렬할때까지 반복 문제 22. 수 정렬하기 3 N개의 수가 주어졌을 때 이를 오름차순 정렬하는 프로그램을 작성하시오. 입력 첫 번째 줄에 수의 개수 N(1 따라서, O(kn)의 시간 복잡도인 기수 정렬을 사용한다. 2단계. .. [알고리즘] 1-5. 병합 정렬 [재귀 함수, 투 포인터 이용] 1. 병합 정렬 : 분할 정복 [divide and conquer] 방식을 사용해 데이터를 분할하고 분할한 집합을 정렬하면서 합치는 알고리즘 -> 시간 복잡도의 평균값은 O(nlogn)으로 준수한 편이다. (1) 구현 과정 -> 가장 작은 데이터 집합으로 분할 후, [divide] -> 병합해 가면서 정렬 [conquer] -> 각각의 집합을 정렬 후 -> 병합 -> 정렬 후 -> 병합 과정을 반복해 전체를 오름차순으로 정렬 : 2개의 그룹을 병합하는 원리를 이용 # 2개의 그룹을 병합하는 과정 [투 포인터 개념 이용] 왼쪽 포인터와 오른쪽 포인터의 값을 비교 두 포인터가 가리키는 값 중 작은 값을 결과 배열에 추가하고, 해당 포인터를 오른쪽으로 1칸 이동 [우측 시프트 연산] 두 포인터 모두 마지막 i.. [알고리즘] 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 2 3 4 5 다음
