자료알고/자료구조 검색 결과

해당 글 43건
선형 큐 : push 연산의 횟수만큼 크기를 할당하면 된다.

Queue를 직접 구현해야 할 때에는 어떻게 해야 할까요? 사실, 선형 큐를 먼저 고려합니다. 큐는 먼저 넣은 친구가 먼저 빠지는 특성을 지닙니다. 예를 들자면, 은행 창구를 생각해 보세요. 먼저 번호표를 뽑은 손님이 먼저 처리됩니다. 그런가요? 그렇기 때문에, 포인터가 front하고 rear, 이렇게 2개가 있는데요. front는 제일 앞에 있는 것을, rear는 제일 뒤에, 넣을 위치를 가리킵니다. 선형 큐를 구현할 때, 저는 is_full 처리를 하지 않아요. 그렇기 때문에 초기 크기를, 큐에 들어가는 원소의 갯수 + 10로 잡습니다. 예를 들어서, 가로 r개, 세로 c개의 맵이라면 BFS를 돌릴 때, rc만큼 들어가기 때문에 크기를 rc + 10 정도로 잡습니다. 처음에 front와 rear의 값..
자료알고/자료구조 2019. 8. 16. 23:57
조세퍼스 문제 : 어느 순서대로 제거되는지 출력해 보자.

조세퍼스 문제는 다음과 같습니다. 시계 방향으로 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
java queue : 어떻게 사용하는지 간단히 알아봅시다.

java에서 Queue는 어떻게 사용할까요? 저번 시간에 리스트를 잘 보셨다면, 대략적으로 감이 오실 거에요. 아. 이건 빼박 리스트구나. 사실 동적 배열을 이용해도 되는데요. 이것은 잘 생각해 보세요. 예제 프로그램을 봅시다. 일단 저는 my_Object 객체를 Queue에 넣을 거에요. 이건 아마 딱 봐도, 미로 찾기나, 어느 지점에서부터 최단 거리를 구할 때 쓰는 것 같군요. 이제 main 함수를 볼까요? 16번째 줄이 보이시나요? 저는 LinkedList를 쓸 거에요. LinkedList는 deque를, deque는 queue를 implements를 한 관계입니다. 이것은 Collections 시간에 다시 정리해 봅시다. 일단 오늘은, 아 이런 게 있구나. 정도만 보시면 되겠습니다. 사실 큐의 특..
자료알고/자료구조 2019. 8. 5. 17:48
백준 1406 에디터 : List를 이용해서 해결해 봅시다.

링크드 리스트를 이용해서 간단한 편집 프로그램, 그러니까 vim과 같은 것들을 구현할 수 없을까요? 물론, 실제로 제가 구현할 것은 이것보다는 간단한 녀석입니다. 보통, 자료구조 프로젝트 때 적지 않게 하실 수도 있을 듯 싶네요. 사실 기능은 생각보다 단순해 보입니다. 커서를 이동시킵니다. 그리고 커서 앞에 문자를 추가시킵니다. + 앞에 't'를 추가시켰습니다. 이게 add 연산입니다. 아니면, 커서 앞에 있는 문자를 제거할 수도 있어요. 예를 들어서, 여기에서는 ( 앞에 있는 y라는 문자를 제거했습니다. 이런 간단한 편집 프로그램은 어떻게 구성하면 좋을까요? 단, 삽입, 삭제, 커서 이동 쿼리가 최대 60만개 들어옵니다. 배열은 장점이 무엇인가요? cache friendly 하다는 겁니다. 단점이 무엇..
자료알고/자료구조 2019. 8. 4. 00:57
이중 연결 리스트 : 노드를 연결하는 포인터가 2개다.

보통 C++의 STL에서는 double list를 많이 쓰는데요. 노드를 가리키는 포인터가 2개입니다. 각각 이전 것과, 다음 것을 가리키고 있습니다. 실제로, 이전 것도 가지고 있으면, 삭제하거나, 들어가야 하는 위치를 안다고 했을 때, 빠르게 자료구조에서 데이터를 삭제하거나, insert를 할 수 있어요. 기준 위치로부터 이전 노드의 주소도 알고 있기 때문입니다. 오늘은 이중 연결 리스트를 구현 해 보도록 하겠습니다. 먼저 node형 구조체는 다음과 같이 선언합니다. 각각, data를 담아두는 필드와, 이전 것 prev, 그리고 next를 가리키는 요소를 저장하고 있습니다. 다음에 head와 tail이 있는데요. 이것은 각각 리스트의 시작 위치와 끝나는 위치를 나타냅니다. 그러면 연결 리스트를 초기화..
자료알고/자료구조 2019. 7. 27. 17:30