개발조아

문제 링크 : https://www.acmicpc.net/problem/20010 20010번: 악덕 영주 혜유 FT온라인 게임에서 치열한 경쟁을 통해 영주가 된 혜유는 퀘스트를 받았다. 퀘스트의 내용은 자신이 관리하고 있는 마을 사이에 교역로를 건설하여 마을 간 교류를 활성화시키는 것이다. 이때, www.acmicpc.net MST와 DFS로 풀이 했다. 첫번째 답은 모든 마을을 연결하는 최소 비용을 출력해야하므로 MST 로 구한다. 두번째 답은 마을과 마을 사이의 최단 경로 중 비용이 가장큰 경로 이므로 BFS나 다익스트라로 구하면 된다. MST는 크루스칼로 구현했다. MST를 구성하면서 BFS에서 사용할 그래프를 인접리스트로 저장했다. 인접리스트 중 길이가 1인 점에서만 BFS를 수행했다. 끝에서 ..

문제 링크 : https://www.acmicpc.net/problem/3108 3108번: 로고 로고는 주로 교육용에 쓰이는 프로그래밍 언어이다. 로고의 가장 큰 특징은 거북이 로봇인데, 사용자는 이 거북이 로봇을 움직이는 명령을 입력해 화면에 도형을 그릴 수 있다. 거북이는 위치와 www.acmicpc.net BFS로 풀이 했다. 문제를 정리하면 한붓 그리기를 위해선 붓을 맵에 놓아야하는데 이때 붓을 몇번 놓는지 구하면 된다. 내 풀이의 핵심은 도형의 크기를 두배 확장하는 것이다. 나는 BFS를 통해서 한붓그리기가 가능한지 판별한다. 근데 테두리가 겹치는 것만 한붓그리기가 가능하지만 BFS를 수행하면 동서남북으로 인접한 곳을 확인하게 된다. 그러면 사각형안에 사각형이 있는 경우고 가능하다고 판별하게 ..

문제 링크 : https://www.acmicpc.net/problem/23034 23034번: 조별과제 멈춰! 교수님이 시험 기간에 조별 과제를 준비하셨다...! 가톨릭대학교의 조교 아리는 N명의 학생을 2개의 조로 구성하여 과제 공지를 하려 한다. 이때, 구성된 각 조의 인원은 1명 이상이어야 한다. 각 www.acmicpc.net MST와 BFS로 풀었다. 처음에는 단순하게 MST 구성해서 가중치 합 구하고 x,y의 간선 정보만을 보고 빼주면 될줄 알고 제출했더니 틀렸다. 당연하다. 문제는 두개의 점을 기준으로 두개의 MST를 만드는 것이다. 그래서 모든점을 포함하는 MST를 구성하고, 두 점을 기준으로 두개의 MST로 나누어야한다. 따라서 두 점 사이의 간선 중 가중치가 가장 큰 것을 빼주면 두개..

문제 링크 : https://www.acmicpc.net/problem/17472 17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net 예전에 풀었던 걸 MST로 다시 풀어봤다. 예전에는 BFS,DFS로 완탐으로 해결했었다. 이번에는 BFS, MST로 해결했다. BFS로 각 섬에 번호 매기면서 섬의 가장자리를 구한다. 이때 해당 점에서 이동하려는 점이 격자판 안에 있고 물인 경우 가장자리로 판별해서 저장했다. (x,y,방향) 이때 방향은 해당 칸으로 온 방향이다. 구한 가장자리에서 다리를 만들면..

문제 링크 : https://www.acmicpc.net/problem/2479 2479번: 경로 찾기 길이가 같은 두 개의 이진수 코드 A와 B가 있다고 하자. 이 두 코드 사이의 해밍 거리는 A와 B의 각 비트를 왼쪽부터 오른쪽으로 차례대로 비교할 때 서로 다른 값을 가진 비트의 수이다. 예를 들 www.acmicpc.net BFS로 풀이 하였다. 그냥 모든 경우 다 따져도 될 것 같다. BFS 돌면서 현재 점과 방문하지 않은 점들중 해밍 거리가 1인 것만 골라서 BFS를 진행해도 무방할 듯 하다. 30 * 1000 * 1000 = 30,000,000 이므로 다 따져도 충분하다. 그치만 나는 그냥 미리 해밍 거리가 1인걸 구하고 그 녀석들 가지고만 BFS를 수행했다. 그리고 가장 중요한것은 경로를 저..

문제 링크 : https://www.acmicpc.net/problem/1944 1944번: 복제 로봇 첫째 줄에 미로의 크기 N(4 ≤ N ≤ 50)과 열쇠의 개수 M(1 ≤ M ≤ 250) 이 공백을 사이에 두고 주어진다. 그리고 둘째 줄부터 N+1째 줄까지 미로의 정보가 주어진다. 미로는 1과 0, 그리고 S와 K로 주어 www.acmicpc.net 접근법이 떠오르지 않아 밑에 알고리즘 분류를 보고 해결한 문제이다. MST로 해결하였다. 출발점과 모든 열쇠점을 연결하는데 이때 가중치가 최소가 되어야한다. 그러므로 MST로 해결하면 된다. 이때 주어진 미로를 그래프로 변환해야한다. 이것은 각 지점별로 다른 지점까지 최단경로를 계산해서 만들어주면 된다. 그래서 나는 미로를 좀 수정했다. S를 1로, K..

문제 링크 : https://www.acmicpc.net/problem/5670 5670번: 휴대폰 자판 휴대폰에서 길이가 P인 영단어를 입력하려면 버튼을 P번 눌러야 한다. 그러나 시스템프로그래밍 연구실에 근무하는 승혁연구원은 사전을 사용해 이 입력을 더 빨리 할 수 있는 자판 모듈을 개발 www.acmicpc.net 문제 등급은 높지만 어렵지 않은 문제이다. 핵심은 트라이 자료구조를 사용하는 것이다. 현재 문자에서 이어질 다음 문자를 다 저장했다가 사용해야므로 트리구조가 떠올랐고, 그중 다음 글자를 자식 노드로 저장하는 트라이가 떠올랐다. 우선 입력으로 들어온 단어를 모두 트라이로 구성하자. 이때 해당 글자에서 단어가 끝난다는 표시를 해주자. 다음은 루트 노드의 자식 글자에서 시작해서 재귀로 탐색하면..

문제 링크 : https://www.acmicpc.net/problem/1647 1647번: 도시 분할 계획 첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 www.acmicpc.net MST 문제이다. 나는 크루스칼로 풀이 했다. 문제는 마을을 두개로 분리하고 두부분의 가중치의 합이 최소가 되어야한다. 정점을 n이라 했을 때 n-2개의 간선은 고르면 된다. MST 문제를 풀때 n-1개의 간선을 고르면 된다. n-1개를 고르면 하나의 그래프가 탄생하고 사이클이 형성되지 않은 상태이다. 이때 간선을 하나 지우면 두개의 그래프가 나..