Algorithm/BOJ172 [BOJ]13116번: 30번 문제: https://www.acmicpc.net/problem/13116 수학 문제입니다. 최대 1024개의 노드가 있을 때 임의의 두 수가 주어지면 최대 공통 조상을 찾아야 합니다. 최대 공통 조상을 찾는 방법은 힙의 원리처럼 주어진 수 / 2 를 계속해서 1까지 가보면 거쳐가는 모든 수가 자신의 조상 노드입니다. 쿼리가 최대 5만개이고, 하나의 쿼리를 처리하는데 걸리는 시간은 O(10) 입니다. (최대 노드 크기가 1023이고 1023도 2^10 이기 때문에 나누기 2 연산의 최대 깊이는 10을 넘지않습니다.) 문제를 해결하는 방법은 여러가지입니다. 저는 주어진 수를 작은 수, 큰 수로 나눴고 작은 수가 거쳐간 모든 조상을 표시한 뒤, 큰 수의 모든 조상을 구하면서 한 번이라도 작은 수의 조상과 일.. 2022. 3. 17. [BOJ]14425번: 문자열 집합 문제: https://www.acmicpc.net/problem/14425 트라이 문제입니다. N, M 제한이 1만이므로 정직하게 2중 포문을 돌면 시간초과가 납니다. 트라이 자료구조에 대한 설명: https://www.notion.so/Trie-875eeb41921f4559b87a38f1e4136e7e 트라이를 사용하면 하나의 문자열에 대해 최대 문자열의 길이만큼만 탐색이 이뤄지기 때문에 O(500*M) 으로 통과할 수 있습니다. 코드: https://github.com/cotchan/algorithm/blob/main/BOJ/BOJ14425.java 2022. 3. 15. [BOJ]1327번: 소트 게임 문제: https://www.acmicpc.net/problem/1327 브루트 포스(완전 탐색)을 통해 해결할 수 있습니다. 브루트 포스 방법은 BFS를 사용하였습니다. 큐에서 하나씩 숫자를 뽑은 후 그 숫자를 처음 인덱스부터 N-K인덱스까지 순회하며 K 범위 내 숫자를 전부 뒤집고 다시 큐에 집어넣습니다. 이 작업을 반복하며 해당 숫자가 오름차순으로 나오는 경우를 리턴해줍니다. 코드: https://github.com/cotchan/algorithm/blob/main/BOJ/BOJ1327.java 2022. 3. 7. [BOJ]20040번: 사이클 게임 문제: https://www.acmicpc.net/problem/20040 유니온/파인드 문제입니다. 진행된 차례 m의 상한이 100만이므로 한 차례마다 사이클 탐색에 O(M)이 소모되면 O(M^2)으로 시간초과가 됩니다. 그러므로 현재 차례에서 사이클을 탐색하는데 시간을 줄여야 시간 초과가 나지 않습니다. 사이클 판별 방법 1. 매 두 점이 들어올 때 마다 두 점을 union 연산으로 같은 컴포넌트로 연결시켜줍니다. 2. 특정 차례에서 들어온 두 점이 이미 같은 컴포넌트에 있다면, 이 둘을 연결시키면 싸이클이 만들어집니다. 싸이클 판별인 find 연산에 O(logM)이 걸리므로 시간 복잡도는 O(MlogM)입니다. 코드: https://github.com/cotchan/algorithm/blob/mai.. 2022. 3. 6. 이전 1 ··· 5 6 7 8 9 10 11 ··· 43 다음
