본문 바로가기

분류 전체보기107

[구현] 백준 1347: 미로 만들기 1347번: 미로 만들기 (acmicpc.net) 1347번: 미로 만들기 홍준이는 미로 안의 한 칸에 남쪽을 보며 서있다. 미로는 직사각형 격자모양이고, 각 칸은 이동할 수 있거나, 벽을 포함하고 있다. 모든 행과 열에는 적어도 하나의 이동할 수 있는 칸이 있다. 홍 www.acmicpc.net 이 문제에서 찝찝한 점은 처음 시작할 때 미로가 몇 칸짜리인지 미리 알 수 없다는 점이다. 따라서 최악의 경우를 고려해서 미로의 최대 크기를 미리 구해 놓고, 그 중간에서부터 주어진 input에 따라 미로를 그려 나가는 작업을 하였다. 이 경우는 통상적인 정의의 "미로"라고는 할 수 없겠지만, input이 모두 'F'인 경우가 미로 크기가 가장 길어지는 경우일 것이다. input 길이는 50보다 작으므로, 나는.. 2024. 1. 16.
[자료구조] Binary Search Tree 정의 다음과 같은 조건을 만족하는 binary tree를 binary search tree(BST) 라고 한다. 1. left subtree의 element들이 root element보다 작을 것. 2. right subtree의 element들이 root element보다 클 것. 가령, 1,2,3,4,5,6,7을 위 BST로 구현하면 다음과 같이 될 것이다. 특징 1. 앞서 binary tree를 포스팅하면서 binary tree의 순회 방식에는 pre-, in- , post- order의 3 가지 형태가 있다고 했었다. 이 중 inorder traversal은 root node의 방문 순서가 중간에 오는 방식이다. (left -> root -> right node 순서로 방문) 따라서, BST를 i.. 2024. 1. 12.
[자료구조] Binary Tree Binary Tree는 ordered tree의 일종으로, 각 node가 최대 2개까지의 children을 가질 수 있는 tree이다. 이 때, 모든 node의 children 개수가 모두 0 또는 2이면 이 binary tree는 'proper'하다고 하고, 그렇지 않으면 'improper' 하다고 한다. Binary Tree의 특징 모든 node의 children 갯수가 2 이하라는 특징 때문에, (nonempty) binary tree는 다음과 같은 특징을 지닌다. 1. 높이가 h일 때, 전체 노드의 갯수는 h+1 보다 크거나 같고 2^(h+1)-1 보다 작거나 같다. 전체 노드의 갯수가 h+1인 경우는 각 internal node가 단 하나의 child만을 가질 때, 전체 노드의 갯수가 2^(h+.. 2024. 1. 10.
[BruteForce] 백준 16197: 두 동전 16197번: 두 동전 (acmicpc.net) 16197번: 두 동전 N×M 크기의 보드와 4개의 버튼으로 이루어진 게임이 있다. 보드는 1×1크기의 정사각형 칸으로 나누어져 있고, 각각의 칸은 비어있거나, 벽이다. 두 개의 빈 칸에는 동전이 하나씩 놓여져 있고, www.acmicpc.net 재귀함수를 이용한 brute force 문제. 동전은 무조건 2개이고, 가능한 입력 방향은 4개이다. 다음과 같은 구조를 생각하면서 재귀함수를 작성하였다. 사실 대단히 어려운 문제가 아니지만 42% 정도에서 계속 오류가 나서 고생을 했는데, 알고 보니 내가 base case 조건을 [버튼을 10번 보다 많이 누를 것]이 아닌 [버튼을 10번 이상 누를 것]으로 오독해서 생긴 문제였다. 재귀함수를 짤 때는 항상 ba.. 2024. 1. 9.

티스토리툴바