솧로그

https://school.programmers.co.kr/learn/courses/30/lessons/258711 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 특정 알고리즘을 사용할 필요는 없고, 문제의 이해와 해석이 요구되는 문제였다.  각 그래프의 특징을 생각하고, 이를 기반으로 각 그래프의 갯수를 구하면 된다. 각 그래프의 특징은 다음과 같다.추가된 정점: 나가는 선이 2개 이상이면서 들어오는 선이 없다. 그리고 추가된 정점에서 나가는 선의 개수가 총 그래프의 갯수이다.8자 모양 그래프: 나가는 선이 2개 이상이다.막대 모양 그래프: 나가는 선이 없..

https://school.programmers.co.kr/learn/courses/30/lessons/43105 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr dp 기본 문제이다. 다음과 같이 한 숫자를 기준으로 봤을 때 왼쪽과 합쳐질 수도 있고 오른쪽과 합쳐질 수도 있다. 그리고 더 큰 값으로 합치면 된다. dp[i][j] = max(dp[i - 1][j - 1], dp[i - 1][j]) + arr[i][j] 이를 코드로 구현하면 다음과 같다. import java.util.*;class Solution { public int solution(in..

https://school.programmers.co.kr/learn/courses/30/lessons/42895 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr DP를 사용해서 풀 수 있는 문제였다.  처음에는 다음과 같이 만들어진 숫자의 끝에 사칙연산을 추가하는 식으로 풀었다.num + Nnum - Nnum * Nnum / N그런데 이렇게 풀면 오답이다. 만약 5을 4번 사용한다고 했을 때 (5 + 5) * (5 + 5) (= 100)라는 식이 있을 수 있다. 그런데 위 방법대로라면 저 식은 나올 수 없고 (5 + 5) * 5 + 5 (= 55)라는 식만 ..

https://school.programmers.co.kr/learn/courses/30/lessons/42884 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 그리디로 풀 수 있는 문제였다.최대한 적은 수의 카메라를 설치하기 위해서는 각 자동차가 위치한 범위 내에서 최대한 뒤쪽에 카메라를 설치하면 된다. 그래야 다음 자동차도 이미 설치된 카메라 범위에 포함될 가능성이 있기 때문이다. 즉, 당장에 가장 좋은 것을 선택(= 가장 뒤에 카메라를 설치) 한다는 점에서 그리디 알고리즘이다. 위 아이디어를 가지고 구현하면 되는데, 자동차가 고속도로를 나간 시점을 기준..

https://school.programmers.co.kr/learn/courses/30/lessons/258705 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr dp로 풀 수 있는 문제이다. 처음에 문제에서 말하는 n을 다른 의미로 해석해서 점점 이상한 길을 가게 되었는데.. 문제에서 의미하는 대로 n을 생각해야 한다. n = 3일 때 만들어지는 도형을 채울 수 있는 경우의 수를 dp[3]이라고 하자. 이때 dp[3]의 앞 순서인 dp[2]는 다음과 같이 두 가지 경우로 나뉠 수 있다.마름모로 채워져 끝나는 경우 (즉, 파란색 부분을 dp[2]에서 마름모 ..

https://school.programmers.co.kr/learn/courses/30/lessons/42861 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 유니온 파인드(+ 그리디)를 사용하면 아주 간단하게 풀 수 있는 문제이다. (그런데 나는 유니온 파인드를 머릿 속에서 잊고 있어서 못 풀었다.)유니온 파인드를 통해 모든 노드가 하나의 집합이 되도록 다리를 건설하면 된다.그런데 최소 비용이 되도록 다리를 건설해야 하므로, 건설 비용이 적은 다리부터 건설하면 된다.즉, "다리 건설 비용이 적은 순"으로, "모든 노드가 하나의 집합이 될 때까지" 다리를 ..

https://school.programmers.co.kr/learn/courses/30/lessons/43162 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr dfs로 아주 간단하게 풀 수 있는 문제다. 이차원 배열을 순회한다. 이때 아직 방문하지 않았으면서 값이 1이면 dfs를 시작한다.dfs를 통해 이어진 모든 노드들을 방문한다.dfs를 수행한 횟수가 네트워크 개수가 된다.import java.util.*;class Solution { int answer = 0; int n; int[][] computers; boolean[..

https://school.programmers.co.kr/learn/courses/30/lessons/43163 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 처음에는 익숙한 dfs로 풀었었는데, begin을 target으로 변환하는 가장 빠른 과정을 찾아야 하므로 bfs가 더 적합한 거 같다. 그런데 dfs로 풀더라도 가지치기를 하면 되니까 큰 차이는 없을 거 같다.  dfs로 푼 풀이는 다음과 같다.import java.util.*;class Solution { String begin; String target; String[] ..

https://school.programmers.co.kr/learn/courses/30/lessons/87694 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr bfs 문제인 건 딱 보고 알았는데 구현을 어떻게 해야할지 감이 안왔다. 주의할 점들은 다음과 같다.우선 내가 막힌 부분은 "테두리를 의미하는 꼭짓점을 이차원 배열로 구현하는 것이 올바른가?"였다. 그런데 다음을 보면, 테두리를 기준으로 해서 테두리 수를 셌을 때랑, 이차원 배열을 기준으로 해서 가장자리 칸들의 수를 셌을 때랑 차이가 없다는 것을 알 수 있다. 따라서 이차원 배열로 구현해도 된다!다음..

https://school.programmers.co.kr/learn/courses/30/lessons/43164 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 처음에 푼 풀이는 다음과 같다. import java.util.*;class Solution { public String[] solution(String[][] tickets) { Map> map = new HashMap(); for (String[] ticket : tickets) { PriorityQueue que = map.getOrDefault..