CS
알고리즘 - 에라스토스테네스 체(소수찾기)[Swift]
에라스토스테네스 체 소수를 찾는 알고리즘이다. 0 ~ 3000 범위의 소수를 찾는다고 할경우 n = 3000이 된다. 우선 n+1개의 불리언 배열을 생성해야 한다. n개를 생성할 경우 0을 포함하기 때문에 2999까지 만들어져서 인덱스를 벗어나게된다. 만약 자기 자신이 이미 false처리 되었다고 하면 pass를 하게되고 아닐 경우 i + i ~ n+1 까지 i씩 증가하면서 i의 배수(소수가 아닌 수)의 인덱스를 false 처리 하게된다 소스코드 let n = 3000 var isPrime = [Bool](repeating: true, count: n+1) //0과 1은 소수가 아니다. isPrime[0] = false isPrime[1] = false for i in 0...n{ for j in str..
알고리즘 - 유클리드호제법[Swift](최대공약수)
최대 공약수 최대 공약수를 구하기 위해 매우 쉬운 공식인 유클리드 호제법은 에우클라이데스라는 그리스의 수학자가 만든 호제법이다. 계산 과정 648, 232 라는 수를 a % b = r을 가지고 계산해나간다. 큰 수가 a, 작은수가 b 가 되며, a를 b로 나눈 나머지가 r이된다 계산을 마치면 b -> a // r -> b 가 된다 648 % 232 = 184 232 % 184 = 48 184 % 48 = 40 48 % 40 = 8 40 % 8 = 0 8 % 0 = 0 조건은 b가 0이 아닌 동안이니 b가 0이 되었으므로 a를 return 한다. 소스코드 func GDC(_ num1: Int, _ num2: Int) -> Int{ var a = num1 > num2 ? num1 : num2 var b = ..
알고리즘 - 조합(Conbinations) 구현[Swift]
조합에는 "순서"가 없다. 그저 몇 개를 뽑을 것인지를 사용할 때 조합을 사용한다. 순서는 상관없고 몇개를 다양하게 뽑을지.. 순서가 없다는건 1, 2, 3과 3, 2, 1을 같은 숫자로 본다는 것이다. 조합의 개수를 구하는 공식은 다음과 같다 n = 자료의 총 개수 r = 뽑아서 사용할 자료의 개수 만약 5C3일 경우 이 되며 5! = 120 (n-r)2! = 2 3! = 6이 되어 120/12 -> 10이 된다. [1, 2, 3, 4, 5] 5개의 숫자에서 3개를 뽑는 경우의 수는 실제로 1, 2, 3 2, 3, 4 1, 2, 4 2, 3, 5 1, 2, 5 2, 4, 5 => 총 10개이다 1, 3, 4 3, 4, 5 1, 3, 5 1, 4, 5 실제로 횟수를 구하는 공식이 아닌 리스트를 구하는 공..
그래프, BSF 구현[Swift]
그래프 구현 문제를 풀다보면 그래프를 구현하여 DFS, BFS 알고리즘을 구현해야 할 때가 많다 간선배열, 노드의 개수로 그래프를 구현(인접 리스트, 무 방향성) 간선배열(wires)= [[1,3],[2,3],[3,4],[4,5],[4,6],[4,7],[7,8],[7,9]] 노드의 수(n) = 9 위와같은 모습의 그래프를 인접리스트로 구현하면 오른쪽 표처럼 구현할 수 있다. 표의 칠해진 부분은 노드의 번호, 칠해지지 않은 부분은 해당 노드와 연결된 노드다. 해당 리스트를 Swift 언어로 표현 var graph: [Int: [Int]] = [:] 딕셔너리 형태로 키, 벨류(배열)로 저장하면 된다. 그래프를 초기화 let wires= [[1,3],[2,3],[3,4],[4,5],[4,6],[4,7],[7,..
알고리즘 - 그래프 탐색 알고리즘 구현(DFS)[Swift]
1. 간선의 배열과 노드의 개수가 주어졌을 때 위 그래프를 인접행렬의 이차원 배열로 만든다면 아래와 같다. 1 1 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 1 1 1 0 1 0 0 0 1 1 1 1 0 0 0 0 0 0 1 1 1 1 0 0 0 1 0 1 1 0 1 0 0 0 0 1 0 1 0 0 0 0 0 0 1 0 1 //간선의 배열 let graph = [[1, 1, 0 ,0 ,0 ,0 ,0, 0], [1, 1, 1, 1, 0, 0, 0, 0], [0, 1, 1, 1, 0, 1, 0, 0], [0, 1, 1, 1, 1, 0, 0, 0], [0, 0, 0, 1, 1, 1, 1, 0], [0, 0, 1, 0, 1, 1, 0, 1], [0, 0, 0, 0, 1, 0, 1, 0], [0, 0,..
자료구조 - 그래프
그래프 그래프는 정점과 간선으로 구성되는 자료구조. 정점은 하나의 객체를 의미하며 Vertex 노드라고 표현한다. 간선은 정점과 전점을 이어주는 선을 의미한다. 용어 정점 : Vertex라고 하며 하나의 점을 의미한다 간선 : edge라고 하며 정점과 정점 사이를 이어주는 선을 의미한다. 정점의 차수 : 정점의 연결되어있는 간선의 개수 가중치 : 간선의 가중치 가중치 그래프 간선에 가중치를 보유한 그래프 방향 그래프 간선이 방향을 가지고 있는 그래프. 간선의 방향으로만 이동이 가능하다. 그래프를 표현하는 방법 인접행렬 정점의 개수 N에 대해 N * N의 사이즈로 0과 1로 구성된 이차원 배열을 사용하여 구해주는 방법. a라는 인접행렬을 만들었다면 a[i][j]의 값은 i번 정점에서 j로 가는 정점이 연결..
알고리즘 - DFS BFS
드라마를 볼 경우 DFS(Depth-first search) 깊이우선탐색 = 한개의 드라마를 처음부터 끝까지 몰아본다 그래프에서 깊은 부분을 우선적으로 탐색하는 방식이다. 1 -> 2 -> 3 -> 4 -> 6 -> 5 문제 유형 1. 경로 탐색 유형(최단거리, 시간) A점부터 B점까지의 최단 거리와 시간을 구하라. 2. 네트워크 유형(연결) 여러 개체들이 주어진 상태에서 연결되어있는 그룹의 개수를 구하거나, 개체가 같은 네트워크 안에서 연결되어 있는지 확인하는 문제 https://www.youtube.com/watch?v=3G2lwJkLFEY&list=PLDV-cCQnUlIZH0wklfVG1IN9ks4g92oN7&index=4 3. 조합 유형(모든 조합 만들기) 여러가지의 조합을 전부 만들고 비교해봐야..
알고리즘 - 순열(Permutation Algorithm)
수학에서 순열(Permutation)또는 치환은 순서가 부여된 임의의 집합을 다른 순서로 뒤섞는 연산이다. n개의 숫자가 쓰여진 공증에서 r개의 수를 뽑아 나열한 경우의 수. 순서대로 나열한것 = "순열" 공식 (nPr) 서로 다른 n개 중 r개를 선택하는 경우의 수. (! = 팩토리얼) 3P2인 경우 공식은 3! / 1! 가 되므로 3!는 1, 2, 3 = 6이 된다(6개의 경우의 수) 모든 경우의 수를 계산하는 완전탐색에서 사용하는 알고리즘이다. 예를들어 {1, 2, 3}이 있다고 했을때 가능한 경우의 수) 1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1 구현방법 - 머리속으로 생각하기 쉽지만 구현은 어렵다. DFS와 체크리스트를 사용하는게 가장 쉬운 방법. 코드를 외우고 있는것이 좋..
알고리즘 - 유클리드 호제법(Euclidean- Algorithm)
유클리드 호제법 예를 들어 A와 B의 최대 공약수 흔히 GCD라고 부르는 최대공약수를 구하는데, 이럴 때 만약 A>B라면 A와 B의 최대공약수는 A를 B로 나눈 나머지를 R이라고 할 경우 A와 B사이의 최대 공약수는 B와 R사이의 최대 공약수와 똑같다. 최대 공약수 문제가 나왔을 때 흔히 A = aG, B = bG (G = 최대공약수) 최대 공약수라는 이름을 유지하기 위해서는 더이상의 공약수가 없어야 하기 때문에 여기서 a와 b는 서로소다. 이들의 최대 공약수가 G니까 정말로 A를 B로나눈 나머지가 r이였을 때, b와 r과의 최대공약수도 G가 되는지만 확인하면 된다. A를 예를들어 B로 나누었으면 몫이 있다. 그 몫을 우리는 q라고 해본다. 이럴 경우 A = q*B+r이 된다. A = a * G다 라고 ..