이틀째 헤매는 간단한 알고리즘 문제....
아래에 질문을 올렸었는데 답변이 없어서 정리해서 다시 올립니다...^^..
벌써 이 문제하나로 이틀째입니다.. :(
부디 도움을 부탁드릴께요... :wink:
일단 문제는 아래와 같습니다..
n(>1)개의 리스트가 1차원 배열 space[m]에 순차적으로 표현된다고 가정하자
0 <= i < n 에 대해 front[i]는 i번째 리스트의 첫째 원소 위치보다 1이 작은 위치를, rear[i]는 i번째 리스트의 마지막 원소를 가리킨다고 하자.
rear[i] <= front[i+1], 0<= i < n이고 front[n] = m-1 이라고 가정한다.
이 리스트에 대해 삽입과 삭제를 수행하는 함수들이다.문제: i번째 리스트의 (j-1)번째 원소다음에 item을 삽입하는 함수 Insert(int i, int j, int item)을 작성하라.
이 함수는 space에 이미 m개의 원소가 있는 경우에만 삽입연산에 실패하여야 한다.
만일 아래와 같은 데이터가 있다면
0번째 리스트 : 1,2,3,4
1번째 리스트 : 5,6,7,8
2번째 리스트 : 9,10,11,12
space배열은 : 1,2,3,4,5,6,7,8,9,10,11,12i=0 일때 : front[0]=없음 rear[i]=4
i=1 일때 : front[i]=4 rear[i]=8
i=2 일때 : front[i]=8 rear[i]=12
i=3 일때 : front[i]=12 rear[i]=없음(가정에 따라서 front[i]만 있음)
여기서 Insert(int i=2, int j=2, int item=10) 으로 함수를 호출했다면..
11이 있는 위치를 말하는건데요..(j도 0부터 시작한다고 가정하면)
제가 궁금한건 왜 front[], rear[] 두개가 필요한지입니다..
이건 큐가 아닌거 같은데...왜 굳이 위치값을 나타내는 두개의 배열이 필요한건지..
그냥 front[i]가 각 리스트의 첫번째 위치를 나타낸다면 쉽게 Insert()함수로 들어오는
위치를 찾아 값을 넣을 수 있을텐데요...
대체 어떻게 front[]와 rear[]를 조작해서 원하는 위치에 넣으라는 건지..
제가 이해한 자료구조가 완전히 잘못된걸까요..?..^^;;
Insert()함수를 만들 수 있는 개략적인 설명 좀 해주셨으면..
부디 조언 부탁드립니다...지쳐가는군요.. :(
Re: 이틀째 헤매는 간단한 알고리즘 문제....
이상의 방식처럼만 배치할 필요가 있나요?
일단 sadrove님께서 이해한 방식 (rear[i]가 왜 필요해??? 그냥 모든 n개의 배열을 따딱따닥 이어 붙여놓으면 필요없자나.)으로
구현 해보셨겠지요?
그렇다면 insert를 구현하셨을 때 어떤 점이 이상하진 않았나요?
쓸데없는 작업이 많진 않았습니까?
힌트를 좀더 드리자면,
for (int i = 0; i < 10; ++i) insert(0, 0, i);와 같이 첫번째 배열의 첫번째 원소 앞에 원소를 추가하기 위해
sadrove님께서 구현한 insert함수는 얼마나 비싼 작업들을 하나요?
단지 0번째 배열에만 어떤 작업을 하고 픈데, 1번째, 2번째 배열의 원소도 옮겨야 하진 않나요?
m은 큽니다. space[m]을 넓게 넓게 사용해 주세요.
그런 의미에서
입니다. 작거나 같다이죠. 작은 경우도 존재합니다.
(두개의 인접한 배열 사이에 공간을 넣어둘 수 있습니다!!)
혹시나 하는 마음이지만 숙제 문제같은 느낌이 들어 이만 접겠습니다.
(괜한 의심(? )이었다면 죄송합니다.)
[quote]m은 큽니다. space[m]을 넓게 넓게 사용해 주세요.[
시간이 있으시면 넓게 사용하는 방법도
여러가지로 아이디어를 내볼수 있을 것 같네요.
반복되는 Insert로 두 인접한 배열 사이의 공간이 없어진 이후 다시 Insert가 일어날 때
뒷 배열을 (어차피 옮겨야 하니) 얼마나 옮기는게 좋을지도
이슈로 보면 이슈가 될수 있을듯도 합니다. :roll:
Re: 이틀째 헤매는 간단한 알고리즘 문제....
숙제 맞습니다.. :wink:
사실 아직도 무슨 말인지 잘 모르겠네요... :(
왜 이렇게 사람들이 숙제를 질문하면 꺼려하는지 잘 모르겠습니다..
물론 스스로 해결해야 하지만...
모르는 부분은 물어볼 수도 있다고 생각하는데...
yui님께 어떤 불만이 있어서 그러는 건 아니고요...
그냥 제 자신이 무능해 보여서 그럽니다.. :?
답변 감사드리고요...좋은 하루 되세요..
힌트를 드리면요.리스트가[quote]0번째 리스트 :
힌트를 드리면요.
리스트가
이렇게 있을 때, m 이 15쯤 된다면요.
space[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 0, 0, 0 }이렇게 구성할 수도 있지만요.
space[] = { 1, 2, 3, 4, 0, 5, 6, 7, 8, 0, 9, 10, 11, 12, 0 }이렇게 구성할 수도 있겠죠 ?
각각에 대해 front[]와 rear[]를 각각 구성해보시고,
첫번째 리스트에 수를 하나 Insert해서 과정과 결과를 확인해보시면
도움이 될것 같네요. ^^
Front 와 rear가 왜 둘다 필요하냐면요...
링크드 리스트 인가요?
여러 배열들사이에 순서 혹은 연결고리로 그 둘이 사용되기 때문입니다
말씀대로 front 나 rear만 있다면 a배열뒤에 어떤 배열이다라고 단정지을 수 있는
연결고리가 없습니다. 혹시나 그 순서를 배열이 담긴 배열의 순서로 잡고싶다면
그때 윗분들이 말하는 복사 문제가 발생합니다
Quote: ... rear[i] <=
rear[i] <= front[i+1] 조건 때문에 예제가 틀린 것 같네요.
예를들어 i=2 일때, 12 <= 9 는 참이 아님.
그냥.. 다들 그 지적이 없는 것 같아서
댓글 달기