분류 전체보기361 [코딩테스트 연습] 스킬트리 문제: https://programmers.co.kr/learn/courses/30/lessons/49993 시뮬레이션 문제입니다. 임의의 스킬이 스킬트리의 패턴과 일치하지 않는 지 확인하는 방법은 아래와 같습니다. 스킬트리의 맨 처음단어부터 패턴과 일치하는 지 idx 변수로 조사하고 있다고 하겠습니다. (일치하는 단어를 찾았다면 idx++) for (int i = 0; i < random_skill.length(); ++i) int position = skill_tree.find(random_skill[i]) 위와 같이 임의의 스킬에서 스킬트리와 일치하는 알파벳을 찾았는데, 이 알파벳의 위치가 idx 변수보다 크다면 아직 앞의 단어가 처리되지 않았는데 뒤에 있는 단어가 먼저 임의의 스킬에서 등장한 것임.. 2020. 5. 10. [코딩테스트 연습] 기지국 설치 문제: https://programmers.co.kr/learn/courses/30/lessons/12979 N제한이 2억, 배열의 크기 10,000 W제한은 10,000 입니다. 큰 숫자 제한을 보면, 단순히 선형탐색만 해도 시간초과가 난다는 걸 알 수 있습니다. 그러므로 선형탐색보다 더 빠르게 탐색을 해야 답이 나오는 걸 알 수 있습니다. 즉, 로그 시간 탐색을 하거나 단순 숫자 계산만으로 해결해야 합니다. 제가 해결한 아이디어입니다. 시작좌표를 0으로 잡고, 전체 station 을 순회합니다. (오름차순 정렬이 되어있으므로) 1. "시작좌표 ~ station[i] 기지국이 커버하는 범위의 하한"을 구합니다. 2. 이 범위 사이에 몇 개의 기지국이 필요한 지 구합니다. 3. 그리고 나서 시작좌표를 ".. 2020. 5. 10. [코딩테스트 연습] 숫자 게임 문제: https://programmers.co.kr/learn/courses/30/lessons/12987 원소 B[i]가 이길 수 있는 A[i]의 원소 중 max(A[i])를 계속 매칭해주면 됩니다. 배열 B의 각 원소에 대한 탐색은 최소 N만큼 이뤄져야 하고, N제한이 10만이므로 O(N^2)이 해가 되면 터집니다. 그러므로 각 원소에 대한 탐색은 logN만에 탐색을 해야 NlogN으로 시간초과를 피할 수 있을 것입니다. 그래서 logN 탐색 방법 중 이분탐색으로 해결하였습니다. A, B 배열 모두를 오름차순으로 정렬한 뒤, B배열의 맨 뒤에서부터 B[i]가 이길 수 있는 A 배열의 숫자 중 가장 큰 수랑 매칭하도록 해줍니다. 코드: https://github.com/cottory/algorithm.. 2020. 5. 10. [BOJ]4358번: 생태학 문제: https://www.acmicpc.net/problem/4358 map이나 트라이 알고리즘으로 해결할 수 있는 문제입니다. 정해는 트라이입니다. 위 코드가 트라이로 해결한 방법이고, 아래 코드가 map으로 해결한 방법입니다. 둘 사이에 왜 이런 시간 차이가 생기냐면, 나무 이름: T (30) 나무의 종류 갯수: N (10,000) 주어지는 나무의 그루 수: M (1,000,000) 트라이를 사용 경우: 하나의 나무를 트라이에 넣을 때 O(T) 만큼의 시간이 걸립니다. map을 사용하는 경우: 하나의 나무를 map에 넣을 때 O(logN * logN)의 시간이 걸립니다. (나무가 map에 있는지 체크하는데 logN, 그리고 map에 나무를 넣는데 logN) 그러므로 트라이 알고리즘의 시간복잡도는 .. 2020. 5. 10. 이전 1 ··· 81 82 83 84 85 86 87 ··· 91 다음
