모항이코딩한다

풀이방법 2022.03.02 기준이 되는 문자열의 알파벳별 개수를 센다. 길이가 26인 정수 배열 arr1을 선언하여, arr1[0]에는 A의 개수를, arr1[1]에는 B의 개수를... arr1[25]에는 Z의 개수를 저장하는 방식으로 세면 된다. 그 다음 문자열부터 다음의 과정을 거친다. 1. 기준문자열의 알파벳별 개수를 셌던 것과 같은 방식으로, 문자열의 알파벳별 개수를 세어 arr2에 저장한다. 2. int[] gap을 선언한다. gap[i] = arr1[i] - arr2[i]이다. 3. gap[0]~gap[25]를 점검한다. 2 이상의 정수 혹은 -2 이하의 정수가 저장된 요소가 존재하면 즉시 점검을 종료하고 다음 문자열로 넘어간다. 2개 이상의 문자를 변경해야 할 경우, 이 문자열은 비슷한 문..

풀이방법 사용된 것: 스택 2022.03.02 boolean 형 변수 v를 사용한다. 해당 문자열이 올바른 괄호 문자열이면 v 를 true로, 그렇지 않으면 false로 설정할 것이다. v의 초기값은 true이다. 반복문 내에서, 주어진 문자열을 가장 앞 글자부터 한 글자씩 다룬다. 이번 문자가 '(' 라면 스택에 넣는다. 이번 문자가 ')' 라면, 현재 스택에 '(' 가 하나 이상 들어있을 경우 '(' 하나를 pop 한다. 현재 스택이 비어있다면 이 문자열은 올바른 괄호 문자열이 아니다. v의 값을 false로 바꾸고 반복문을 종료한다. 중단 없이 문자열의 마지막 글자까지 처리를 마쳤다면, 이 때 스택이 비어있으면 이 문자열은 올바른 괄호 문자열이다. 이 때 스택에 '(' 가 하나 이상 남아있다면 이 ..

