키리Kirri's IT노트

정렬 알고리즘 정리

🎶 단순 정렬시간 복잡도 O(n2)효율이 좋지 않음 버블 정렬 (Bubble Sort)이웃한 두 요소의 대소 관계를 비교해 교환을 반복 (가장 기본적인 정렬)n개 요소의 정렬이 모두 끝나려면 n-1회의 패스가 수행되어야 함하나의 패스에서 요소 간의 교환이 이루어지지 않았다면 정렬이 완료된 상태로 간주하여 정렬 작업 중단나아가 특정 인덱스부터 요소 간의 교환이 이루어지지 않았다면 해당 인덱스까지는 정렬 완료 상태로 간주 for(int i = 0; i i; j--) { if(a[j-1] > a[j]) { // 앞의 요소와 비교 및 교환 swap(a, j, j-1); chk++; } } if(chk == 0) { break; } // 패스 내에서 요소 간 교환이 이루어지지 않았으므로 ..

문자열 검색(String Searching)이란? 어떤 문자열 안에 다른 문자열이 들어 잇는지 조사하고, 들어 있다면 그 위치를 찾아내는 것 편의상 검색할 문자열을 패턴(pattern)이라 하고, 문자열 원본은 텍스트(text)라고 정의 브루트-포스법 검색할 텍스트의 맨 처음부터 한 칸씩 뒤로 옮기며 패턴 검색 패턴의 앞 글자부터 순서대로 텍스트와의 일치 여부 검색 그러다가 다른 문자가 나타나면 검사를 중단하고 검색할 텍스트의 위치를 한 칸 뒤로 이동 선형 검색을 확장한 알고리즘으로 단순법, 소박법이라고도 함 효율이 좋은 검색법은 아님 [실습 코드] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 //브루트-포스법으로 문자열을 검색하는 메서드 static int bfMat..

집합과 요소 집합(set)이란 객관적으로 범위를 규정한 '어떤 것'의 모임이며, 그 집합 안에서 각각의 '어떤 것'을 요소(element)라고 부름 예를 들어, 아이돌 그룹 '트와이스'를 하나의 집합으로 규정한다면 '모모', '미나', '다현' 등은 '트와이스'라는 집합의 요소라고 할 수 있음 집합의 요소는 중복될 수 없음 ※요소의 중복을 허용하는 집합은 다중집합이라고 하며, 집합과는 구별해서 부름 집합 X의 요소가 1, 5인 경우 아래와 같이 표현 X = {1, 5} 집합의 요소에는 순서가 없기 때문에 아래와 같이 표현해도 무방 X = {5, 1} 자연수의 집합: 일반적으로 N이라는 집합의 이름과 ...기호를 사용 N = {1, 2, 3, 4, ...} 정수의 집합: 일반적으로 Z라는 집합의 이름과 ...

도수 정렬 요소의 대소 관계를 비교할 필요가 없음 도수분포표 작성, 누적도수분포표 작성, 목적 배열 만들기, 배열 복사의 4단계로 이루어짐 [10점 만점의 테스트에서 학생 9명의 점수 도수 정렬] 1단계. 도수분포표 만들기 학생 점수 배열 a를 바탕으로 '각 점수에 해당하는 학생이 몇 명인지'를 나타내는 도수분포표 작성 모든 요소의 값을 초기화한 배열 f에 배열 a를 처음부터 스캔하면서 도수분포표 작성 예를 들어, a[0]이 5점이면 f[5]를 1만큼 증가시키고 a[1]이 7점인 경우 f[7]을 1만큼 증가시키는 작업을 반복 for(int i = 0; i < n; i++) f[a[i]]++; 2단계. 누적도수분포표 만들기 '0점부터 점수 n까지 몇 명의 학생이 있는지' 누적된 값을 나타내는 누적도수분포표..

힙이란?힙(heap)을 사용해 정렬하는 알고리즘힙은 '부모의 값이 자식보다 항상 크다(우선순위가 높다)'는 조건을 만족하는 완전이진트리부모의 값이 자식보다 항상 작아도 힙이라고 함(부모와 자식 요소의 관계만 일정하면 됨)우선순위 큐(Priority Queue)가 힙 자료구조를 이용해 구현됨 👆 완전이진트리부모는 자식을 왼쪽부터 추가하며(완전), 부모가 가질 수 있는 자식의 개수가 최대 2개(이진)인 트리 완전이진트리 → 힙 전환 힙은 루트가 가장 큰(혹은 작은) 값이어야 함즉, 모든 부모와 자식의 관계는 항상 부모의 값 >= 자식의 값이 성립되어야 함힙에서 부모와 자식 관계는 일정하지만 형제 사이의 대소 관계는 일정하지 않음 힙의 요소를 배열에 저장 힙의 요소를 배열에 저장하면 부모와 자..