🔗 문제 23290번: 마법사 상어와 복제 23290번: 마법사 상어와 복제 첫째 줄에 물고기의 수 M, 상어가 마법을 연습한 횟수 S가 주어진다. 둘째 줄부터 M개의 줄에는 물고기의 정보 fx, fy, d가 주어진다. (fx, fy)는 물고기의 위치를 의미하고, d는 방향을 의미한다. 방향 www.acmicpc.net ✏️ 풀이 일단 이 문제는 내가 무려 밍기적 거리는 시간 포함해서 2주 동안 못 풀고 있던 것입니다. 이유는 예제 4, 5, 8에서 오답이 나와서, 다음은 예제 5번이 안 나와서. 총 2번의 대수정을 거쳐서 메모리 2028KB, 0ms로 문제로 맞았습니다!! 를 보게 됐다. 풀이 안 쓰려고 했는데 나한테도 도움될 것 같아서 오랜만에 자세히 써보고자 한다.. 문제를 읽으면 알겠지만, 간단하..

🔗 문제 https://softeer.ai/practice/info.do?idx=1&eid=582 Softeer 연습문제를 담을 Set을 선택해주세요. 취소 확인 softeer.ai ✏️ 풀이 다익스트라 문제다. (1) 출발 지점이 주어져있고, (2) 양방향이며, (3) 가중치가 양수다. 무엇보다 출발 지점에서 특정지점까지 필요한 값을 출력해야한다는게 다익스트라문제라는 큰 힌트다. 다익스트라를 학습할 때 주로 사용하는 최소 경로가 아니라 최소 레벨을 구해야하는게 작은 차이일 뿐이다. 정석 다익스트라 풀이로 priority_queue를 이용했다. dp[node]에 1에서 node까지 가는 가장 큰 레벨을 저장한다. 문제의 제약조건을 보면 총 노드의 수는 $2 ≤ N ≤ 10,000$ 로 한정되어 있다. 가..

🔗 문제 11404번: 플로이드 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net ✍️ 풀이 제목부터 거저주는 플로이드 기초 문제 모든 도시의 쌍 (A, B)에 대해서 도시 A에서 B로 가는데 필요한 비용의 최솟값을 구하는 프로그램을 작성하시오. 플로이드 와샬이다. 시작 도시와 도착 도시를 연결하는 노선은 하나가 아닐 수 있다. 그렇다면 A→B 중 가장 작은 비용 값을 저장하자. 💾 소스 #include #include #include const int INF = 1e9; std::vector adj; int N..

🔗 문제 1389번: 케빈 베이컨의 6단계 법칙 1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻 www.acmicpc.net ✍️ 풀이 무방향 그래프에서 모든 정점의 최단 경로를 구해야 한다? 플로이드 와샬 문제였다. 주의 사항 무방향 그래프이므로 a→b면 b→a임을 잊지 말자. 플로이드 와샬이 방문하지 않은 인접행렬의 초기값은 INF이지만 이 문제에서 자기 자신으로 가는 값은 0으로 설정하는 것에 유의해야 한다. 출발노드가 중간노드나 목적지가 되는건 찾을 필요가 없다. 💾 소스 #incl..

🔗 문제 1956번: 운동 1956번: 운동 첫째 줄에 V와 E가 빈칸을 사이에 두고 주어진다. (2 ≤ V ≤ 400, 0 ≤ E ≤ V(V-1)) 다음 E개의 줄에는 각각 세 개의 정수 a, b, c가 주어진다. a번 마을에서 b번 마을로 가는 거리가 c인 도로가 있다는 의 www.acmicpc.net ✍️ 풀이 방향 그래프로 표현되는 경로에, 두 정점의 최단 거리를 구한다? 플루이드 와샬을 이용해서 푼다. 그래프가 주어졌을 때 두 정점의 최단 거리를 구할 때 사용한다. 그래프를 인접 행렬로 표현하며, 아직 경로를 찾지 못한 곳은 INF이다. 플루이드 와샬의 핵심은 a→b로 이동하고자 할때 중간 노드를 고려한다는 점이다. O(V^3)의 시간이 걸리지만 v가 400으로 작은 축에 속해서 문제를 풀 수 ..

