굳건하게

안녕하세요, 여행벌입니다.

C언어로 쉽게 풀어쓴 자료구조 6장 - 연결리스트1 연습문제 풀이입니다.

01 ~ 08 번은 손으로 09 ~ 24번은 직접 코드 구현으로 문제를 해결했습니다.

틀린 부분 혹은 이해가 안가시는 부분은 같이 댓글로 얘기해봐요!

[ 9번 ]

책의 insert와 다르게 insert된 Node를 연결리스트 제일 뒤에다가 붙이고 출력하면 입력한 순서대로 저장할 수 있습니다.

[ 10번 ]

연결리스트를 head부터 순회하며 count 해주면 됩니다.

[ 11번 ]

10번과 마찬가지로 head부터 순회하며 sum 해주면 됩니다.

[ 12번 ]

head부터 순회하며 특정 데이터를 count 해주면 됩니다.

[ 13번 ]

head부터 순회하며 특정 데이터를 찾고 그 부분을 책과 같이 remove 해주면 됩니다.

[ 14번 ]

Node에 이름, 나이, 키를 담을 수 있게 구조체를 새롭게 선언해주면 됩니다.

기타 다른 연산은 책과 동일하게 진행하면 되므로 생략하겠습니다.

[ 15번 ]

연결리스트를 head부터 순회하며 min, max 값을 저장하고 return 해주면 됩니다.

[ 16번 ]

먼저, 첫 번째 데이터를 삭제하고 그 뒤부터 한 칸씩 건너뛰며 삭제하면 됩니다.

연습문제 중에 가장 해결하기 까다로웠던 것 같습니다.

[ 17번 ]

연결리스트 A, B의 노드들을 똑같이 번갈아가며 새로운 연결리스트에 삽입해주면 됩니다.

[ 18번 ]

연결리스트 A, B의 노드들을 앞에서부터 순회하며 더 작은 값을 새로운 연결리스트에 삽입해주면 됩니다.

[ 19번 ]

연결리스트 C를 순회하며 flag 변수를 이용해 하나씩 번갈아가며 A, B에 노드를 삽입해주면 됩니다.

[ 20번 ]

책에도 자세히 나와있는 코드로 설명을 생략하겠습니다.

[ 21번 ]

값 x가 들어오면 expon만큼 x를 곱해서 x^expon을 만들고 거기에 coef를 곱해주며 sum하면 됩니다.

[ 22번 ]

배열을 이용해서 리스트를 구현하면 됩니다.

[ 23번 ]

앞에서 다루던 연결리스트 함수들을 조금씩만 수정해주면 됩니다.

[ 24번 ]

희소행렬은 14번과 마찬가지로 구조체만 새롭게 선언해주면 구현하는데 큰 어려움이 없습니다.

구조체만 코드로 표현했습니다.

안녕하세요, 여행벌입니다.

C언어로 쉽게 풀어쓴 자료구조 5장 - 큐 연습문제 풀이입니다.

01 ~ 07 번은 손으로 08 ~ 11번은 직접 코드 구현으로 문제를 해결했습니다.

12번은 생략했습니다.

틀린 부분은 같이 댓글로 얘기해보면 좋을 것 같습니다!

[ 8번 ]

원형큐이기 때문에, front와 rear가 역전된 상황만 따로 처리해주면 됩니다.

[ 9번 ] 

문제에서 하라는 대로 Stack을 2개 이용해서 Queue를 구현하면 됩니다.

[ 10번 ]

원형큐를 이용해서 적은 메모리로도 피보나치수열을 구현할 수 있습니다.

물론, int 형 범위를 넘어가는 수에 대해서는 오버플로우에 의해 이상한 값이 출력됩니다.

[ 11번 ]

덱을 책에서처럼 연결리스트로 구현하지 않고, 원형큐를 이용해서 구현해보았습니다.

안녕하세요, 여행벌입니다.

