본문 바로가기

C++156

[백준] 7662번 - 이중 우선순위 큐 (C++) 문제 및 풀이 문제) 백준 - 우선순위 큐 - 이중 우선순위 큐 https://www.acmicpc.net/problem/7662 7662번: 이중 우선순위 큐 입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 Q에 적 www.acmicpc.net C++의 multiset을 활용해 해결했습니다. multiset은 중복을 허용한 set으로서 삽입과 삭제를 O(logN)에 처리할 수 있습니다. multiset의 iterator를 사용하여 최대와 최소를 삭제합니다. C++ 소스코드) Full Code) https://github.com/Chocochip101/BOJ_Solution/blob/m.. 2022. 1. 12.
[백준] 20208번 - 진우의 민트초코우유 (C++) 문제 및 풀이 문제) 백준 - 백트래킹 - 진우의 민트초코우유 https://www.acmicpc.net/problem/20208 20208번: 진우의 민트초코우유 첫번째 줄에 민초마을의 크기인 N과 진우의 초기체력 M, 그리고 민트초코우유를 마실때 마다 증가하는 체력의 양 H가 공백을 두고 주어진다. N, M, H는 모두 10보다 작거나 같은 자연수이다. 두번째 www.acmicpc.net 민트초코우유의 개수가 10개 이하이며, 마을의 크기(N)이 10보다 작은 자연수이기에 백트래킹을 활용해 민트초코우유의 최대 개수를 구할 수 있습니다. 민트초코우유의 조표를 저장하는 mint 벡터와 visited를 통해 재귀적으로 백트래킹하며 해결할 수 있었습니다. C++ 소스코드) Full Code) https://github.c.. 2022. 1. 12.
[백준] 7569번 - 토마토 (C++) 문제 및 풀이 문제) 백준 - BFS - 토마토 https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net BFS를 통해 해결했습니다. Queue에 익은 토마토를 넣어주고 dist배열을 통해 방문 여부와 시간을 memo 합니다. 배열에 토마토 익힘 여부를 표시하여 BFS 종료 후, 안 익은 토마토가 있다면 -1을 출력하고 다 익었다면 dist 배열에서 최댓값을 출력합니다. C++ 소스 코드) Full Code) https://github.com/.. 2022. 1. 8.
[백준] 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.
[백준] 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.
[백준] 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.
반응형

티스토리툴바