□ 이론/알고리즘 (12) 썸네일형 리스트형 기수 정렬(Radix sort) ▶기수 정렬 (Radix sort)자리 수가 존재하는 데이터들의 경우 적용 가능한 방법이다. (안정 정렬이 보장됨)e.g) OO자리 양의 정수, 문자열 가장 큰 자리수 혹은 작은 자리 수부터 선입 선출 방식의 자료구조에 분류해서 저장한 뒤, 해당 자리의 숫자가 작은 것부터 데이터를 꺼내 정렬하는 과정을 더 이상 크거나 작은 자리 수가 존재하지 않을 때까지 반복하여 정렬을 완료한다. 정렬에 O(dN)의 시간이 걸리며, d는 정렬해야 할 데이터의 최대 자리 수를 말한다. 빠른 속도로 정렬이 가능하나, 데이터를 분류해서 저장하는 데 필요한 공간이 더 필요하다는 단점이 있다. 같은 데이터 값이더라도 그 순서가 뒤바뀌지 않는 안정 정렬이다. 조합 생성 알고리즘 ▶조합 (Combination)서로 다른 n개의 원소 중에서 순서에 상관 없이 r개를 취하는 것을 'n개에서 r개를 택하는 조합'이라고 한다. (표기 : nCr) ▶필요성문제를 해결하는 과정에서 n개의 숫자 중 r개를 선택할 때선택된 r개의 숫자들의 합이 최대/최소가 되는 경우를 찾아야 하는 경우가 있다. 불가피하게 모든 경우를 확인해보는 수밖에 없다면어떤 소스코드를 작성해서 문제를 해결해야할까? ▶예제 : 5C3의 모든 경우를 출력하라.[주어진 원소]15, 23, 5, 1, 42 [결과]15 23 515 23 115 23 4215 5 115 5 4215 1 4223 5 123 5 4223 1 425 1 42 ▶Hint재귀 함수로 구현하면 간단한 코드로 해결할 수 있게 된다.주어진 원소들을 저장할 길이 .. 패턴 매칭 알고리즘 ▶패턴 매칭본문에서 특정 string(패턴)을 찾아야 하는 경우에 유용하게 쓰일 수 있다. 예시)"asdgsadf" "a"를 찾아서 "AAA"로 변경하라. 위와 같은 문제가 있을 때, 문제 해결을 위해서 우선 "a"의 위치를 찾아야한다.이 때 본문이 되는 "asdgsadf"에서 "a"라는 패턴을 찾는 방법을 패턴 매칭이라고 한다. ▶패턴 매칭 알고리즘 - 고지식한 패턴 검색 알고리즘(Brute Force)본문 string을 처음부터 끝까지 차례대로 순회하면서 패턴 내의 문자들을 일일이 비교하는 방식으로 동작한다.(길이가 10000인 string에서 길이 80의 패턴을 찾는다면 10000*80 = 800000번의 비교가 일어남) - KMP 알고리즘: 불일치가 발생한 텍스트 스트링의 앞 부분에 어떤 문자가 .. 순열 생성 알고리즘 ▶순열 (순서가 있는 열) - 서로 다른 것들 중 몇 개를 뽑아서 한 줄로 나열하는 것 - 순서화된 요소들의 집합에서 최선의 경우를 찾는 문제와 관련이 있다. ▶반복문을 통한 순열 생성그리디하게 접근해서 바로 문제가 해결되는 경우도 있지만,결국 모든 경우의 수를 다 따져보지 않고서는 정답을 알 수 없는 문제들이 존재한다. 그럴 때, 나올 수 있는 모든 순열을 생성하는 코드를 응용하여 문제를 해결할 수 있다. 순열 생성에 필요한 요소의 수가 고정적인 경우간단히 반복문으로 모든 순열을 생성할 수 있다. - 슈도코드 : {1, 2, 3}을 포함한 모든 순열을 생성123456FOR i1 in 1->3 FOR i2 in 1->3 IF i2 != i1 FOR i3 in 1->3 IF i3 != i1 AND i3 !.. 이전 1 2 다음