분류 전체보기

알고리즘 스터디를 준비하며 풀게 된 문제이다. 물론 어려운 문제였지만 이때까지 완전 검색과 DFS를 풀면서 많이 봤던 유형이었기 때문에 어떻게 풀지 비교적 쉽게 방향을 잡을 수 있었다. 문제를 간략히 설명하자면, 배열이 주어졌을 때, 그 배열을 정사각형으로 나누고, 그 정사각형이 모두 같은 값이면 하나로 압축할 수 있고 이렇게 압축했을 때 배열의 최종적으로 남는 0의 개수와 1의 개수를 출력하는 문제이다. 이 문제에서 제공하는 그림을 본다면, 가장 왼쪽 사각형처럼 초기배열 상태에서는 모든 수가 같지 않기 때문에 2^(1/2) 배수로 정사각형을 나눠야 하고, 그렇게 나누어진 게 두 번째 사각형이다. 두 번째 사각형에서는 1 사분면의 값이 모두 같아지기 때문에 0으로 압축할 수 있다. 이 과정은 정사각형의 ..

최근에 풀었던 문제 중에 가장 재밌게 푼 문제인 것 같다. 물론 쉽게 푼 문제는 아니었지만, 어떻게 풀지 고민하는 과정과 실제로 그 과정에서 정답이 나오는 게 알고리즘 문제를 푸는 재미인 것 같다. 문제를 간단히 설명하자면, 몇 번의 클릭으로 지뢰가 아닌 곳을 오픈할 수 있는지 횟수에 대한 최솟값을 묻는 문제이다. 추가적인 제약사항은 *(지뢰가 아닌 곳)을 클릭했을 때, 인접한 곳에 지뢰가 없다면 인접한 블록까지 공개가 된다. 그림에서 숫자는 인접한 위치의 지뢰 개수인데, 문제에서 묻는 것은 최소 클릭 횟수이기 때문에 구현하지 않았다. 문제를 처음 보고 최소한의 횟수? 'DFS!'를 생각했지만, 게임판의 길이(N) 이 300까지 가능하기 때문에 DFS는 절대 아니라고 생각했다. 그럼 내 지식에서 남은 보..

이 문제는 수업과정에서 한번 풀어봤던 문제였지만, 그 이후로 그래프나 완전 탐색 문제 위주로 풀다가 오랜만에 마주하니 어떻게 풀어야 할지 감이 잡히지 않았다. 문제는 음주가무를 즐기다가 조교들의 눈을 피해 일사천리로 자신의 방으로 돌아가야하는 고등학생들의 자기 방으로 돌아가는 최단 시간을 구하는 문제이다.(경로가 겹치는 경우 한 명씩 지나갈 수 있으므로 한 단위 시간이 증가한다) 문제만 읽었을 때는 막막했지만, 교수님께서 알려주신 필살기인 손으로 문제 상황을 적으면서 생각을 해보았다. 이 문제는 친절하게 그림으로도 설명을 해주었기 때문에 쉽게 이해할 수 있었다. 손코딩을 하면서 내가 생각해낸 해법은 통로를 하나의 배열로 생각하여 그 통로를 지나는 경우 방문 체크를 하는 것이다. 즉, 위 그림에서 1번 방..