본문 바로가기

PS(Problem Solving)221

[백준] 6593번 - 상범 빌딩 (C++) 문제 및 풀이 문제) 백준 - BFS - 상범빌딩 https://www.acmicpc.net/problem/6593 6593번: 상범 빌딩 당신은 상범 빌딩에 갇히고 말았다. 여기서 탈출하는 가장 빠른 길은 무엇일까? 상범 빌딩은 각 변의 길이가 1인 정육면체(단위 정육면체)로 이루어져있다. 각 정육면체는 금으로 이루어져 있어 www.acmicpc.net 3차원 미로를 탈출할 수 있는 최단 시간을 찾는 문제였습니다. 그래프 탐색에서 최단 시간을 찾을 때, 간선의 비용이 같으면 BFS를 사용합니다. 기본적인 3차원 BFS를 연습하기에 좋은 문제였습니다. C++ 소스 코드) Full Code) https://github.com/Chocochip101/BOJ_Solution/blob/main/Problem%205000~99.. 2022. 1. 6.
[백준] 13023번 - ABCDE (C++) 문제) 백준 - DFS - ABCDE https://www.acmicpc.net/problem/13023 13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net C++ 소스코드) Full Code) https://github.com/Chocochip101/BOJ_Solution/blob/main/Problem%2010000~14999/13023_ABCDE.cpp GitHub - Chocochip101/BOJ_Solution: BOJ Solutions BOJ Solutions. Contribute to Chocochip101/BOJ_Solution development by creating an account on GitHu.. 2022. 1. 5.
[백준] 1956번 - 운동 (C++) 문제 및 풀이 문제) 백준 - 플루이드 와샬 - 운동 https://www.acmicpc.net/problem/1956 1956번: 운동 첫째 줄에 V와 E가 빈칸을 사이에 두고 주어진다. (2 ≤ V ≤ 400, 0 ≤ E ≤ V(V-1)) 다음 E개의 줄에는 각각 세 개의 정수 a, b, c가 주어진다. a번 마을에서 b번 마을로 가는 거리가 c인 도로가 있다는 의 www.acmicpc.net 마을의 개수(V=400)가 충분히 작기 때문에 플루이드 와샬로 최단 거리를 구할 수 있었습니다. 사이클 여부는 최단거리를 구한 후 board [i][j]와 board [j][i]가 존재하면 사이클이 존재하는 것으로 판단하면 됩니다. C++ 소스 코드) Full Code) https://github.com/Chocochip10.. 2022. 1. 5.
[백준] 17471번 - 게리맨더링 (파이썬) 문제 및 풀이 문제) 백준 - BFS - 게리맨더링 https://www.acmicpc.net/problem/17471 17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net 삼성 기출스러운 조합+그래프 탐색 문제였습니다. 조합을 사용할 때, 파이썬 itertools에 내장된 combinations만큼 편한 게 없기 때문에 파이썬의 해결했습니다. N개의 구역 중에 1부터 N//2 구역을 뽑은 후 BFS를 통해 인구 수와 방문한 구역 수를 반환합니다. 마찬가지로, 위에서 뽑은 구역을 제외한 나머지 구역에 대해 인구 수와 구역 수를 계산하여 이전에 계산한 .. 2022. 1. 4.
[백준] 1110번 - 더하기 사이클 (파이썬) 문제 및 풀이 문제) 백준 - 구현 - 더하기 사이클 https://www.acmicpc.net/problem/1110 1110번: 더하기 사이클 0보다 크거나 같고, 99보다 작거나 같은 정수가 주어질 때 다음과 같은 연산을 할 수 있다. 먼저 주어진 수가 10보다 작다면 앞에 0을 붙여 두 자리 수로 만들고, 각 자리의 숫자를 더한다. 그 다음, www.acmicpc.net C++ 소스 코드) 2022. 1. 1.
[백준] 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.
반응형

티스토리툴바