YJLee-devlog 🍎

https://github.com/YoungJaeLee-github/Swift-DataStructure-And-Algorithm GitHub - YoungJaeLee-github/Swift-DataStructure-And-Algorithm: Swift Algorithm Study Swift Algorithm Study. Contribute to YoungJaeLee-github/Swift-DataStructure-And-Algorithm development by creating an account on GitHub. github.com 신입 iOS Engineer를 준비하는 과정 중 Coding Interview를 준비하면서 Swift Language 관점에서 Data Structure와 Algorit..

1. 문제 2. 입출력 3. 입출력 예시 4. 문제 설계 d가 1인 경우, 정방향 d가 2인 경우 역방향으로 배열의 원소에 대해 위치(index)를 회전해야 함 여기서 x의 위치를 0번 인덱스에서 시작해서 계속해서 회전한 결과의 위치를 기준으로 그 다음 회전을 해야 하므로, x의 위치를 계속해서 바꿔줘야 하는 점에 유의해야 함 또, y의 입력 범위가 100이하 이므로 n으로 나눈 나머지를 다시 y에 할당하게 되면 반복되는 주기를 없앨 수 있음 위 조건을 만족하면서 정방향의 경우에는 x + y가 n보다 크거나 같은 경우, 배열의 오른쪽 끝을 벗어나게 되므로 n을 다시 빼주고, 작은 경우에는 그 만큼 회전하면 되고, 역방향의 경우에는 x - y 가 0보다 작은 경우 배열의 왼쪽 끝을 벗어나게 되므로 n을 더..

1. 문제 2. 입출력 3. 입출력 예시 4. 문제 설계 SCC 문제를 응용한 문제로, 코사라주 알고리즘에서 역방향 그래프에 대해서 DFS를 한번 더 적용하는 것과 다르게 생각해야 함 결론적으로, SCC인 그래프들은 어떠한 정점을 터뜨려도 다 터지기 때문에 1개의 정점으로 봐도 무방함 따라서 SCC인 그래프들을 1개의 정점으로 보고, 나머지에 대해 가장 효율적이게 폭발물을 설치해야 하는데, 자세히 살펴보면 나에게 들어오는 간선이 없는 정점에 대해 터뜨리게 되면 가장 최소한의 다이너마이트를 사용하여 폭발물을 설치할 수 있음 이를 코사라주 알고리즘을 응용하여 빠져나오는 순서를 기록하고, 재귀함수(DFS)의 특성상 가장 나중에 빠져나온 정점이 나에게 들어오는 간선이 없는 간선이므로, 이번에는 역방향이 아닌 원..

1. 문제 2. 입출력 3. 입출력 예시 4. 문제 설계 방향 그래프에서 같은 그룹의 정점이라면 서로 오고갈수 있는 경로가 존재하는 그룹끼리 그래프를 나누는 것을 SCC(Strongly Connected Component)라고 하며, 이를 구할 수 있는 대표적인 알고리즘이 코사라주 알고리즘 따라서 주어진 그래프를 정방향 그래프와 역방향 그래프 두가지로 구성하고, 정방향 그래프에 대해 DFS를 적용하여 빠져나오는 순서대로 그 정점의 번호를 기록하고, 가장 나중에 빠져나온 정점이 역방향 그래프에서는 단말노드가 되므로, 역방향 그래프에 대해 가장 나중에 빠져나온 정점부터 다시 DFS를 적용하게 되면 SCC를 구할 수 있음 따라서 O(V + E)의 시간복잡도로 문제를 해결할 수 있음 5. 전체 코드 //MARK..

1. 문제 특정 숫자가 소수인지 아닌지 판별하는것이 아닌, 2부터 주어진 수까지 범위 내의 모든 소수를 찾는 알고리즘인 에라토스테네스의 체를 구현 2. 문제 설계 1인 소수가 아니므로, 배열에 1번째 원소에는 0을 저장하고 2부터 주어진 수까지 각 수를 배열에 그에 대응하는 위치에 원소를 저장함 가장 작은 소수인 2부터 그의 배수들을 배열에서 모두 0으로 지워나가면 소수만 남게됨 따라서, 주어진 수가 N이라면 O(N log N)에 특정 범위내의 모든 소수를 찾을 수 있음 특정 수가 소수인지 아닌지를 판별하는 문제에서는 제곱근 까지 나누어보는 것이 효율적이고, 특정 범위 내의 모든 소수를 찾을 때는 에라토스테네스의 체를 활용하는 것이 효율적임 3. 전체 코드 //MARK: - 에라토스테네스의 체 //MA..

