C++156 [백준] 11562번 - 백양로 브레이크 (C++) 문제 및 풀이 문제) 백준 - 플루이드 와샬 - 백양로 브레이크 https://www.acmicpc.net/problem/11562 11562번: 백양로 브레이크 서울 소재 Y모 대학교에서 대규모 공사를 진행하면서, 학교가 마치 미로처럼 변해버리고 말았다. 공사 이전까지는 어떤 건물에서 출발하더라도 다른 모든 건물로 갈 수 있는 길이 있었으나, 공 www.acmicpc.net 건물의 수(n)가 250 이하이기 때문에 O(n^3)의 시간 복잡도를 가진 플루이드 와샬로 풀이가 가능합니다. 양방향 길은 모두 0, 일방통행 길은 한 방향은 0으로 나머지는 1로 부여해 플루이드 와샬을 진행합니다. C++ 소스코드) Full Code) https://github.com/Chocochip101/BOJ_Solution/blob/ma.. 2022. 1. 19. [백준] 21924번 - 도시 건설 (C++) 문제 및 풀이 문제) 백준 - 최소 스패닝 트리 - 도시 건설 https://www.acmicpc.net/problem/21924 21924번: 도시 건설 첫 번째 줄에 건물의 개수 $N$ $(3 \le N \le 10^5 )$와 도로의 개수 $M$ $(2 \le M \le min( {N(N-1) \over 2}, 5×10^5)) $가 주어진다. 두 번째 줄 부터 $M + 1$줄까지 건물의 번호 $a$, $b$ $(1 \le a, b \le N, a ≠ b)$와 두 www.acmicpc.net 전형적인 최소 스패닝 트리 문제입니다. rank를 이용한 Disjointset과 kruskal 알고리즘을 이용하여 최소 비용을 구합니다. 비용의 개수로 모든 도시 연결 여부를 판단하여 -1 또는 절약 예산을 구합니다. C++ 소.. 2022. 1. 18. [백준] 2745번 - 진법 변환 (C++) 문제 및 풀이 문제) 백준 - 구현 - 진법 변환 https://www.acmicpc.net/problem/2745 2745번: 진법 변환 B진법 수 N이 주어진다. 이 수를 10진법으로 바꿔 출력하는 프로그램을 작성하시오. 10진법을 넘어가는 진법은 숫자로 표시할 수 없는 자리가 있다. 이런 경우에는 다음과 같이 알파벳 대문자를 www.acmicpc.net 문자열을 입력받아 진법 변환하는 쉬운 문제였습니다. C++ 소스코드) 2022. 1. 18. [백준] 18312 - 시간 (C++) 문제 및 풀이 문제) 백준 - 구현 - 시각 https://www.acmicpc.net/problem/18312 18312번: 시각 정수 N과 K가 입력되었을 때 00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중에서 K가 하나라도 포함되는 모든 시각을 세는 프로그램을 작성하시오. 시각을 셀 때는 디지털 시계를 기준으로, www.acmicpc.net 각 시, 분, 초를 완전 탐색합니다. C++ 소스 코드) 2022. 1. 17. [백준] 10653번 - 마라톤 2 (C++) 문제 및 풀이 문제) 백준 - 동적 계획법 - 마라톤 2 https://www.acmicpc.net/problem/10653 10653번: 마라톤 2 젖소 박승원이 2번째 와 4번째 체크포인트를 건너뛸경우 경로는 (0,0) -> (1,1) -> (2,2) 로 4가 된다. 이보다 더 짧게 달릴수는 없다. www.acmicpc.net 모든 체크 포인트의 좌표를 입력 받아 거리를 미리 계산합니다. 그 후, 체크 포인트를 뛰어넘는 경우와 그렇지 않는 경우로 각 최소 거리를 계산합니다. C++ 소스코드) Full Code) https://github.com/Chocochip101/BOJ_Solution/blob/main/Problem%2010000~14999/10653_%EB%A7%88%EB%9D%BC%ED%86%A4%202... 2022. 1. 17. [백준] 19942번 - 다이어트 (C++) 문제 및 풀이 문제) 백준 - 백트래킹 - 다이어트 https://www.acmicpc.net/problem/19942 19942번: 다이어트 식재료 N개 중에서 몇 개를 선택해서 이들의 영양분(단백질, 탄수화물, 지방, 비타민)이 일정 이상이 되어야 한다. 아래 표에 제시된 6가지의 식재료 중에서 몇 개를 선택해서 이들의 영양분의 각 www.acmicpc.net 맨 처음에 문제를 읽고 DP를 생각했으나, N이 15 이하인것을 보니 백트래킹으로 충분히 해결할 수 있었습니다. temp 벡터에 인덱스를 집어 넣어, res 벡터에 조건을 만족하는 인덱스 벡터를 넣어 정렬하여 출력합니다. C++ 소스코드) Full Code) https://github.com/Chocochip101/BOJ_Solution/blob/main/P.. 2022. 1. 16. [백준] 2629번 - 양팔저울 (C++) 문제 및 풀이 문제) 백준 - 동적 계획법 - 양팔저울 https://www.acmicpc.net/problem/2629 2629번: 양팔저울 첫째 줄에는 추의 개수가 자연수로 주어진다. 추의 개수는 30 이하이다. 둘째 줄에는 추의 무게들이 자연수로 가벼운 것부터 차례로 주어진다. 같은 무게의 추가 여러 개 있을 수도 있다. 추의 무 www.acmicpc.net 추의 인덱스와 한쪽 저울에 올린 무게를 memoization을 적용하여 동적 계획법을 진행합니다. 추를 올릴 경우, 추를 올리지 않을 경우, 반대쪽에 올릴 경우를 생각하여 해결합니다. C++ 소스코드) Full Code) https://github.com/Chocochip101/BOJ_Solution/blob/main/Problem%201000~4999/26.. 2022. 1. 15. [백준] 20365번 - 블로그2 (C++) 문제 및 풀이 문제) 백준 - Greedy - 블로그2 https://www.acmicpc.net/problem/20365 20365번: 블로그2 neighbor 블로그를 운영하는 일우는 매일 아침 풀고 싶은 문제를 미리 정해놓고 글을 올린다. 그리고 매일 밤 각각의 문제에 대하여, 해결한 경우 파란색, 해결하지 못한 경우 빨간색으로 칠한 www.acmicpc.net 주어진 문자열의 연속된 R, B를 하나로 줄인 후, 최소로 사용된 것을 선택하면 됩니다. C++ 소스코드) 2022. 1. 14. [백준] 15658번 - 연산자 끼워넣기 (2) (C++) 문제 및 풀이 문제) 백준 - 백트래킹 - 연산자 끼워넣기(2) https://www.acmicpc.net/problem/15658 15658번: 연산자 끼워넣기 (2) 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1보다 크거나 같고, 4N보다 작거나 같은 4개의 정수가 주어지는데, 차례대 www.acmicpc.net 처음에 permutations를 활용하기 위해 파이썬으로 시도했다가 TLE로 틀려, C++을 통한 백트래킹으로 해결했습니다. 부분합, 인덱스, 4가지 연산자의 개수를 매개변수로 백트래킹을 적용합니다. C++ 소스코드) Full Code) https://github.com/Chocochip1.. 2022. 1. 13. 이전 1 ··· 6 7 8 9 10 11 12 ··· 18 다음 반응형
