알고리즘 검색 결과

해당 글 51건
배열 회전 알고리즘 : 읽는 방법만 생각하면 어렵지 않아요.

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

백준 사이트에 있는 구현 문제는, 대다수가 브루트 포스로 풀리는 경우가 많습니다. 코딩 테스트를 준비하시는 분들도 적지 않으실 거 같은데요. 그것들을 잘 풀기 위해서, 이론적인 지식 3~4편 정도만 올리고, 실전에 들어가도록 하겠습니다. 백트래킹 탐색은, 다음과 같은 알고리즘으로 동작합니다. 뭔가 복잡해 보이는데요. 제일 중요한 부분은, (1)번과 (3)번, (5)번이라고 할 수 있어요. 이 셋만 잘 작성하면 끝났다고 볼 수 있어요. 그런데, 아직 이해가 안 가는 부분이 많습니다. 들어올 수 있는 상태들은 대체 무엇을 의미할까요? 예를 들어, 스토쿠를 생각해 봅시다. 빈칸에 숫자를 넣어야 할 때, 1부터 9까지만 넣을 수 있어요. 즉, 우리가 빈 칸에 넣을 수 있는 숫자들의 집합은 {1, ... , 9}..
구현 2019. 9. 26. 20:07
팬 케이크 정렬 : 위에서부터 k개를 뒤집는다.

팬케이크 정렬은 유튜브에서 영상으로 한 번 쯤은 보셨을 겁니다. 이것을 최소한으로 뒤집는 횟수를 구하는 것은 경시 대회 이상에서 나올 만한 문제입니다. 우리는 단지, 어떻게 잘 뒤집어서 정렬을 잘 시키면 됩니다. 팬 케이크 더미에서는 위에서 k개만 뒤집을 수 있습니다. 단, k는 총 갯수보다 작을 거에요. 갯수를 n개라고 한다면 2n-3번 이하 뒤집어야 합니다. 이 때에는 어떻게 해야 할까요? 사실, 잘 모르겠습니다. 일단, 1회전이 끝날 때 마다, 2회의 단위 연산을 수행해야 한다는 것은 알겠습니다. 그러면 한 회전마다 어떤 일이 일어나면 좋을까요? 팬 케이크가 이런 식으로 쌓여 있다고 생각해 봅시다. '위에서 k개를 뒤집는다'는 연산 특성상, k가 n이 아니라면, 맨 아랫쪽에 있는 것은 움직이지 않습..
자료알고/알고리즘 2019. 9. 17. 13:29
라빈 카프 알고리즘 : 그래도 비벼볼 만한 문제가 있다.

오늘은 라빈 카프 알고리즘을 배워 보겠습니다. 어떠한 문자열을 수 하나, 혹은 2개, 3개로 압축할 수 있다. 이것은 꽤 엄청납니다. 그렇게 하면, 사실 어떠한 문자열에서 다른 패턴을 찾는 거 또한, 상당히 빠르게 수행할 수 있습니다. 다만, 정확성이 문제라면 문제인데요. 이 부분은 모듈러를 2개, 3개 이상 주는 식으로 해결합니다. 즉, 데이터가 강하지 않을 거라는 믿음을 가지고 수행을 하는 편입니다. 이 알고리즘을 잘 배워놓으면, 문자열 알고리즘을 모를 때, 조금이라도 건드려 볼 수 있습니다. 그러니 알아두시면 나름 좋습니다. 이 포스팅은 부분합 알고리즘을 이해했다는 전제 하에 쓰여졌습니다. 만약에, 그 부분에 대해서 이해를 하지 못하셨다면, 아래 포스팅을 먼저 보시고 오시는 것을 강력하게 권해드립니..
자료알고/알고리즘 2019. 9. 6. 17:16
조화 급수 : ps에서 간간히 나온다.

A(x)을 x의 약수 갯수라고 해 봅시다. 이 때, A(1) + ... + A(n)의 값은 어디에 근접할까요? 이 간단한 질문에서, 오늘의 주제를 이야기 해 보도록 하겠습니다. a가 b의 배수라면, b는 a의 약수입니다. 이 점을 이용해 봅시다. 예를 들어 4의 약수는 1, 2, 4입니다. 그러면, 4는 1의 배수이면서 2의 배수이고, 4의 배수이기도 합니다. 그러면 1에서 출발해서, 1만큼 건너 뛸 때, 2에서부터 출발해서 2만큼 건너 뛰었을 때, 4에서부터 출발해서 4만큼 건너 뛰었을 때, 4를 visit 할 수 있게 됩니다. 그러면 1부터 n까지의 약수의 갯수의 합을 구하는 건 어떻게 하면 좋을까요? 역시 거꾸로 생각하시면 됩니다. 예를 들어서, 약수가 1인 수들을 찾는다고 해 봅시다. 그러면 1,..
자료알고/알고리즘 2019. 9. 5. 18:05