본문 바로가기

PS(Problem Solving)221

[백준] 17142번 - 연구소 3 (Python) 문제 및 풀이 문제) 백준 - BFS - 연구소 3 https://www.acmicpc.net/problem/17142 17142번: 연구소 3 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고 www.acmicpc.net 백트래킹을 이용한 조합 구현이 귀찮아 파이썬의 combination을 이용해 활성화된 바이러스의 조합을 구합니다. 활성화된 바이러스를 뽑아서 각 경우의 수마다 BFS를 실행하여 최소 시간을 구하면 해결할 수 있습니다. Python 소스코드) Full Code) https://github.com/Chocochip101/BOJ_Solution/blob/main/Proble.. 2021. 12. 26.
[백준] 9205번 - 맥주 마시면서 걸어가기 (C++) 문제 및 풀이 문제) 백준 - DFS - 맥주 마시면서 걸어가기 https://www.acmicpc.net/problem/9205 9205번: 맥주 마시면서 걸어가기 송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다. www.acmicpc.net 좌표를 모두 입력받아 20*50을 넘는 점을 제외하고 graph에 인접 리스트 형태로 나타냅니다. DFS를 통해 탐색하면서 visited [N+1] 번째를 방문 여부에 따라 'happy' 또는 'sad'를 출력합니다. C++ 소스코드) Full code) https://github.com/Chocochip101/BOJ_Solution/blob.. 2021. 12. 26.
[백준] 2636번 - 치즈 (C++) 문제 및 풀이 문제) 백준 - BFS - 치즈 https://www.acmicpc.net/problem/2636 2636번: 치즈 아래 과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(에서 네모 칸에 X친 부분)에는 치즈가 놓 www.acmicpc.net BFS로 board에서 치즈 개수를 탐색하며 0으로 바꿉니다. prevCheeze로 이전 치즈의 개수를 저장하고 cntCheeze가 0이면 break 합니다. C++ 풀이) Full Code) https://github.com/Chocochip101/BOJ_Solution/blob/main/Problem%201000~4999/2636_%EC%B9%98%EC%A6%88.cpp GitHu.. 2021. 12. 23.
[백준] 5582번 - 공통 부분 문자열 (C++) 문제 및 풀이 문제) 백준 - 동적 계획법 - 공통 부분 문자열 https://www.acmicpc.net/problem/5582 5582번: 공통 부분 문자열 두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오. 어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예를 들 www.acmicpc.net LCS랑 유사한 연속된 공통 문자열을 찾는 문제였습니다. LCS를 풀어봤다면 쉽게 풀 수 있는 문제입니다. C++ 소스코드) 2021. 12. 22.
[백준] 10803번 정사각형 만들기 (C++) 문제 및 풀이 문제) 백준 - 동적 계획법 - 정사각형 만들기 https://www.acmicpc.net/problem/10803 10803번: 정사각형 만들기 두 변의 길이가 모두 양의 정수인 직사각형 모양의 종이가 주어져 있다. 이 종이를 칼로 여러 번 잘라서 모든 조각이 한 변의 길이가 양의 정수인 정사각형이 되도록 하고자 한다. 칼로 종이를 www.acmicpc.net 쉬운 DP문제일 줄 알았으나, TLE에서 최적화하느라 꽤 걸린 문제였습니다. (i)의 방법으로 1~n/2, 1~m/2까지 자릅니다. 하지만 큰 수에서 O(n*m)의 연산이 필요하기 때문에 큰 수에서는 (ii) 방법을 이용하여 최소 정사각형 개수를 구합니다. C++ 소스코드) Full Code) https://github.com/Chocochip1.. 2021. 12. 20.
[백준] 1213번 - 팰린드롬 만들기 (C++) 문제 및 풀이 문제) 백준 - 구현 - 팰린드롬 만들기 https://www.acmicpc.net/problem/1213 2021. 12. 20.
[백준] 1043번 - 거짓말 (C++) 문제 및 풀이 문제) 백준 - Union Find - 거짓말 https://www.acmicpc.net/problem/1043 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net N이 50 이하이기 때문에 알고리즘 유형이 Union Find인 것을 직감하셨으면 쉽게 풀 수 있었던 문제입니다. C++ 소스 코드) Full Code) https://github.com/Chocochip101/BOJ_Solution/blob/main/Problem%201000~4999/1043_%EA%B1%B0%EC%A7%93%EB%A7%90.cpp GitHu.. 2021. 12. 16.
[백준] 13913번 숨바꼭질 4 (C++) 문제 및 풀이 문제) 백준 - BFS - 숨바꼭질 4 https://www.acmicpc.net/problem/13913 13913번: 숨바꼭질 4 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net BFS를 통해 탐색하면서 동생의 위치를 찾는 문제였습니다. tr 배열을 이용해 방문했던 이전 점의 좌표를 저장했습니다. 그 후 반복문을 통해 이동한 자취를 출력했습니다. C++ 소스코드) Full Code) https://github.com/Chocochip101/BOJ_Solution/blob/main/Problem%201.. 2021. 12. 14.
[백준] 1766번 - 문제집 (C++) 문제 및 풀이 문제) 백준 - 위상 정렬 - 문제집 https://www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 문제를 세 개의 조건에 맞게 출력하는 문제였습니다. 조건 2(먼저 푸는 것이 좋은 문제가 있는 문제는, 먼저 푸는 것이 좋은 문제를 반드시 먼저 풀어야 한다)를 통해 위상 정렬을 사용해야됨을 알 수 있습니다. 조건 3(가능하면 쉬운 문제부터 풀어야 한다)을 통해 위상 정렬 Queue 내부에서 정렬이 필요함을 알 수 있는데 이 정렬.. 2021. 12. 13.
반응형

티스토리툴바