본문 바로가기

알고리즘

 (419)
중복 된 숫자 개수 세기 [1. 개요]어떤 배열에서 중복 된 숫자의 개수를 세야 할 때,재귀로 구현했을 때 간과할 수 있는 오류(?) 등을 정리[2. 재귀적인 방법]fn _solve(input: &Vec, i: usize) -> i32 { if i >= input.len() { return 0; } let mut ret = 0; for j in i+1..input.len() { if input[i] == input[j] { ret += 1; } } return ret + _solve(&input, i+1);} 아래는 위 rust 함수에 입력과 출력을 정리한 것이다.입력출력[7, 7, 7]3[6, 5, 4]0[6, 2, 6] 1 [7, 7, ..
farthest insertion [1. 개요]TSP 에서 N (노드) 개수가 커질 수록 완전탐색으로는 현실적인 시간 안에서 해결이 불가능 하다.따라서 최적해를 구하기 위한 휴리스틱 알고리즘 중 하나.Nearest insertionCheapest insertion등 이 더 있음.farthest insertion 알고리즘은 기본적으로 가장 멀리 있는 방문지를 먼저 선택하고,이 방문지 사이에 그 다음으로 멀리 있는 방문지를 삽입 함 으로서 전체 방문 순서를 결정한다. 물론, best solution 이 아닐 수 있다.그러나, 현실적인 시간 안에서 optimal solution 을 낼 수 있는 방법 중 하나이다.[2. 알고리즘]일단, 모든 정점 간에 소요되는 비용이 있는 테이블을 D 라 정의하고,D[S][T] 는 S->T 로 가는 비용이라 하..
언어 별 io 성능 개선 C++GoRustPythonJava
탐욕법. [1339] [1. 문제 설명] https://www.acmicpc.net/problem/1339 [3. 코드]
분할 정복. [5904] [1. 문제 설명] https://www.acmicpc.net/problem/5904 [2. 풀이 접근] 생성 되는 문자열은 Left / Middle / Right 로 구성 되고 있으며, 여기서 Left 와 Right 는 서로 같다. 최소 어느 정도의 k 일 때 해당 문자열이 찾고하는 위치를 포함하게 된다. 여기서, Left 와 Middle 의 문자열 각각의 길이를 알 수 있기 때문에 찾고자 하는 문자열이 Left 와 Middle 의 속하는지 확인하고, Left 에 속하면 재귀 호출을 반복하고, Middle 에 속하면 M 인지 O 인지 바로 알 수 있다. 마지막으로 Right 에 속하는 경우는 Left 에 속하는 것과 같다고 볼 수 있으므로, 찾고자 하는 문자의 위치를 Left 와 대칭되는 위치로 변경하..
이분탐색. [2473] [1. 문제 설명] https://www.acmicpc.net/problem/2473 [2. 풀이 접근] 먼저 두 용액의 조합을 모두 찾는다. 이제 각 조합에 대해서 한 용액만 첨가하여 0에 가장 가까워지는 조합을 찾아내도록 한다. 주석 참조 삼분 탐색 (?) [3. 코드]
이분탐색. [2467] [1. 문제 설명] https://www.acmicpc.net/problem/2467 [2. 풀이 접근] 용액을 하나 정한다. 전체에 대해서, 이 용액과 더해서 그 합이 0에 가장 가까워 지는 용액을 이분 탐색으로 찾는다. 용액들이 이미 정렬 된 상태이므로, 이분 탐색 시 두 용액의 합이 0보다 작다면 # 양수 용액을 더해서 0으로 만들 수 있다. # 따라서 다음 탐색 구간을 (mid ~ hi] 구간을 잡아야 한다. 0보다 크다면 # 음수 용액을 더해서 0으로 만들 수 있다. # 따라서 다음 탐색 구간을 [lo ~ mid) 구간을 잡아야 한다. [3. 코드]
이분탐색. [1253] [1. 문제 설명] https://www.acmicpc.net/problem/1253 [2. 풀이 접근] 풀이 시 주의 할점 std::lower_bound 에 대응되는 sort.Search() 는 하한 값 중 가장 먼저 오는 index 를 반환한다. 중복된 값에 대해서도 확인이 필요한 경우, upper_bound 에 해당하는 index 까지 구할 필요가 있다. 즉, [lo, hi) 까지 순차적으로 확인 해 볼 필요가 있다. 시간 복잡도는 O(N^2 logN) 인데, N 의 최대가 2,000 이므로, 현실적인 시간 내에 해결 가능하다. [3. 코드]
최장 증가 부분 수열. [12738] [1. 문제 설명] https://www.acmicpc.net/problem/12738 [2. 풀이 접근] LIS 관련 문제 접근은 보통 아래와 같은 방식으로 진행한다. 완전 탐색 동적 계획법 (완전 탐색에서 부분 문제에 대한 메모이제이션 적용) 완전 탐색 접근법은 아래와 같다. 수열 A[0] 부터 시작할 때 가장 긴 수열의 길이를 찾는다. 수열 A[1] 부터 시작할 때 가장 긴 수열의 길이를 찾는다. 수열 A[2] 부터 시작할 때 가장 긴 수열의 길이를 찾는다. 이런 방식을 수열의 끝까지 적용하면 구할 수 있으나, 시간복잡도가 O(2^N) 가 되므로, 길이가 1백만 이상인 수열에 대해서는 현실적인 시간내에 구할 수 없다. 다만 여기서 중복문제가 있다는 것을 인지하면, 메모이제이션을 적용하여 조금 더 빠..
정렬. [10825] [1. 문제 설명] https://www.acmicpc.net/problem/10825 [2. 풀이 접근] 전체 데이터를 구조체 형태고 감싸서 해당 배열을 정렬하는 방식으로 구현 할 수 있지만, 이렇게 할 경우, 불필요한 복사가 발생 하게 된다. 각 데이터를 순서대로 입력받아 각각의 배열에 저장하고, 각 배열 내 데이터를 가리키는 인덱스 배열을 생성한다. 이 인덱스 배열을 정렬하여 구현하도록 한다. [3. 코드]

티스토리툴바