목록알고리즘 공부 (17)

개발자가 되고 싶은 준개발자

[정렬] 가장 큰 수 (예외 케이스 및 코드)

문제 https://programmers.co.kr/learn/courses/30/lessons/42746# 코딩테스트 연습 - 가장 큰 수 0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요. 예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 programmers.co.kr 테스트 케이스 Parameters Return [6, 10, 2] "6210" [3, 30, 34, 5, 9] "9534330" [121, 12] "12121" [0, 0, 0] "0" [51, 15] "5115" 여기서 가장 중요한 케이스는 마지막 [51,15]였다. 풀이 1. Brute ..
알고리즘 공부/프로그래머스 2021. 8. 21. 16:36
[LeetCode] 16. 3Sum Closest 파이썬 코드

문제 16. 3Sum Closest [Medium] Given an array nums of n integers and an integer target, find three integers in nums such that the sum is closest to target. Return the sum of the three integers. You may assume that each input would have exactly one solution. Example 1: Input: nums = [-1,2,1,-4], target = 1 Output: 2 Explanation: The sum that is closest to the target is 2. (-1 + 2 + 1 = 2). Constrai..
알고리즘 공부/LeetCode 2021. 5. 29. 16:36
[LeetCode] 7. Reverse Integer 파이썬 코드

문제 7. Reverse Integer [Easy] Given a signed 32-bit integer x, return x with its digits reversed. If reversing x causes the value to go outside the signed 32-bit integer range [-231, 231 - 1], then return 0. Assume the environment does not allow you to store 64-bit integers (signed or unsigned). Example 1: Input: x = 123 Output: 321 Example 2: Input: x = -123 Output: -321 Example 3: Input: x = 12..
알고리즘 공부/LeetCode 2021. 5. 29. 15:08
[LeetCode] 235. Lowest Common Ancestor of a Binary Search Tree 풀이 및 코드

문제 Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST. According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and qas descendants (where we allow a node to be a descendant of itself).” BST가 주어질 때 가장 낮은 공통의 조상을 찾아라. 코드 문제 풀면서 주의 해야 했던 사항은 모든 노드가 uni..
알고리즘 공부/LeetCode 2021. 3. 7. 16:35
[LeetCode] 230. Kth Smallest Element in a BST 문제 및 풀이 코드

문제 Given the root of a binary search tree, and an integer k, return the kth (1-indexed) smallest element in the tree. BST가 주어졌을 때 K번째로 작은 수를 찾아라. 코드 BST 문제의 경우 우선 순회를 어떤 식으로 할지 정해야 한다. 순회의 방식에는 inorder(left->root->right), postorder(left->rightt->root), preorder(root->left->right) 세가지의 경우가 있다. 이 문제에서는 K번째 수를 찾으라 했으니 순회를 했을때 정렬이 되는 방법을 택하는 게 좋을 듯 하다. 따라서 inorder를 택했다. # Definition for a binary tre..
알고리즘 공부/LeetCode 2021. 3. 7. 15:54
[LeetCode] 98. Validate Binary Search Tree 풀이 및 코드

문제 트리가 주어졌을 때, 트리가 Binary Search Tree인지 판별하라 코드 (Naive 버전) 트리가 BST인지를 판별하기 위해서는 1) 왼쪽 subtree, 오른쪽 subtree가 BST여야 하며, 2) root의 왼쪽 subtree에 있는 값들은 root보다 모두 작아야 하며, root의 오른쪽 subtree에 있는 값들은 root보다 모두 커야 한다. (재귀적으로 바닥까지 모든 subtree가) 따라서 직관적으로 tree를 모두 traverse하면서 이를 확인하는 코드를 짰다. # Definition for a binary tree node. # class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = No..
알고리즘 공부/LeetCode 2021. 2. 27. 20:32
[프로그래머스] 베스트 앨범 (해쉬) - 파이썬 문제 풀이

문제 스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다. 속한 노래가 많이 재생된 장르를 먼저 수록합니다. 장르 내에서 많이 재생된 노래를 먼저 수록합니다. 장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록합니다. 노래의 장르를 나타내는 문자열 배열 genres와 노래별 재생 횟수를 나타내는 정수 배열 plays가 주어질 때, 베스트 앨범에 들어갈 노래의 고유 번호를 순서대로 return 하도록 solution 함수를 완성하세요. programmers.co.kr/learn/courses/30/lessons/42579?language=python3 코딩테스..
알고리즘 공부/프로그래머스 2021. 1. 3. 22:27
[LeetCode] 100. Same Tree 풀이 및 코드

문제 주어진 두 개의 트리가 같은 트리인지 확인해라. 풀이 이 문제는 각 하위 트리마다 모든 노드들이 같은지 확인해 주면 되므로 깊이우선탐색(DFS)으로 간단하게 풀 수 있다. 코드 # Definition for a binary tree node. # class TreeNode(object): # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution(object): def isSameTree(self, p, q): """ :type p: TreeNode :type q: TreeNode :rtype: bool """ if not p and no..
알고리즘 공부/LeetCode 2020. 9. 26. 23:41
[LeetCode] 103. Binary Tree Zigzag Level Order Traversal 풀이 및 코드

문제 레벨 별로 다른 순서(왼쪽->오른쪽, 오른쪽->왼쪽)로 이진 트리(Binary Tree)를 순회하라. 풀이 쉬울 줄 알았는데 생각보다 통과하기가 어려웠다. 기본적인 알고리즘은 이전 포스트인 이진 트리를 BFS(너비 우선 탐색) 방식으로 레벨별로 순회하는 알고리즘과 비슷하다. (june-coder.tistory.com/16?category=913762) [LeetCode] 102. Binary Tree Level Order Traversal 풀이 및 코드 문제 트리를 level 순으로 순회하여 각 레벨 별 노드의 값을 리턴한다. 풀이 이 문제는 트리를 level 순으로 순회하는 문제이기 때문에 BFS(너비 우선 탐색)가 적합하다. 트리의 루트부터 leaf까지 순� june-coder.tistory.c..
알고리즘 공부/LeetCode 2020. 9. 26. 22:40
[LeetCode] 102. Binary Tree Level Order Traversal 풀이 및 코드

문제 트리를 level 순으로 순회하여 각 레벨 별 노드의 값을 리턴한다. 풀이 이 문제는 트리를 level 순으로 순회하는 문제이기 때문에 BFS(너비 우선 탐색)가 적합하다. 트리의 루트부터 leaf까지 순회를 하면서 한 레벨 씩 리스트에 담는다. 한 레벨 씩 리스트에 담기 위해서는 이전 레벨의 노드들의 리스트를 받아 해당 노들들의 left, right을 리스트에 넣으면 된다. 코드 # Definition for a binary tree node. # class TreeNode(object): # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class So..
알고리즘 공부/LeetCode 2020. 9. 26. 21:56
이전 Prev 1 2 Next 다음