Problem : https://leetcode.com/problems/split-a-string-into-the-max-number-of-unique-substrings Difficulty : Medium Status : Solved Time : 00:08:17  문제 설명  더보기문자열 s가 주어졌을때, 주어진 문자열을 분할하여 얻을 수 있는 유일 부분 문자열의 가장 큰 개수를 반환하라. 문자열 s는 임의의 공백이 아닌 부분문자열 리스트로 분할할 수 있고, 이 부분문자열을 이었을 때 원본 문자열이 된다. 그러나, 모든 부분문자열이 유일하도록 분할이 반드시 이루어져야 한다. 부분 문자열은 문자열 내부에 존재하는 연속적인 문자들로 정의된다. 풀이 DFS로 풀어보자. 현재 i번째 문자열부터 탐색을 진행한다..

Problem : https://leetcode.com/problems/lexicographical-numbers Difficulty : Medium Status : Solved Time : 00:14:11  문제 설명  더보기정수 n을 입력으로 받았을 때, [1, n] 범위의 정수를 사전식 순서대로 정렬하여 반환하라. 이 때, O(n)시간복잡도와 O(1) 추가 공간복잡도 알고리즘을 사용해야만 한다. 풀이 사전식 순서 = DFS. 사전식 순서의 규칙을 떠올려보자.한 숫자가 다른 숫자의 진부분집합이면, 그 숫자가 앞에 와야 한다 (예 : 111 -> 1111 -> 1112)그렇지 않다면..처음 자리부터 두 숫자의 교집합을 구하고 (예 : 111452,)교집합이 아닌 자리수부터 둘을 비교하여, 더 작은 숫자..

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..

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 : ..

Problem : https://www.acmicpc.net/problem/13023 Difficulty : Gold 5 Status : Solved Time : ?? : ?? : ??  문제 설명 더보기BOJ 알고리즘 캠프에는 총 N명이 참가하고 있다. 사람들은 0번부터 N-1번으로 번호가 매겨져 있고, 일부 사람들은 친구이다.오늘은 다음과 같은 친구 관계를 가진 사람 A, B, C, D, E가 존재하는지 구해보려고 한다.A는 B와 친구다.B는 C와 친구다.C는 D와 친구다.D는 E와 친구다.위와 같은 친구 관계가 존재하는지 안하는지 구하는 프로그램을 작성하시오.  입력 및 출력 더보기입력 첫째 줄에 사람의 수 N (5 ≤ N ≤ 2000)과 친구 관계의 수 M (1 ≤ M ≤ 2000)이 주어진다.둘..

Problem : https://www.acmicpc.net/problem/14570 14570번: 나무 위의 구슬 이진 트리란, 위처럼 모든 노드의 자식의 수가 2개 이하인 트리이다. 각 노드에 쓰여 있는 수는 노드의 번호를 의미한다. 특히, 이 문제에서는 루트가 고정되어 있으며, 노드의 순서가 중요한(어 www.acmicpc.net Difficulty : Gold 1 Status : Solved Time : 00:36:36 문제 설명 더보기 이진 트리란, 위처럼 모든 노드의 자식의 수가 2개 이하인 트리이다. 각 노드에 쓰여 있는 수는 노드의 번호를 의미한다. 특히, 이 문제에서는 루트가 고정되어 있으며, 노드의 순서가 중요한(어떤 서브트리에서도 좌우를 변경할 수 없는) 이진 트리에 대해 다루기로 한..