본문 바로가기

Algorithm

 (117)
[백준] Python - 2003. 수들의 합 2 https://www.acmicpc.net/problem/2003 2003번: 수들의 합 2 첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmicpc.net 슬라이딩 윈도우 형태로 문제를 풀었습니다 슬라이딩 윈도우의 크기를 왼쪽, 오른쪽을 조절하면서 연속된 합이 target값과 같은지 비교하면됩니다! 1. 슬라이딩 윈도우의 합이 target보다 크거나 같다면 왼쪽 요소를 빼주고, window_start 인덱스를 1증가시켜줍니다. (구간이 작아지는 효과) 2. 슬라이딩 윈도우의 합이 target보다 작다면 오른쪽..
[LeetCode] Python - 720. Longest Word in Dictionary https://leetcode.com/problems/longest-word-in-dictionary/ Longest Word in Dictionary - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 한번에 한 문자를 만들수 있는 단어중에서 사전순으로 가장 작고, 가장 긴 단어를 찾는 문제이다. 생각 1. set으로 구성된 리스트를 만들고 처음은 빈 문자열로 초기화해준다. 조건에 해당하지 않는 경우 빈 문자열을 리턴해야하기 때문에 빈문자열을 원소로 가지게끔 초..
[LeetCode] Python - 98. Validate Binary Search Tree https://leetcode.com/problems/validate-binary-search-tree Validate Binary Search Tree - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 1. left 서브트리는 부모노드보다 작기때문에, 재귀함수를 통해 호출할때 right 파라미터에 현재 node의 값을 넣어 오른쪽 boundary를 갱신시켜줍니다. 2. right 서브트리는 부모노드보다 커야하기 때문에, 다음번 노드를 탐색하기위해 재귀함수로 호..
[LeetCode] Java, Python - 94. Binary Tree Inorder Traversal https://leetcode.com/problems/binary-tree-inorder-traversal/ Binary Tree Inorder Traversal - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 이진트리가 주어졌을때, 중위순회의 결과를 출력하는 문제이다. 중위순회는 left -> root -> right (왼쪽자식노드, 부모노드, 오른쪽자식노드) 순서대로 탐색하기때문에 재귀를 사용하여 풀었다. 1. 현재 노드가 null이 아니라면 먼저 가장 왼..
[LeetCode] Python - 648. Replace Words https://leetcode.com/problems/replace-words/ Replace Words - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 주어진 문장에서 각 단어들이 dictionary에 포함된다면 가장 짧은 어근이 되도록 교체하는 문제이다. sentence의 공백을 기준으로 단어의 개수는 1이상 1000이하이고, dictionary의 길이도 1이상 1000이하이기 때문에 이중포문을 돌아도 시간초과가 나지 않습니다. SSAFY 친구들과 같이 시..
[LeetCode] Java - 6. ZigZag Conversion https://leetcode.com/problems/zigzag-conversion/ ZigZag Conversion - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 문자열과 row의 크기가 주어지면 이를 지그재그 패턴으로 읽는 문제이다. 처음엔 지그재그패턴으로 한글자씩 읽어 2차원배열로 저장하려고 했다가, 이를 다시 지그재그패턴으로 읽은 문자열을 반환해야되서 단순하게 numRows 의 길이를 가진 1차원 배열에 넣어 지그재그패턴으로 읽은 값을 각 행별로 저..
[LeetCode] Java - 64. Minimum Path Sum (DFS + DP 기본문제) 이번 SSAFY 계절학기에서 진행한 알고리즘 특강 내용을 간단하게 정리했습니다! 우선 DFS와 메모이제이션을 사용한 다이나믹 프로그래밍입니다. 주어진 문제에서 N이 30이하일때 모든 경우를 탐색해야하는경우, 단순히 DFS만을 통해 문제를 풀수없는 경우가 있습니다. 이때 반드시 메모이제이션을 활용해야 문제를 풀수있습니다. 아래와 같은 문제를 통해 Top-down 방식으로 메모이제이션을 연습했습니다. https://leetcode.com/problems/minimum-path-sum/ Minimum Path Sum - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledg..
[백준] JAVA - 2805. 나무 자르기 https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net Python Code def solve(tree, length, height): maxHeight = 0 #적어도 length만큼 나무 가져갈려면 절단기 높이 최대값 몇으로 설정? left, right = 0, 1000000000 while(left = mid : remain += h-mid # print("mid : ", mid, " remain : ",r..

티스토리툴바