Krafton_jungle 5기 25 ~ 26일차 TIL - 알고리즘, 자료구조

알고리즘

 

1890 점프

# 실패코드!

import sys
from collections import deque

input = sys.stdin.readline

n = int(input())
arr = []
for _ in range(n):
    arr.append(list(map(int, input().split())))

queue = deque()
# x,y 좌표값 추가
queue.append((0,0))
res = 0
while queue:
    cur_y, cur_x = queue.popleft()
    if cur_y == n-1 and cur_x == n-1:
        res += 1
        continue
    distance = arr[cur_y][cur_x]
    new_x = cur_x + distance
    if distance != 0 and new_x < n:
        queue.append((cur_y, new_x))
    new_y = cur_y + distance
    if distance != 0 and new_y < n:
        queue.append((new_y, cur_x))

print(res)

처음엔 바보같이 BFS로 접근했다가 당연하게도 시간 초과가 떠버렸다.

이후 DP로 방향성을 잡고 점프가 가능한 최적의 해를 DP table에 저장하는 식으로 완성함

 

# 완성코드

n = int(input())
board = [list(map(int, input().split())) for _ in range(n)]
d = [[0] * n for _ in range(n)]
dx = [0, 1]
dy = [1, 0]
d[0][0] = 1  # 시작점 초기화
for x in range(n):
    for y in range(n):
        jump = board[x][y]
        if jump == 0:  # 도착
            break
        for i in range(2):
            nx = x + jump * dx[i]
            ny = y + jump * dy[i]
            if 0 <= nx < n and 0 <= ny < n:
                d[nx][ny] += d[x][y]
        for i in d:
            print(i)
        print()
print(d[n-1][n-1])

 

2579 계단 오르기

import sys
input = sys.stdin.readline
n = int(input())
stair = [int(input()) for _ in range(n)]


def up(stair):
    m = len(stair)
    dp = [0] * (m)
    if m == 1:
        return stair[0]
    elif m == 2:
        return sum(stair)
    dp[0] = stair[0]
    dp[1] = stair[0] + stair[1]
    dp[2] = max(stair[0] + stair[2], stair[1] + stair[2])
    for i in range(3,n):
        dp[i] = max(dp[i - 2] + stair[i], dp[i - 3] + stair[i - 1] + stair[i])
    return dp[-1]
print(up(stair))

 

이것도 마찬가지로 뛸 수 있는 최적의 해를 구해 누적시키는 방법으로 풀이했음

 

 

자료구조

 

1. 연결리스트 - insert sorted LL

typedef struct _listnode{
	int item;
	struct _listnode *next;
} ListNode;			// You should not change the definition of ListNode

typedef struct _linkedlist{
	int size;
	ListNode *head;
} LinkedList;	


//////////////////////////////////////////////////////////////////////////////////

int insertSortedLL(LinkedList *ll, int item)
{
	// 리턴할 인덱스
	int index = 0;
	// 노드 생성 및 데이터 초기화
	ListNode *new_node;
	new_node = (ListNode *) malloc(sizeof(ListNode));
	new_node -> item = item;
	new_node -> next = NULL;

	// 만약 리스트가 비어있으면 노드를 리스트 첫번째에 추가
	if (ll -> head == NULL) {
		ll -> head = new_node;
	} else {
		ListNode* cur = ll -> head; // 탐색을 위한 포인터
		ListNode* prev = NULL; 

		if (cur -> item > new_node -> item) {
			new_node -> next = cur;
			ll -> head = new_node;
		} else {
			while (cur != NULL && cur -> item < new_node -> item) {
				prev = cur;
				cur = cur -> next;
				index += 1;
			}
			if (cur != NULL && cur -> item != new_node -> item) {
				new_node -> next = cur;
				prev -> next = new_node;
				return index;
			} else if (cur == NULL) {
				prev -> next = new_node;
				return index;
			} else if (cur -> item == new_node -> item) {
				free(new_node);
				return -1;
			}
		}
	}
}

///////////////////////////////////////////////////////////////////////////////////

요구 조건은 간단하다. LL에 노드를 삽입하는데 오름차순으로 넣고, 등록에 성공하면 index를 반환한다.

만약 이미 같은 수가 들어가있거나 등록에 실패하면 -1을 반환하는 기초적인 LL 코드

 

2. 연결리스트 - alternate merge LL

void alternateMergeLinkedList(LinkedList *ll1, LinkedList *ll2)
{
    // 리스트의 head가 null이면
    if (ll1->head == NULL || ll2->head == NULL)
    {
        return;
    }

    ListNode* cur1 = ll1->head;

    while (cur1 != NULL && ll2->head != NULL) {
        ListNode* cur2 = ll2->head;
        ll2->head = cur2->next;
        cur2->next = cur1->next;
        cur1->next = cur2;
        cur1 = cur2->next; // 다음 첫 번째 노드로 이동
    }
}

노드의 구조체는 처음 예제와 동일함으로 해당 함수만 올리겠다.

해당 코드를 간단하게 설명하자면 

이런 형식의 리스트 2개를

이렇게 하나로 이어주는 함수를 작성하면 된다.

 

 

3. 연결리스트 - move odd items to back LL

