Algorithm
[leetcode] 689. Maximum Sum of 3 Non-Overlapping Subarrays
[leetcode] 689. Maximum Sum of 3 Non-Overlapping Subarrays
2024.12.28https://leetcode.com/problems/maximum-sum-of-3-non-overlapping-subarrays/description/ 해당 문제는 정수배열 nums 와 k 가 주어졌을 때 겹치지 않는 최대합을 가지는 길이 k 의 부분 배열 3개를 찾아서 반환하는 문제입니다여기서 주의할 점은 정답이 여러개 인 경우 index 가 작은것 부터 반환해야 합니다. Approach해당 문제는 총 3개의 부분 배열을 반환해야 합니다 그러므로 3 개의 section 으로 분할 할 수 있고 이것을 left, middle, right 라고 정의 하겠습니다. 먼저 sliding window 를 통해 구간 합을 미리 구해 두겠습니다.val sums = IntArray(n) { i -> nums.sl..
leetcode - 862. Shortest Subarray with Sum at Least K
leetcode - 862. Shortest Subarray with Sum at Least K
2024.11.17https://leetcode.com/problems/shortest-subarray-with-sum-at-least-k/description/?envType=daily-question&envId=2024-11-17 Approach해당 문제를 O(N) 시간 복잡도로 문제를 해결 하기 위해서 PrefixSum 과 단조 증가 (Monotonic increasing) Queue 를 사용할 예정입니다. 해당 문제를 한글로 번역해보자면 다음과 같습니다. 정수 배열 nums와 정수 k가 주어졌을 때, 다음 조건을 만족하는 가장 짧은 부분 배열의 길이를 반환하세요:부분 배열의 합이 최소한 k 이상이어야 함부분 배열은 비어있지 않아야 함만약 이러한 조건을 만족하는 부분 배열이 존재하지 않는다면 -1을 반환여기서 **..
leetcode: Maximum Sum Circular Subarray (kadane 알고리즘)
leetcode: Maximum Sum Circular Subarray (kadane 알고리즘)
2024.11.10https://leetcode.com/problems/maximum-sum-circular-subarray/ 해당 문제는 kadane 알고리즘 방법으로 접근하여 문제를 해결 하였습니다. Approach Kadane's algorithm을 사용하여 일반적인 최대 부분합을 O(n)에 구합니다.순환하는 경우는 전체 합에서 최소 부분합을 빼서 구합니다.모든 원소가 음수인 경우는 별도로 처리합니다.시간복잡도: O(n) 공간복잡도: O(1)전체 배열의 합 (total): 5 + (-3) + 5 = 7최소 부분합 (minSum): -3연속된 부분 배열 중 가장 작은 합total - minSum = 7 - (-3) = 10이것이 바로 [5,5]를 선택했을 때의 합과 같습니다!이렇게 되는 이유는:순환 배열에서 양 끝의 ..
Leetcode - Gas Station
Leetcode - Gas Station
2024.03.02Problem There are n gas stations along a circular route, where the amount of gas at the ith station is gas[i]. You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from the ith station to its next (i + 1)th station. You begin the journey with an empty tank at one of the gas stations. Given two integer arrays gas and cost, return the starting gas station's index if you ..
Leetcode86. partition list (kotlin)
Leetcode86. partition list (kotlin)
2023.04.22https://leetcode.com/problems/partition-list/ Partition List - LeetCode Can you solve this real interview question? Partition List - Given the head of a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x. You should preserve the original relative order of the no leetcode.com Given the head of a linked list and a value x, partition..
Leetcode79. Word Search (w. kotlin)
Leetcode79. Word Search (w. kotlin)
2023.04.16Given an m x n grid of characters board and a string word, return true if word exists in the grid. The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once. Example 1: val board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]] val word = "SEE" Output: true..
순열(Permutation) 구하기 with kotlin
순열(Permutation) 구하기 with kotlin
2022.11.261, 2, 3 이라는 배열이 주어졌을때 해당 element 에 대해서 permutation 을 구한다고 가정해봅시다. 경우의 수는 총 6 가지 입니다 6개의 경우의 수가 나온는 것을 증명 하려면 첫번째 자리수에 올수 있는 것들은 총 [1, 2, 3] 세가지 중 하나 입니다. 두번째 자리수에 올수 있는 것들은 첫번째 를 제외한 총 두가지 중 하나 입니다. 세번째 자리수에 올수 있는 것들은 첫번째 두번째를 제외한 총 한가지 입니다. 3 * 2 * 1 = 6 경우의 수를 구하는 대표적인 방법은 backtracking 입니다. 해당 Tree 를 코드로 구현해보면 다음과 같습니다. fun solution(nums: IntArray): Unit { val endpoint = nums.size val result =..
Leet code 3 — Longest Substring Without Repeating Characters
Leet code 3 — Longest Substring Without Repeating Characters
2022.10.01Given a string s, find the length of the longest substring without repeating characters. Example 1: Input: s = "abcabcbb" Output: 3 Explanation: The answer is "abc", with the length of 3. Example 2: Input: s = "bbbbb" Output: 1 Explanation: The answer is "b", with the length of 1. Example 3: Input: s = "pwwkew" Output: 3 Explanation: The answer is "wke", with the length of 3. Notice that the ans..
합이 같은 부분집합(DFS : 아마존 인터뷰) - (golang)
합이 같은 부분집합(DFS : 아마존 인터뷰) - (golang)
2022.05.28문제 풀이 해당 문제는 subset(부분집합) 을 만들어서 전체 배열의 원소의 합을 2로 나누었을 때 부분집합 의 합과 똑같으면 YES 다르면 NO 를 출력 하는 방식으로 접근 해보았다. 먼저 부분집합을 만드는 방식에 있어서 해당 원소를 부분집합으로 포함 할지 안할지 이렇게 2진 트리로 재귀호출을 할수 있다. func SameSumSubSet(depth, sum int) { SameSumSubSet(depth+1, sum+array[depth]) SameSumSubSet(depth+1, sum) } depth 와 함께 sum 이라는 변수를 재귀호출 로 넘김으로써 depth 가 N 과 같아졌을때 총합 / 2 와 비교하기 위해서 사용한다. 첫번째 재귀 호출은 해당원소를 부분집합으로 사용하는 재귀호출이고 두번..
[백준] 9663번 : N-Queen - Golang
[백준] 9663번 : N-Queen - Golang
2022.05.22https://st-lab.tistory.com/118 [백준] 9663번 : N-Queen - JAVA [자바] www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하.. st-lab.tistory.com 해당 블로그를 참조하여 문제를 해결 하였습니다. 처음에는 2차원 배열을 사용하여 문제를 해결 하려고 하였는데 DFS 의 특성상 깊이를 행 for 문을 사용하여 열을 검사하는 방식으로 풀면 1차원 배열로도 해당 문제를 풀수 있엇습니다. package main import ( "bufio" "fmt" "math" ..
Easy - 9 . is palidrome (with golang)
Easy - 9 . is palidrome (with golang)
2022.04.21Given an integer x, return true if x is palindrome integer. An integer is a palindrome when it reads the same backward as forward. For example, 121 is a palindrome while 123 is not. Example 1: Input: x = 121 Output: true Explanation: 121 reads as 121 from left to right and from right to left. Example 2: Input: x = -121 Output: false Explanation: From left to right, it reads -121. From right to l..
백준 - 좌표정렬하기 11650번 (정렬) with golang
백준 - 좌표정렬하기 11650번 (정렬) with golang
2021.10.04좌표 정렬하기 1 초 256 MB 55178 26613 20212 48.139% 문제 2차원 평면 위의 점 N개가 주어진다. 좌표를 x좌표가 증가하는 순으로, x좌표가 같으면 y좌표가 증가하는 순서로 정렬한 다음 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다. 출력 첫째 줄부터 N개의 줄에 점을 정렬한 결과를 출력한다. 예제 입력 1 5 3 -1 4 2 1 2 1 3 1 3 예제 출력 1 복사 1 -1 1 1 2 2 3 3 3 4 해결방법 package main import (..