개인 활동

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라고 함 사고 흐름 문자열..

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을 구하고 외판..