void moveOddItemsToBack(LinkedList *ll)
{
    // 빈 리스트이거나 리스트에 노드가 하나만 있는 경우
    if (ll->head == NULL || ll->head->next == NULL)
    {
        return;
    }

    ListNode *cur = ll->head;
    ListNode *before = NULL;
    ListNode *odd_head = NULL;
    ListNode *odd_tail = NULL;

    while (cur != NULL) {
        if (cur->item % 2 != 0) {
            ListNode* odd = cur;
            if (before != NULL) {
                before->next = cur->next;
            } else {
                ll->head = cur->next;
            }

            cur = cur->next;
            odd->next = NULL;

            if (odd_head == NULL) {
                odd_head = odd_tail = odd;
            } else {
                odd_tail->next = odd;
                odd_tail = odd;
            }
        } else {
            before = cur;
            cur = cur->next;
        }
    }

    if (odd_head != NULL) {
        if (ll->head == NULL) {
            ll->head = odd_head;
        } else {
            before->next = odd_head;
        }
    }
}

이 코드의 동작은 다음과 같다.

이런 리스트를

홀수를 뒤로 밀어주는 형식

 

head와 tail을 계속 업데이트 해주며 완성된 리스트 뒤에 붙여주는 방식으로 풀었음

 

 

4. 연결리스트 - move even items to back LL

void moveEvenItemsToBack(LinkedList *ll)
{
	ListNode* cur = ll -> head;
	ListNode* before = NULL;
	ListNode* even_head = NULL;
	ListNode* even_tail = NULL;

	while (cur != NULL) {
		if (cur->item % 2 == 0) {
			ListNode* even = cur;
			if (before != NULL) {
				before->next = cur->next;
			} else {
				ll->head = cur->next;
			}
			cur = cur->next;
			even->next = NULL;

			if (even_head == NULL) {
				even_head = even_tail = even;
			} else {
				even_tail->next = even;
				even_tail = even;
			}
		} else {
			before = cur;
			cur = cur->next;
		}
	}

	if (even_head != NULL) {
		if (ll->head == NULL) {
			ll->head = even_head;
		} else {
			before->next = even_head;
		}
	}
}

이건 사실상 3번 함수에서 != 를 ==로 바꿔주기만 하면 됨

 

5. 연결리스트 - front back split LL

void frontBackSplitLinkedList(LinkedList *ll, LinkedList *resultFrontList, LinkedList *resultBackList)
{
	ListNode* slow = ll->head;
	ListNode* fast = ll->head;
	ListNode* prev;

	while (fast != NULL && fast->next != NULL) {
		prev = slow;
		slow = slow->next;
		fast = fast->next->next;
	}

	if (prev != NULL) {
		if (fast != NULL) {
			resultBackList->head = slow->next;
			prev->next->next = NULL;
			resultFrontList->head = ll->head;
		} else {
			prev->next = NULL;
			resultFrontList->head = ll->head;
			resultBackList->head = slow;
		}
	}
}

이 방법은 정말 바보같이 풀었는데 기본적으로 제공되는 linked_list의 size를 쓰면 되는문제다.

나는 그 사실을 뒤늦게 알게 되어 그렇게 안하고 1칸씩 전진하는 slow 포인터와 2칸씩 전진하는 fast 포인터를 선언해준 뒤 fast 포인터가 탈출조건을 만족하면 그걸 기준으로 리스트를 나누도록 작성했다.

 

6. 연결리스트 - move max to front

int moveMaxToFront(ListNode **ptrHead)
{
	if (*ptrHead == NULL || (*ptrHead)->next == NULL) {
		return 0;
	}
	// 가장 큰 값을 가진 노드의 바로 전 노드를 저장할때 사용
	ListNode *maxPrev = NULL;
	ListNode *prev = NULL;
	ListNode *cur = *ptrHead;
	ListNode *max = *ptrHead;

	while(cur->next != NULL) {
		if (cur->next->item > max->item) {
			maxPrev = cur;
			max = cur->next;
		}
		prev = cur;
		cur = cur->next;
	}

	if (maxPrev != NULL) {
		maxPrev->next = max->next;
		max->next = *ptrHead;
		*ptrHead = max;
		return 1;
	}

	return 0;
}

해당 문제는 가장 큰 값을 가지고 있는 노드를 맨 앞으로 보내는 코드인데, 2중 포인터의 개념만 이해하면 쉽게 풀 수 있는 문제였다.

 

7. 연결리스트 - recursive reverse

void RecursiveReverse(ListNode **ptrHead)
{
	printList(*ptrHead);
	if (*ptrHead == NULL || (*ptrHead)->next == NULL) {
		return;
	}
	ListNode* cur = *ptrHead;
	ListNode* next_node = cur->next;

	// 최소단위로 나누기
	RecursiveReverse(&next_node);

	cur -> next -> next = cur;

	cur -> next = NULL;
	*ptrHead = next_node;
	printList(*ptrHead);
}

이 문제는 내 스스로의 힘으로 풀지 못하고, 같은 조원의 도움을 받아서 풀었다.

재귀를 사용해 최소 단위로 나눈 뒤, 배열을 역순으로 조합하는데, 그 과정은 다음 화면과 같다.

어떻게 이렇게 정렬을 할 생각을 했을까...