문제 파악가장 중요한 조건은i번째 집은 i-1번째 집과 i+1번째 집과 색이 같지 않아야 한다.첫 번째 집과 마지막 집은 색이 같지 않아야 한다.두 조건이였습니다. 문제 풀이 첫 번째 집의 색상을 R, G, B 중 하나로 고정해서 3가지 경우를 각각 계산DP 배열을 사용하여 i번째 집을 어떤 색으로 칠했을 때의 최소 누적 비용을 저장-> DP 배열은 매번 새로 선언해야 함. 마지막 집의 색상이 첫 번째 집과 다른 경우만 정답 후보 ! 코드 구현import java.util.*;import java.lang.*;import java.io.*;class Main { static int n; static int [][] cost; static final int INF = 1_000_000_..
java
문제 파악https://www.acmicpc.net/problem/16953 접근 방법bfs를 통해 접근하면 어떨까?2를 곱하는 경우1을 을 수의 가장 오른쪽에 추가하는 경우두 가지의 경우의 수를 큐에 넣어 준 다음, 만약 a가 b와 같게 된다면 answer를 갱신하고, 반복문을 종료하였다.무한 루프의 반복을 막기 위해, 다음 수가 b값을 넘지 않는 조건에서만 큐에 다음 수를 넣어주었다. 코드 구현첫번째 코드(틀린 코드)import java.util.*;import java.lang.*;import java.io.*;// The main method must be in a class named "Main".class Main { public static void main(String[] ar..
✔ 문제 파악https://www.acmicpc.net/problem/1700 ✔ 문제 풀이그리디 알고리즘 문제이다.그리디 알고리즘이란?매 선택에서 당장 눈 앞에 보이는 최적의 상황만 쫓아 최종적인 해답에 도달하는 방법이다. 그리디 유형에서 가장 중요한 것은, 그리디 유형인지 알아보는 것이다 ! (당연한 말씀을.. ) 최소한으로 제품을 뽑아내면서 모든 제품을 사용할 수 있도록 멀티탭을 관리하기 위해서 생각난 알고리즘은OPT 알고리즘이다. OPT알고리즘은 페이지 교체 알고리즘 중 하나로, 앞으로 가장 오랫동안 사용하지 않을 페이지를 교체하는 알고리즘이다.그렇게 때문에 우리는 현재 상황에서 앞으로 가장 오랫동안 사용하지 않을 플러그를 빼버리고 지금의 플러그를 꽂아줄 것이다. 크게 2가지 상황으로 나..
https://school.programmers.co.kr/learn/courses/30/lessons/43163 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 1. 백트래킹(dp) 풀이(재귀를 활용한 풀이) import java.util.*;class Solution { String target; String [] words; int answer = Integer.MAX_VALUE; boolean [] visited; int result=0; public int solution(String begin, String target, String[] words..
https://www.acmicpc.net/problem/15654 ✔ 문제 풀이재귀의 정석인 N과 M시리즈 5를 모셨습니다.매번 느끼지만 아무래도 알고리즘은 파이썬이 짱인듯해요 ! 재귀에서 가장 중요한 것은 종료조건 설정(return)여기에서 종료조건은 👉 result (우리가 출력할 배열)의 크기가 M개인 것 (M개를 뽑기 때문이다). 그 이외는 배열을 미리 정렬해줄 것.중복된 숫자를 뽑지 않기 위해 방문배열을 기록해줄 것이다 ~~! 이해하기 어렵다면 N과 M 시리즈를 처음부터 풀어보는 것을 추천한다.https://www.acmicpc.net/workbook/view/2052 static void dp(int depth){ // 종료조건 : M개만 뽑을 것 if(depth..
✔ 문제설명https://school.programmers.co.kr/learn/courses/30/lessons/42860 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr조이스틱으로 알파벳 이름을 완성하세요. 맨 처음엔 A로만 이루어져 있습니다.ex) 완성해야 하는 이름이 세 글자면 AAA, 네 글자면 AAAA조이스틱을 각 방향으로 움직이면 아래와 같습니다.▲ - 다음 알파벳▼ - 이전 알파벳 (A에서 아래쪽으로 이동하면 Z로)◀ - 커서를 왼쪽으로 이동 (첫 번째 위치에서 왼쪽으로 이동하면 마지막 문자에 커서)▶ - 커서를 오른쪽으로 이동 (마지막 위치에서 오른쪽으로 이동하면 첫 번째 문자에 커서)예..
✔ 문제파악https://school.programmers.co.kr/learn/courses/30/lessons/42862?itm_content=course14743 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 체육복을 잃어버린 사람들의 배열과, 여분 체육복을 가진 사람들이 존재한다.만일, 앞뒤 사람에게만 체육복을 빌려줄 수 있을 경우, 최대한 많은 학생이 체육복을 입을 수 있는 경우의 수는 무엇일까? ✔ 접근방법그리디 알고리즘 1) int answer = n-lost.length;-> 체육복을 잃어버린 사람 수를 빼준다. 2-1) 옷은 잃어버렸지만, 여분의 체육복이 있었을 경우 -> 다른 ..
https://www.acmicpc.net/problem/1062 ✔ 문제파악첫번 째 줄에 단어의 개수 N과 배울 수 있는 글자 수 K가 주어진다. 그리고 단어 배열이 주어진다.선생님은 학생들에게 K개의 글자를 가르칠 수 있는데, K개의 글자를 가르친 후 학생들이 읽을 수 있는 단어의 개수가 최대인 값이 무엇인지 구하여라.접두사는 "anta", 접미사는 "tica"로 끝난다. ✔ 접근방법백트래킹(DP 문제), 브루트포스 알고리즘 1) 단어 배열을 예쁘게 만들어 준 후, 공통된 접두사와 접미사에 포함된 글자를 방문 처리해준다.=> 우리는 배운 글자를 boolean 방문 배열을 통해 해결해줄 것이다 ! visited['a' - 97]을 빼주는 이유는 소문자 a의 아스키코드가 97이기 때문. 🎐..
문제파악https://www.acmicpc.net/problem/14888숫자가 배열로 주어지고, 연산자의 개수가 주어진다.배열 [1,2,3] 와 [1,0,1,0] -> {+:1, *:1} 이 주어졌다면, 1+2*31*2+3 총 두 가지의 식이 나올 수 있음 ! 수와 수 사이에 연산자를 넣어 나올 수 있는 답의 최댓 값과 최소 값을 구한다.연산자 우선 순위 규칙은 무시한다 ! 접근방법전형적인 재귀 문제 ! -> 백트래킹 문제 백트래킹이란? : 가능한 모든 조합을 탐색하되, 이미 잘못된 경우는 중간에 탐색을 중단하는 방식(종료 조건) 이 문제에서의 종료 조건은 n까지의 수의 연산이 끝났을 때이다.그 때, MAX_VALUE와 MIN_VALUE를 갱신시켜주고 return 해주면 된다. 코드 구현..
1. List정렬✔ Collections.sort();Collections.sort(list); // 오름차순Collections.sort(list, Comparator.reverseOrder()); // 내림차순 2. 배열 (int [])정렬 ✔ Arrays.sort(); int [] arr = {3, 1, 2};Arrays.sort(arr); // 오름차순Arrays.sort(arr, Comparator.reverseOrder()); //내림차순 3. HashMap 정렬: HashMap은 순서가 없으므로, 정렬하려면 Entry를 List로 변환해야 함 ✔ Key로 정렬List> entryList = new ArrayList(map.entrySet());entryList.sort(Map.En..
