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,..

알고리즘 - 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다 라고 ..

알고리즘 - 최소 편집 거리(Minimum Edit Distance)

문자열 S를 다른 문자열 T로 변환하고자 할 때 필요한 최소의 편집 연산 횟수를 구하는 문제. 1회의 연산에는 삽입(insert), 삭제(delete), 대체(substitute)중 한 가지만 할 수 있다. 문자열 S = strong 문자열 T = stone S를 T로 변환하기 위해서는 총 4회의 편집 연산이 필요하다. s t r o n g s t o n e 1. o 삽입 2. r 삭제 3. o 삭제 4. g -> e 대체 총 4회의 편집 연산이 필요하다.

알고리즘 - 플로이드 와샬 알고리즘(Floyd Warshall Algorithm)

다익스트라 알고리즘 하나의 정점에서 출발했을 때 다른 모든 정점으로의 최던 경로를 구하는 알고리즘. 가장 적은 비용을 하나씩 선택을 해서 그 노드의 인접한 노드로 가는 길을 하나씩 계산해서 푼다. 1에서 3으로 가는 비용이 바로가는것보다 2을 거쳐간다면 거쳐가는 만큼의 비용으로 1에서 3으로 가는 비용을 수정한다. 플로이드 와샬 알고리즘 모든 정점에서 모든 정점으로의 최단 경로를 구하는 알고리즘 거쳐가는 정점을 기준으로 한다. 아예 반복문의 중심에 거쳐가는 노드가 있다. 에초에 거쳐가는 노드를 하나씩 설정해서 확인한다. 그래프가 있을 경우 2차원 배열의 형태로 유지한다. 1번 2번 3번 4번 1번 0 7 무한 무한 2번 5 0 9 6 3번 2 무한 0 4 4번 무한 무한 3 0 왼쪽 번호에서 상단 번호로..