파이썬
-
Problem : https://leetcode.com/problems/evaluate-boolean-binary-tree/ Difficulty : Easy Status : Solved Time : 00:04:22 문제 설명 풀이 DFS로 간단히 접근하자.만약 현재 노드가 리프노드라면, 현재 노드값이 1인지의 boolean 값을 검사하여 반환하자.리프노드가 아니라면, 조건상 Full binary tree이므로 왼쪽과 오른쪽 서브트리가 반드시 존재한다. 왼쪽, 오른쪽 결과물을 현재 노드값에 따라 or 연산, 혹은 and 연산을 가하여 바로 반환하면 된다.비재귀로도 가능하겠지만 재귀면 역시 간단하게 풀린다. 풀이 코드(Python)# Definition for a binary tree node.# c..
2331. Evaluate Boolean Binary TreeProblem : https://leetcode.com/problems/evaluate-boolean-binary-tree/ Difficulty : Easy Status : Solved Time : 00:04:22 문제 설명 풀이 DFS로 간단히 접근하자.만약 현재 노드가 리프노드라면, 현재 노드값이 1인지의 boolean 값을 검사하여 반환하자.리프노드가 아니라면, 조건상 Full binary tree이므로 왼쪽과 오른쪽 서브트리가 반드시 존재한다. 왼쪽, 오른쪽 결과물을 현재 노드값에 따라 or 연산, 혹은 and 연산을 가하여 바로 반환하면 된다.비재귀로도 가능하겠지만 재귀면 역시 간단하게 풀린다. 풀이 코드(Python)# Definition for a binary tree node.# c..
2024.05.16 -
Problem : https://www.acmicpc.net/problem/19951 Difficulty : Gold 5 Status : Solved Time : 00:08:12 문제 설명 더보기2020년 5월 14일 논산훈련소에 입대한 태상이는 첫 총기 훈련에서 가스 조절기를 잃어버리는 중대한 실수를 범했다. 그로 인해, 태상이는 조교들에게 눈총을 받게 되었다. 조교들은 태상이에게 연병장(운동장)의 흙을 옮기는 일을 주고 제대로 수행하지 못하면 징계를 내리려고 한다. 연병장은 일렬로 이어진 N개의 칸으로 이루어져 있으며 각 칸마다 높이를 가지고 있고, 첫 번째 칸부터 순서대로 1번, 2번, 3번, ..., N번 칸으로 명칭이 붙어있다. 조교들은 총 M명이 있으며, 각 조교들은 태상이에게 a번 칸부터 ..
[백준/19951] 태상이의 훈련소 생활 (Python)Problem : https://www.acmicpc.net/problem/19951 Difficulty : Gold 5 Status : Solved Time : 00:08:12 문제 설명 더보기2020년 5월 14일 논산훈련소에 입대한 태상이는 첫 총기 훈련에서 가스 조절기를 잃어버리는 중대한 실수를 범했다. 그로 인해, 태상이는 조교들에게 눈총을 받게 되었다. 조교들은 태상이에게 연병장(운동장)의 흙을 옮기는 일을 주고 제대로 수행하지 못하면 징계를 내리려고 한다. 연병장은 일렬로 이어진 N개의 칸으로 이루어져 있으며 각 칸마다 높이를 가지고 있고, 첫 번째 칸부터 순서대로 1번, 2번, 3번, ..., N번 칸으로 명칭이 붙어있다. 조교들은 총 M명이 있으며, 각 조교들은 태상이에게 a번 칸부터 ..
2024.05.14 -
Problem : https://leetcode.com/problems/path-with-maximum-gold Difficulty : Medium Status : Solved Time : ??:??:?? 문제 설명 풀이 DFS로 풀이할 수 있는 문제. 총 grid 영역이 15 x 15이므로, 탐색을 통해 시간 내에 모든 경로를 테스트해 볼 수 있겠다. 풀이 코드 (Python)class Solution: dx = [0, 0, -1, 1] dy = [-1, 1, 0, 0] visited = [[]] n = 0 m = 0 def dfs(self, grid: List[List[int]], x : int, y : int, golds : int) -> int : ..
1219. Path with Maximum GoldProblem : https://leetcode.com/problems/path-with-maximum-gold Difficulty : Medium Status : Solved Time : ??:??:?? 문제 설명 풀이 DFS로 풀이할 수 있는 문제. 총 grid 영역이 15 x 15이므로, 탐색을 통해 시간 내에 모든 경로를 테스트해 볼 수 있겠다. 풀이 코드 (Python)class Solution: dx = [0, 0, -1, 1] dy = [-1, 1, 0, 0] visited = [[]] n = 0 m = 0 def dfs(self, grid: List[List[int]], x : int, y : int, golds : int) -> int : ..
2024.05.14 -
Problem : https://leetcode.com/problems/score-after-flipping-matrix/ Difficulty : Medium Status : Solved Time : ??:??:?? 문제 설명 풀이 비트마스킹은 너무 느렸다...! 좀 더 간결히, 그리고 문제의 본질을 꿰뚫어야 풀 수 있는 문제였다. 언뜻 보면 모든 경우의 수를 다 테스트해보아야 할 것 같지만, 함정이 있다. score는 이진법으로 계산되므로, 제일 높은 차수(0번째 column)가 모두 1인 경우가 그리디하게 가장 큰 값을 지니게 된다. 즉 column 0을 1로 세팅하도록 하자. 이제 column 1부터 순회를 시작하면 된다. 이 때, column 0이 원래 1인 경우는 row가 뒤집어진 경우이므로..
861. Score After Flipping MatrixProblem : https://leetcode.com/problems/score-after-flipping-matrix/ Difficulty : Medium Status : Solved Time : ??:??:?? 문제 설명 풀이 비트마스킹은 너무 느렸다...! 좀 더 간결히, 그리고 문제의 본질을 꿰뚫어야 풀 수 있는 문제였다. 언뜻 보면 모든 경우의 수를 다 테스트해보아야 할 것 같지만, 함정이 있다. score는 이진법으로 계산되므로, 제일 높은 차수(0번째 column)가 모두 1인 경우가 그리디하게 가장 큰 값을 지니게 된다. 즉 column 0을 1로 세팅하도록 하자. 이제 column 1부터 순회를 시작하면 된다. 이 때, column 0이 원래 1인 경우는 row가 뒤집어진 경우이므로..
2024.05.14 -
Problem : https://www.acmicpc.net/problem/17425 Difficulty : Gold 4 Status : Solved Time : ?? : ?? : ?? 문제 설명 더보기 두 자연수 A와 B가 있을 때, A = BC를 만족하는 자연수 C를 A의 약수라고 한다. 예를 들어, 2의 약수는 1, 2가 있고, 24의 약수는 1, 2, 3, 4, 6, 8, 12, 24가 있다. 자연수 A의 약수의 합은 A의 모든 약수를 더한 값이고, f(A)로 표현한다. x보다 작거나 같은 모든 자연수 y의 f(y)값을 더한 값은 g(x)로 표현한다.자연수 N이 주어졌을 때, g(N)을 구해보자. 입력 및 출력 더보기입력 첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 100,000)가 주..
[백준/17425] 약수의 합Problem : https://www.acmicpc.net/problem/17425 Difficulty : Gold 4 Status : Solved Time : ?? : ?? : ?? 문제 설명 더보기 두 자연수 A와 B가 있을 때, A = BC를 만족하는 자연수 C를 A의 약수라고 한다. 예를 들어, 2의 약수는 1, 2가 있고, 24의 약수는 1, 2, 3, 4, 6, 8, 12, 24가 있다. 자연수 A의 약수의 합은 A의 모든 약수를 더한 값이고, f(A)로 표현한다. x보다 작거나 같은 모든 자연수 y의 f(y)값을 더한 값은 g(x)로 표현한다.자연수 N이 주어졌을 때, g(N)을 구해보자. 입력 및 출력 더보기입력 첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 100,000)가 주..
2024.05.14 -
Problem : https://www.acmicpc.net/problem/2694 Difficulty : Gold 3 Status : Solved Time : 00:15:24 문제 설명 더보기 어떤 수열이 있을 때, 순서를 유지하면서 적절히 그룹으로 나누면서, 각 그룹에 들어있는 수의 합을 같게 만들 수 있다.예를 들어, 2, 5, 1, 3, 3, 7은 (2, 5), (1, 3, 3), (7)와 같이 나누면 각 그룹에 들어있는 수의 합이 7로 모두 같아진다.양의 정수로 이루어진 수열이 주어졌을 때, 이를 합이 같은 구간으로 나누는 방법은 여러 가지가 있다. 이때, 합의 최솟값을 구하시오.참고로 수열을 통째로 그룹 1개에 넣을 수 있다. 그럼 이때, 수의 합은 수열의 합이 된다. 입력 및 출력 더보기..
[백준/2694] 합이 같은 구간Problem : https://www.acmicpc.net/problem/2694 Difficulty : Gold 3 Status : Solved Time : 00:15:24 문제 설명 더보기 어떤 수열이 있을 때, 순서를 유지하면서 적절히 그룹으로 나누면서, 각 그룹에 들어있는 수의 합을 같게 만들 수 있다.예를 들어, 2, 5, 1, 3, 3, 7은 (2, 5), (1, 3, 3), (7)와 같이 나누면 각 그룹에 들어있는 수의 합이 7로 모두 같아진다.양의 정수로 이루어진 수열이 주어졌을 때, 이를 합이 같은 구간으로 나누는 방법은 여러 가지가 있다. 이때, 합의 최솟값을 구하시오.참고로 수열을 통째로 그룹 1개에 넣을 수 있다. 그럼 이때, 수의 합은 수열의 합이 된다. 입력 및 출력 더보기..
2024.05.12