프로그래머스69 [코딩테스트 연습] 배달 문제: https://programmers.co.kr/learn/courses/30/lessons/12978 기본적인 다익스트라 문제입니다. 1. N제한이 크지 않고 2. "두 마을 a, b를 연결하는 도로는 여러 개가 있을 수 있습니다." 위 두 가지 이유 때문에 인접리스트보다 인접행렬로 최소 비용의 간선만 저장하도록 그래프를 구현하였습니다. 1번 마을은 무조건 배달이 되므로, 2번 부터 N번 마을까지 다익스트라를 돌려서 dist[N] 2020. 5. 11. [코딩테스트 연습] 스킬트리 문제: 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. 이전 1 ··· 14 15 16 17 18 다음
