![]()
프로그래머스의 불량 사용자 문제를 풀어보았다. 지난번에 풀다가 실패했던 링크 점수 이후로 정규화에 대해 공부해 보았기 때문에 이 문제를 봤을 때, 정규화로 풀어볼 수 있겠다는 생각이 들었다. 이 문제는 모든 아이디가 공개되어 있는 이벤트 응모자 아이디와 아이디가 일부분 '*'로 가려져 있는 불량사용자 아이디를 제공한다. 이 정보를 통해 이벤트 응모자 아이디 중 불량 아이디를 가려내고자 할 때, 불량 아이디로 가려내질 응모자 아이디의 경우의 수를 묻는다. 이렇게 두 정보가 제공됐을 때, 불량사용자로 인해 제재받는 경우의 수는 [frodo, abc123], [fradi, abc123] 이렇게 두 가지의 경우가 있다. 추가적으로 고려해야 할 제약사항은 불량사용자 아이디는 무조건 하나의 응모자 아이디를 가리키고..
![]()
알고리즘 스터디를 준비하며 풀게 된 문제이다. 물론 어려운 문제였지만 이때까지 완전 검색과 DFS를 풀면서 많이 봤던 유형이었기 때문에 어떻게 풀지 비교적 쉽게 방향을 잡을 수 있었다. 문제를 간략히 설명하자면, 배열이 주어졌을 때, 그 배열을 정사각형으로 나누고, 그 정사각형이 모두 같은 값이면 하나로 압축할 수 있고 이렇게 압축했을 때 배열의 최종적으로 남는 0의 개수와 1의 개수를 출력하는 문제이다. 이 문제에서 제공하는 그림을 본다면, 가장 왼쪽 사각형처럼 초기배열 상태에서는 모든 수가 같지 않기 때문에 2^(1/2) 배수로 정사각형을 나눠야 하고, 그렇게 나누어진 게 두 번째 사각형이다. 두 번째 사각형에서는 1 사분면의 값이 모두 같아지기 때문에 0으로 압축할 수 있다. 이 과정은 정사각형의 ..
