모항이코딩한다

풀이방법 사용된 것: 그리디 알고리즘 정렬 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 순..

풀이방법 및 문제점 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가 텅 ..

풀이방법 사용된 것: 동적 프로그래밍 2022.02.22 피보나치 수열 문제와 비슷한 문제이다. 주어진 숫자가 n일 때 문제의 답을 f(n)이라 하면, f(n) = f(n-1) + f(n-2) 이다. (단 f(1) = 1, f(2) = 2) 이를 재귀함수로 구현하면 시간초과가 발생한다. 1 ≤ n ≤ 1000 이므로, 길이가 1000 이상인 배열에 미리 f(1) ~ f(1000)을 모두 구해 저장해둔 뒤 거기서 값을 꺼내어 출력하면 된다. 나는 편의를 위해 길이가 1000이 아닌 1001인 배열을 사용하였다. k번 인덱스의 위치에 f(k)가 저장되게 하기 위해서이다. 코드 Java(2022.02.22) import java.io.*; public class Main { static int[] nums; ..

풀이방법 사용된 것: Comparator 두 개의 변수를 기준으로 비교하기 위하여 Comparator를 직접 Override하였다. 그리디 알고리즘 선택 가능한 회의들 중 무조건 제일 일찍 끝나는 것부터 고르는 게 최선의 선택이다. 따라서 그리디 알고리즘에 적합하다. 2022.02.14 오답노트 #1931 : 회의실 배정 풀이방법 및 문제점 2022.02.14 (1) 그리디 알고리즘 문제이다. 주어진 회의들을 끝나는 시간을 기준으로 오름차순 정렬한다. 정렬된 순서대로 차근차근 방문하며, 이전 회의와 겹치지 않는다면 즉 blowupmomo.tistory.com 입력값으로 제공된 회의들을 먼저 끝나는 시간 기준으로 오름차순 정렬한다. 끝나는 시간이 같은 회의들끼리는 시작하는 시간 기준으로 오름차순 정렬한다...

풀이방법 및 문제점 2022.02.14 (1) 그리디 알고리즘 문제이다. 주어진 회의들을 끝나는 시간을 기준으로 오름차순 정렬한다. 정렬된 순서대로 차근차근 방문하며, 이전 회의와 겹치지 않는다면 즉시 스케줄표에 해당 회의를 추가한다. 그럼 빨리 끝나는 순서대로 차근차근 겹치지 않게 스케줄표에 추가할 수 있다. 그런데 87%에서 틀렸습니다가 뜬다. 백준에 올라온 다음의 테스트케이스에 대하여 올바른 답을 출력하지 못하는 것을 보고 원인을 알 수 있었다. 5 6 7 6 6 5 6 5 5 7 7 답:5 이 테스트케이스를 찾은 게시글 링크 끝나는 시간이 서로 같은 회의가 포함되어있을 경우를 고려하지 않은 것이 문제였다. 끝나는 시간이 동일한 회의끼리는 시작 시간을 기준으로 오름차순 정렬을 해주어야 한다. 그런데..

풀이방법 사용된 것: HashMap 2022.02.14 집합 S에 포함되어있는 문자열을 HashMap에 넣는다. 정수형 변수 cnt의 초기값은 0이다. 포함 여부를 판별해야하는 문자열을 대상으로 HashMap.contains(문자열)이 true이면 cnt를 1 증가시킨다. cnt를 화면에 출력한다. 코드 Java(2022.02.14) import java.util.HashSet; import java.io.*; public class Main { public static void main(String[] args) throws IOException{ // TODO Auto-generated method stub BufferedReader br = new BufferedReader(new InputStre..

풀이방법 및 문제점 2022.02.12 55%에서 시간초과가 난다. 예제의 답은 옳게 출력된다. 일단은 출력 방식을 바꾸어봐야겠다. 18870번 문제를 풀 때처럼 System.out.println을 Q번 수행한 것이 문제일 수 있다. 혹은 재귀함수를 많이 써서 시간이 많이 걸린 것일까? 트리를 생성하는 makeTree 함수도 재귀함수이고, 서브트리의 노드의 개수를 구하는 count 함수도 재귀함수이다. 하지만 재귀를 쓰지 않는 방식이 떠오르지 않는다. 자고 일어나서 생각해봐야겠다. 혹은 트리의 구현 방식이 문제일 수도 있다. 다른 방식으로 구현해봐야겠다. 자바에서 트리 형식의 라이브러리를 제공하는지도 알아봐야겠다. 사용한 풀이 방법은 다음과 같다. 먼저, n-1개의 간선 정보를 인접 리스트(ArrayLi..

풀이방법 사용된 것: ArrayList DFS(깊이우선탐색) BFS(너비우선탐색) 2022.02.08 깊이우선탐색 방식으로 1번 컴퓨터와 연결된 모든 컴퓨터를 방문하고, 새로운 컴퓨터를 방문할 때마다 초기값이 0인 int 변수 count를 1씩 증가시켰다. 깊이우선탐색에는 재귀함수를 사용하였다. 그래프의 표현에는 인접리스트 방식을 사용하였다. 모든 간선이 무방향이기 때문에, 서로 연결된 두 노드의 리스트에 모두 서로를 추가하였다. 예를 들어 3과 5가 연결되어있다면 3번 리스트에도 5를 추가하고, 5번 리스트에도 3을 추가하는 식이다. 2022.06.01 너비우선탐색 방식의 코드를 추가해주는 김에, 조금 더 정리한 깊이우선탐색 코드도 추가했다. 코드 Java(2022.02.08) 첫 DFS 코드 impo..