방법1: 제곱근 만약 N이 12라고 할 때 N의 제곱근은 약 3.46이다. 그리고 12의 약수는 1,2,3,4,6,12 이다. 1과 12를 제외하고는 2*6, 3*4, 4*3, 6*2이다. 2*6, 3*4, 4*3, 6*2의 관계는 몫이 커지면 나누는 값이 작아지거나 값이 커지면 몫이 작아지는 반비례 관계이다. 결국 N의 제곱근까지 향하게 되면 이후 몫과 나누는 값이 반대로 바뀌게만 되는 상황이다. -> 따라서 N의 제곱근까지 나누어 떨어지는 여부를 조사하면 소수 판별이 가능하다. 알고리즘 1. 1은 소수가 아니므로 먼저 처리 2. 짝수는 소수가 아니므로 false처리 3. 2 ~ N 제곱근까지 나눠본 후 하나라도 나눠 떨어지는 것이 존재하면 false 4. N제곱근까지 나눴음에도 나눠떨어지지 않는 경우..
버블정렬 버블 정렬의 시간 복잡도 = O(N^2) 다음의 숫자들을 오름차순으로 정렬하는 프로그램을 작성하세요 1 10 5 8 7 6 4 3 2 9 버블 정렬은 선택 정렬과 마찬가지로 직관적인 해결 방법이다. 인접해 있는 두 숫자끼리 비교를 해서 더 작은 숫자를 앞으로 보내주는 것을 반복하는 것이다. 즉, 옆에 있는 값과 비교하여 더 작은 값을 반복적으로 앞으로 보내는 정렬 방법이다. 버블 정렬은 정렬 알고리즘 중에서 구현은 가장 쉽지만 가장 비효율적인 알고리즘이다. var i: Int var j: Int var temp: Int var arr = [1,10,5,8,4,2,5,7,4,3] for a in 0...10 { for b in 0...(9-a) { if arr[b] > arr[b+1] { temp..
일반적으로 알고리즘을 공부할 때 가장 먼저 풀어보는 문제는 "정렬(sort)"문제이다. 다음의 숫자들을 오름차순으로 정렬하는 프로그램을 작성하세요 1 10 5 8 7 6 4 3 2 9 선택 정렬 시간복잡도: O(N^2) - 가장 작은 것을 선택해서 제일 앞으로 보내는 알고리즘 - 가장 원시적이고 기초적인 방법 var min: Int var index: Int var temp: Int var arr = [1,10,5,8,7,6,4,3,2,9] for i in 0...10 { min = 9999 for j in i...10 { if min > arr[j] { min = arr[j] index = j } } temp = arr[i] arr[i] = arr[index] arr[index] = temp } 위 코..
알고리즘이란 문제를 해결하는 절차이다. 알고리즘은 입력, 출력, 유한성, 명백성, 효과성을 만족해야 한다. 알고리즘은 분석을 통해 좋고 나쁨을 평가할 수 있다. 알고리즘은 기초 프로그래밍과 자료구조를 공부한 이후에 배우면 좋다. 알고리즘은 논리이며 수학이고 실질적인 개발에 적용되는 기초적인 아이디어이다. 알고리즘은 '개발'의 전체 과정에 사용된다. 실제 프로그램을 개발할 때 효율적인 알고리즘을 적용함으로써 원하는 결과를 도출해야 한다. 스케줄 관리 프로그램: 달력에서 특정한 달에 해당하는 일 수는 어떻게 구할까? 내비게이션 프로그램: 여러 개의 중간 지점을 거쳐서 특정 지점으로 갈 때 가장 빠른 길은 무엇일까? 게시판 프로그램: 한 페이지당 게시글을 10개씩 출력해야 하는데 어떻게 출력할까? 출처: ht..
