YJLee-devlog 🍎

1. 문제 2. 입출력 3. 입출력 예시 4. 문제 설계 i의 범위를 보더라도 완전탐색으로 절대 시간안에 문제를 해결할 수 없는 것을 알 수 있음 따라서 더 효율적인 탐색 알고리즘으로 문제를 해결해야 하고, 각각의 시작점과 끝점을 저장하는 2차원 배열을 구성하거나, 각각을 1차원 배열에 저장하는 방법도 있음, 이때 시작점 끝점을 입력받아 각각 배열에 저장할 때 O(n)으로 저장해야 하는 것에 유의 해야함 모든 시작점과 끝점의 정보가 저장되어 있는 배열을 O(n)의 시간복잡도로 최소 시작점, 최대 끝점을 각각 구하고, 최소 시작점부터 최대 끝점에 대해 이진탐색을 통해 문제를 해결할 수 있음 모든 구간의 합집합에 대해 O(n)의 시간 복잡도로 최소 시작점에서 최대 끝점 범위에 해당하는 각각의 숫자의 위치를 ..

1. 문제 2. 입출력 3. 입출력 예시 4. 문제 설계 n(100,000)개의 숫자에 대해 구간 1일때 부터 n일때 까지 중복이 있는지 검사하게 된다면, 시간안에 문제를 해결할 수 없음 따라서 해당 구간이 중복 없는 구간인지 검사하는 함수를 통해 중복이 가능하다면, start를 이동시키고, 불가능하다면 end를 이동시켜, 투 포인터가 맞붙었을 때, start를 반환하게 되면, 구간의 최대값을 알 수 있음 만약 4개의 구간이 중복이 없다면, 4개의 구간보다 작은 구간들은 전부 중복이 없는 것을 알 수 있고, 특정 구간이 중복이 있다면 그 구간보다 큰 구간들은 전부 중복이 있는 것을 알 수 있기 때문에 위 알고리즘을 사용할 수 있음 여기서 구간이 중복이 있는지 없는지 파악하는 것이 가장 중요하고, 이를 통..

1. 문제 2. 입출력 3. 입출력 예시 4. 문제 설계 O(N^2) 완전탐색을 통해 문제를 해결하게 되면 100,000 * 100,000이므로 시간안에 문제를 해결할 수 없음 우리가 알 수 있는 수는 1 ~ N * N 범위의 수이고, 해당 범위의 수가 몇 번째 수인지 O(N)의 시간복잡도로 알아낼 수 있음 NN단표에서 1부터 N까지 중, 1 * N이 현재 수보다 작게 되면 현재의 단계에서는 현재 숫자보다 작은 숫자가 N개가 있다는 것을 알 수 있고, 현재 숫자가 현재 단계로 나누어 떨어지게 된다면 그 몫에서 자기 자신을 제외하게 되면 현재 숫자보다 작은 숫자의 개수를 알 수 있고, 나누어 떨어지지 않는다면, 그 몫이 현재 숫자보다 작은 숫자의 개수임을 알 수 있음 위 3 ~ 5 과정의 개수를 모두 더해..

