문제https://www.acmicpc.net/problem/8111 어떻게 풀 것인가?우선 문제를 읽으면서 수를 보며 잠깐 수학개념에 대해서 생각을 하다가, "어? BFS문제로 풀릴거 같은데?" 라는 생각으로 접근하였다. 하지만 문제가 풀리지 않아서 다른 분의 풀이를 결국엔 참고할 수 밖에 없었다. 맨 아래에 참고했던 블로그들의 링크를 걸어 두었다. 그래도 내가 이해한 것을 기반으로 작성해보자. 모듈러 법칙을 활용한 BFS 접근법 정리:이 문제는 주어진 수 N 으로 나누어 떨어지는 0과 1로 이루어진 가장 작은 수를 찾는 문제다. 단순히 BFS로 숫자를 확장하는 것만 생각하면 해결하기 어렵지만, 모듈러 연산의 특성을 이용하면 효율적인 탐색이 가능하다. 모듈러 법칙 활용어떤 수 A 를 B 로 나눈 나머지..
문제https://www.acmicpc.net/problem/15683 어떻게 풀 것인가?CCTV 방향 탐색을 위한 순열 생성permutation(0, cctvList.size())을 호출하여 DFS 기반 순열 생성을 수행한다.각 CCTV는 최대 4가지 방향을 가질 수 있으므로, 모든 CCTV의 가능한 방향 조합을 만들어서 하나씩 테스트한다.모든 CCTV에 대해 방향이 결정되면, 원본 map을 copyMap에 복사한 후, 해당 조합으로 CCTV 감시를 수행한다.CCTV 감시 영역 설정direction(CCTV cctv, int d) 함수는 CCTV의 종류에 따라 감시 방향을 설정하는 역할을 한다.각 CCTV는 다음과 같이 감시할 방향을 결정한다:1번: 한 방향 감시2번: 서로 반대 방향 두 곳 감시3번:..
문제https://www.acmicpc.net/problem/17471 어떻게 풀 것인가?문제의 접근조차 어려워서 잠깐의 고민 끝에 결국엔 다른분의 풀이를 참고하였다. 오늘의 포스팅은 기억을 남기기 위한 용도라고 생각하며 작성하였다. 문제의 접근의 경우 지역에 두 개의 선거구 중에 하나를 할당한다. (1 또는 2로 표현)나눠진 지역들이 두개의 구역으로 연결되는지 확인한다. (DFS/BFS 탐색으로 구함)두 지역의 차이 값 중에서 최소값을 찾아준다.좀 더 풀어서 작성해보자. 먼저, 입력을 통해 각 지역의 인구 수와 연결된 지역 정보를 받아 저장한다. 이후, 선거구를 나누기 위해 각 지역이 속할 선거구를 정하는 모든 경우의 수를 탐색한다. 이를 위해 깊이 우선 탐색(DFS)을 사용하며, 각 지역을 두 개의 ..
문제https://www.acmicpc.net/problem/1655 1655번: 가운데를 말해요첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -1www.acmicpc.net 어떻게 풀 것인가?이 문제는 우선순위 큐(PriorityQueue)를 사용하여 효율적으로 중간값을 찾는 문제이다.기본적으로 2개의 우선순위 큐(MinHeap, MaxHeap)를 활용하면 쉽게 해결할 수 있다. MaxHeap (왼쪽 그룹)중간값을 기준으로 작거나 같은 값들을 저장.최댓값을 빠르게 구하기 위해 내림차순 정렬.PriorityQueue maxHeap = new Priori..
문제https://www.acmicpc.net/problem/1941 어떻게 풀 것인가?이 문제는 백트래킹(Backtracking) 을 이용해서 풀었다.우선 문제를 잘 읽어보면 배열의 크기와 조건이 크지 않음을 알 수 있다.즉, 브루트포스(완전 탐색) 및 백트래킹을 사용해도 시간 초과 없이 해결할 수 있다.따라서, 25명 중 7명을 선택하는 조합(combination)을 수행한 후,선택된 7명이 서로 연결되어 있는지 확인하고,최소 4명이 ‘이다솜파’(S)인지 확인하는 방식으로 접근했다. 풀면서 놓쳤던점DFS 탐색 방식의 오류단순히 DFS로 인접한 학생을 탐색하는 것이 아니라, 25명 중 7명을 조합으로 선택한 후, 그 7명이 하나의 연결된 그룹인지 확인해야 했다.즉, DFS로 직접 7명을 선택하면 모든 ..
문제https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그www.acmicpc.net 어떻게 풀 것인가?문제의 제목부터가 "최소비용 구하기" 이다. 그래서 다익스트라 최단경로 구하는 알고리즘을 사용하였다.사실 그래서 처음 접근 자체는 크게 어렵지 않았다.내 코드의 핵심은 "우선순위 큐를 활용한 다익스트라 최단 경로 탐색" 이라고 볼 수있다. 우선순위 큐를 사용하는 다익스트라 알고리즘의 시간 복잡도는 O((V + E) log V) 이다. Priori..
문제https://www.acmicpc.net/problem/11729 어떻게 풀 것인가?컴퓨터 공학부 전공자라면 자료구조 혹은 알고리즘 수업 시간에 재귀를 공부하면서 항상 자주보는 문제였을 것 이다. 나는 사실 과거에 기억에 의존하여 문제를 풀었기때문에 굉장히 쉬웠지만 그래도 한번 차근차근 문제를 뜯어보자. 우선 하노이의 탑문제를 살펴보자.일단, 하노이탑의 가장 큰 규칙은 "작은 원판 위에 큰 원판은 올 수 없다" 이다. 세 개의 기둥(A, B, C)과 여러 개의 크기가 다른 원판이 있다.처음에는 원판들이 가장 큰 것부터 가장 작은 것까지 차례대로 한 기둥(A)에 쌓여 있다.이 원판들을 다른 기둥(C)으로 모두 옮겨야 한다.단, 다음과 같은 규칙을 반드시 지켜야 한다.한 번에 하나의 원판만 이동할 수 ..
문제https://www.acmicpc.net/problem/2133 어떻게 풀 것인가?처음 문제를 풀었을 때 우선적으로는 DP가 떠올랐다.DP 정리는 아래에 있다.https://superohinsung.tistory.com/198 [Algorithm] 동적 계획법(Dynamic Programming)동적 계획법(Dynamic Programming) 동적 계획법(Dynamic Programming, DP)란 컴퓨터 프로그래밍 기법 중 하나로, 주로 최적화 문제나 중복되는 부분 문제를 효율적으로 해결하는 데 사용되는 알고리즘 설계superohinsung.tistory.com 세로 3칸의 크기는 고정되었다. 즉, 주어지는 N에 따라서 타일을 채울 수 있는 경우의 수가 달라진다.그래서 간단하게도 이 문제는 N..