풀이방법 사용된 것: 브루트포스 0부터 시작하여 n 미만의 모든 정수를 점검하는 방법이 가장 빠른 방법이므로 브루트포스 알고리즘이 적합하다. 2022.03.02 0부터 시작하여, n 미만의 모든 정수의 분해합을 구해본다. 분해합이 n인 정수가 발견되면 즉시 그 정수를 화면에 출력하고 프로그램을 종료한다. n-1까지 모두 점검하였는데도 해당하는 수가 없다면 화면에 0을 출력하고 프로그램을 종료한다. 코드 Java(2022.03.02) import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { static int n; static int a,b,c,d,e,f,g;//..

풀이방법 사용된 것: 그리디 알고리즘 정렬 2022.02.24 자라는 데 가장 오래 걸리는 나무부터 심어야 한다. 그러므로 자라는 데 걸리는 일 수를 내림차순 정렬해준다. 정렬된 배열의 앞에 있는 나무부터 심는다. 한 나무가 다 자라는 날의 날짜는, (이 나무를 심기 전에 다른 나무를 심느라 보낸 시간) + (이 나무를 심는 데 걸리는 하루) + (이 나무가 자라는 데 걸리는 시간) 이다. 모든 나무에 대하여, 다 자라는 날의 날짜를 구한다. 다 자라는 날이 가장 나중인 놈이 있을 것이다. 그놈이 다 자라는 날짜가 바로 정답이다. 코드 Java(2022.02.24) import java.io.BufferedReader; import java.io.IOException; import java.io.Inpu..

풀이방법 사용된 것: 그리디 알고리즘 2022.02.24 예제를 통해 설명하겠다. n = 5, k = 6 사람이 5명, 만들어야 하는 관계가 6개인 경우를 보자. 일단 초기상태로, 5명에게 오름차순으로 쪽지를 쥐어준다. 이 상태에서 쪽지를 한 단계에 하나씩만 옮길 것이다. 하나를 옮길 때마다, 그렇고 그런 관계들이 새로 생기게 된다. 그럼 새로 생긴 만큼을 k에서 빼준다. k가 0이 될 때까지 이를 반복한다. 첫 번째 단계이다. 현재 k = 6이다. 쪽지를 하나만 옮겨서 가장 많은 그렇고 그런 관계를 만드는 방법은 무엇일까? 그렇다. 숫자의 크기가 가장 큰 쪽지를 제일 왼쪽으로 보내는 것이다. 다음과 같이 움직이면 된다. 그렇고 그런 관계가 4개 만들어졌다. (5, 1), (5, 2), (5, 3), (..

풀이방법 사용된 것: 그리디 알고리즘 정렬 Comparator 재정의 2022.02.24 각 날마다, 5000원짜리와 1000원짜리 중 무조건 더 맛있는 것을 고른다. 두 메뉴의 맛수치가 같다면 1000원짜리를 고른다. 그 후, 사용할 돈이 예산을 초과하는지 체크한다. 초과하지 않는다면 지금의 맛수치 합을 출력하고 프로그램을 종료한다. 예산을 초과한다면 다음과 같이 돈 아끼기를 수행한다. 일단, 각 날마다 '맛손실'을 구한다. 맛손실이란, 5000원짜리를 고르지 않고 1000원짜리를 골랐을 때 손해보는 맛수치의 크기이다. 즉, (5000원짜리의 맛수치 - 1000짜리의 맛수치) 이다. 1000원짜리가 더 맛있는 날에는 맛손실이 음수이다. 맛손실을 기준으로 날들을 오름차순 정렬한다. 그 후, 정렬된 배열의..

풀이방법 사용된 것: 정렬 동적 프로그래밍(DP) 2022.02.24 이 문제는 DP를 사용하기에 적합하다. n번째 사람의 최종 소요시간은 n-1번째 사람의 최종 소요시간에 자신의 개인 소요시간을 더한 것이다. 즉 앞사람의 최종 소요시간을 구하는 것이 뒷사람의 최종 소요시간을 구하는 문제의 부분 과제이다. 사람들의 개인 소요시간을 담은 배열을 오름차순으로 정렬한 뒤, DP를 이용해 앞 사람부터 차곡차곡 수를 더해가며 값을 기록해주면 된다. 코드 언어(2022.02.24) import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.ut..

풀이방법 사용된 것: 동적 프로그래밍 깊이우선탐색(DFS) 2022.02.23 오답노트 #15681 : 트리와 쿼리 풀이방법 및 문제점 2022.02.12 55%에서 시간초과가 난다. 예제의 답은 옳게 출력된다. 일단은 출력 방식을 바꾸어봐야겠다. 18870번 문제를 풀 때처럼 System.out.println을 Q번 수행한 것이 문제일 수 있 blowupmomo.tistory.com 동적 프로그래밍을 사용한다. n번 노드의 자식이 m1, m2라 할 때, n의 서브노드의 개수는 m1의 서브노드 개수 + m2의 서브노드 개수 + 1 이다. 따라서 이 문제는 동적 프로그래밍으로 풀기에 알맞다. 간선정보를 일단 이중 ArrayList에 저장해둔다. 이 정보를 활용하여, 루트에서 출발하여 모든 노드를 DFS 순..

문자열의 각 문자 하나씩을 다루어야 할 때가 있다. 이럴 때 문자열이 String 타입이 아닌 char 배열 형태라면 더 편한 경우가 있다. 그럴 때는 toCharArray()를 쓰면 된다. 코드 String str = "가나다라마"; char[] letters = str.toCharArray(); String 타입 str를 char[] 타입으로 바꾼 letters를 만드는 코드

풀이방법 및 문제점 2022.02.22 왠지 스택을 이용해 풀 수 있을 것 같아서 스택으로 구현해보았는데 틀렸다. 50%에서 실패가 뜬다. 얌전히 동적 프로그래밍 또는 그래프로 풀어야겠다. 내가 시도한 풀이법은 다음과 같다. 문자를 저장하는 스택 A, B, C를 선언한다. 첫 번째 단어를 스택 A에, 두 번째는 B에, 세 번째는 C에 앞 글자부터 push한다. C의 top에 있는 글자가 A의 top에 있는 글자와 동일하다면 A와 C에서 한 글자를 pop한다. C의 top에 있는 글자가 B의 top에 있는 글자와 동일하다면 B와 C에서 한 글자를 pop한다. C의 top에 있는 글자가 A와 B 중 어느 것의 top과도 같지 않다면 no를 출력하고 다음 데이터로 넘어간다. no로 판별하는 일 없이 C가 텅 ..