백준34 [BOJ]1766번: 문제집 www.acmicpc.net/problem/1766 문제들 간에 우선순위가 존재하므로 위상 정렬로 해결할 수 있는 문제입니다. 1st. 자기 보다 선행 되어야 하는 문제가 없고 parentCnt[now_problem] == 0 2nd. 난이도는 쉬운 문제부터 풀어야 한다. 두 가지 가중치가 존재하므로 이 두 가지 값을 가중치로 놓는 최소힙을 선언해서 최소힙에서 현재 풀 수 있는 문제 후보부터 뽑아내면 됩니다. 코드: github.com/cotchan/algorithm/blob/main/cpp/BOJ/BOJ1766.cc 2021. 3. 4. [BOJ]17142번: 연구소3(py) www.acmicpc.net/problem/17142 시뮬레이션 문제입니다. n개의 바이러스 위치 중에 m개를 뽑아서 최소를 찾는 문제이므로 조합(combination)을 통해 해결할 수 있습니다. 한 가지 주의 사항은 바이러스의 종류와 무관하게 빈 칸(0)만 채우면 됩니다. 그러므로 탐색을 종료 조건은 BFS로 채운 빈 칸의 숫자가 주어진 입력의 0칸 갯수와 동일하면 됩니다. 코드: github.com/cotchan/algorithm/blob/main/python/BOJ/BOJ17142.py 2021. 2. 3. [BOJ]19236번: 청소년 상어 www.acmicpc.net/problem/19236 시뮬레이션 문제입니다. 어떻게 움직여야하는 지는 문제 꼼꼼히 읽어보면 아실테니 그것보다는 푸시면서 신경써야할 예외케이스에 대해 말하겠습니다. 1. DFS로 푸시든 BFS로 푸시든 매 상태의 2차원 그래프는 서로 분리되어 있어야 합니다. 그냥 매 깊이 갈 때 마다 copy를 하시든, 아니면 가공하고 다시 원상복귀를 하시든 매 상태는 구분되어야 합니다. 즉 탐색하고 빠져나오면 다시 원래 상태에서 다음 탐색을 시작해야된다는 의미입니다. 이게 머릿속에서 꼬이시면 시뮬레이션은 답이 없습니다. 2. 물고기들이 이동하는 시점을 처리할 때 각 물고기는 한 번만 이동해야 합니다. 저 같은 경우는 그냥 2차원 배열 다 뒤지면서 숫자 작은 것부터 이동시켰는데요. //BA.. 2020. 9. 17. [BOJ]1865번: 웜홀 www.acmicpc.net/problem/1865 라이님 블로그(blog.naver.com/kks227/220796963742)의 풀이를 참고하여 해결했습니다. 임의의 정점에 대해 모두 벨만포드를 돌 수 없으므로 그래프를 BFS 탐색을 통해 컴포넌트로 나눠주고, 각 각의 컴포넌트에 대해서만 한 번씩 벨만포드를 돌면 됩니다. 하나의 컴포넌트라도 컴포넌트내에 음의 싸이클이 있다면 YES, 아니면 NO를 출력하면 됩니다. 코드: github.com/cottory/algorithm/blob/master/BOJ/BOJ1865.cc 2020. 9. 11. 이전 1 2 3 4 5 6 ··· 9 다음