C언어로 쉽게 풀어 쓴 자료구조 4장 - 스택 연습문제 풀이입니다.

01 ~ 09 번은 손으로 10 ~ 16번은 직접 코드 구현으로 문제를 해결했습니다.

틀린 부분은 같이 댓글로 얘기해보면 좋을 것 같습니다!

[ 10번 ]

Stack은 LIFO 구조로 입력이 들어오는 순서대로 Push 한 다음에, Pop을 하면서 출력하면 반대로 출력이 됩니다.

[ 11번 ]

Stack을 활용한 괄호 짝 찾기 문제의 활용 버전으로 ' ( ' 를 만나면 Stack에 Push하고 ' ) ' 를 만나면 Stack의 Top 에 있는 ' ( ' 와 짝을 맺어준다.라는 기본 개념을 이용하면 됩니다.

' ( ' 마다 차례대로 번호를 부여하며 Stack 에 Push 하고 '  ) ' 를 만나면 Stack의 top이 지금 만난 ' ) '와 짝인 ' ( ' 이므로 ' ( ' 의 번호를 출력하며 Pop을 진행하면 됩니다.

[ 12번 ]

왜... 스택을 이용해야 되는지 이해할 수 없는 문제지만... 억지로 스택을 사용해보았습니다.

Input으로 들어온 문자 배열을 맨 앞에서부터 순회할 것입니다.

1. 내가 가리키고 있는 문자 now에서 대/소문자가 now와 같은 경우까지 문자 배열을 순회하며 count해준다.

2. now와 다른 문자가 나오면 지금까지의 count와 now를 Stack1에 Push해줍니다.

( 이때, 대문자면 소문자로 바꿔서 Push해줍니다. )

3. 문자 배열 순회가 끝났으면 Stack1에 저장된 원소들을 Pop하며 Stack2에 Push 해줍니다.

( 역순 출력을 위해서 )

4. Stack2를 Pop하며 출력합니다.

[ 13번 ]

이 문제도... 왜 스택을 이용해야 되는지 이해할 수 없는 문제다.

12번과 마찬가지로 Input으로 들어온 문자 배열을 맨 앞에서부터 순회하며 Stack1에 저장하고,

Stack1에 저장된 값들을 Pop하며 Stack2에 다시 저장해 출력을 하면 된다.

[ 15번 ]

좌표를 저장해 줄 element 를 선언하고 element 배열에 경로를 저장해나가면 된다.

[ 16번 ]

Stack에 문자 배열을 입력하고 Pop을 하면 문자배열을 역순으로 참조할 수 있다.

Stack에 문자배열을 소문자, 대문자를 다 소문자로 입력하고 문자배열을 순회하며 Stack이랑 비교하면 된다.

안녕하세요, 여행벌입니다.

오늘은 삽입 정렬(insertion sort)에 대해서 포스팅해보겠습니다.

삽입 정렬 이란

자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여,

자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 정렬 방식입니다.

EX)

바로 예시를 통해서 익혀보도록 하겠습니다.

[ 3 1 2 5 4 8 7 6 ] 배열을 삽입 정렬을 통해서 정렬해보겠습니다.

STEP 

1은 현재 정렬되어 있는 부분 [ 3 ] 과 비교했을 때 맨 앞으로 가야 됩니다.

따라서, [ 1 3 ] 으로 정렬이 진행됩니다.

STEP 2]

2는 현재 정렬되어 있는 부분 [ 1 3 ] 에서 1 과 3 사이에 위치해야 합니다.

STEP 3]

5는 현재 정렬되어 있는 부분의 맨 뒤에 위치해야 하므로 다음 STEP을 진행한다.

STEP 4]

4는 현재 정렬되어 있는 부분의 3과 5 사이에 위치해야 합니다.

STEP 5]

8은 현재 정렬되어 있는 부분이 맨 뒤에 위치하면 되므로 다음 STEP으로 넘어간다.