1. 문제 주어진 수가 소수인지 아닌지 판별하는 문제 2. 문제 설계 완전탐색으로 2부터 특정 숫자까지 나누어 떨어지는지 일일히 확인하면서 O(N)에 소수를 판별할 수도 있지만, 가장 작은 소수인 2부터 시작해서 나누어 떨어진다면, 그의 제곱수로는 확인해볼 필요가 없으므로 현재 소수인지 아닌지 판별하려고 하는 숫자가 2부터 시작하는 수의 제곱수보다 작거나 같을 때 까지 그 수로 나누어 떨어지는지 확인하게 되면 보다 더 효율적으로 소수를 판별할 수 있음. 쉽게 말하면 2부터 현재 판별하려는 수의 제곱근 까지 나누어 보는 것이랑 동일함 위 알고리즘은 O(root(N))의 시간복잡도를 가짐 3. 전체 코드 //MARK: - adv. 소수 판별 //MARK: - Framework import Foundation..

1. 문제 조합(Combination)을 손쉽게 구할 수 있는 파스칼 삼각형을 구현 2. 문제 설계 n C 0 = 1, n C n = 1은 n개 중에서 0개, n개 중에서 n개를 뽑는 경우의 수이므로 1, 즉 2차원 배열(파스칼 삼각형)의 (i, 0), (i, i)는 모두 1로 채울 수 있음 그리고 나를 결정하기 위해서는 나의 왼쪽 위 대각선 값과 바로 위 값을 더해줌으로써 구할 수 있고, 최종적으로 n C r을 알기 위해서는 2차원 배열(파스칼 삼각형)의 (n, r)의 원소를 출력함으로써 값을 얻을 수 있음 3. 전체 코드 //MARK: - 파스칼 삼각형 //MARK: - Framework import Foundation //MARK: - Function func solution() -> Void { ..

1. 문제 기본 정렬 알고리즘인 버블정렬을 구현 2. 문제 설계 버블정렬은 인접한 두 원소를 비교해가면서 정렬을 하는 알고리즘, 선택정렬 및 삽입정렬과 다르게 오른쪽 부터 정렬이 되는 형태를 가짐 O(N^2)의 시간복잡도를 가짐 3. 전체 코드 //MARK: - 버블정렬(Bubble Sort) //MARK: - Framework import Foundation //MARK: - Function func solution() -> Void { //MARK: - input guard let N: Int = Int(readLine() ?? "0") else { return } guard let input = readLine()?.components(separatedBy: " ") else { return } v..

1. 문제 기본 정렬 알고리즘인 삽입정렬을 구현 2. 문제 설계 왼쪽에서 오른쪽 방향으로 원소를 왼쪽 부분에 삽입하여 정렬해 나가는 알고리즘 O(N^2)의 시간복잡도를 가짐 3. 전체 코드 //MARK: - 삽입정렬(Insertion Sort) //MARK: - Framework import Foundation //MARK: - Function func solution() -> Void { //MARK: - input guard let N: Int = Int(readLine() ?? "0") else { return } guard let input = readLine()?.components(separatedBy: " ") else { return } var array: Array = input.map ..

1. 문제 기본 정렬 알고리즘인 선택정렬을 구현 2. 문제 설계 최솟값을 찾아 왼쪽에서 오른쪽으로 정렬해 나가는 알고리즘 O(N^2)의 시간복잡도를 가짐 3. 전체 코드 //MARK: - 선택정렬(Selection Sort) //MARK: - Framework import Foundation //MARK: - Function func solution() -> Void { //MARK: - input guard let N: Int = Int(readLine() ?? "0") else { return } guard let input = readLine()?.components(separatedBy: " ") else { return } var array: Array = input.map { Int($0) ?..