Algorithm/BOJ172 [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. [BOJ]18809번: Gaaaaaaaaaarden BFS 문제입니다. 이 문제의 시간복잡도는 (경우의 수 생성 x BFS)로 이뤄지기 때문에 1. 경우의 수 생성 방법 2. BFS - O(NM) 둘 중 하나라도 과하게 구현하면 시간초과가 나게 됩니다. 2020. 5. 2. [BOJ]18808번: 스티커 붙이기 바킹독님 모의고사 시뮬레이션 문제입니다. 시간복잡도는 O(4*N*M*K*R*C)을 해도 64,000,000 이므로 제한시간 내에 들어올 수 있습니다. 주어진 상황을 얼마나 잘 나누어 구현했느냐가 중요한 문제입니다. 2020. 5. 2. [BOJ]15655번: N과 M(6) 조합 문제입니다. combination(idx + 1, cnt) combination(idx + 1, cnt + 1) 위 코드 두 줄의 의미가 가장 중요합니다. idx: 배열의 숫자 중 탐색을 수행할 인덱스 번호 cnt: N개 중 현재 몇 개를 뽑았는지 조합은 특정 숫자에 대해 뽑을지/말지를 결정합니다. 그러므로 매 깊이마다 최대 2개로 뻗어나갈 수 있습니다. 이를 통해 특정 숫자 num[idx]를 뽑을 수 있다면, 특정 숫자를 뽑는 combination(idx+1,cnt+1)과 뽑지 않는 combination(idx+1,cnt)을 모두 수행하고, 특정 숫자가 이미 사용되어 뽑을 수 없다면 뽑지 않는 combination(idx+1,cnt)만 수행해줍니다. 2020. 3. 6. 이전 1 ··· 40 41 42 43 다음
