문제분석https://school.programmers.co.kr/learn/courses/30/lessons/340211 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr2차원 좌표계에서 방문 대상 Point 배열과 로봇이 방문해야 하는 Point 배열이 주어진다.각 로봇은 좌표(r,c)에 대해서 목표 Point에 대해 r을 우선시하여 움직인다. 이때, 로봇이 같은 좌표안에 있는 경우 위험 상황으로 인지한다.최적 경로 이동 시 발생가능한 위험 상황의 수는 ? 길이 자체는 100정도로 작다. 즉, 거의 대부분의 풀이가 시간이내에 들어오게 된다. 로봇의 현재 위치..
문제 분석https://www.acmicpc.net/problem/2138N가능한 최소의 스위치 조작으로 주어진 전구 배열을 정답 배열로 만들려하는데 이때 드는 비용(횟수)을 구하는 문제이다. 처음 시도한 풀이는 아래와 같다.맨 마지막 2개의 전구에 대해서 그 앞의 전구까지 가능한 최소의 비용으로 스위치 조작을 해서 정답 배열과 일치시켜 오게 된다면 이를 3개짜리 전구를 조작하는 문제로 변경할 수 있다고 생각했다.즉, 1010111000 -> 00000000 이런 배열에 대해서 결국에는 0 a b -> 0 0 0 이 상태가 되는 문제로 변경할 수 있게 된다.따라서 3개의 전구에 대해서 각각 최소의 스위치 조작으로 정답 배열과 일치시킬 수 있다면 해당 횟수를, 없다면 -1을 리턴하는 방식으로 구현했었다. ..
문제 분석https://www.acmicpc.net/problem/1253N개의 수가 주어지고 각 수마다 해당 숫자를 자신을 제외한 서로 다른 두 수의 합으로 만들어낼 수 있는지 판단하고 그렇다면 좋은 수로 여긴다.이때 좋은 수의 갯수를 구하는 문제. N은 2000까지, 값은 절댓값기준 10억 이하 정수N이 작기에 n^2의 풀이도 통과될 수 있다. 처음엔 간단하게 for loop를 2번 돌리며 가능한 모든 수의 합을 Set에 넣고 배열에 대해서 있으면 ans ++ 하는 방식으로 구현했었다. 즉, 0~n-2의 인덱스 i에 대해 i+1 ~ n-1의 인덱스와의 합을 Set에 저장했다. 그런데, 생각해봐야 하는 부분이 있다.0 + k 는 k다. 여기서, 합쳐진 결과 k는 자기자신을 사용하였기에 문제의 조건에 어..
문제 분석https://www.acmicpc.net/problem/4485전형적인 bfs문제다.보드가 주어지고 0,0에서 n-1,n-1로의 경로 중 가장 저렴한 비용으로 갈 때 그 비용을 묻는 문제였다. point마다 해당 point까지 온 cost를 저장하고 이를 PQ에 낮은 순으로 삽입한다.또, point에 방문했을 때 굳이 더 비싼 비용으로 도착한 경우 탐색을 이어나갈 필요가 없기에 이 부분도 같이 체크해주면 된다. 코드import java.util.*;public class Main { public static void main(String[] args) throws InterruptedException { Scanner sc = new Scanner(System.in); ..
문제 분석https://www.acmicpc.net/problem/1107티비의 채널을 N으로 변경하려하는데M개의 숫자 버튼이 고장나있다.그리고, +,- 버튼이 존재한다.100번에서 N번 채널으로 최소한의 버튼 조작으로 이동할 때 그 이동 횟수를 구하는게 문제다. 처음에 앞의 자리수 부터 가장 가까운 수를 넣어 최적의 이동 횟수를 구하는 방법을 생각해봤었는데생각해보면 10000이라는 숫자에 대해서 1에 가장 가까운 유효한 수는 2지만 9999가 더 가깝다. 그런데, 주어진 N의 범위가 500000 밖에 되지 않는다.즉, 10^6가지의 숫자만 고려해주면 되고 이정도는 충분히 돌아도 제한 시간을 만족하게 된다. 따라서 나는 아래와 같은 구조로 문제를 풀었다. 주어진 숫자의 길이 -1 의 숫자 중 가장 큰 수..
문제 분석https://school.programmers.co.kr/learn/courses/30/lessons/258705 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr정삼각형으로 이루어진 사다리꼴이 주어지고 그 위에 정삼각형을 일부 얹은 도형이 주어지고해당 도형에서 정삼각형 2개를 이어붙인 마름모 혹은 정삼각형으로 색을 칠하는 경우의 수를 구하는 문제다. n의 크기는 10만이니 가능하다면 O(n)에 끝내거나 O(nlongn)에는 끝내야 한다. 처음 들었던 생각은 X개의 정삼각형으로 이루어진 사다리꼴에 대해서 dfs로 접근을 했었다.그리고 최적화를 위해 i..
문제분석https://www.acmicpc.net/problem/1365 X -> Y로 하나의 전선씩 연결되어 있는데, 이 중 최소의 전선을 잘라 전선끼리 겹치는 것이 없게 만드는 것이 목적이다. 전선이 서로 겹치지 않기 위해선 최종적으로 남는 각 전선 쌍들이 단조적이여야 한다.즉, 1-2 / 2-3/ 3-4 이런식으로 서로 겹치지 않아야 한다. 이런 순차적인 쌍들의 최댓값을 찾는 것이 최소의 전선을 자르는 방법이기에 이 문제는 LIS(최장 증가 부분수열) 알고리즘으로 접근할 수 있다. N = 10^5 이기에 O(N^2)으론 시간을 맞출 수 없다. https://velog.io/@min-ji99/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98%EA%B0%80%EC%9E%A5-%EA%B..
문제분석https://www.acmicpc.net/problem/10330~N-1의 인덱스 사이의 비율 p/q를 주고이걸 바탕으로 각 인덱스에 해당하는 재료를 정수로 만들었을 때 그 합이 최소가 되게 만들라는 문제다. 따라서1. 인덱스 0과 연결된 노드는 최소 1개 이상 존재하기 때문에 (칵테일을 제조할 수 있다는 전제가 있음) 해당 노드를 찾아 두 노드를 기준으로 삼는다 (비율이 p/q면 a,b의 질량을 p,q로 산정한다) (당연히 p,q는 서로소다)2. bfs로 인접 노드끼리 비교하며 모든 노드간 비율을 구한다.3. 유클리드 호제법을 통해 최소공배수를 구한다https://programmer-chocho.tistory.com/9 [JAVA] 최대 공약수(GCD), 최소 공배수(LCM) 구하기최대 공약수..
