솧로그

https://leetcode.com/problems/find-if-path-exists-in-graph/description/class Solution { boolean[] vis; List> gr; void dfs(int node) { if (vis[node]) return; vis[node] = true; for (int child : gr.get(node)) { if (!vis[child]) dfs(child); } } public boolean validPath(int n, int[][] edges, int source, int destination) { vis..

https://school.programmers.co.kr/learn/courses/30/lessons/150366# 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 유니온 파인드 + 구현 문제이다. 문제 풀이 아이디어 자체는 어렵지 않은데 구현 중간중간 실수하고 헷갈려서 헤맸다.. 특히 유니온 파인드를 통해 여러 집합을 하나의 집합으로 merge하고 반대로 unmerge하기도 하는데, 이때 생각을 잘 해야 한다.merge 된 노드 간에는 모두 최상위 부모 노드가 같다. 즉, parent[][] 값 자체는 다를 수 있지만, find() 메소드를 통해 얻게 되는..

https://school.programmers.co.kr/learn/courses/30/lessons/49190 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 주의할 점은 다음과 같다.방이 되기 위해선 다음 두 조건을 모두 만족해야 한다.이미 방문한 노드를 재방문 하는 경우해당 간선이 처음 생성된 간선인 경우이차원 배열을 사용하려면 new int[200,001][200,001]의 크기의 배열이 필요하다. 따라서 이차원 배열을 사용할 수 없으며, 대신 Map을 사용한다. 다음과 같이 교차점이 있을 경우 위 로직대로 생각하면, 방이 1개인 것으로 계산된다. 즉..

https://school.programmers.co.kr/learn/courses/30/lessons/150370 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 구현 문제로, 주의할 점은 다음과 같다.모든 달이 28일까지 있다고 가정한다. 따라서 특정 날짜를 일수로 변환해서 날짜 간 비교하면 된다. ex, 2021.05.02 ➡️ 2021 * 12 * 28 + 5 * 28 + 2마침표(.)를 기준으로 문자열을 자르고 싶으면 split(".")이 아니라 split("[.]") 또는 split("\\.")을 사용해야 한다.split() 메소드는 파라미터로 정규..

https://leetcode.com/problems/k-th-smallest-prime-fraction/submissions/1284723688/ class Solution { public int[] kthSmallestPrimeFraction(int[] arr, int k) { int len = arr.length, numerator = -1, denominator = -1, fractionPosCovered = 0; double left = 0, right = 1; while(fractionPosCovered != k) { fractionPosCovered = 0; doubl..

https://school.programmers.co.kr/learn/courses/30/lessons/150367 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 처음에는 문제를 이해하기 어려웠는데, 결론은 다음과 같다.포화 이진트리가 되기 위해서는, 이진수의 길이(= 포화이진트리의 노드 수)는 2^n - 1이어야 한다.포화 이진트리의 노드 수는 다음과 같다. ➡️ 1, 3, 7, 15, ...루트 노드가 0이면 그 아래 자식 노드들은 모두 0이어야 한다.문제에서 이진트리(1)에 더미노드(0)를 추가하여 포화 이진트리를 만든다고 했다. 따라서 루트 노드가 1..

https://school.programmers.co.kr/learn/courses/30/lessons/43236 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 완전탐색으로 풀 경우, 50,000개의 바위 중 n개를 고르고(50,000 ^ n) 선택된 n개의 바위 간 간격을 구하므로(n) 약 50,000 ^ n * n의 시간복잡도를 갖는다. 따라서 시간 초과가 날 것이므로 다른 방법으로 풀어야 한다.우선, 문제가 요구하는 것은 바위 간 간격의 최솟값 중 최댓값을 구하는 것이다.이 문제는 이분 탐색으로 풀어야 하는데, 이분 탐색은 어떤 값을 left와 righ..

https://school.programmers.co.kr/learn/courses/30/lessons/42897 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr dp로 풀 수 있는 문제로, 주요 포인트는 다음과 같다.인접한 두 집을 털 수 없다. 따라서 i번째의 집까지 훔칠 수 있는 최대 금액을 dp[i]라고 했을 때, dp[i] = max(dp[i - 1], dp[i - 2] + arr[i])이다.그런데 마지막 집에서 문제가 발생한다. 만약 첫 번째 집을 털었으면 마지막 집을 털 수 없고, 그렇지 않으면 마지막 집을 털 수 있다. 따라서 dp에 채워진 최대..

https://school.programmers.co.kr/learn/courses/30/lessons/150369 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 우선 이동 거리를 최소로 하기 위해서는 물류창고로부터 멀리 떨어진 집을 우선으로 배달/수거를 해야 한다. (그리디 알고리즘) 따라서 배달할 수 있는 상자의 수를 d, 수거할 수 있는 상자의 수를 p라고 하면, 다음과 같이 구현할 수 있다.int d = cap;int p = cap; // 가장 먼 집부터 배달/수거for (int i = n - 1; i >= 0; i--) { d -= delive..

https://school.programmers.co.kr/learn/courses/30/lessons/1843 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 주어진 식에 대한 연산의 최댓값을 구하는 문제이다. 예를 들어 1 - 3 + 5 - 8라는 식이 주어졌을 때 괄호의 위치에 따라 여러 연산 결과가 나오는데 그 중 최댓값을 구하면 된다.이때 다음과 같은 dp 개념이 사용된다.A + B의 최댓값을 구하려면, A와 B 둘 다 최댓값이어야 한다.A - B의 최댓값을 구하려면, A는 최댓값, B는 최솟값이어야 한다.위와 같이 - 연산자의 뒤에 있는 수는 최솟값..