SQL 안 쓴지 좀 되어서 SQL 고득점키트 풀면서 상기시간을 가져보자 참고하기 좋은 MySQL 함수모음: https://inpa.tistory.com/entry/MYSQL-%F0%9F%93%9A-%EB%82%B4%EC%9E%A5%ED%95%A8%EC%88%98-%EC%A0%95%EB%A6%AC#string_%ED%95%A8%EC%88%98 다 MySQ...

https://leetcode.com/problems/pacific-atlantic-water-flow/description/ 이런 문제는 재밌어 보인다. 2중 for문 돌면서 특정 r 인덱스에 있는 정점으로부터 출발해 Pacific과 Atlantic에 모두 닿을 수 있는지 체크하면 될 것 같다. 그럼 Pacific에 닿는다는 것과 Atlantic에 ...

https://leetcode.com/problems/course-schedule/description/ 아이디어가 떠오르지 않아서 시간초과로 솔루션 참고함 위상 정렬을 통해 유향 그래프에 사이클이 존재하는지 여부를 체크하는 것이 핵심 진입차수를 기록하는 별도의 배열을 만들어서 관리하며 인접리스트를 사용해 선행과 후행의 연결고리를 관리한다. 진입차수...

https://leetcode.com/problems/clone-graph/description/ 무방향 그래프 탐색을 하면서 깊은 복사를 하는 문제인 것 같다. Node 인스턴스를 새로 만들어야 한다는 뜻 DFS, BFS 어떤 방식으로든 탐색이 가능할 것 같다. BFS 방식 Queue를 이용해서 poll(), 이어지는 노드는 offer() - 큐가 ...

https://leetcode.com/problems/jump-game/description/ DP는 익숙해지지가 않음.. 핵심 아이디어는 i + nums[i] 가 goal보다 크거나 같으면 닿을 수 있다는 것 goal은 다시 i로 초기화하고 점진적으로 0까지 갈 수 있는지 확인하면 된다. i + nums[i] >= goal 이라면 i까지만 와도 유...

https://leetcode.com/problems/unique-paths/description/ 오른쪽과 아래로만 이동 가능하다는 제약이 있다. 그렇다면 i, j 에는 i-1과 j-1값을 더해주면 된다고 생각했다. 방어조건으로는 n이나 m이 1인 경우 무조건 1을 리턴하도록 했다 (한가지 수밖에 없음) dp는 m 사이즈로 세팅해주고, 경우의 수 누...

https://leetcode.com/problems/decode-ways/description/ 숫자는 한자리가 될 수도, 두 자리가 될 수도 있다. 기본적인 아이디어는 dp[i]에 두 자리로 가능한 경우 dp[i - 2]의 값을 누적하고, 한 자리로 가능한 경우 dp[i - 1]의 값을 누적한다. 다만, 중요한 것은 두 경우가 다 가능할 수 있기 ...

https://leetcode.com/problems/house-robber-ii/description/ house robber 문제에서 변형이 된 문제다. 집들이 원형으로 이어져 있다는 전제가 추가되었다. 0 ~ n-1 까지 탐색하면 원형 조건에 걸리지 않는다(맨 마지막 집 계산 제외). 1 ~ n 까지 탐색하면 원형 조건에 걸리지 않는다(맨 처음 집...

https://leetcode.com/problems/house-robber/description/ 기본적으로 아이디어가 중요하다. 선택지는 2가지가 있다. 현재 인덱스를 터느냐/마느냐다. DP로 풀 때 dp[i]는 i-1 값과 i-2 + (현재인덱스 amount) 중 큰 값으로 넣으면 된다. i-1 값을 그대로 i에 세팅한다는 것은 현재 인덱스(i)...

https://leetcode.com/problems/combination-sum-iv/description/ Climbing Stairs의 심화버전 같은 문제다. 경우의 수가 nums만큼이 있으므로 이것을 계산해야 한다. dp 배열은 다른 문제들과 같이 target+1 길이를 가지는 int배열로 만들어 주고, dp[target]을 통해 가능한 경우의...

