모항이코딩한다

풀이방법 사용된 것: 동적 프로그래밍 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; ..

기본 데이터타입이 아닌 객체(Object)를 정렬해야 할 때가 있다. 또한, 자바에서 기본으로 제공해주는 정렬함수로는 수행하기 힘든 복잡한 방식/기준의 정렬이 필요할 때도 있다. 백준 #1931 회의실 배정 문제가 그 예시이다. 이럴 때 쓸 수 있는 방법은 여러 가지가 있는데, 그 중 Comparator의 compare 함수를 재정의하여 사용하는 방법을 정리해보겠다. 자바에 정의되어있는 Comparator를 오버라이드하여 내가 정한 기준에 따라 객체를 정렬하도록 만드는 방식이다. 어떤 새로운 형식의 객체를 정의하든지 상관 없다. 정렬의 방식과 기준도 자유롭게 정할 수 있다. 1차원 배열을 정렬할 때는 Arrays.sort() List 등을 정렬할 때는 Collections.sort()를 사용한다. 사용법..

풀이방법 사용된 것: 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..

자바에서 간단한 트리를 만들어보았다. 클래스 Node 필드: 이름, 부모, 자식들 public int name; public Node parent; public ArrayList childs; 메소드: 생성자 public Node (int name){ this.name = name; childs = new ArrayList(); } 트리는 Node 객체들의 배열이다. 직관적으로 사용하기 위하여 1번 노드는 tree[1], 2번 노드는 tree[2]인 것으로 한다. 즉 5개의 노드를 가진 트리는 길이가 6인 Node 배열로 구현한다. parent가 null이면 그 노드는 root이다. childs가 비어있다면 그 노드는 leaf이다. 코드 다음은 입력받은 노드의 바로 아랫단계의 자식들을 모두 출력하는 코드..

substring(int index) 특정 위치부터 끝까지의 부분문자열을 리턴한다. String str = "일이삼사오"; System.out.print(str.substring(2)); 위와 같은 코드를 실행하면 화면에는 "삼사오"가 출력된다. substring(int start, int end) 부분문자열의 시작위치와 끝 위치를 모두 지정할 수 있다. start 위치의 문자부터 end-1 위치의 문자까지를 리턴한다. end까지가 아닌 end-1까지라는 점에 주의하자. String str = "일이삼사오"; System.out.print(str.substring(1,4)); 위와 같은 코드를 실행하면 화면에는 "이삼사"가 출력된다. StringIndexOutOfBounds 예외를 관리할 때에도 1의 차..

풀이방법 사용된 것: 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..

풀이방법 및 문제점 2022.02.05 (1) 예제 입력에 대한 출력값은 올바르게 나오지만 채점 결과는 틀렸다고 나오는 상황이 또 발생했다. 큰일이다... 문제점이 무엇인지 모르겠다. 채점 시 6%에서 틀렸습니다 가 나온다. 잠이 부족한 상태에서 풀다 보니 놓친 반례가 생긴 것일까? 단계별로 다시 차근차근 검토해보아야겠다. 사용한 풀이방법은 다음과 같다. 가장 위 한 줄을 잘라내면, 이번 차례에 비교대상이 되는 단어들은 모두 앞전에 비교대상이었던 단어들의 가장 앞 한 글자만 떼어낸 접미사이다. Polynomial Hashing 기법을 사용하면 접미사를 빠르게 해싱할 수 있으므로, Polynomial Hashing으로 모든 접미사들의 해싱을 미리 끝내둔 뒤, 그 해시값을 비교하며 count 값을 구하였다...