STEP 6]

7은 현재 정렬되어 있는 부분이 5와 8 사이에 위치해야 합니다.

STEP 7]

마지막으로 6은 5와 7 사이에 위치해야 합니다.

예시를 통해 알 수 있듯이, 삽입 정렬은 해당 원소가 삽입되어야 하는 위치로 삽입을 진행하며 정렬하는 방식입니다.

그렇다면 해당 원소가 삽입되어야하는 위치로 어떻게 삽입할 수 있을까요??

정답은 해당 원소가 원하는 위치에 도달할 때까지 계속 옆의 원소와 교환(SWAP)을 진행하는 방법입니다.

예를 들어, [ 2 3 4 5 1 ] 과 같이 배열이 있을 때, 1은 [ 2 3 4 5 ] 배열 맨 앞으로 가야 합니다.

따라서, 5와 SWAP하고 4와 SWAP하고 3과 SWAP하고 2와 SWAP해 원하는 위치에 도달할 수 있습니다.

코드 구현

void insertion_sort ( int list[], int n ){
  int temp;
  for ( int i = 1; i < n; i++ )
  {
    temp = list[i];
    int j = i - 1;
    while(j >= 0 && temp < list[j]){
    	list[j + 1] = list[j];
        j--;
    }
    list[j + 1] = temp;
  }
}

코드는 간단합니다.

i 번째 원소의 위치를 찾기 위해 i - 1 번 째 원소부터 차례대로 비교해나가며 자기 위치가 아니라면 SWAP을 진행합니다.

자기 위치를 찾았다면, while 문이 깨지고 찾은 위치 j + 1 번 째에 원소를 저장해줍니다.

복잡도 분석

N개의 원소가 있다고 가정하고 삽입 정렬의 복잡도를 분석해보겠습니다.

삽입 정렬은 버블 정렬, 선택 정렬과 다르게 최선의 경우, 최악의 경우 시간 복잡도가 다릅니다.

먼저, 최선의 경우(이미 배열이 정렬되어 있는 경우)에 대해서 생각해보겠습니다.

이미 자기 위치에 있는 원소는 옆에 있는 원소와 비교 연산 1회만 진행한 후 다음 STEP 으로 넘어가게 됩니다.

즉, 최선의 경우 N - 1 개의 원소에 대해서 비교 연산을 1번씩만 진행하면 되므로 O( N )의 복잡도를 가지게 됩니다.

그다음으로는 최악의 경우(배열이 역순으로 정렬되어 있는 경우)에 대해서 생각해보겠습니다.

모든 STEP마다 정렬되어 있는 배열의 모든 원소들과 비교 연산을 진행해야 하므로

총 ( N - 1 ) + ( N - 2 ) +  ⋯ + 1 번 비교 연산이 발생합니다.

등차수열의 합으로 O ( N ^ 2 ) 의 시간 복잡도를 가지는 것을 확인할 수 있습니다.

안정 정렬

삽입 정렬은 '안정 정렬' 입니다. 즉, 동일한 두 원소 간의 순서가 정렬 후에 바뀌지 않습니다.

삽입 정렬 작동 원리를 생각해보면 동일한 두 원소끼리는 이미 위치가 정해져 있으므로 순서가 바뀌지 않는 것을 쉽게 이해할 수 있습니다.

원활한 이해를 돕기 위해 [ 5-1  2  1  5-2 ] 를 삽입 정렬을 통해서 정렬해보겠습니다.

동일한 두 원소 5를 구분하기 위해 5-1 / 5-2 로 표현했습니다.

정렬 전 [ 5-1  2  1  5-2 ] → [ 2  5-1  1  5-2 ] → [ 1  2  5-1  5-2 ] 

다음과 같이 삽입 정렬은 안정 정렬인 것을 확인할 수 있습니다.

이상으로 삽입 정렬 포스팅을 마치겠습니다.