1. 문제 2. 입출력 3. 입출력 예시 4. 문제 설계 나무의 길이 M의 경우 Int64의 자료형으로 안전하게 담는 것이 좋을 수 있음 문제에서 요구하는 나무길이의 합은 항상 M을 넘게 되므로 Int64의 자료형으로 담아야 함 나무의 길이가 10억이므로 완전탐색으로 나무의 높이가 최대 10억이므로 절단기의 높이 또한 최대 10억임을 알 수 있음 절단기의 높이가 10억을 넘게 되면 나무가 아무리 높더라도 10억이므로 잘릴 나무가 없음. 따라서 N개의 숫자에 대해 1부터 10억까지의 절단기 높이에 따라 잘린 나무의 개수를 파악하게 되면 시간안에 문제를 해결할 수 없음 따라서 1부터 절단기의 최대 높이에 대해 각각의 잘린 나무의 길이를 가져가고자 하는 나무의 높이와 비교를 통해 이진탐색하여 O(N log N..

1. 문제 2. 입출력 3. 입출력 예시 4. 문제 설계 숫자 a의 최대값을 보면 19자리 이므로, Int64 자료형에 저장해야하는 것을 알 수 있음 f(x) = x ^ x + x 2차식을 곱셈 형태로 변형하게 되면, f(x) = x * (x + 1) 즉, 자기 자신과 자신보다 1큰 수의 곱을 통해 a를 만들어내야 되는 것을 알 수 있음 두 수의 곱을 통해 a를 얻어내야 하므로, 완전탐색을 하게 된다면 O(N)으로 문제를 해결할 수 없음 따라서 이진탐색을 통해 0부터 a의 제곱근 + 1까지의 수를 x * (x + 1) 연산 함으로써 값을 얻어낼 수 있음 5. 전체 코드 //MARK: - 2차식 정답 추측 //MARK: - Framework import Foundation //MARK: - Function..

1. 문제 2. 입출력 3. 입출력 예시 4. 문제 설계 완전탐색으로 각각 차이를 구하여 0에 가까운지 검사하면 O(100,000 * 100,000)의 시간복잡도를 소요하게 됨 따라서 먼저 배열을 정렬한 후, 0번 숫자부터 해당 숫자의 반대 부호(1인 경우 -1, -1인 경우 1) 숫자와 차이가 작은 숫자를 이진탐색을 통해 찾아야 함 배열의 원소의 값이 10억이므로 안전하게 Int64 자료형으로 처리를 해줄 수 있음 현재 숫자의 반대 부호 숫자보다 중간 값이 작은 경우 start를 옮기고, 크거나 같은 경우에는 end를 옮겨 투 포인터가 맞붙었을 때, start와 현재 숫자의 차이(절대값)와 end와 현재 숫자의 차이(절대값)이 더 작은 수를 반환하여 각각을 배열에 저장함 원래의 배열과 이진탐색을 통해 ..

1. 문제 2. 입출력 3. 입출력 예시 4. 문제 설계 n(100,000)개의 숫자에 대해 q(100,000)번 숫자의 개수를 탐색하게 되면, O(100,000 * 100,000)으로 시간 안에 문제를 해결할 수 없음 따라서 n(100,000)개의 숫자에 대해 고급 정렬을 통해 O(n log n) 시간 복잡도가 소요되고, 이후 q번의 이진탐색 O(q log n)의 시간복잡도가 소요됨 이 문제는 이진탐색을 두 번 해야 하는데, 한 번은 현재 찾고자 하는 값이 mid보다 크거나 같은 경우, end를 이동 시켜 투 포인터(start와 end가 붙게 되었을 때 즉, start + 1 == end 일 때)가 맞붙었을 때, end를 반환하게 되면 해당 숫자의 가장 작은 index를 반환하게 되고, 마지막 한 번은..

1. 문제 2. 입출력 3. 입출력 예시 4. 문제 설계 N(300,000)개의 숫자에 대해 M(500,000)번의 탐색을 하게 되면, 300,000 * 500,000 = 150,000,000,000 이므로, 시간안에 문제를 해결할 수 없음. 따라서 다른 탐색 알고리즘을 사용하여 문제를 해결해야 함 N(300,000)개의 숫자에 대해 정렬을 하게 되면 합병 정렬, 퀵정렬 등 고급 정렬을 통해 O(N log N)의 시간복잡도로 정렬을 할 수 있고, 이미 정렬된 알고리즘에 대해 이진탐색을 하게 되면 O(log N)이고 이를 M(500,000)번 반복하게 되면, O(N log N) + O(M log N)의 시간복잡도로 문제를 해결할 수 있음 5. 전체 코드 //MARK: - 숫자박스 //MARK: - Fram..

1. 문제 2. 입출력 3. 입출력 예시 4. 문제 설계 n(100,000)개의 숫자에 대해 q(100,000)번의 탐색을 하게되는 경우, 한 번 탐색할 때마다 최악의 경우 100,000번을 q번 하게 되면, 100,000 * 100,000 = 10,000,000,000 이므로, 시간안에 문제를 해결할 수 없음. 따라서 다른 탐색 알고리즘을 통해 문제를 해결해야 하는데 자세히 살펴보면 이미 정렬되어 있는 수열이므로, 이진탐색을 통해 O(log n)의 시간복잡도로 탐색을 할 수 있고, 이를 q번 반복하여 O(q log n)의 시간복잡도로 문제를 해결할 수 있음 5. 전체 코드 //MARK: - 이진탐색 //MARK: - Framework import Foundation //MARK: - Function f..