전체 글
14889번-스타트와 링크
문제 https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 접근방법 1) 접근 사고 start팀과 link팀을 구분하기 위해 visited배열을 활용하여 탐색의 높이가 3이 되었을 때 visited 배열값을 활용하여 팀을 구분하고 결과 값을 계산하여 최소값을 갱신해주었습니다. 2) 시간 복잡도 BackTracking을 통한 모든 경우를 탐색해야 하므로 O(n^2)의 시간복잡도를 가집니다. 3) 배운 점 구현력이 무럭무럭 자라고 있습니다. 4) PS 정답 코드 1 2 3 ..
14888번-연산자 끼워넣기
문제 https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 접근방법 1) 접근 사고 가능한 모든 연산의 경우를 탐색해줘야 하는 문제였습니다. DFS 알고리즘을 통해 모든 경우의 수를 구해주었습니다. 2) 시간 복잡도 O(V + E) 3) 배운 점 매개변수를 적절하게 사용하면 코드의 라인이 절약될 수 있다는걸 느낀 문제입니다. 4) PS 정답 코드 1 2 3 4 5 6 7 8 9 10 11 12 ..
14503번-로봇청소기
문제 https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어 www.acmicpc.net 접근방법 1) 접근 사고 DFS 문제로 생각하여 DFS를 활용해서 문제를 풀었습니다. 문제의 구현량은 간단하나 DFS의 이해도가 높지 않다면 어려움을 겪을수 있는 문제입니다. 문제 에서 깊이우선탐색을 활용한 응용하는 부분이 들어있습니다. 보통 DFS는 최하단으로 내려간뒤 가지를 치면서 탐색을 하는데 이 문제의 경우 가지를 치는 방식이 기존 코드와 다르게 한 개의 시작점 부터만 가지치기가 됩..