목록Algorithm/프로그래머스 (5)
봄봄.devlog
https://programmers.co.kr/learn/courses/30/lessons/43165 코딩테스트 연습 - 타겟 넘버 n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다. -1+1+1+1+1 = 3 +1-1+1+1+ programmers.co.kr 📖 문제 풀이 - DFS에서는 점화식과 종료조건을 찾는 것이 가장 중요하다. 📖 소스 코드 public class 타겟넘버 { public static void main(String[] args) { int[] numbers = {1,1,1,1}; int target = 3; System.out.println..
https://programmers.co.kr/learn/courses/30/lessons/1829 코딩테스트 연습 - 카카오프렌즈 컬러링북 6 4 [[1, 1, 1, 0], [1, 2, 2, 0], [1, 0, 0, 1], [0, 0, 0, 1], [0, 0, 0, 3], [0, 0, 0, 3]] [4, 5] programmers.co.kr 🎈 문제 풀이 - DFS를 활용하면 되는 문제였다. - 다른 문제와 다르게 했던 점은 다음 인접 정점을 탐색하기 위해서는 계속 "같은 색상의 값"이어야 했기 때문에 dfs 파라미터로 처음 dfs 탐색을 시작할 때 가지고 있던 색상 값을 받아서 현재 탐색 중인 정점과 비교했다. - 한 번 dfs를 돌 때 마다 numberOfArea를 1씩 추가하고 - dfs 호출을 ..
🎈문제 풀이 송신탑은 뒤에서 차례대로 하나씩 빼주기 때문에 Stack에 적합하다. 그런데 송신탑의 경우 수신탑보다 높이가 큰 것이 나올 때까지 계속 빼줘야 한다. - 뺏던 것을 다시 집어넣어줘서 원상복귀를 시켜주거나(스택 하나만을 사용하는 경우), 송신자가 바뀔 때마다 수신자 스택을 새로 생성해줘야 한다. - answer에 위치 값을 저장해줘야 하기 때문에 송신자와 수신자의 위치 정보를 알고 있어야 한다. 🎈 소스 코드 static int[] solution(int[] heights) { Stack stack = new Stack(); int[] ans = new int[heights.length]; for(int n : heights) stack.push(n); int sender, receiver; ..
https://programmers.co.kr/learn/courses/30/lessons/42583 코딩테스트 연습 - 다리를 지나는 트럭 트럭 여러 대가 강을 가로지르는 일 차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 트럭은 1초에 1만큼 움직이며, 다리 길이�� programmers.co.kr 🎈문제 풀이 큐 이용해서 풀면 되겠구나 하고 간단하게 생각했는데 생각보다 오래 걸렸던 문제.. - wait 큐와 bridge큐 2개를 만든다. - 트럭이 다리를 어느정도 지나가고 있는지 확인해야 건넜는지 여부를 알 수 있으므로 Truck 클래스를 만들어서 기록한다. - 종료조건 : 두개의 큐가 다 비어있는 경우, 모든 트럭이 다리를 건넜다는 ..
왜 이분탐색을 할까? 빠르게 원하는 답을 찾기 위해서! [ 풀이법 ] 정렬하고 탐색 시작하기!! 1. 최소 & 최대값의 중간값을 구한다. 2. 조건에 맞춰 총합이 M보다 작으면 최소값이 중간값이 된다. 3. 그렇지 않은 경우, 최댓값이 mid가 된다. -> 종료조건 : 이전의 mid의 값(preMid)가 새로운 mid값과 같으면 탐색을 멈춘다. (모든 값들 탐색 완료) [ 효율성 2번 에러 문제 ] 1. 요청한 금액의 총합이 준비된 예산(M)보다 적을 경우, 요청된 예산요청 중 가장 큰 요청을 return 2. 요청한 금액의 총합이 Integer 최대 값을 넘길 수 있으니, Long으로 선언 (효율성 2번 통과 방법) static int solution(int[] budgets, int M) { int ..