모항이코딩한다

풀이방법 사용된 것: 동적 프로그래밍 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 입력값으로 제공된 회의들을 먼저 끝나는 시간 기준으로 오름차순 정렬한다. 끝나는 시간이 같은 회의들끼리는 시작하는 시간 기준으로 오름차순 정렬한다...

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

풀이방법 사용된 것: 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.01.28 (1) 빨대들을 모두 큰 것부터 정렬한다. 가장 긴 빨대를 1번, 가장 짧은 빨대를 N번이라 부르겠다. 일단 1번 빨대와 2번 빨대가 무조건 쓰일 것이라고 가정한다. 3번부터 N번까지 차례차례 살피면서, (2번빨대의 길이) + (j번째 빨대의 길이) > (1번 빨대의 길이) 인 j를 찾는다. 찾아지면 1번, 2번, j번 빨대 세 개로 만드는 삼각형의 변의 합이 정답이다. 위의 과정에서 N번 빨대까지 모두 살폈는데 조건에 부합하는 빨대가 없었다면, 2번 빨대와 3번 빨대가 무조건 쓰일 것이라고 가정하고 4번부터 살펴 합당한 j를 찾는다. 또 없었다면, 3번 빨대와 4번 빨대가 무조건 쓰일 것이라고 가정하고 5번부터 살핀다. 이렇게 N-2번 빨대..

풀이방법 사용된 것: HashMap StringTokenizer StringBuilder 2022.01.28 오답노트 #18870 : 좌표 압축 풀이방법 및 문제점 2022.01.28 (1) 입력 수열의 값을 복사한 temp 배열을 크기순으로 정렬하면 각 좌표의 압축 결과를 쉽게 구할 수 있다. 그 다음 temp값과 기존 입력 수열의 값을 비교하여 본래 순서 blowupmomo.tistory.com 주어진 정수들에 순위를 매겨 그 순위를 출력하는 문제이다. 값이 같은 정수끼리는 순위도 같다. 가장 작은 정수가 0위이며 클수록 순위는 1씩 증가한다. 수들을 입력된 순서대로 저장하는 배열, 수들을 정렬하여 오름차순으로 정렬할 배열, 각 수마다의 순위를 저장할 HashMap이 필요하다. 오름차순으로 정렬한 배..

풀이방법 2022.01.26 입력값으로 n개의 정수 배열이 주어진다. 이 정수 배열을 nums라 부르자. 길이가 n인 정수 배열 dp를 만든다. dp[i] 는 nums[i]를 마지막 순서로 갖는 가장 긴 증가하는 배열의 길이이다. 예를 들어, 아래의 표를 보자. nums 10 20 10 30 20 50 dp 1 2 1 3 2 4 nums[0]의 값은 10이다. 10으로 끝나는 가장 긴 증가하는 배열은 {10}이다. {10}의 길이는 1이다. 따라서 dp[0]은 1이다. nums[3]의 값은 30이다. 30으로 끝나는 가장 긴 증가하는 배열은 {10, 20, 30}이다. {10, 20, 30}의 길이는 3이다. 따라서 dp[3]은 3이다. 이를 코드로 구현한 뒤에 dp 배열의 요소 중 가장 큰 것을 화면에..

풀이방법 사용된 것: 그리디 알고리즘 2022.01.24 가지고 있는 동전을 액수가 큰 것부터 차례대로 살핀다. 현재 살피는 중인 동전의 액수 값을 t라 한다. 만들어내야 하는 금액을 k라 한다. 출력할 답은 ans에 저장한다. ans의 초기값은 0이다. 만약 t=0; i--) { coins[i] = sc.nextInt(); } for(int i = 0; i

풀이방법 2022.01.22 재귀함수로 구현하면 제한시간 1초 내에 해결할 수 없는 문제이다. 반복문을 사용해 정수 배열에 피보나치 수들을 미리 저장해놓고 꺼내쓰면 빠르게 해결할 수 있다. n

풀이방법 사용된 것: DP 알고리즘 더보기 도움이 된 블로그 글 2022.01.22 (i, j)에서 (i+1, j+1)까지 대각선으로 이동할 경우, (i+1, j)를 거쳐 'ㄴ'자로 이동한 경우와 (i, j+1)을 거쳐 'ㄱ'자로 이동한 경우보다 사탕을 더 많이 모으는 것이 불가능하다. 그러므로 대각선으로 이동하는 경우는 배제한다. 따라서, (i, j)까지 이동하면서 모을 수 있는 사탕의 최대 개수는 (i-1, j)까지 이동하면서 모을 수 있는 사탕의 최대 개수에 (i, j)에 있는 사탕의 개수를 더한 것 (i, j-1)까지 이동하면서 모을 수 있는 사탕의 최대 개수에 (i, j)에 있는 사탕의 개수를 더한 것 위의 두 값 중 더 큰 쪽이다. 이 아이디어를 이용하면 (N, M)까지 이동하면서 모을 수 있..