튼튼발자 개발 성장기🏋️

문제 기출 : [https://www.acmicpc.net/problem/2529] 풀이 방법 [백트래킹 : backTracking] 접근 가장 먼저 default 값을 만들자. 최대값의 경우에는 9부터 -1씩 해가면서 채워주고, 최소값의 경우에는 -부터 _1씩 해가면서 채워준다. 이제부터 backTracking 기법을 사용하여 부등호를 만족하는지 체크한다. 부등호를 읽어올 필요없이 그냥 javascript engine을 사용해서 boolean 값을 받기만 하면 된다. 부등호가 만족하지 않는다면 앞의 숫자와 자리를 바꿔준다. 왜냐하면 최대값과 최소값을 구해야하기 때문이다. 이런식으로 체크를 끝까지 하게 되었을 때 나온 값이 바로 최대값 최소값이 될 수 있다. 단 한 번의 backTracking으로 최대값..

문제 기출 : [https://www.acmicpc.net/problem/2352] 풀이 방법 #1 [backTracking] 접근 2일 동안 이 문제에만 몰두했다. 그냥 생각나는대로 경우의수를 나열하여 백트래킹 기법으로 하나하나 탐색하여 체크했다. 문제는 풀었지만 당연하게도 시간초과..(정답인지도 모르겠다.) 그래서 다른 방법을 채택했다. 문제 풀이 #2 public class Main { private static int maxCount = 0; public static void backTracking(int[] input, int start, int end) throws Exception { int count = 1; int temp = end; int flag = 0; if(start == inp..

문제 기출 : [https://www.acmicpc.net/problem/2217] 풀이 방법 [그리디알고리즘] 접근 1. N개의 버틸 수 있는 중량을 배열에 저장하여 sort. 2. 버틸 수 있는 최대 중량을 구해야하므로 큰 값 먼저 탐색하여 다음 식을 적용 i번째 로프의 버틸 수 있는 중량 x (로프의 수 - i) 3. 최대값이 정답이 된다. 문제 풀이 public class Main { public static void main(String[] args) { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int answer = 0; try { int N = Integer.parseInt(br.readLine());..

문제 기출 : [https://www.acmicpc.net/problem/1946] 풀이 방법 [그리디알고리즘] 접근 문제를 읽고 "이건 무조건 객체 정렬이다!"라고 생각했다. 가장 먼저 서류 설적과 면접 성적을 따로 받고 두 성적에 대해 제한을 두고 있으니 당연한 것이 아닌가. 객체 정렬 후 오직 면접 성적만을 비교하여 큰 값을 갱신해가며 카운팅하면 된다. 문제 풀이 public class Main { public static void main(String[] args) { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int answer = 0; try { int testCase = Integer.parseInt(b..

문제 기출 : [https://www.acmicpc.net/problem/1969] 풀이 방법 [그리디알고리즘] 접근 해답의 가장 큰 핵심은 각 N개의 DNA의 각 M번째 자리수(char)가 가장 많은 문자를 출력하고 카운팅해주면 된다. 가장 좋았던 조건. 체크해야할 문자를 4개로 제한 한것. (만약 제한이 없고 Alphanumeric이었다면 과연 어땠을까..?ㅠㅠ) 2중 for문을 이용해서 N개의 DNA를 탐색하면서 각 자리의 char를 체크한다. A면 A를 카운팅, T면 T를 카운팅 ····. 카운팅 된 수 중, 가장 큰 값을 채택하고 그 값을 N에서 뺀 것을 누적하여 더해주면 Hamming Distance의 합이 될 수 있다!!! 채택된 해당 max값을 가진 char를 가지고 온다. 그 값이 바로 ..

문제 기출 : [https://www.acmicpc.net/problem/1931] 풀이 방법 [그리디알고리즘] 접근 여러가지 풀이 방법이 떠올랐다. 한참 이 문제를 풀 때 쯤에 Comparator와 Comparable을 연습하고있던 찰나여서 생각나는대로 작성했다. 2차원 배열에 입력 값을 저장 -> sort (끝나는 시간 기준, 같으면 시작시간 기준) -> 끝나는 시간을 체크해가면 카운팅 -> 마지막 카운트 값을 출력 참고로 더 간단하게 풀이도 가능하다. 우선순위 큐를 생각해보면 답이 나올 것이다. 문제 풀이 public class Main { public static void main(String[] args) { BufferedReader br = new BufferedReader(new Input..

문제 기출 : [https://www.acmicpc.net/problem/1541] 풀이 방법 [그리디알고리즘] 접근 연산자는 +와 -만을 다루고 피연산자는 양수인 것만 알아도 쉽게 접근할 수 있다. 괄호를 사용해서 최소값을 만든다고 했는데 괄호에 현혹될뻔했다. 먼저 +연산 먼저 해서 크기를 키운 다음 -연산을 하면 되지 않는가? 한 마디로, +연산으로 최대한 값을 키운 다음 그 값을 빼면 최소 값을 쉽게 도출할 수 있다. 식에서 '-'를 기준으로 식을 잘라 저장하면 나머지는 +연산이 되고, 그 값을 모두 더한 다음 -연산하면 정답을 빠르게 구할 수 있다. ※ 번외. 어디선가 비슷한 문제를 풀어본 적이 있다. 문자열로 사칙연산과 괄호를 포함한 문자열(String)을 input으로 주고 그 연산을 실행한 ..

문제 기출 : [https://www.acmicpc.net/problem/1439] 풀이 방법 [그리디알고리즘] 접근 어쨌든 문자열은 0과 1로만 이루어져 있으므로 각각 뒤집었을 때의 count를 비교해서 크기가 작은 값이 답이 될 것이다. 주어진 문자열 S의 첫 문자를 첫 기준으로 잡고 S의 각 문자가 기준되는 문자와 다르면 기준에 따라 카운트. 카운트를 해줬다면 기준이 달라지기 때문에 0은 1로 바꿔주고 1은 0으로 바꿔야된다. 이렇게 기준점을 두고 S의 각 문자가 다르면 기준이 되는 문자의 카운트를 세어주기만 하면된다. 이러면 0일 때와 1일 때의 카운트가 각각 나오게 되는데 이 두 카운트 중에 최소값을 출력하면 된다. 문제 풀이 public class Main { public static void..