전체 글
-
99클럽(2기) - 코테스터디 15일차 TIL # GraphAlgorithm 2024. 6. 12. 20:57
LeetCode - 1791. Find Center of Star Graph There is an undirected star graph consisting of n nodes labeled from 1 to n. A star graph is a graph where there is one center node and exactly n - 1 edges that connect the center node with every other node.You are given a 2D integer array edges where each edges[i] = [ui, vi] indicates that there is an edge between the nodes ui and vi. Return the center..
-
99클럽(2기) - 코테스터디 14일차 TIL # Binary SearchAlgorithm 2024. 6. 11. 20:42
LeetCode - 1351. Count Negative Numbers in a Sorted MatrixGiven a m x n matrix grid which is sorted in non-increasing order both row-wise and column-wise, return the number of negative numbers in grid.Constraints:m == grid.lengthn == grid[i].length1 -100 1. 첫 번째 풀이 풀이는 20분 정도 걸렸지만이중 반복문으로 모든 행과 열을 순회하기 때문에 시간 복잡도가 O(m * n)이다. 모든 행은 다 탐색하더라도 열에 대해서는 이분 탐색을 적용할 수 있을 것 같았지만 해결책이 쉽게 떠오르지 않았다. 1) 행렬..
-
99클럽(2기) - 코테스터디 13일차 TIL # Binary SearchAlgorithm 2024. 6. 11. 00:32
LeetCode - 35. Search In Position Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.You must write an algorithm with O(log n) runtime complexity.Constraints1 -104 nums contains distinct values sorted in ascending order.-104 1. 첫 번째 풀이 원래는 풀이 과정을 머릿속으로 그려보고 답을 낼 수 있을 것 같다는..
-
99클럽(2기) - 코테스터디 12일차 TIL # Dynamic ProgrammingAlgorithm 2024. 6. 10. 10:42
LeetCode - 1025. Divisor Game Alice and Bob take turns playing a game, with Alice starting first. Initially, there is a number n on the chalkboard. On each player's turn, that player makes a move consisting of:Choosing any x with 0 and n % x == 0.Replacing the number n on the chalkboard with n - x.Also, if a player cannot make a move, they lose the game.Return true if and only if Alice wins the..
-
99클럽(2기) - 코테스터디 11일차 TIL # Dynamic ProgrammingAlgorithm 2024. 6. 7. 20:56
LeetCode - 118. Pascal's TriangleGiven an integer numRows, return the first numRows of Pascal's triangle.In Pascal's triangle, each number is the sum of the two numbers directly above it as shown: 1. 나의 첫 번째 풀이 동적 계획법을 풀기 위해 반복적으로 등장하는 동일한 패턴을 찾으려고 했다. 현재 행의 현재 열에 들어갈 데이터는 이전 행의 '현재 열 - 1인 인덱스'를 가지는 데이터의 값과 이전 행의 '현재 열과 동일한 인덱스'를 가지는 데이터의 값을 합친 값이라는 패턴을 발견했다. 즉, 현재 위치의 값은 바로 윗 줄의 양쪽 대각선 방향으로 인접한..
-
99클럽(2기) - 코테스터디 10일차 TIL # Dynamic ProgrammingAlgorithm 2024. 6. 6. 19:11
LeetCode - 338. Counting BitsGiven an integer n, return an array ans of length n + 1 such that for each i (0 ), ans[i] is the number of 1's in the binary representation of i.정수 n이 주어졌을 때, n + 1 길이의 array ans반환ans의 요소는 0부터 n까지의 10진수를 2진수로 변환했을 때의 1의 개수 풀이1) 0부터 n까지의 정수로 이루어진 리스트 생성 리스트 컴프리핸션으로 0부터 n까지의 수를 리스트로 만들었다. 리스트 Comprehension 사용법[표현식 for 요소 in 이터러블] 2) 해당 리스트의 모든 요소를 바이너리로 변환 map 함수로 0부터 ..
-
99클럽(2기) - 코테스터디 9일차 TIL # GreedyAlgorithm 2024. 6. 4. 16:24
프로그래머스 - 체육복문제점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다. 예를 들어, 4번 학생은 3번 학생이나 5번 학생에게만 체육복을 빌려줄 수 있습니다. 체육복이 없으면 수업을 들을 수 없기 때문에 체육복을 적절히 빌려 최대한 많은 학생이 체육수업을 들어야 합니다. 전체 학생의 수 n, 체육복을 도난당한 학생들의 번호가 담긴 배열 lost, 여벌의 체육복을 가져온 학생들의 번호가 담긴 배열 reserve가 매개변수로 주어질 때, 체육수업을 들을 수 있는 학생의 최댓값을 return 하도록 solu..
-
99클럽(2기) - 코테스터디 8일차 TIL # Binary Tree # DFS # 재귀Algorithm 2024. 6. 4. 00:12
LeetCode - 104. Maximum Depth of Binary TreeGiven the root of a binary tree, return its maximum depth.A binary tree's maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node. 1. 나의 풀이(accepted 되었지만 올바른 풀이 방식이 아님!) 루트 노드를 기준으로 리프 노드 방향으로 왼쪽 자식 노드들의 간선의 개수, 오른쪽 자식 노드들의 간선의 개수를 각각 세어서 그 둘 중 최대값을 2로 나눈 몫에 1을 더한 값을 반환하면 된다고 생각했다. 간선의 개수를 2로 나눈 몫에..