hoodbilen's warroom

이번 과제는 main문과 struct 구조만 알려준 채로, 해당 main문 내에 존재하는 함수를 구현하고 알맞게 출력하도록 코딩을 하는게 목표였다.

위에는 알려준 구조체와 전역 포인터 ptr이고,

위에는 알려준 main문이다.

필자가 구현해야 했던 함수는 총 9개로

첫번째 indexSet함수를 제외한 8개의 함수는 모두 main문에서 사용된다.

main문을 분석해보면

#7 해당 소스 실행파일은 인자를 정확히 두개만 받는다.

#21 argv[1]에 들어간 문장("iamacybersecuritygenius.")을 insert함수를 이용해 각각 한개씩 구조체로 만들어준다.

(+조건 :  새로 선언하는 구조체의 index는 항상 0으로 해줘야한다. ex) 마지막구조체(value = '.')의 index = 0)

#23 invert함수를 이용해 node방향을 뒤집어 준다.

(+조건 : 각각의 index도 전환해줘야한다. ex) 첫번째구조체(value = 'i')의 index = 0 )

#24 current라는  현재 위치의 포인트변수를 선언하고 ptr값을 넣은다.

#25 printList함수에 current값을 넣어 link를 따라가며 모든 value값을 출력한다.

#27 length함수에 current값을 넣어 현재 구조체의 개수를 구한다.

#28 readValue함수에 i값을 넣어 index가 i인 구조체의 value값을 뽑아준다.

#34 delete함수를 이용해 next에 할당된 구조체를 free해주고 current가 next 다음함수를 가르키도록 한다.

#42 search함수를 이용해 해당 문자가 value의 값인 구조체를 찾아 index를 리턴해준다. findNode함수를 이용해 해당 구조체의 포인터를 리턴해준다.

이제 해당 main문에서 출력되는 값과, 과제에서 주어진 조건을 맞춰 함수를 구성한다.

함수를 순서대로 보면,

indexSet함수는 index를 설정해주는 함수이다. 사실 Single Linked List구조에 대해 생각해보면 link만 잘 연결해 주면 될것 같은데 문제 난이도를 위해 index 설정 조건을 넣으신거같다.

insert함수를 구현할 때 node가 NULL일때와 NULL이 아닐때에 대해 고려해줘야하는 조건이 있었다. NULL일 경우에는 새로운 구조체를 만들고 전 구조체에 연결해주고, NULL이 아닐 경우에는 이미 존재하는 구조체 사이에 값을 넣어주는 것으로 구현해 줬다.

Single Linked List의 link방향을 뒤집어주는 invert함수를 구현한다.(조건에 index도 바꿔 줘야한다 했음으로 index도 재설정해줬다.)

link를 따라 각 구조체의 value값을 출력해주는 printList함수를 구현해줬다.

입력받은 포인터부터 구조체 link의 끝가지 넘어가며 총 Single Linked List의 길이를 구해주는 length함수를 구현해준다.

num값을 인자로 받아 index가 num인 구조체의 value값을 return 해주는 readValue함수를 구현해준다.

포인터 x를 인자로 받아 x다음 구조체를 free해주고 그 다음 구조체와 x의 link를 연결해주는 delete함수를 구현해준다.

data를 인자로 받아 구조체의 value가 data와 같은 구조체가 존재하면 해당 구조체의 index를 return해주고, 아닐 경우 -1을 return해주는 search함수를 구현해준다.

num값을 인자로 받아 해당 num 값이 index에 들어있는 구조체를 찾아서 해당 구조체의 주소를 return해주는 findNode함수를 구현해준다.

이것으로 모든 함수를 구현해 주었고, 출력값을 보면

이런식으로 출력됨을 볼 수 있다.

고전적인 하노이타워 문제변형을 풀어봤다.

기존 하노이타워 문제는 3개의 rod와 여러개의 disk가 존재하는데, 1rod에 존재하는 모든 disk를 3rod에 모두 옮기면 되는 문제이다. 단, disk의 크기는 모두 다르고, disk는 한번에 한 개씩 옮길 수 있으며,  큰 disk가 작은 disk 위에 올라가서는 안된다. 라는 조건이 들어가 있다.

위 문제의 코드를 작성하면,

이렇게 작성할 수 있다.

honoi는 재귀함수 방식을 쓰며, 해당 코드를 분석하면

#9 rod1에 있는 n-1개의 disk를 rod2에 옮긴다.

#10 rod1에 있는 마지막 disk를 rod3에 옮긴다.

#11 rod2에 있는 n-1개의 disk를 rod3에 옮긴다.

해당 코드의 출력값을 보면

이렇게 출력이 가능하다.

그럼 이제 하노이타워 변형문제에 대해 설명하겠다.

이번 문제는 disk를 옮길때 rod를 건너 뛸 수 없다는 조건이 들어간다. 말 그대로 rod1에서 rod3으로 옮기고 싶다면 반드시 "rod1에서 rod2", "rod2에서 rod3"이렇게 두번 출력해주어야 한다는 말이다.

해당 문제를 코드로 작성하면

이런식으로 작성할 수 있다.

해당코드를 분석하면

#10 rod1에 있는 n-1개의 disk를 rod3에 옮긴다.

#11 rod1에 있는 마지막 disk를 rod2에 옮긴다.

#12 rod3에 있는 n-1개의 disk를 rod1에 옮긴다.

#13 rod2에 있는 마지막 disk를 rod3에 옮긴다.

#14 rod1에 있는 n-1개의 disk를 rod3에 옮긴다.

해당 코드의 출력값을 보면

출력 마지막 부분을 보면 이동한 횟수가 나오는데, 해당 코드는 𝑇𝑛 = 3𝑇(𝑛−1) + 2 그리고 𝑇1 = 2. 를 따른다.

해당 수열을 정리하면,  이동한 최소 횟수는 𝑇𝑛 = 3^𝑛 − 1 를 따르는 것을 알 수 있다.