본문 바로가기

Algorithm125

[LEET CODE] 1038. Binary Search Tree to Greater Sum Tree # Problem Given the root of a Binary Search Tree (BST), convert it to a Greater Tree such that every key of the original BST is changed to the original key plus sum of all keys greater than the original key in BST. As a reminder, a binary search tree is a tree that satisfies these constraints: The left subtree of a node contains only nodes with keys less than the node's key. The right subtree of.. 2021. 5. 24.
[Baekjoon] 2014. 소수의 곱 ( 탐욕 알고리즘 ) # Problem K개의 소수가 있다. 이때, 이 소수들 중에서 몇 개를 곱해서 얻게 되는 수들이 있을 것이다. 소수들을 선택할 때에는 같은 수를 선택해도 되며, 주어지는 소수 자체도 포함시키자. 예를 들어 세 소수가 2, 5, 7이었다면, 이러한 곱들을 오름차순으로 나타내 보면, 2, 4, 5, 7, 8, 10, 14, 16, 20, 25, 28, 32, 35, 등이 된다. K개의 소수가 주어졌을 때, 이러한 소수의 곱들 중에서 N번째 수를 구해 보자. 단 정답은 231보다 작은 자연수이다. 입력 첫째 줄에 K(1 ≤ K ≤ 100), N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 K개의 소수가 오름차순으로 주어진다. 같은 소수가 여러 번 주어지는 경우는 없으며, 주어지는 소수는 모두 54.. 2021. 5. 16.
[Baekjoon] 1080. 행렬 ( 탐욕 알고리즘 ) # Problem 0과 1로만 이루어진 행렬 A와 행렬 B가 있다. 이때, 행렬 A를 행렬 B로 바꾸는데 필요한 연산의 횟수의 최솟값을 구하는 프로그램을 작성하시오. 행렬을 변환하는 연산은 어떤 3*3크기의 부분 행렬에 있는 모든 원소를 뒤집는 것이다. (0 -> 1, 1 -> 0) 입력 첫째 줄에 행렬의 크기 N M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 행렬 A가 주어지고, 그 다음줄부터 N개의 줄에는 행렬 B가 주어진다. 출력 첫째 줄에 문제의 정답을 출력한다. 만약 A를 B로 바꿀 수 없다면 -1을 출력한다. # Solution n,m = map(int,input().split()) a = [list(map(int,input()))for _ in ran.. 2021. 5. 16.
[Baekjoon] 2437. 저울 ( 탐욕 알고리즘) # Problem 하나의 양팔 저울을 이용하여 물건의 무게를 측정하려고 한다. 이 저울의 양 팔의 끝에는 물건이나 추를 올려놓는 접시가 달려 있고, 양팔의 길이는 같다. 또한, 저울의 한쪽에는 저울추들만 놓을 수 있고, 다른 쪽에는 무게를 측정하려는 물건만 올려놓을 수 있다. 무게가 양의 정수인 N개의 저울추가 주어질 때, 이 추들을 사용하여 측정할 수 없는 양의 정수 무게 중 최솟값을 구하는 프로그램을 작성하시오. 예를 들어, 무게가 각각 3, 1, 6, 2, 7, 30, 1인 7개의 저울추가 주어졌을 때, 이 추들로 측정할 수 없는 양의 정수 무게 중 최솟값은 21이다. 입력 첫 째 줄에는 저울추의 개수를 나타내는 양의 정수 N이 주어진다. N은 1 이상 1,000 이하이다. 둘째 줄에는 저울추의 무.. 2021. 5. 16.
[Baekjoon] 16676. 근우의 다이어리 꾸미기 # Problem 곧 2018년이 끝나고, 2019년이 온다. 근우는 2019년에는 꼭 다이어리를 쓰기로 했다. 하지만, 처음 써보는 다이어리에 쓸 내용이 없어 고민하던 중 자신의 목표 연봉을 다이어리 앞에 쓰기로 했다. 다이어리를 쓰는 사람은 알겠지만 예쁜 다이어리의 핵심은 스티커다. 그렇기 때문에 근우는 목표 연봉을 손으로 쓰지 않고, 스티커로 붙이려고 한다. 목표연봉이 100이라면 [1] [0] [0]과 같이 붙이는 것이다. [1]이란 1이 써져있는 스티커로, 다른 숫자에 대해서도 동일한 규칙이 적용된다. 근우는 자신의 연봉 최댓값이 N임을 안다. 그렇기에 근우는 0부터 N까지의 수를 하나씩 스티커를 통해 모두 표현하고자 한다. 최댓값 N이 10이면 만드는 과정은 다음과 같다. 스티커 더미에서 [0.. 2021. 5. 15.
[Baekjoon] 12849. 본대 산책 (DP) # Problem 숭실 대학교 정보 과학관은 캠퍼스의 길 건너편으로 유배를 당했다. 그래서 컴퓨터 학부 학생들은 캠퍼스를 ‘본대’ 라고 부르고 정보 과학관을 ‘정보대’ 라고 부른다. 준영이 또한 컴퓨터 학부 소속 학생이라서 정보 과학관에 박혀있으며 항상 본대를 가고 싶어 한다. 어느 날 준영이는 본대를 산책하기로 결심하였다. 숭실 대학교 캠퍼스 지도는 아래와 같다. (편의 상 문제에서는 위 건물만 등장한다고 가정하자) 한 건물에서 바로 인접한 다른 건물로 이동 하는 데 1분이 걸린다. 준영이는 산책 도중에 한번도 길이나 건물에 멈춰서 머무르지 않는다. 준영이는 할 일이 많아서 딱 D분만 산책을 할 것이다. (산책을 시작 한 지 D분 일 때, 정보 과학관에 도착해야 한다.) 이때 가능한 경로의 경우의 수를.. 2021. 5. 8.
반응형

티스토리툴바