조세퍼스 문제는 다음과 같습니다. 시계 방향으로 1번부터 n번 사람이 있습니다. 처음에 k번째 사람을 뽑습니다. 뽑은 사람은 제거가 됩니다. 제거가 된 사람으로부터 k번 시계 방향으로 이동해서 있는 사람을 뽑습니다. 그 사람은 제거됩니다. 이런 식으로 n번 수행했을 때, 어떤 순서대로 제거되는지 구할 수 있을까요? 예를 들어 n = 7이고 k = 3이라면, 3, 6, 2, 7, 5, 1, 4 순서대로 제거가 될 겁니다. 나이브하게 풀었을 때, 주로 일어나는 연산은 2개입니다. 탐색, 삭제. List를 사용하면 배열에 비해 유리할 듯 싶습니다. 그렇지만, 탐색이 매우 많이 일어난다면 꼭 유리하다고 할 수도 없어요. k칸 이동을 O(1)만에 할 수 없기 때문입니다. 대신 배열은 랜덤 접근이 됩니다. 따라서 ..
array 검색 결과
해당 글 7건
조세퍼스 문제 : 어느 순서대로 제거되는지 출력해 보자.
자료알고/자료구조
2019. 8. 10. 19:51
java 1차원, 2차원 배열 : 간단한 예제를 보고 배워봅시다.
Java에서 배열은 어떻게 쓸까요? C언어에서의 배열과 똑같습니다. 다만, 자바에서는 배열이 실제로 객체이기 때문에, Heap 영역에 생성이 된다는 것 정도의 차이밖에 없어요. 그리고 크기가 고정되어요. 즉, 고정 힙 배열, fixed heap array 정도로 생각하면 좋겠습니다. 예제 프로그램 1을 봅시다. 일단, 우리는, 크기가 2인 int형 배열 arr을 선언하려고 합니다. 그러면, int arr[] = new int[2]; 이렇게 선언할 수 있어요. int형을 저장할 수 있는 2개의 공간을 할당한다는 건데요. 일단 6번째 줄까지 수행이 되면, 메모리에 다음과 같이 저장이 됩니다. arr이 int형을 2개 저장할 수 있는 공간을 가리키고 있어요. arr은 스택에, 실제로 real int를 2개 저..
코딩/Java
2019. 8. 9. 11:29
최근댓글