백준알고리즘15 [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. [BOJ]14425번: 문자열 집합 트라이로 해결한 문제입니다. Map을 통해 해결해도 되지만, 트라이를 사용하면 O(500 * 10000) 정도에 해결할 수 있습니다. 주의해야할 점은, 아래 그림처럼 포함관계가 있는 경우에는 false를 리턴하도록 코드를 짜야합니다. baekjoononlinejudge (트라이에 있는 문자) bakjoon (쿼리로 들어온 문자) 2020. 5. 8. [BOJ]16946번: 벽 부수고 이동하기 4 N, M 제한이 1000 이므로 벽 한 칸당 BFS를 돌아버리면 O(N^2*M^2)으로 시간초과가 납니다. 그러므로 단 한번만 O(NM)에 BFS를 돌려 모든 컴포넌트 정보를 얻어냅니다. 그 후에 벽에서 이동할 수 있는 칸 계산은 move = 1 + 4방향 컴포넌트의 갯수 합이 됩니다. 그래서 O(NM)만에 모든 벽 정보에 대해 벽에서 이동할 수 있는 칸을 계산할 수 있습니다. 단, 함정이 하나있다면, 00000 00000 00100 00000 00000 이와 같이 벽을 둘러싼 컴포넌트가 동일한 형태일 때 4방향을 다 더해주면 중복이 날 것입니다. 그러므로 컴포넌트를 구할 때 하나의 컴포넌트가 다른 컴포넌트와 구분될 수 있도록 조치를 취해야 합니다, 저 같은 경우는 pair의 second 값을 이용했고,.. 2020. 5. 8. 이전 1 2 3 4 다음
