배열돌리기 검색 결과

해당 글 3건
백준 배열 돌리기 5 : 전략적인 브루트 포스로 풀어봅시다.

배열 돌리기 5는 solved 난이도로 골드 1인 문제입니다. 200만개의 쿼리를 브루트 포스하게 실행시키면, 시간초과가 나는 것은 당연해 보입니다. 높이가 100, 너비가 100인 배열을 어떻게 압축을 시키면 좋을까요? 문제가 되는 것은 5번, 6번임을 알 수 있습니다. 가로로 반, 세로로 반을 나눠서 처리해야 하기 때문입니다. 사실 그것만 없었다면, 그냥 시점만 이동해서 풀 수 있었을 겁니다. 일단, 제 풀이는 브루트 포스입니다. 그런데, 100 by 100 전체를 브루트 포스를 하지 않습니다. 데이터를 압축하는 것이 목표입니다. 어떻게 잘 압축을 할까요? 배열 S가 아래와 같이 있다고 해 보겠습니다. 5, 6번 연산 때문에 이렇게 나누었다는 것을 눈치채셨을 겁니다. 이 4개의 영역 중에, 모서리 부..
자료알고/알고리즘 2021. 4. 4. 03:29
백준 배열 돌리기 4 : 요소별로 나누면 어렵지 않다.

오늘은 어떤 것을 배워볼까요? 시계처럼 x칸씩 회전하는 연산을 배워보겠습니다. 17406번 배열 돌리기 문제를 보겠습니다. 문제가 요구하는 것은 간단합니다. 그 중에서 가장 중요한 것은 rotate 연산입니다. 이것은 정사각형을 시계방향으로 1칸씩 돌린다는 의미입니다. 문제가 다소 복잡하니, 분할해서 생각해 보도록 하겠습니다. 먼저, 돌아가는 단위를 기준으로 나누면, 기준점을 하나 잡을 수 있습니다. 이 기준점들을 먼저 잡아보겠습니다. 먼저 회전 반경이 1이라고 해 보겠습니다. 0번만 있는 요소, 그리고 1 ~ 8까지 있는 요소 둘로 나눠보겠습니다. 그러면, 제가 보라색으로 칠한 것은 각각의 요소들의 기준점으로 볼 수 있습니다. 그리고, 1번은 1 ~ 8은 하나의 요소로 볼 수 있습니다. 이들이 1칸씩 ..
구현 2020. 4. 14. 00:25
배열 회전 알고리즘 : 읽는 방법만 생각하면 어렵지 않아요.

배열 회전 알고리즘은, 구현 문제에서 심심찮게 보이는 문제 중에 하나입니다. 우리는 n by n 배열을 시계, 그리고 반시계 방향으로 temp array를 쓰고 회전하는 방법을 배워보도록 하겠습니다. 물론, 면접에서는 n by n짜리를 안 쓰고 돌리는 방법을 물어볼 수도 있습니다. 이에 대한 방법은, 과제로 드리겠습니다. 배열이 있습니다. 이것을 시계 방향으로 90도 회전시키면 어떻게 그려질까요? 요렇게 그려집니다. 그런가요? 그러면 우리는 첫 번째 줄부터 특징을 잡아야 하는데요. 1번째 줄에는, [..][0]이 들어갔다는 것을 알 수 있습니다. 2번째 줄에는 [..][1]이, 3번째 줄에는 [..][2]가 들어갔다는 것을 알 수 있어요. 이제 0열부터 2열까지 열별로 볼까요? 그러면, 0열은 [2][...
구현 2019. 10. 7. 15:43