본문 바로가기

분류 전체보기140

[백준] 11967 - 불켜기 https://www.acmicpc.net/problem/11967 11967번: 불켜기 (1, 1)방에 있는 스위치로 (1, 2)방과 (1, 3)방의 불을 켤 수 있다. 그리고 (1, 3)으로 걸어가서 (2, 1)방의 불을 켤 수 있다. (2, 1)방에서는 다시 (2, 2)방의 불을 켤 수 있다. (2, 3)방은 어두워서 갈 수 없으 www.acmicpc.net 이 문제는 단순히 bfs로 풀게 되면, 나중에 불을 켜는 경우에 새로운 경로가 생겨 좀 까다롭게 된다. 본인은 이 문제를 두 방법으로 해결했다. 첫 번째 방법은 불을 켤 수 있는 방에 위치하면 모든 방문 배열을 초기화하고 해당 위치에서 다시 bfs를 돌린다. #include #include #include using namespace std; .. 2022. 8. 17.
[백준] 2637 - 장난감 조립 https://www.acmicpc.net/problem/2637 2637번: 장난감 조립 첫째 줄에는 자연수 N(3 ≤ N ≤ 100)이 주어지는데, 1부터 N-1까지는 기본 부품이나 중간 부품의 번호를 나타내고, N은 완제품의 번호를 나타낸다. 그리고 그 다음 줄에는 자연수 M(3 ≤ M ≤ 100)이 주 www.acmicpc.net dfs + dp 문제이다. 먼저 기본 부품을 구하는 과정은 위상 정렬을 하기 위해 사용하는 입력 간선 배열로 구하였다. 입력 간선의 개수가 0이면, 기본 부품이라는 뜻이다. 답을 구하는 과정은 임의의 부품의 번호 정점부터 완제품까지의 경로의 가중치의 곱이다. 따라서 dp[i] = 완제품을 만들기 위해 필요한 i 부품의 개수 로 정의하였다. 여기서 주의해야 할 점은 dfs.. 2022. 8. 9.
[백준] 15971 - 두 로봇 https://www.acmicpc.net/problem/15971 15971번: 두 로봇 2018년 강원도에서 새로운 동굴이 발견되었다. 이 동굴에는 총 N개의 넓은 방이 존재하며 좁은 통로로 서로 연결되어 있는 것으로 밝혀졌다. N개의 방은 1번부터 N번까지의 번호를 붙여 1번 방, 2번 www.acmicpc.net 두 정점 간의 최단 거리에서, 경로에 포함되어있는 최대 가중치를 빼는 문제이다. dfs를 이용해 s부터 임의의 정점까지의 거리를 구하는 dist배열과 경로 상 최대 가중치를 저장하는 maxW 배열을 채워넣는다. #include #include using namespace std; int n, s, d; vector v; int dist[100001], maxW[100001]; void g.. 2022. 8. 9.
[백준] 5214 - 환승 https://www.acmicpc.net/problem/5214 5214번: 환승 첫째 줄에 역의 수 N과 한 하이퍼튜브가 서로 연결하는 역의 개수 K, 하이퍼튜브의 개수 M이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ K, M ≤ 1000) 다음 M개 줄에는 하이퍼튜브의 정보가 한 줄에 하나씩 주어 www.acmicpc.net 발상의 전환이 필요했던 문제이다. 나는 발상의 전환을 하지 못해서 다른 분의 블로그를 참고했다. 내가 해결하려했던 방법은 입력으로 주어지는 모든 정점 간의 쌍들을 저장하는 것이었다. 하지만 1000 ^ 3의 시간, 공간 복잡도로 통과할 수 없었다. 핵심은 하이퍼튜브 노드를 추가하는 것이다. 링크의 예제 입력 1에서 주어지는 입력으로 설명하면, 1 - 2 - 3 을 연결하.. 2022. 8. 9.
[백준] 1958 - LCS 3 https://www.acmicpc.net/problem/1958 1958번: LCS 3 첫 줄에는 첫 번째 문자열이, 둘째 줄에는 두 번째 문자열이, 셋째 줄에는 세 번째 문자열이 주어진다. 각 문자열은 알파벳 소문자로 이루어져 있고, 길이는 100보다 작거나 같다. www.acmicpc.net 3개의 문자열의 LCS를 구하는 것이다. 처음에는 아래와 같이 생각해서 구현하였고, 틀렸습니다가 나왔다. 문자열을 각각 s1, s2, s3라 하고, LCS(s1, s2)와 LCS(s2, s3)를 구하였다. 그런 다음 LCS(LCS(s1, s2), LCS(s2, s3))를 구하고 답을 출력했다. 하지만 이런 반례가 존재했다. s1: dababcf s2: ababdef s3: df LCS(s1, s2) : abab.. 2022. 8. 9.
[백준] 11780 - 플로이드 2 https://www.acmicpc.net/problem/11780 11780번: 플로이드 2 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 문제 이름에 나와있는 것처럼 플로이드를 활용해서 푸는 문제인데, 출력이 굉장히 길다. 처음 출력은 플로이드를 수행한 결과 배열을 출력하는 것이고, 다음부터는 모든 정점 쌍 i, j에 대하여 i에서 j로 가는 경로중, 최단 경로일 때 거치는 정점을 출력하는 것이었다. 처음 출력은 플로이드-와샬 알고리즘을 이용해서 해결할 수 있다. 하지만 뒷부분의 출력 때문에 이 알고리즘 수행 중에, 경로를 저장.. 2022. 8. 9.
[백준] 2240 - 자두나무 https://www.acmicpc.net/problem/2240 2240번: 자두나무 자두는 자두를 좋아한다. 그래서 집에 자두나무를 심어두고, 여기서 열리는 자두를 먹고는 한다. 하지만 자두는 키가 작아서 자두를 따먹지는 못하고, 자두가 떨어질 때까지 기다린 다음에 떨어 www.acmicpc.net t초간, 처음의 자두의 위치는 1이고, w이하로 움직여 얻을 수 있는 가장 많은 자두의 개수를 구하는 문제이다. 모든 경우의 수를 따져보면 최대 1000초간 30번 움직일 수 있으므로 1000C30이 돼서 불가능하다. 따라서 dp를 이용하고, 다음과 같이 dp 배열을 정의하였다. dp[i][j][k] = i 초에, j 번 움직였으며, k 위치에 있을 때 먹을 수 있는 최대의 자두 개수 또한 이 문제의 특징.. 2022. 8. 9.
[백준] 2617 - 구슬 찾기 https://www.acmicpc.net/problem/2617 2617번: 구슬 찾기 모양은 같으나, 무게가 모두 다른 N개의 구슬이 있다. N은 홀수이며, 구슬에는 번호가 1,2,...,N으로 붙어 있다. 이 구슬 중에서 무게가 전체의 중간인 (무게 순서로 (N+1)/2번째) 구슬을 찾기 위해서 www.acmicpc.net 문제를 처음 봤을 때 구슬... 무게... 순서... 이런 단어가 포함돼 있어서 당연히 위상 정렬일 줄 알았다. 하지만 구하려는 것은 순서가 아닌 정확한 대소 관계를 구해야 했고, 따라서 위상 정렬을 사용할 수 없었다. 먼저 절대 무게가 중간이 될 수 없다는 것은 어떻게 구할 수 있을까? 바로 자신보다 큰 무게의 구슬 또는 작은 무게의 구슬의 개수가 (n + 1) / 2 초과일 .. 2022. 8. 9.
[백준] 1719 - 택배 https://www.acmicpc.net/problem/1719 1719번: 택배 첫째 줄에 두 수 n과 m이 빈 칸을 사이에 두고 순서대로 주어진다. n은 집하장의 개수로 200이하의 자연수, m은 집하장간 경로의 개수로 10000이하의 자연수이다. 이어서 한 줄에 하나씩 집하장간 경 www.acmicpc.net n 제한이 200이므로 플로이드-와샬 알고리즘을 통해 최단 거리를 구할 수 있다. 그러면 최단 경로는 어떻게 구해야 할까? 플로이드-와샬 알고리즘을 살펴보면, for(int k = 0; k < n; k++) { for(int i = 0; i < n; i++) { for(int j = 0; j < n; j++) { //가중치가 최소일 때 업데이트 } } } 이러한 형태로 구현된다. i, j, .. 2022. 8. 9.

티스토리툴바