BOJ75 [BOJ]15787번: 기차가 어둠을 헤치고 은하수를 문제: https://www.acmicpc.net/problem/15787 시뮬레이션 + 비트마스킹 문제입니다. M개의 명령에 대해서는 시뮬레이션으로 처리를 하고, 은하수를 건너는 기차의 조건은 비트마스킹으로 상태를 표현 후 Set에 저장 후 Set의 사이즈를 리턴하면 됩니다. 코드: https://github.com/cotchan/algorithm/blob/main/BOJ/BOJ15787.java 2022. 4. 12. [BOJ]4195번: 친구 네트워크 문제: https://www.acmicpc.net/problem/4195 유니온, 파인드 문제입니다. 주어지는 친구 관계가 최대 10만이고, 한 번 친구 관계를 조회할 때 최대 10만개까지 노드를 탐색할 수 있습니다. (BFS, DFS 기준) 그러므로 O(10만^2) 으로 시간초과가 납니다. 그래서 노드 탐색 시간을 log시간으로 줄여야 시간 초과를 해결할 수 있습니다. 노드 탐색 시간을 log 시간으로 내리는 방법은 친구 관계가 주어질 때 마다 유니온, 파인드를 사용하여 컴포넌트 간에 연결 관계를 맺어줍니다. 새로운 관계를 맺는다면 친구 관계는 component1 + component2의 합이 될 것이고 이미 맺어진 관계(같은 컴포넌트에 속함)라면 component1 이나 component2 중 하나의.. 2022. 3. 2. [BOJ]1976번: 여행 가자 문제: https://www.acmicpc.net/problem/1976 N제한이 작으므로 완전 탐색으로 해결할 수 있습니다. 여행 계획 E-C-B-C-D를 예시로 설명해보면, 여행 계획을 출발지-도착지 관계로 E-C, C-B, B-C, C-D로 나눈 후 각 각을 방문할 수 있는지 DFS로 조사합니다. 시간복잡도는 O(N^2*M)으로 최악의 경우에도 O(40,000,000)이므로 시간 제한에 걸리지 않습니다 :) 코드: https://github.com/cotchan/algorithm/blob/main/BOJ/BOJ1976.java 2022. 3. 2. [BOJ]2493번: 탑 https://www.acmicpc.net/problem/2493 스택으로 해결할 수 있는 문제입니다. 1. 입력으로 주어지는 탑의 높이를 큐 자료구조에 저장합니다. 2. 큐에서 나오는 각 element에 대해 필요한 연산을 하고 저장을 할 스택(rest)을 만듭니다. - 스택의 의미는 현재 큐에 나오는 element가 쏘는 레이저를 송신하는 탑을 의미합니다. 3. 큐에서 하나씩 element를 뽑으면서 내 레이저를 송신할 탑을 찾습니다. -1 현재 스택의 TOP에 있는 탑의 높이가 현재 element 탑의 높이보다 높다면 => ---- 현재 element의 레이저를 송신하는 탑으로 스택의 TOP을 저장하고 현재 element를 스택에 push합니다. -2 현재 스택의 TOP에 있는 탑의 높이가 현재 e.. 2021. 6. 18. 이전 1 2 3 4 5 6 7 ··· 19 다음
