튼튼발자 개발 성장기🏋️

문제 기출 : [https://www.acmicpc.net/problem/1543] 풀이 방법 [그리디알고리즘] 접근 내가 문제를 잘못 이해 했는지 두 시간 가량을 잘못된 방향으로 풀이되어서 상당히 시간낭비하였다. 문제를 읽어보면 "찾는 단어가 최대 몇 번 중복되지 않게 등장하는지?"이다. 주어진 조건 "몇 번부터든지 시작 index는 모두 가능"을 생각하여 나는 코드를 작성하였지만 전부 다 실패... 아무리 문제를 되새김질해도 난 모르겠다... 그래서 다른 블로그를 참고하였더니 문제 이해를 도와주었다...ㅠㅠ 주어진 문자열에서 찾을 문자열을 찾되, 중복되지 않게 등장하는 최대값을 구해야한다. 즉 주어진 문자열에서 찾을 문자열을 찾고 찾은 문자열을 빼버리면서 카운트 하면 되는 아주 간단한 문제였다.. 나..

문제 기출 : [https://www.acmicpc.net/problem/2437] 풀이 방법 [그리디알고리즘] 접근 정답 비율이 37%라서 겁먹었지만 아주 쉬운 문제다. 최소값을 구하라고 했으니까 당연하게도 오름차순으로 정렬이 우선이다. 그래서 작은 무게의 추를 먼저 가지고 와서 체크를 할꺼다. 새로운 추를 가지고 왔는데 만약 이 새로운 무게가 저울의 (무게의 합 + 1)보다 크면 저울의 (무게의 합 + 1)이 최소값이 될 수 밖에 없다. 문제 풀이 public class Main { public static void main(String[] args) { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int answ..

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