본문 바로가기

백준198

[백준] 2251번 - 물통 (C++) 문제 및 풀이 문제) 백준 - BFS - 물통 https://www.acmicpc.net/problem/2251 2251번: 물통 각각 부피가 A, B, C(1≤A, B, C≤200) 리터인 세 개의 물통이 있다. 처음에는 앞의 두 물통은 비어 있고, 세 번째 물통은 가득(C 리터) 차 있다. 이제 어떤 물통에 들어있는 물을 다른 물통으로 쏟아 부 www.acmicpc.net a, b, c의 양을 bfs를 통해 탐색합니다. 모든 경우(물 옮겨 담기)를 시행하면서, a가 0일 경우 임의의 배열에 담아 결과를 출력합니다. C++ 소스코드) Full Code) https://github.com/Chocochip101/BOJ_Solution/blob/main/Problem%201000~4999/2251_%EB%AC%BC%ED.. 2021. 12. 31.
[백준] 2533번 - 사회망 서비스(SNS) (C++) 문제 및 풀이 문제) 백준 - DP - 사회망 서비스(SNS) https://www.acmicpc.net/problem/2533 2533번: 사회망 서비스(SNS) 페이스북, 트위터, 카카오톡과 같은 사회망 서비스(SNS)가 널리 사용됨에 따라, 사회망을 통하여 사람들이 어떻게 새로운 아이디어를 받아들이게 되는가를 이해하는 문제가 중요해졌다. 사회망 www.acmicpc.net 양방향 그래프에서 해결할 방법이 떠오르지 않아 단방향 그래프로 바꾼 후에 DP를 통해 순회하며 해결했습니다. DP(node, flag)로 모델링하여 최소 얼리어답터의 수를 memo 합니다. C++ 소스코드) Full Code) https://github.com/Chocochip101/BOJ_Solution/blob/main/Problem%201.. 2021. 12. 30.
[백준] 10826번 - 피보나치 수 4 (Python) 문제 및 풀이 문제) 백준 - DP - 피보나치 수 4 https://www.acmicpc.net/problem/10826 10826번: 피보나치 수 4 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 www.acmicpc.net 큰 수 구현이 귀찮아서 파이썬으로 해결했습니다. Python 소스코드) import sys input = sys.stdin.readline dp = [0 for _ in range(10001)] N = int(input()) dp[0] = 0 dp[1] = 1 for i in range(2, N + 1): dp[i] .. 2021. 12. 30.
[백준] 13549번 - 숨바꼭질 3 (C++) 문제 및 풀이 문제) 백준 - BFS - 숨바꼭질 3 https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 순간 이동하는 경우에 드는 비용이 없으므로, 움직이는 방법에 대해 우선순위를 매겨야 합니다. 우선순위 큐(priority queue)를 이용하여 움직이는 최소 시간이 적은 것부터 방문하게 하며, 순간이동은 비용이 들지 않으므로 걷는 것보다 먼저 방문합니다. C++ 소스코드) Full Code) https://github.co.. 2021. 12. 28.
[백준] 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.
반응형

티스토리툴바