전체 글 검색 결과

해당 글 904건
조세퍼스 문제 : 어느 순서대로 제거되는지 출력해 보자.

조세퍼스 문제는 다음과 같습니다. 시계 방향으로 1번부터 n번 사람이 있습니다. 처음에 k번째 사람을 뽑습니다. 뽑은 사람은 제거가 됩니다. 제거가 된 사람으로부터 k번 시계 방향으로 이동해서 있는 사람을 뽑습니다. 그 사람은 제거됩니다. 이런 식으로 n번 수행했을 때, 어떤 순서대로 제거되는지 구할 수 있을까요? 예를 들어 n = 7이고 k = 3이라면, 3, 6, 2, 7, 5, 1, 4 순서대로 제거가 될 겁니다. 나이브하게 풀었을 때, 주로 일어나는 연산은 2개입니다. 탐색, 삭제. List를 사용하면 배열에 비해 유리할 듯 싶습니다. 그렇지만, 탐색이 매우 많이 일어난다면 꼭 유리하다고 할 수도 없어요. k칸 이동을 O(1)만에 할 수 없기 때문입니다. 대신 배열은 랜덤 접근이 됩니다. 따라서 ..
자료알고/자료구조 2019. 8. 10. 19:51
비교 기반 정렬 : 왜 하한이 nlogn일까?

비교 기반 정렬은, 키 2개를 가지고 비교를 하는 것들을 말합니다. 예를 들어서, 우리가 sort 함수를 호출할 때 이런 식으로 compare 함수를 재작성을 합니다. 그러면 이것은 key a와, b를 비교한 것입니다. 대다수의 정렬은 이 키 값 2개를 비교해서 순서를 ordering 한다고 보시면 됩니다. 물론 예외가 몇 개 있는데요. 카운트, 버킷, 기수 정렬 등이 예외입니다. 크기가 n인 배열이 있습니다. 물론, 이 n개의 수는 서로 다른 수라고 합시다. 보통 그렇게들 많이 주어지니까요. 그러면, 서로 다른 수 n개를 순서 고려해서 배열하는 가짓수는 n!입니다. 즉, 길이가 n인 순열이 n!개가 나온다는 것입니다. 예를 들어서 n = 4라고 해 봅시다. 그러면 1번째 칸에는 4개 중 하나만 들어가면..
자료알고/알고리즘 2019. 8. 10. 11:34
c언어 if문 : 조건이 참이면 블록 안으로 들어간다.

C언어에서, 어떠한 조건문을 만족하면, 특정한 문장을 수행하게 할 수 없을까요? if, else if, else 공식으로 하실 수 있어요. 먼저, 이런 경우 먼저 생각해 봅시다. 패턴 1은 다음과 같습니다. if(조건문) 명령1; 명령2; 이 경우 조건문이 참이라면 명령1, 명령2 순서대로 실행이 되고, 그렇지 않다면 명령 1만 수행되는 패턴입니다. if(x>=0)이 하나 있어요. x가 0보다 크다면 work() 함수가 수행이 될 거에요. 그렇지 않다면, 바로 7번째 줄로 갈 겁니다. 이것을 흐름도로 그려보면 아래와 같습니다. 만약에 x>=0이라면 work를 수행합니다. 그렇지 않다면, work를 수행하지 않고, 그냥 건너 뛴다는 것을 알 수 있어요. 만약에, 조건을 만족하지 않으면, 다른 문장이나 블록..
코딩/C 2019. 8. 9. 22:26
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
반복자 무효화 : 어떠한 연산을 조심해야 할까요?

STL을 공부하시다 보면, 반복자 무효화라는 용어는 한 번 쯤 들어보셨으리라 생각합니다. 반복자는 순회, 탐색 등을 위해서 쓰는 녀석인데요. 이것이 어떠한 이유로 무효화가 될 수 있습니다. 보통, iterator가 가리키는 것이 삭제 되었을 때 무효화가 되는데요. vector와 같이, 동적 배열을 사용할 때는 그 이외에도 조심해야 할 부분들이 몇 가지 더 있어요. 예제 프로그램 1을 봅시다. 먼저, 이 프로그램을 생각해 봅시다. vector v에 원소를 200개 추가했습니다. 그리고, 이 때, 벡터의 시작 원소를 iter가 가리키게 했습니다. 그리고 난 다음에, v에다가 0부터 1999까지 또 추가를 합니다. 프로그램에는, 벡터에 remove 연산을 가하지 않았습니다. 그런데 결과가 의외입니다. 0 0 ..
레퍼런스/예제 2019. 8. 8. 18:47