Algorithm
-
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로 나눈 몫에..
-
99클럽(2기) 코테 스터디 3일차 TIL # 완전탐색Algorithm 2024. 5. 30. 03:08
프로그래머스 - 소수 찾기문제: 한자리 숫자가 적힌 종이 조각이 흩어져 있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다. 각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어질 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 반환하도록 solution 함수를 완성해주세요.제한 사항:numbers는 길이 1 이상 7 이하인 문자열입니다.numbers는 0~9까지 숫자만으로 이루어져 있습니다."013"은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.1. 나의 풀이 문제 풀이에 앞서 문제를 어떻게 풀지 정리해보자면, numbers 문자열을 재배치할 수 있는 모든 경우의 수에서 소수가 몇 개인지 확인하면 된다. 소수 판별함수를 따로 만들면 좋을 것..
-
99클럽(2기) 코테 스터디 2일차 TIL # SortingAlgorithm 2024. 5. 28. 14:01
프로그래머스 - 최소 직사각형문제: 모든 명함의 가로 길이와 세로 길이를 나타내는 2차원 배열 sizes가 매개변수로 주어집니다. 모든 명함을 수납할 수 있는 가장 작은 지갑을 만들 때, 지갑의 크기를 반환하도록 solution 함수를 완성해주세요.제한사항: sizes의 길이는 1이상 10,000 이하입니다.sizes의 원소는 [w, h] 형식입니다.w는 명함의 가로 길이를 나타냅니다.h는 명함의 세로 길이를 나타냅니다.w와 h는 1이상 1,000 이하인 자연수입니다. 풀이 (시간복잡도: O(n)) 우선 문제를 풀기 쉽게 재구성해본다. sizes의 원소는 가로와 세로로 구성되어있는데, 사실 가로와 세로는 고정된 게 아니다. 직사각형을 90 회전시키면 회전 이전의 가로는 세로가, 회전 이전의 세로는 가로가..
-
99클럽(2기) 코테 스터디 1일차 TIL # Sorting # Two PointersAlgorithm 2024. 5. 28. 08:56
LeetCode 2824. Count Pairs Whose Sum is Less Than TargetGiven a 0-indexed integer array nums of length n and an integer target, return the number of pairs (i, j) where 0 and nums[i] + nums[j] .* 1 * -50 문제: n개의 integer로 구성된 array 'nums'와 integer 'target'이 주어졌을 때, 아래 조건을 만족하는 (i, j) 쌍의 개수를 반환조건: 0 1. 첫 번째 풀이 (시간복잡도: O(n^2))1) answer값 초기화 answer 값을 0으로 초기화한다. 2) 조건을 만족하는 nums의 인덱스 (i, j) 쌍 찾기 ..