Algorithm283 [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. [코딩테스트 연습] 방문 길이 2차원 배열 위를 탐색하면서 중복되지 않은 Edge의 개수를 구하는 문제입니다. Edge는 (시작점좌표, 끝점좌표) 두 개의 정보를 가지고 있습니다. 이를 다양한 저장방식으로 저장하면 됩니다. 1. visit[11][11][11][11] 2. 좌표 1개를 하나의 int로 만들어서, 두 좌표를 두 int로 만든 후set로 관리 3. 좌표 4개를 하나의 스트링으로 묶어서 set으로 관리 단, 첫 번째 방식은 그래프 크기가 100만 넘어가도 메모리 초과가 나므로 지양해야 합니다. 2020. 5. 9. [2018 카카오 기출] 셔틀버스 시뮬레이션 문제입니다. 버스를 객체로 만든 후, 벡터로 관리해줍니다. 그리고 콘을 제외한 나머지 승객들이 버스를 탄 상황을 셋팅해줍니다. 두 가지 경우로 답을 나눌 수 있을 것입니다. 1. 버스를 탈 수 있는 경우 → 그냥 마지막에 온 빈 버스에 타면 됩니다. 2. 버스를 탈 수 없는 경우 → 콘이 봐야할 거는 한 가지입니다. 마지막 버스에 탄, 마지막 승객만 이기면 됩니다. 그 승객보다 1분만 먼저 타면 그게 정답이 됩니다. 2020. 5. 9. [BOJ]14425번: 문자열 집합 트라이로 해결한 문제입니다. Map을 통해 해결해도 되지만, 트라이를 사용하면 O(500 * 10000) 정도에 해결할 수 있습니다. 주의해야할 점은, 아래 그림처럼 포함관계가 있는 경우에는 false를 리턴하도록 코드를 짜야합니다. baekjoononlinejudge (트라이에 있는 문자) bakjoon (쿼리로 들어온 문자) 2020. 5. 8. 이전 1 ··· 63 64 65 66 67 68 69 ··· 71 다음
