출처 프로그래머스 봉인된 주문 접근 문제 분석 알파벳 순으로 정렬된 주문서에서 주어진 숫자(n)에 해당하는 주문서를 찾는 문제입니다. 이 때, 특정 주문(bans)이 삭제되어 있는 상태입니다. 시간복잡도 분석 주어진 숫자는 n = 10^15 인 long 타입의 숫자입니다. 따라서 해당 숫자에서 글자를 가져오는 알고리즘은 O(N)보다 작아야 합니다. 주어진 주문인 bans는 길이가 300,000이하입니다. 또한, 각 주문의 길이는 최대 11입니다. 모든 주문의 알파벳을 비교하기 위해서는 300,000 x 300,000(주문 간 비교) x 11(주문 길이) = 9x10^12 x 11 이므로 시간복잡도가 초과될 가능성이 있습니다. 따라서 전체 주문을 최대 O(NlogN)까지 확인할 수 있습니다. ...
출처 Programmers 자물쇠와 열쇠(2020 KAKAO BLIND RECRUITMENT) 접근 문제 분석 주어진 자물쇠와 열쇠를 이동시키고 돌려서 맞출 수 있는지 확인하는 문제입니다. 열쇠 혹은 자물쇠를 돌리는 로직과, 이동시키는 로직을 구현하면 됩니다. 문제에서 주어진 열쇠보다 자물솨의 크기가 작기 때문에, 자물쇠를 이동시키고 돌리는 식으로 구현하는 것이 더 효율적입니다. 모든 칸에 대해서 자물쇠를 돌리면서 맞추고, 이동하는 식으로 완전탐색을 진행합니다. 시간복잡도 분석 자물쇠와 열쇠의 크기는 M <= N <= 20이므로, 전체 칸의 개수는 M^2 <= N^2 <= 400입니다. ...
출처 Programmers 표 병합(2023 KAKAO BLIND RECRUITMENT) 접근 문제 분석 표 편집 프로그램의 기능을 구현해야 합니다. UPDATE : 셀 1개의 값 바꾸기, 모든 셀의 값 찾아 바꾸기 MERGE : 셀 합치기(그룹화) UNMERGE : 셀 분리하기(그룹화 해제) PRINT : 셀 1개의 값 출력하기 표의 크기가 50 x 50이고, 명령의 길이가 1000 이하이므로, 시간복잡도는 충분한 편입니다. UPDATE는 비교적 쉽게 구현할 수 있지만, 문제의 이름처럼 표 병합을 얼마나 정확하고 빠르게 구현하는지가 중요한 문제입니다. ...
출처 https://www.acmicpc.net/problem/17470 접근 시간복잡도 분석 문제에서 주어진 배열의 크기는 최대 100 x 100이고, 전체 연산의 개수는 2,000,000개 이므로, 일반적인 회전을 구현할 경우 시간 초과가 발생합니다. O(N) = 100 x 100 x 2,000,000 = 2 x 10^13입니다. 배열 연산 압축하기(X) 해당 접근은 잘못된 풀이입니다. 올바른 풀이는 아래를 참고하시기 바랍니다. 연산을 구현하고 배열을 돌리다 보면, 뭔가 최적화할 수 있는 것 같은 느낌이 듭니다. 상하(1)-좌우(2) 반전 2번 하면 원래 배열로 복귀합니다. 오른쪽(3) 왼쪽(4) 회전 ...
출처 메두사와 전사들 접근 복잡한 문제인만큼 구현하면서 순차적으로 처리해야 할 과정이 많은데, 이에 필요한 알고리즘을 정리해보면 다음과 같습니다. 메두사의 이동경로 구현 BFS + 경로 역추적 시선 생성 배열 탐색 구현 병사 이동 및 공격 배열 탐색 구현 알고리즘 자체는 어렵지 않으나, 배열 탐색을 구현하는 과정이 복잡합니다. 메두사 이동경로 구현(BFS) 메두사가 이동하는 과정에 장애물이 있기 때문에, BFS를 통해 미로를 탐색하는 최단경로를 구해야 합니다. 또한, 이동경로를 다시 돌면서 병사들과의 상호작용을 확인하기 위해 이러한 경로를 별도 배열에 저장해야 합니다. ...