https://www.acmicpc.net/problem/16724 16724번: 피리 부는 사나이 첫 번째 줄에 지도의 행의 수를 나타내는 N(1 ≤ N ≤ 1,000)과 지도의 열의 수를 나타내는 M(1 ≤ M ≤ 1,000)이 주어진다. 두 번째 줄부터 N개의 줄에 지도의 정보를 나타내는 길이가 M인 문자열이 주 www.acmicpc.net 분리집합 + 그래프 탐색 문제이다. 주어진 입력에서 연결요소의 개수를 세면 된다. 같은 연결요소인지 아닌지 구분하기 위해 나는 분리집합을 사용했는데, 2차원 분리집합 구현은 처음이라 조금 애를 먹었던 것 같다. 그냥 단순무식하게 튜플을 있는 그대로 비교했는데, 다른 방법도 있을 것 같다. 내가 사용한 알고리즘 1. 모든 배열을 순회하면서 아직 방문하지 않은 노드..
https://www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net 사이클에 속하지 않는 노드의 개수를 세는 문제이다. 생각보다 최적화를 깐깐하게 요구했던 문제이다. 하지만 덕분에 내가 놓치고 있던 부분을 확실하게 바로잡을 수 있었다. 살면서 처음으로..!! python 그룹 언어에서 제일 빠르게 푼 사람이 되보았다 ㅋㅋㅋ (21.12.17 오전 10시 30분 기준) 물론 저 32ms 차이는 크게 의미있는 차이는 아니지만.. 기분이 좋다 ㅎㅎ 이 문제의 알고리즘 분류는..
https://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N 과 건물간의 건설순서규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 그래프 문제를 풀고 싶어서, solved.ac의 그래프 태그 문제를 찾아보다가 발견한 문제이다. 스타크래프트를 연상시키는 문제인데, 그래프에 DP를 섞은 재미있는 문제였다. 우선 이 문제는 문제에서 주어진대로 시작하는 건물부터 차근 차근 건물을 지어나가다가 마지막에 원하는 건물을 짓게되면 멈추는 풀이로는 접근이 쉽지가 않다. 그래서 거꾸로 원하는 건물을 짓기 위해 지어야 하는 건물들을 역탐색..