https://leetcode.com/problems/word-break/description/ DP왜이렇게 어렵냐.. 고민하다 솔루션 참고 아이디어는 s 길이 + 1만큼의 boolean dp[] 배열을 만들고 해당 인덱스까지(== 문자열에서 해당 포인트까지) 접근 가능한지 여부를 true/false 세팅해둔 뒤 최종적으로 dp[s.length()]하...

https://leetcode.com/problems/longest-common-subsequence/description/ 힌트를 참고해서 2차원 배열로 dp배열을 만들면 된다는 아이디어를 보고.. text1과 text2의 길이를 이용한 dp배열을 만들었다. 이후 2중 for문으로 dpi값을 제어하면 되는데, text1의 i-1 번째와 text2의 j...

https://leetcode.com/problems/longest-increasing-subsequence/description/ 문제에서 O(n log n)으로 풀어보라는 챌린지가 있는데 바로 떠오르진 않고.. O(n^2)는 다음과 같이 할 수 있겠다. nums길이와 똑같은 배열을 만들어서 1로 초기화한다(자기 자신 포함 길이기 때문에 최소 1). ...

https://leetcode.com/problems/coin-change/description/ > 이 문제를 코인 크기대로 정렬한 뒤 큰 순서대로 나누고 나머지 연산으로 누적해간다는 아이디어를 떠올린다면 틀린 것이다. 모르겠으면 아래 경우를 테스트케이스에 추가해 보라. coins = [3, 5], amount = 9 아이디어는 아래와 같다. 우선 ...

https://leetcode.com/problems/climbing-stairs/description/ DP의 입문이고 많이 본 문제다. 간단하게 풀어본다. 1까지 가는 경우의 수 = 1 (1 step) 2까지 가는 경우의 수 = 2 (1 step + 1 step OR 2 steps) 3부터는 i-1 + i-2가 됨 왜냐? 1 step으로 가는 경우...

https://leetcode.com/problems/reverse-bits/description/ int자료형 32비트이므로 32번의 순환 + 시프트연산으로 O(1)으로 해결할 수 있을거란 생각을 했다. 아이디어까지는 좋았으나 마지막비트 누적 연산에서 오류가 있어 통과하지 못하는 케이스가 있었다. 결국 뒤집을 대상(n)의 마지막 비트를 OR 연산하면...

https://leetcode.com/problems/missing-number/description/ O(n) 시간복잡도로 풀라는데, 사실 Binary라고 고정하지 않고 생각하면 쉽다. 그냥 n+1 사이즈로 카피 배열을 만들어서 nums[i]값을 인덱스로 값을 세팅해주면 된다.. boolean이든, 아니면 범위에서 벗어난 int값(예를 들어 -1)을 ...

https://leetcode.com/problems/counting-bits/description/ 문제에서 O(n log n)으로 풀면 쉽지만 O(n) 시간으로 풀 수 있는지 묻고 있다. O(n log n)으로 푸는 방식은 0 ~ n 까지 수행 * 각 순회마다 비트수 계산이다. 비트 수 계산은 Number of 1 Bits 문제에서 사용한 것과 같...

https://leetcode.com/problems/number-of-1-bits/description/ 참고: Integer 클래스에는 bitCount라는 메서드가 존재한다. 솔루션 참고해보니 -1 값과 함께 AND연산해가며 카운트하는 방식이 있고 아니면 int가 32비트라는 점을 참고해서 32번의 shift와 AND연산하며 카운팅하는 방식이 있다....

https://leetcode.com/problems/sum-of-two-integers/description/ 비트연산자가 익숙하지는 않아 솔루션 참고한다. Carry값을 찾으려면 AND 연산을 하면 되고 XOR 연산을 하면 캐리 고려하지 않고 합계를 계산할 수 있다고 한다. 캐리를 찾았으면 시프트연산해서 자릿수를 올려주고 더이상 캐리가 존재하지 않...