분류 전체보기

leetcode 1361. Validate Binary Tree Nodes

문제 이해 주어진 그래프가 B-Tree인지 체크하는 문제 문제 접근 그래프가 B-Tree인지 확인하려면 Circular Reference가 없어야 한다. 루트 노드가 반드시 하나 존재해야 한다. 모든 노드는 하나의 부모 노드만 가져야 한다. 루트 노드부터 시작하여 모든 노드를 탐색할 수 있어야 한다. (연결) 그래프가 B-Tree인지 확인하는 조건들은 예시를 분석하며 빠르게 접근할 수 있었지만 표현에 서툼이 있었음. Try 1. B-Tree를 구성하며 조건 체크 코드를 작성하다보니 시간복잡도가 O(n^2)까지 치솟았다. 노드의 개수가 최대 10^4개이기 때문에 시간복잡도에서 해결될 수 없어서 포기했다. Try 2. Graph를 미리 만들고 조건을 검사 그래프를 만들고 난 후에 검사를 하게 되면 각 조건 ..

leetcode 746. Min Cost Climbing Stairs

문제 이해 계단을 끝까지 올라가기 위해 필요한 최소 비용을 구하는 문제 각 계단의 비용은 int[] cost 에 저장되어 있음 문제 접근 계단을 올라가는 경우의 수가 많고 딱히 수학적 규칙이 떠오르지 않으니 완전 탐색을 시도 dfs를 활용하여 완전 탐색 시도 1. dfs로 접근 완전 탐색은 성공적이였지만 시간 초과 발생 class Solution { int answer = Integer.MAX_VALUE; public int minCostClimbingStairs(int[] cost) { dfs(cost, -1, 0); return answer; } void dfs(int[] cost, int idx, int sum) { int newSum = sum; if(idx != -1 && idx != cost...

leetcode 1095. Find in Mountain Array

문제 이해 Mountain Array가 주어지고 해당 배열에서 target을 찾는 문제 (여러 target 값이 존재한다면 index가 제일 낮은 값을 찾으면 된다.) 제한 조건으로는 Mountain Array를 100번 이하로 접근해야 한다. 문제 접근 상승 배열과 하강 배열이 합쳐져있는 형태이며 target을 찾기 위해 binary search를 활용하면 될 것이라고 생각 binary search를 활용하기 위해서는 상승 배열과 하강 배열로 나누는 top (변곡점)의 index 값을 찾아야함 target이 2개 존재할 수 있기 때문에 상승 배열에서 먼저 찾아보고 하강 배열에서 찾아보면 된다. 결과적으로 이 문제는 변곡점을 찾는다. target을 찾는다. 두가지 과정이 필요하다. 복잡도 예상 변곡점 t..

프로그래머스 - 괄호 회전하기

https://school.programmers.co.kr/learn/courses/30/lessons/76502 문제 이해 주어진 문자열 s의 맨 앞 문자를 맨 뒤로 이동시켜서 주어진 조건에 만족하는 케이스가 몇 개인지 체크하는 문제 풀이를 위한 고민 문제에서 알려준대로 실제로 문자열을 조작(회전)시키면서 조건을 검사해볼거냐 회전을 하지 않아도 풀 수 있는 방법이 있지 않을까? 실제로 문자열을 조작해서 조건 검사하는 직관적인 풀이로 접근해보기로 결정. 코드 구상 문자열 맨 앞 문자를 맨 뒤로 이동시키기 위해 Queue를 활용해보자 -> 삽입에 O(n) 소요 괄호 검사를 위해서 check 함수를 정의하자 문자열을 한 바퀴 돌아야 하기 때문에 O(n) 소요 s의 길이만큼 체크를 해야하기 때문에 결국 O(n..

프로그래머스 - 징검다리 건너기

https://school.programmers.co.kr/learn/courses/30/lessons/64062 설명 그대로 풀기 설명 그대로 니니즈 친구들을 하나씩 보내보면서 해답을 찾는다. For 문을 2회 돌리는 방식 제한사항을 읽었을 때, 설명 그대로 풀게 되면 stones의 각 원소 값이 2억이므로 2억번 for loop를 돌 가능성이 있다. 하지만 딱히 다른 방법이 생각나지 않았기에 일단 그대로 풀어보기로 함. Code class Solution { public int solution(int[] stones, int k) { int answer = 0; int n = stones.length; while(true) { for(int i = 0; i < n; i++) { for(int j = ..

Leetcode 392. Is Subsequence

https://leetcode.com/problems/is-subsequence LeetCode - The World's Leading Online Programming Learning Platform Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 문제 이해 두 문자열 s, t가 주어지고 s가 t의 subsequence이면 true 아니면 false 반환 문자열에 상대적인 순서를 해치지 않고 문자열을 제거했을 때 만들어지는 문자열을 subsequence라고 함 사고 흐름 문자열..

슬라이딩 윈도우 | sliding window algorithm

배열에서 일정 범위를 탐색하며 조건에 부합하는 Subset을 찾는 방식. 창문을 오른쪽으로 미는 느낌이 나기 때문에 Sliding Window라는 이름이 붙은 것 같다. 알고리즘 활용 투포인터 배열 내의 일정 범위를 기억해야하기 때문에 시작과 끝을 마킹하는 변수가 필요하다. start, end left, right 필자는 left, right를 즐겨쓴다. 크기 고정 or 변동 배열 내의 하위 배열(sliding window)의 크기는 풀고자하는 문제에 따라 고정일수도 있고 변동일 수도 있다. 변동일 경우 right가 움직일 때마다 조건을 검사해주어 left를 조정해주어야 한다. 아래는 구간을 변동하는 간단한 예시이다. int left = 0; for(int right = 0; right < len; ri..

LeetCode 847. Shortest Path Visiting All Nodes

https://leetcode.com/problems/shortest-path-visiting-all-nodes/ LeetCode - The World's Leading Online Programming Learning Platform Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 풀이 시간 2시간정도.. ㅠㅠ 문제 이해 그래프에서 모든 노드를 방문할 때 필요한 최소 비용(간선 사용 횟수) 사고 흐름 최소 비용이라고 해서 Node to Node weight map을 구하고 외판..

Java Spring 엔티티 of 도메인 생성자

이 문서에서는 of 메서드의 의미와 형태, 테스트 방법에 대해 알아봅니다. of 함수의 의미와 형태 of 함수는 새로운 객체를 생성하기 위한 함수입니다. 생성자 함수와 기능이 같은데 의미는 조금 다릅니다. of 함수는 객체로 새로운 객체를 만든다는 의미를 가지고 있습니다. 예를 들어, 모임 접수를 나타내는 MeetReceipt 객체를 만들기 위해 다음과 같은 of 함수가 정의됩니다. public static MeetReceipt of(Long meetId, MeetReceiptRequestBody meetReceiptRequestBody){ return MeetReceipt.builder() .meetId(meetId) .userId(meetReceiptRequestBody.getUserId()) .st..

Flutter BLOC 기반의 Widget Test

BLOC 패턴을 적용하면 가독성있는 테스트 코드를 작성할 수 있다. 특히 각각의 BLOC 단위 테스트 말고도 BLOC과 상호작용하는 위젯을 테스트하는 코드도 깔끔하게 작성할 수 있다. 이 문서에서는 BLOC 패턴이 적용된 페이지 위젯을 테스트하는 위젯 테스트에 대하여 알아본다. 편의상 Bloc 대신 Cubit을 활용하였다. 위젯 테스트란? 화면에 그려진 위젯에 대하여 클릭이나 스크롤과 같은 이벤트가 발생했을 때 원하는 결과가 발생하는 지 확인하는 테스트. 예를 들어 로그인 버튼을 눌렀을 때 로그인 요청이 발생하는지 테스트하려면 앱을 켜서 직접 눌러보아야 하는데, 매번 사람이 테스트 할 수 없으니 코드 레벨에서 테스트 하여 결과값을 보장받는 것이다. 위젯 테스트는 단위 테스트보다 포괄적인 테스트를 수행한다..