티스토리

일지 & 개발

검색하기

블로그 홈

일지 & 개발

jih3508.tistory.com/m

응애~ 개발자 님의 블로그입니다.

구독자: 7

방명록 방문하기

주요 글 목록

[BAEKJOON]2748 피보나치 수 2 문제 요약알고리즘 분류: dp난이도: Bronze1문제내용:피보나치 수는 0과 1로 시작한다. 피보나치 식은 아래와 같다.Fn = Fn-1 + Fn-2 N이 주어 졌을때 피보나치 Fn을 구하여라 (N 사이트: https://www.acmicpc.net/problem/2748문제풀이이번 문제는 재귀 호출로 풀기에는 숫자가 커질수록 계산량이 급격히 증가하기 때문에, 동적 계획법(Dynamic Programming, DP*을 사용해야 효율적으로 해결할 수 있다. 동적 계획법에 대해 잘 모르신다면, 아래 링크를 통해 자세한 설명을 확인 해보면 된다.https://jih3508.tistory.com/89 [알고리즘 이론] 동적계획법(Dynamic Programming, DP)이론 이번에 볼 알고리즘은 동적계획법.. 공감수 0 댓글수 0 2025. 1. 14.
[Leetcode]1781. Sum of Beauty of All Substrings 문제 요약알고리즘 분류: 구현, 문자열, 해쉬 난이도: Medium문제내용:문자열의 "아름다움(beauty)"은 가장 많이 나타나는 문자와 가장 적게 나타나는 문자의 빈도 차이로 정의됩니다.예를 들어, 문자열 "abaacc"의 아름다움은 3−1=23 - 1 = 23−1=2입니다.문자열 sss가 주어졌을 때, sss의 모든 부분 문자열(substring)의 아름다움의 합을 반환하세요사이트 주소:https://leetcode.com/problems/sum-of-beauty-of-all-substrings/description/ 문제풀이이번 문제는 주어진 문자열에서 모든 부분 문자열을 추출하여 각 부분 문자열의 "아름다움"을 계산하고 이를 합산하는 문제입니다. 문제를 해결하기 위한 과정은 다음과 같습니다. .. 공감수 0 댓글수 0 2025. 1. 13.
[Leetcode]2120. Execution of All Suffix Instructions Staying in a Grid 문제 요약알고리즘 분류: 이진법, 베열 난이도: Medium문제내용:n × n 크기의 격자가 주어집니다.로봇초기 위치 startPos에서 시작.문자열 s로 주어진 방향 이동 명령 ('L', 'R', 'U', 'D').로봇은 문자열 s의 어떤 i번째 명령부터 실행을 시작할 수 있고, 로봇의 명령을 순차적으로 실행 한다.(단 격자 범위 밖으로 이동시 멈춘다.)정상적으로 실행 가능한 명령의 개수를 반환 하여라사이트 주소: https://leetcode.com/problems/maximum-possible-number-by-binary-concatenation/description/문제풀이이 문제는 간단한 시뮬레이션 구현 문제이다. 문자열 s에서 각 명령을 시작점으로 설정하여 끝까지 실행하며, 실행 가능한 .. 공감수 1 댓글수 0 2025. 1. 12.
[Leetcode]3309. Maximum Possible Number by Binary Concatenation 문제 요약알고리즘 분류: 이진법, 베열 난이도: Medium문제내용:주어진 크기가 3인 정수 배열의 요소들을 이진수로 변환하고, 이들을 다양한 순서로 이어 붙여 만들 수 있는 숫자 중 가장 큰 값을 찾아 반환하여라사이트 주소: https://leetcode.com/problems/maximum-possible-number-by-binary-concatenation/description/문제풀이이번 문제는 3개수를 각 이진법으로 변환하여 여러가지 순서로 이어붙인 다음 10진수로 변환 한것중 가장 큰것을 구하면 된다. 그럼 크게 2가지만 구현 하면된다.3개 숫자 2진수 변환후 이어 붙이 다음 10진수로 변환3개 숫자 순열구현1. 3개 숫자 2진수 변환후 이어 붙이 다음 10진수로 변환 직업 진법을 변.. 공감수 0 댓글수 2 2025. 1. 11.
[Leetcode]2391. Minimum Amount of Time to Collect Garbage 문제 요약알고리즘 분류: 누적합, 문자열난이도: Medium문제내용:garbage 배열: 각 집의 쓰레기 종류 ('M', 'P', 'G')를 나타냄.travel 배열: 집 간 이동 시간 제공.각 트럭은 특정 쓰레기 ('M', 'P', 'G') 유형만 수거함.트럭은 집 0번에서 시작하며 필요한 집만 방문 가능.모든 쓰레기를 수거하는 데 필요한 최소 시간을 계산하여사이트 주소: https://leetcode.com/problems/minimum-amount-of-time-to-collect-garbage/description/ 문제풀이 이번 문제는 O(N)만큼 요구하는 문제이다. 그래서 누적합으로 풀어야한다. 누접합 관련 내용은 아래글에서 확인 해보면 된다.https://jih3508.tistory.com.. 공감수 0 댓글수 5 2025. 1. 10.
[Leetcode]2161. Partition Array According to Given Pivot 문제 요약알고리즘 분류: 배열, 구현난이도: Medium문제내용:pivot 기준으로 pivot보다 작으면 원쪽으로 들어온 값 순서대로 정렬하고 pivot보다 크면 오르쪽으로 들어온 값 순서대로 정렬하세요.사이트 주소: https://leetcode.com/problems/partition-array-according-to-given-pivot/description/문제풀이이번 문제는 단순한 구현 문제인 일반 적인 정렬 문제는 아니다. 만약 아래와 같이 단순 정렬 하면 오답처리가 될 것이다.그래서 아래와 같이 들어온값 순서 대로 정렬 해야 정답 처리가 될것이다.그래서 아래와 같이 pivot 기준으로 3가지로 구분한 다음 합치기만 하면 구현적인 부분은 끝이다.왼쪽: pivot보다 작을 때중간: pivot이.. 공감수 1 댓글수 0 2025. 1. 9.
[Leetcode]948. Bag of Tokens 문제 요약알고리즘 분류: 그리디, 투 포인터난이도: Medium문제내용:초기 에너지(initial power)와 초기 점수(initial score) 0을 가지고 게임을 시작한다.수 배열 tokens가 주어지며, 이 배열의 tokens[i]는 각 토큰의 에너지 값을 나타낸다.각 토큰은 한 번만 사용할 수 있으며, 다음 두 가지 방법 중 하나로 사용할 수 있습니다앞면: 현재 에너지가 tokens[i] 이상인 경우, 토큰 tokens[i]를 사용하여 에너지를 tokens[i]만큼 잃고 점수를 1 증가시킬 수 있습니다.뒷면: 현재 점수가 1 이상인 경우, 토큰 tokens[i]를 사용하여 점수를 1 잃고 에너지를 tokens[i]만큼 얻을 수 있습니다.최대 점수를 반환 하여라사이트 주소: https://le.. 공감수 1 댓글수 0 2024. 12. 1.
[BAEKJOON]1965 상자넣기 문제 요약알고리즘 분류: dp, LIS난이도: Silver2문제내용:상자가 일렬로 있다. 앞에 있는 상자의 크기가 뒤에 있는 상자의 크기보다 작으면, 앞에 있는 상자를 뒤에 있는 상자 안에 넣을 수가 있다.. 예를 들어 앞에서부터 순서대로 크기가 (1, 5, 2, 3, 7)인 5개의 상자가 있다면, 크기 1인 상자를 크기 5인 상자에 넣고, 다시 이 상자를 크기 7인 상자 안에 넣을 수 있다.앞의 예에서 차례대로 크기가 1, 2, 3, 7인 상자를 선택하면 총 4개의 상자가 한 개의 상자에 들어가게 된다.상자의 크기가 주어질 때, 한 번에 넣을 수 있는 최대의 상자 개수를 출력하는 프로그램을 작성하시오.사이트: https://www.acmicpc.net/problem/1965문제풀이 이번 문제에는 모든.. 공감수 0 댓글수 0 2024. 11. 27.
[BAEKJOON]11055 가장 큰 증가하는 부분 수열 문제 요약알고리즘 분류: dp, LIS난이도: Silver2문제내용:수열 A가 주어졌을 때, 그 수열의 증가하는 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오.예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가하는 부분 수열은 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 이고, 합은 113이다.사이트: https://www.acmicpc.net/problem/11055문제풀이 이번 문제에는 모든 경우의 수를 구해서 풀기가 힘들다. 모든 경우의 수를 구하 O(N^N)개 이상으로 나올수 있다. 그래서 이번 문제는 LIS 개념을 적용해서 풀어야 한다. LIS에 대한 개념은 아래 글에서 확인 해보면된.. 공감수 0 댓글수 0 2024. 11. 24.
[BAEKJOON]11722 가장 긴 감소하는 부분 수열 문제 요약알고리즘 분류: dp, LIS난이도: Silver2문제내용:수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오.예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10} 이고, 길이는 3이다.사이트: https://www.acmicpc.net/problem/11722문제풀이 이번 문제에는 모든 경우의 수를 구해서 풀기가 힘들다. 모든 경우의 수를 구하 O(N^N)개 이상으로 나올수 있다. 그래서 이번 문제는 LIS 개념을 적용해서 풀어야 한다. LIS에 대한 개념은 아래 글에서 확인 해보면된다.https://jih3508.tistory.com/46 [알고리즘.. 공감수 0 댓글수 0 2024. 11. 24.
[BAEKJOON]13417 카드 문자열 문제 요약알고리즘 분류: deque, 문자형, ASCII난이도: Silver3문제내용:가장 처음에 가져온 카드는 자신의 앞에 놓는다.그다음부터는 가져온 카드를 자신의 앞에 놓인 카드들의 가장 왼쪽, 또는 가장 오른쪽에 놓는다. N장의 카드에 적혀있는 알파벳의 처음 순서가 주어질 때, 태욱이가 만들 수 있는 카드 문자열 중 사전 순으로 가장 빠른 문자열을 출력하는 프로그램을 작성하시오.사이트: https://www.acmicpc.net/problem/13417문제풀이 이번 문제에서는 데크활용 하는 문제이다.데크 자료구조는 앞뒤로 삽입, 삭제가 용이 하는 점에서 이용하면 앞에 문자보다 우선 순위가 크면 뒤로 추가 하고 작으면 앞으로 추가만 하면 된다. 하지만 문자형은 단순하게 크기 비교 처리하기가 힘들다 .. 공감수 0 댓글수 0 2024. 11. 12.
[BAEKJOON]14916 거스름돈 문제 요약알고리즘 분류: 그리디난이도: Silver5문제내용:2원, 5원 동전으로 거스름 돈을 줄수 있다.거스름돈이 N일때 최소 동전 개수를 구하여라(안되면 -1로 출력하여)사이트: https://www.acmicpc.net/problem/14916 문제풀이 이번 문제는 전체 경우의 수를 탐색하기에는 최대 거스름돈이 10만이라서 모든 경우의 수를 구하면 시간 초과가 나서 O(N) 탐색으로 푸는 방법을 찾아야 될것이다. 그래서 이번 문제는 그리디로 풀것이다. 그리디에 대한 설명은아래글로 확인 해보면 된다.https://jih3508.tistory.com/70 [알고리즘 이론] 그리디(Greedy)이론 그리디 알고리즘은 탐욕 알고리즘이라고 부르기도 한다. 즉, 매 순간 선택할때 가장 좋은것을 선택하는 알.. 공감수 0 댓글수 0 2024. 11. 10.
[BAEKJOON]27961 고양이는 많을수록 좋다 문제 요약알고리즘 분류: 그리디난이도: Broze1문제내용:다음중 2가지 마법만 사용 할수있다.생성 마법: 고양이 1$1$마리를 마도카의 집에 생성한다.복제 마법: 현재 k개 있으면 k마리 이하만 복제 가능하다.사이트: https://www.acmicpc.net/problem/27961문제풀이 이번 문제는 전체 경우의 수를 탐색하기에는 10^12승 숫자 만큼 탐색하면 시간 초과가 나서 안될것이다. 그래서 O(logN)만큼 나오도록 구현 해야 한다. 그래서 이 문제는 그리디로 접근해야 한다. 그리디에 관련 내용은 아래글에서 확인해보면된다.https://jih3508.tistory.com/70 [알고리즘 이론] 그리디(Greedy)이론 그리디 알고리즘은 탐욕 알고리즘이라고 부르기도 한다. 즉, 매 순간 선택.. 공감수 1 댓글수 1 2024. 11. 10.
[BAEKJOON]7569 토마토 문제 요약알고리즘 분류: BFS, 그래프난이도: Gold5문제내용:문제풀이 CodePythonimport sysfrom collections import dequeinput = sys.stdin.readlinedef solution(boxs, location): dx = [0, -1, 0, 1] dy = [-1, 0, 1, 0] dz = [-1, 1] days = 0 queue = location while queue: z, y, x = queue.popleft() value = boxs[z][y][x] for i in range(4): fx = x + dx[i] fy = y + dy[i].. 공감수 0 댓글수 0 2024. 11. 9.
[BAEKJOON] 2644 촌수계산 문제 요약알고리즘 분류: BFS, DFS난이도: Silver2문제내용:사이트: https://www.acmicpc.net/problem/2644문제풀이 CodePython Javaimport java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); Map> adj = new HashMap(); int N .. 공감수 0 댓글수 0 2024. 11. 4.
[BAEKJOON] 2805 나무 자르기 문제 요약알고리즘 분류: 이진 탐색, 수학난이도: Silver3문제내용: 사이트: https://www.acmicpc.net/problem/2805문제풀이 CodePythonn, m = map(int, input().split())trees = list(map(int, input().split()))min_value = 1max_value = max(trees)while min_value mid]) if m > lenth: max_value = mid - 1 else: min_value = mid + 1print(max_value)Javaimport java.io.BufferedReader;import java.io.IOException;import java.io... 공감수 1 댓글수 0 2024. 11. 2.
[BAEKJOON] 11561 징검다리 문제 요약알고리즘 분류: 이진 탐색, 수학난이도: Silver3문제내용:1번부터 N개번 징검 다리가 있다.첫 징검다리는 아무대나 점프할수 있다.그 다음 징검다리는 이전 이동한 거리보다 1이상 더 긴거리로 이동해야 한다.N번 까지 최대 몇번 건널수 있는지 구하여리첫줄에 케이스 T가 주어지고 각 케이스마다 N이 주어진다.사이트: https://www.acmicpc.net/problem/11561 문제풀이이번 문제에서 최대 징검다리수가 10^16 이다. 이정도 숫자이면 1 부터 10^16까지 탐색하면 시간초과가 나올것이다. O(N) 탐색이 아닌 O(logN)의 탐색으로 처리할수 있도록 해야 시간복잡도 문제를 해결할수 있다. 그래서 이번 문제는 이진 탐새으로 풀어야 할수 있다. 이진 탐색 관련글은 아래에서 확인.. 공감수 1 댓글수 0 2024. 10. 29.
[BAEKJOON] 1072 게임 문제 요약알고리즘 분류: 이진 탐색, 수학난이도: Silver3문제내용:X: 게임 횟수, Y: 이긴 횟수, Z: 승률(정수)계속 이긴다고 가정 했을때 몇판 더해야 승률이 변하는지 구하여라 만약 변하지 못하면 -1로 반환 하여라사이트: https://www.acmicpc.net/problem/1072 문제풀이 이번 문제는 하나씩 +1 씩 대입해서 정답은 나오지만 최대 숫자가 100억이다. 그리고 승률은 소수가 아닌 정수이다. 그럼 변화할라면 1%올라가야 하는데 1000억기준으로 올라갈라면 최대 10억번을 탐색 해야 한다. 그럼 초당 연산 1억기준으로 O(N)탐색 하면 오류가 날수 있다. 그래서 O(logN)탐색 시간초과 이내로 끝내야 통과가 된다. 그래서 이진탐색으로 해결할것이다. 이진탐색에 대한 내용은.. 공감수 4 댓글수 1 2024. 10. 28.
[Leetcode]1222. Queens That Can Attack the King 문제 요약알고리즘 분류: 배열, 시뮬레이션, 구현난이도: Medium문제내용:8 × 8 체스말이 주어진다. 체스말에서 king 1명, queen N명이 있다.Queem 중에서 왕을 잡을수있는 Queen의 위치들을 반한 하여라단 앞에 가로 막는 퀸이 있으면 그것은 제외 해야 한다.사이트 주소: https://leetcode.com/problems/queens-that-can-attack-the-king/description/문제풀이 이번 문제는 구현 문제중에서 시뮬레이션 문제이다. 각 Queen을 이동 시켜 King까지 갈수 있는지 체크만 하면 되는 문제이다. 일단 퀸이 움직일수있는 방향은 대각선, 가로, 세로 총 8군대이다. 하지만 각 queen이 8방향 탐색하면 시간적으로 비효울이 나와서 반대.. 공감수 1 댓글수 0 2024. 10. 27.
[Leetcode]654. Maximum Binary Tree 문제 요약알고리즘 분류: Tree, 재귀호출난이도: Medium문제내용:nums배열, 리스트를 주어 줬을때 아래와 같은 트리를 완성 하여라nums에서 가장 큰 값을 루트 노드로 만듭니다.가장 큰 값의 왼쪽 부분 배열로 왼쪽 서브트리를 재귀적으로 만듭니다.가장 큰 값의 오른쪽 부분 배열로 오른쪽 서브트리를 재귀적으로 만듭니다.사이트 주소:https://leetcode.com/problems/maximum-binary-tree/description/문제풀이 이번 문제는 이진 트리를 완성시켜야 되고 완성시키기 위해서 재귀호출을 사용 해서 풀것이다. 트리에 대한 자세한 글은 아래 글에서 확인 하여라https://jih3508.tistory.com/87 [알고리즘 이론] 트리(Tree)이론 이번에 볼 자료구조는.. 공감수 0 댓글수 0 2024. 10. 5.
[Leetcode]826. Most Profit Assigning Work 문제 요약알고리즘 분류: Two Pointer난이도: Medium문제내용:difficulty, profit, worker 있다.dificulty[i]는 난이도이고 profit[i]는 diffculty[i]수행시 보상이다.worker는 일하는 사람 최대 할수 있는 난이도를 나타내고 diffculty 이하만 수행 할수 있다.worker들이 최대 보상 받을수 있는 합친 값을 나타 내어라사이트 주소: https://leetcode.com/problems/most-profit-assigning-work/description/문제풀이 이번 문제는 브루드포스 같은 모든 경우의 수로 풀면 시간 초과가 난다. 그래서 최적의 시간 복잡도를 돌려야 하는 투포인트 문제이다. 투 포인터 대한 설명은 아래글에 참고하여라https.. 공감수 1 댓글수 0 2024. 10. 2.
[알고리즘 이론] 투 포인터(Two Pointers) 설명은 나중에 올리겠다. 공감수 0 댓글수 0 2024. 10. 2.
[Leetcode]2610. Convert an Array Into a 2D Array With Conditions 문제 요약알고리즘 분류: Array, 구현난이도: Medium문제내용:nums 배열/리스트를 준다.nums에 아래조건하에 2차원 리스트로 변경한것을 반환 해야한다..각 리스트에 중복된 숫자가 없어야 한다.사이트 주소: https://leetcode.com/problems/convert-an-array-into-a-2d-array-with-conditions/description/문제풀이 이번 문제는 간단한 구현문제이다. 구현은 아래와 같이 하면된다.2차원 리스트를 선언한다.각 리스트 1행부터 탐색해서 num이 있는지 확인한다.없으면 없는 행에 추가한다.리스트 각 행마다 탐색했는데 다 있으면 새로 행을 추가해서 num을 담는다.이렇게 구현하면 시간 복잡도는 nums 개수 탐색하는것과 리스트 포함하는지 확인.. 공감수 0 댓글수 0 2024. 9. 28.
[Leetcode]1007. Minimum Domino Rotations For Equal Row 문제 요약알고리즘 분류: Greedy난이도: Medium문제내용:tops, bottoms 같은 길이 주사위 배열을 준다.tops[i], bottoms[i] 같은 index위치끼리 바꿀수 있다.top과 bottom을 바꾸면서 top이나 bottom중에서 같은 주사위 숫자가 같게 만들수 있을때 최소 몇번 바꾸면되는지 반환 하여라 만약 안될 경우 -1로 반환 하여라사이트 주소: https://leetcode.com/problems/minimum-domino-rotations-for-equal-row/description/문제풀이모든 경우의 수로 답은 나오지 브루드포스로 풀경우에는 시간 초과가 나올것이다. 그래서 이번문제는 그리디로 풀어야 한다. 그리디 관련 설명은 아래글을 확인 해보면된다.https://ji.. 공감수 0 댓글수 0 2024. 9. 23.
[Leetcode]3271. Hash Divided String 문제 요약알고리즘 분류: Hash, Ascill Code, 문자열난이도: Medium문제내용:a-z 를 0-25까지 표현한다.(ex. a = 0, b = 1, c = 3 ...... ,z = 25)문제에서 문자열 s, k정수를 준다.문자열 s에서 k만큼 자르고 자른 문자열에서 각 알파벳을 숫자로 변환하고 합친다.합친것을 숫자에서 알파벳으로 변한다. 넘어가면 26나머지 값을 알파벳을 변환한다.자른 문자열에서 처리한 것들을 합친것을 반한하여라사이트 주소: https://leetcode.com/problems/hash-divided-string/description/문제풀이 이번 문제는 문자열을 각 문자형으로 변환후 Ascill Code로 처리하는 문제이다. 문자형 Ascill Code로 변환해서 처리하는 문.. 공감수 0 댓글수 0 2024. 9. 21.
[Leetcode]2181. Merge Nodes in Between Zeros 문제 요약알고리즘 분류: LinkedList, 구현난이도: Medium문제내용:0 사이에 값을 합쳐서 하나의 노드로 표현해라.사이트 주소:https://leetcode.com/problems/merge-nodes-in-between-zeros/description/문제풀이 이번 문제는 링크드리스트 노드 클래스나 구조체를 활용하는 문제이다. 노드클래스에 대한 이해도만 있으면 문제 푸는데는 어렵지 않다. 일단 아래그림처럼 처음에 나온 링크드 리스트에서 0사이 값을 합쳐서 다시 링크드리스트를 만들기만 된다. 그림을 보면 어떻게 구현 해야 할지 보일것이다. 그럼 구현은 아래처럼 하면된다.노드 새로 인스턴스 한다.다음노드가 끝있을때까지 반복문을 돌린다.현재 노드가 0이 아니면 인스턴스한 노드에 값을 더하고 다음 .. 공감수 0 댓글수 0 2024. 8. 30.
[Leetcode]983. Minimum Cost For Tickets 문제 요약알고리즘 분류: 동적계획법(DP)난이도: Medium문제내용:1 ~ 365여행가는 날들 days 변수와 1, 7, 30일 기준 이용료 costs를 준다.days 날짜대로 여행 간다고 했을때 최소 비용 구하여라사이트 주소: https://leetcode.com/problems/minimum-cost-for-tickets/description/문제풀이 이번 문제는 동적계획법(DP)으로 풀어야 통과되는 문제이다. DP에 관한 성명은 아래 글에서 확인 해보면된다.https://jih3508.tistory.com/89 [알고리즘 이론] 동적계획법(Dynamic Programming, DP)이론 이번에 볼 알고리즘은 동적계획법(Dynamic Programming)이다. 이 알고리즘은 줄어서 dp라고 많이.. 공감수 0 댓글수 0 2024. 8. 20.
[Leetcode]1038. Binary Search Tree to Greater Sum Tree 문제 요약알고리즘 분류: Tree, BFS, BST난이도: Medium문제내용:원래 BST의 모든 키가 자신보다 큰 키들의 합과 원래 키를 더한 값으로 변경되도록 하세요.사이트 주소: https://leetcode.com/problems/binary-search-tree-to-greater-sum-tree/description/ 문제풀이문제의 트리 구조는 아래와 같다. 노드의 왼쪽 서브트리는 노드의 키보다 작은 키를 가진 노드들로만 이루어져 있어야 합니다.노드의 오른쪽 서브트리는 노드의 키보다 큰 키를 가진 노드들로만 이루어져 있어야 합니다.왼쪽 및 오른쪽 서브트리 또한 이진 탐색 트리여야 합니다.이번 문제에서는 트리의 탐색하면서 더하는 식으로 진행 하면된다.트리와 DFS 관한 내용은 아래 글에서 확인 .. 공감수 0 댓글수 0 2024. 8. 18.
[Leetcode]935. Knight Dialer 문제 요약알고리즘 분류:동적계획법(DP)난이도: Medium문제내용:나이트는 체스의 이동처럼 같다나이트는 체스판이 아닌 계산기에서 이동한다.(단 *, # 이동 불가능이다.)0~9에서 아무대나 시작한다고 했을때 이동횟수가 n을 주어 졌을때 나올수 있는 경우의 수를 반환 하여라.사이트 주소: https://leetcode.com/problems/knight-dialer/description/문제풀이 이번 문제는 나이트 이동때문에 백트레킹이라고 볼수 있지만 n이 5000인점을 보면 백트레킹으로 풀면 시간 초과로인하여 완전 탐색같은 알고리즘으로는 하기는 그렇다. 그래서 최적화 할 수 있는 동적 계획법을 해야 한다. 동적계획법에 대한 설명은 아래글에서 확인해보면 된다.https://jih3508.tistory... 공감수 1 댓글수 0 2024. 8. 14.
[Leetcode]3211. Generate Binary Strings Without Adjacent Zeros 문제 요약알고리즘 분류: 재귀호출난이도: Medium문제내용:문자열 길이 n이 있다.문자열에는 0과 1만 올수 있다.0뒤에는 1만 올 수 있다.사이트 주소: https://leetcode.com/problems/generate-binary-strings-without-adjacent-zeros/description/문제풀이 이번 문제는 간단한 재귀호춣 구현이다. 구현은 아래와 같이 하면된다.끝에 숫자가 1일때만 0추가하고 재귀호출한다.뒤에 1을 추가하고 재귀호출한다.문자열길이가 n일때 리스트에 추가한다. 재귀호출 기본적인 문제라서 문제 푸는데는 어렵지 않다. 위에 처럼 구현 하면 시간 복잡도는 O(2^n)만큼 나온다.CodePythonclass Solution: def validStrings(sel.. 공감수 0 댓글수 0 2024. 8. 11.

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.