🔗 문제 1949번: 우수 마을 1949번: 우수 마을 첫째 줄에 정수 N이 주어진다. (1 ≤ N ≤ 10,000) 둘째 줄에는 마을 주민 수를 나타내는 N개의 자연수가 빈칸을 사이에 두고 주어진다. 1번 마을부터 N번 마을까지 순서대로 주어지며, 주민 수는 10,00 www.acmicpc.net ✍️풀이 문제를 읽어보면 트리 구조의 마을에 정점에 가중치가 주어진다. 마을은 인접한 마을끼리 우수마을이 될 수 없으며, 우수 마을이 아닌 곳은 적어도 하나의 우수 마을과 인접해야 한다. 어떤 노드를 선택했을 때, 그 마을을 우수 마을로 하느냐 하지 않느냐에 따라서 어떤 합이 나올지 몰라 계산이 필요한 식이다. 그냥 여기서 dp가 떠올랐다. 하지만 .. 어떻게 문제를 풀지는 감이 잡히지 않아서 인터넷의 도움을..

🔗 문제 1937번: 욕심쟁이 판다 1937번: 욕심쟁이 판다 n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에 www.acmicpc.net n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 대나무를 먹는다. 그런데 단 조건이 있다. 이 판다는 매우 욕심이 많아서 대나무를 먹고 자리를 옮기면 그 옮긴 지역에 그 전 지역보다 대나무가 많이 있어야 한다. 이 판다의 사육사는 이런 판다를 대나무 숲에 풀어 놓..

🔗 문제 1676번: 팩토리얼 0의 개수 1676번: 팩토리얼 0의 개수 N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오. www.acmicpc.net 🖍 풀이 아래 블로그를 읽고 이해한 문제 🔗https://sdev.tistory.com/808 [C/C++] 백준 #1676 팩토리얼 0의 개수(수학) 이번 문제는 팩토리얼을 계산했을 때, 뒤에서부터 연속된 0의 개수를 세는 것입니다. 팩토리얼은 1부터 n까지의 곱을 계산한 것인데요. 20 팩토리얼만 해도 2,432,902,008,176,640,000 값이 나와서 정수 sdev.tistory.com 문제 조건이 N ≤ 500으로 factorial(500)을 하면 엄청나게 긴 숫자에 시간초과가 뜰 수 있다. ..

🔗 문제 11403번: 경로 찾기 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 길이가 양수인 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 길이가 양수인 경로가 있는지 없는지 🖍 풀이 DFS를 이용하여 풀었다. N개의 각 정점으로 부터 DFS를 이용해 연결된 모든 정점을 visited로 표시했다. 여기서 DFS에서 사이클을 무한반복하지 않도록 방문하지 않은 정점으로만 가는 조건을 반드시 걸어주어야 한다. 💾 소스 #include const int MAX = 100 + 1; bool graph[MAX]..

🔗 문제 16137번: 견우와 직녀 16137번: 견우와 직녀 견우와 직녀는 여러 섬과 절벽으로 이루어진 지역에서 살고 있다. 이 지역은 격자로 나타낼 수 있으며, 상하좌우로 인접한 칸으로 가는 데 1분이 걸린다. 7월 7일은 견우와 직녀가 오작교를 건너 www.acmicpc.net 문제 정리 (0, 0)에서 (N-1, N-1)로 최소 이동 시간 구하기 N (2 ≤ N ≤ 10) 상하좌우로 이동할 수 있으며 한칸 당 1분 소요 맵 구성요소 1: 이동할 수 있는 일반적인 땅 0: 건널 수 없는 절벽 2 이상의 수: 적혀있는 수 만큼의 주기를 가지는 오작교 오작교 특징 M(2 ≤ M ≤ 20)분 주기에만 오작교가 생성되어 절벽을 건너갈 수 있다. 🖍 풀이 문제 꼼꼼히 보기 오작교는 이처럼 매우 불안정하므로,..