미새문지

연결 리스트 (Linked List) 연결 리스트는 노드의 집합으로, 각 노드가 다음 노드를 가리키는 포인터를 통해 순차적으로 연결된 구조이다. 연결 리스트는 동적 메모리 할당을 사용해 구현되며, 배열과 달리 런타임에 크기가 변경될 수 있다. 연결 리스트의 각 요소는 데이터 필드와 하나 혹은 그 이상의 다음(next) 링크 필드로 구성된다. 즉, 비엔나 소세지 마냥 줄줄이 이어져 있는 느낌이다. 연결 리스트의 종류 단일 연결 리스트(Singly Linked List) 각 노드가 다음 노드만을 가리키는 포인터를 가지며 리스트의 첫 번째 노드는 헤드(Head)라고 한다. 리스트의 마지막 노드는 꼬리(Tail)이며 다음 노드가 없음을 나타내는 NULL 값을 가진다. 작동 원리 삽입(Insertion) 새로운 ..

1번 문제 - 삽입정렬 연결리스트 함수 int insertSortedLL(LinkedList *ll, int item) { /* add your code here */ // 현재 노드와 새 노드를 선언하고 index를 0으로 초기화 ListNode *cur; ListNode *newNode; int index = 0; // 현재 노드에 리스트의 첫 노드값을 넣고 cur = ll->head; // 현재 노드가 값이 있는 동안 while(cur != NULL) { // 만약 현재 노드의 값이 입력된 값과 같으면 -1을 반환 if(cur->item == item){ return -1; } cur = cur->next; } // 현재 노드를 리스트의 첫 노드로 넣기 cur = ll->head; // 연결리스트의..

동적 계획법(Dynamic Programming) 복잡한 문제를 간단한 여러 개의 하위 문제로 분해하여 해결하는 알고리즘 설계 기법 큰 문제를 작은 문제로 나누어 해결하는 분할 정복과 비슷하지만, 다이나믹 프로그래밍은 각 하위 문제들이 서로 연관되어 있고, 작은 문제들의 해결을 통해 전체 문제를 해결한다. 동일한 하위 문제를 반복적으로 해결해야 할 경우, 해결 결과를 메모리에 저장해두고 이를 재사용함으로써 중복 계산을 피해 연산 시간을 단축시키는 것을 메모이제이션(Memoization)이라고 한다. 사용을 위한 두 가지 조건 중복 하위 문제 구조(Overlapping Subproblems) 큰 문제와 작은 문제를 같은 방법으로 해결할 수 있으며, 작은 문제의 답을 메모리에 저장하고 필요할 때마다 활용한다..

하노이탑 3개의 기둥이 있고 하나의 기둥에 여러 개의 원반이 있는데 각자 크기가 다 다르며 한 번에 한 개의 원반만 옮길 수 있고 크기가 큰 원반은 작은 원반 위에 올릴 수 없다. 재귀 함수를 이용한 알고리즘의 대표 문제이며 다음과 같이 동작한다 옮겨야 할 원반이 하나 뿐이라면, 해당 원반을 출발지 기둥에서 목적지 기둥으로 옮기기 그렇지 않으면 재귀함수를 사용해 가장 큰 원반을 제외한 나머지 원반들을 보조 기둥으로 옮긴다. 가장 큰 원반을 목적지 기둥으로 옮기고, 보조 기둥에 있는 원반들을 목적지로 옮긴다. # 하노이 함수(원판의 갯수, 시작봉, 중간봉, 끝봉) def hanoi(n, start, sub, finish): # 만약 원판의 개수가 1개면 끝봉으로 1번 이동하면 끝이니까 리턴값 if n ==..