본문 바로가기

분류 전체보기249

[Leetcode]3111. Minimum Rectangles to Cover Points 문제 요약알고리즘 분류: 그리디난이도: Medium문제내용:2차원 배열 points, points[i] = [xi, yi] 와 정수 w가 주어진다. w는 사각형 가로 길이이다.사각형의 범위가 (x`, 0) , (x` + w, 0), (x`, y`), (x` + 2, y`)로 이루어 진게 몇개가 있습니다.각 points 사각형안에 포함이 되어 있습니다. 모든 점이 사각형 안에 포함 될때 최소 몇 개 사형이 필요한지 반환 하세요.사이트 주소: https://leetcode.com/problems/minimum-rectangles-to-cover-points/description/문제풀이  이번 문제는 모든 경우의 수로 구하면 시간초과가 날것이다. 그래서 최적의 시간내로 풀수 있는 그리디로 풀어야 통과가 되는.. 2024. 6. 26.
[Leetcode]1828. Queries on Number of Points Inside a Circle 문제 요약알고리즘 분류: 기하학난이도: Medium문제내용:[x, y]로 점으로 구성된 points와 [x, y, r]로 원으로 구성된 queries가 주어진다. queries로 주어진 [x, y, r]은 x, y 위치를 의미하고 r은 원의 반지름을 의미한다. 각 query 원 안에서 points 점들이 몇개 포함되는지 반환 하는 함수를 만들어라.사이트 주소: https://leetcode.com/problems/queries-on-number-of-points-inside-a-circle/description/문제풀이  이번 문제는 기하학 문제이고 원에 대한 개념만 알면 문제 풀기가 쉽다. 원은 중심점과 반지름 r로 이루어 져 있다. 원안에 각 point가 포함되어 있는지 여부는 원 중심점과 point.. 2024. 6. 20.
[Leetcode]1282. Group the People Given the Group Size They Belong To 문제 요약알고리즘 분류: Hash, list난이도: Medium문제내용:groupSizes라는 정수 배열이 주어지는데, 여기서 groupSizes[i]는 사람 i가 속한 그룹의 크기이다.그룹은 groupSize 크기 만큼 그룹에 속해야 한다.각 사람이 groupSizes[i]의 크기를 가진 그룹에 속하는 그룹의 목록을 반환해라사이트 주소: https://leetcode.com/problems/group-the-people-given-the-group-size-they-belong-to/description/문제풀이  이번 문제는 Hash와 리스트를 활용 하면되는 간단한 문제 이다. 구현은 아래와 같이 하면된다.결과에 담을 2차원 리스트와 Hash에 저장할 변수를 선언한다. Hash의 key-value는 .. 2024. 6. 7.
[Leetcode]2396. Strictly Palindromic Number 문제 요약알고리즘 분류: 수학난이도: Medium문제내용:숫자 n이 주어지면 2 ~ n-2 진법까지 변환한다.집법으로 변환 한 것에서 뒤집은 숫자와 다른 것 하나라도 있으면 false로 반환 한다. 사이트 주소: https://leetcode.com/problems/strictly-palindromic-number/description/문제풀이  이번 문제는 Palindromic Number 문제이다. 근데 여기서 진법으로 변환해서 뒤집은 숫자와 다른지 파악하면 된다.여기서 구현 해야 할것은 n진법 변환 작업이다. 자바는 n진법 변환 하는 함수 제공하는데 파이썬은 직접 구현 해야한다.파이썬 진법 구현은 아래와 같이 하면된다.# 진법 변환def baseN(num: int, base) -> int: p.. 2024. 5. 21.
[Leetcode]2433. Find The Original Array of Prefix Xor 문제 요약알고리즘 분류: 수학난이도: Medium문제내용:pref이라는 리스트가 주어진다.pref[i] = arr[0] ^ arr[1] ^ arr[2] ...... ^ arr[i]  식처러  arr 0번째 인덱스 부터 i번째 xor연산된 값이다.xor 연산되기 전의 arr를 구하여라사이트 주소: https://leetcode.com/problems/find-the-original-array-of-prefix-xor/description/문제풀이  이번 문제는 xor의 법칙만 알면 쉽게 풀수 있는 문제이다.위 내용 보면 pref[i] = arr[0] ^ arr[1] ^ arr[2] ...... ^ arr[i]으로 되어 있으면 pref[0] = arr[0]으로 0번째 인덱스는 그대로 넣으면 된다. 그럼 첫번.. 2024. 5. 16.
[Leetcode] 221. Maximal Square 문제 요약알고리즘 분류: DP난이도: Medium문제내용:가로, 세로 안에 0 과 1로 채워져 있다. 0은 빈곳 1은 면적이 있는 공간이다.정사각형 최대 넓이를 구하여라사이트 주소: https://leetcode.com/problems/maximal-square/description/문제풀이  이번 문제는 간단한 DP(동적계획법) 문제이다. DP에 대한 자세한 설명은 아래글에서 확인 해보면 된다.https://jih3508.tistory.com/89 [알고리즘 이론] 동적계획법(Dynamic Programming, DP)이론 이번에 볼 알고리즘은 동적계획법(Dynamic Programming)이다. 이 알고리즘은 줄어서 dp라고 많이 불리고 코딩테스트에도 자주 나오는 유형이라서 무조건 알아야 되는 알고즘.. 2024. 5. 13.

티스토리툴바