알고리즘

백준 1929 - Swift https://www.acmicpc.net/problem/1929 이전 DFS에서 소수 찾는 함수에서 생각나서문제 풀러 갔는데 이미 자바로 풀어져 있더라구요.그래서 이번에 Swift로 갱신 +  에라토스테네의 체 원리 해서 다시 풀었습니다! 에라토스테네의 체 원리?구하고자 하는 소수의 범위만큼 배열을 생성한 다음 2부터 현재 선택된 숫자의 배수에 해당하는수를 배열에서 모두 제거하면서 찾는 방법O(nlog(nlogn))으로 시간 복잡도가 굉장히 낮은 편!  코드let input = readLine()!.split(separator: " ").map { Int($0)! }let m = input[0]let n = input[1]var array = Array(repeating: ..

백준 2023 - Swifthttps://www.acmicpc.net/problem/2023   해당 문제느 입력의 max가 8인 것을 보아 어떤 알고리즘을사용하여도 원만하게 풀 수 있는 문제임을 보여주고 있긴 한데요.저는 DFS, 재귀함수를 이용해서 풀이 했어요. 먼저 소수를 정의 해 보자면,소수 : 1과 자기 자신 이오의 약수가 없는 1보다 큰 자연수그렇기 때문에 일단 1의 자리에서 소수는 2, 3, 5, 7이 되는 것이고해당 숫자에서 홀수 (짝수가 되는 순간 != 소수)를 이어 붙여가면서변화하는 숫자가 소수인지 아닌지 파고 들어가면서 확인해주면 되기 때문에계속 파고 들어가는 건 DFS 니, DFS를 활용하였습니다.  소수 판별먼저 소수인지 아닌지 판별할 수 있는 함수를 만들고func isPrime(..

백준 1260 - Swifthttps://www.acmicpc.net/problem/1260  DFS, BFS의 기본 문제로 개념을 알고있다면 쉽게 구현이 가능한 문제입니다!  그런 기념으로 간단하게 정리해보는 DFS, BFS 1) DFS - Depth First Search (깊이우선탐색)완전 탐색 기법 중 하나로써그래프의 시작노드부터 한쪽 분기의 최대 깊이까지 탐색 후 다른쪽 분기로 이동하여 모두 탐색을 완료하는 기법노드의 개수를 V, 에지의 개수를 E라고 했을 때, 시간 복잡도는 O(V+E)재귀 함수, 스택으로 구현함스택으로 구현하는 이유는, "그래프의 시작노드부터 한쪽 분기의 최대 깊이까지 탐색 후"에 따라 결정되는 방법임깊이로 탐색하는 것을 이미지로 그려보면 마지막까지 들어갔다가 그 위부터 po..

안녕하세요. 린다입니다.오늘은 정렬 두번째.. 병합(분할)정렬과 기수 정렬에 대해서 정리해볼게요! 병합 정렬데이터를 분할하고, 분할한 집합을 정렬하며 합치는 알고리즘O(nlogn)의 시간 복잡도) N번의 데이터 접근이 logN 번 일어남경주 문제에서 활용됨하나의 배열을 가장 작은 크기까지 분할한 다음 2개의 포인터를 가지고각 포인터 값의 비교를 통하여 정렬 후 합치고를 반복하는 기법Two Pointer를 활용한 코드// MARK: - 병합 정렬func mergeSort(_ array: inout [Int], _ left: Int, _ right: Int) -> [Int] { if (left    기수 정렬값이 아니라 요소의 자릿수를 비교해서 정렬하는 기법1의 자리 → 10의 자리 → 100의 자리 ..

백준 1436https://www.acmicpc.net/problem/1436   문제 이해)맨 처음에 문제를 읽었을 때는 그냥 N-1해서 666 붙이면 되는거 아닌가? 했는데 아닙니다..N번째를 포함한 영화 제목을 찾아야 하는 문제였어요.즉, N이 입력되면 N이 들어가는 영화의 제목을 출력하는 것 2번째 영화가 아니라 N이 들어가는 영화의 제목을 출력 하는 것 쉽게 풀어보자면,첫 숫자가 666이 되고, 666 += 1 씩해가면서 666이 연속으로 나오는 것을 찾아야 합니다.N = 2라면 666 +=1 을 했을 때 667~900까지 없고 1590없고,1600없다가 1666에서 숫자 N인 1을 발견! 그래서 리턴값이 1666이 되는 패턴입니다.  브루트포스 분류에 있는 만큼 완전 탐색을 통해서 쉽게 풀 수..

안녕하세요. 린다입니다.오늘은 간단하게 알고리즘의 기초인 정렬 알고리즘 중버블, 선택, 삽입, 퀵 정렬에 대해서 정리해볼게요! 버블 정렬데이터의 인접요소끼리 비교하여 swap 연산을 수행하여 정렬하는 기법루프를 돌면서 연산 수행시간복잡도 O(n^2)let array = [99, 98, 97, 96]func bubbleSort(_ array: [Int]) -> [Int] { var bubbleArray = array let n = bubbleArray.count for i in 0.. bubbleArray[j+1] { bubbleArray.swapAt(j, j+1)// let temp = bubbleArray[j]// ..