파이문

Course Schedule 어떤 과목 A 가 주어질 때, 그 과목의 선수 과목 B가 존재하고 이를 [A, B] 라는 리스트로 표현합니다. 이처럼 과목과 그에 맞는 선수 과목의 리스트들이 존재할 때 주어진 목표는 해당 과목들을 모두 이수할 수 있는가? 에 관한 것입니다. 즉 [[A, B], [B, A]] 라고 문제에 주어진다면 A를 이수하기 위해선 먼저 B를 이수해야 하고 그 다음 값에선 B를 이수하기 위해선 A를 먼저 이수해야 합니다. 이럴 경우 A, B 둘 다 이수하지 못하므로 False 를 리턴하면 됩니다. 문제의 스토리는 이와 같은데 결국 해야 하는것은 방향성 그래프(Directed Graph) 에서 Cycle 을 찾는 문제입니다. 방향성 그래프에서 사이클을 찾는 방법은 DFS 와 BFS 가 있고..

Longest Substring Without Repeating Characters 주어진 문자열에서 중복 없는, 연속된 문자열을 만들 때 가장 긴 문자열의 길이를 리턴하는 문제입니다. medium 문제이지만, 크게 어렵지 않은 구현 문제입니다. 2중 for loop로 풀어보진 않았지만, 솔루션에 따르면 전부 다 탐색 해도 (brute-force) 풀수 있게 되어 있다고 합니다. 즉, 주어진 문자열을 다 순회하여서 중복이 있는지 없는지 확인해보며, 현재 길이가 가장 길게 갱신하면 됩니다. (하단 LeetCode solution 참조) public class Solution { public int lengthOfLongestSubstring(String s) { int n = s.length(); int ..

Add Two Numbers (https://leetcode.com/problems/add-two-numbers/) 두 개의 리스트 노드를 입력 받아, 각 리스트 노드의 값을 더한 새로운 리스트 노드를 생성하는 문제입니다. 일반적으로 생각할 때 단순히 두 개의 리스트 노드를 순회하면서 진행하면 될 것 같지만, 더할 때 10을 넘어가면 일반 덧셈 처럼 뒤 값에 해당 몫을 더해주어야 합니다. Input: (2 -> 4 -> 3) + (5 -> 6 -> 4) Output: 7 -> 0 -> 8 Explanation: 342 + 465 = 807. 위와 같은 예에서 가장 마지막 노드의 값이 7이 아닌 8인 이유도 그때문입니다. (Explanation 에서 설명하는 덧셈 로직과 같습니다.) 알고리즘 이라기 보다는..

2293. 동전 1(https://www.acmicpc.net/problem/2293) 동전 경우의 수 구하는, 나름 유명한 문제다. 역시나 알고스팟에도 같은 문제가 있다. (https://algospot.com/judge/problem/read/COINS) 구하려는 값 크기를 갖는 배열 dp를 만드는 데, 이 때 사이즈를 값 + 1 해야, 예외 처리 따로 하지 않고 쉽게 할 수 있다.이렇게 만들어진 dp 에 경우의 수를 갱신하는데, i는 i원을 의미한다. 예를 들어서 dp[3]은 3원을 만드는 방법인데, 3원을 만드는 방법은 1원을 만드는 방법과 2원을 만드는 방법 두개를 더 하면 된다. 유투브에 강의 몇 개가 있어서 하나 첨부해 본다. https://www.youtube.com/watch?v=jaNZ..

11053. 가장 긴 증가하는 부분 수열(https://www.acmicpc.net/problem/11053) 유명한 문제이다. (알고스팟에도 있는 문제다. https://algospot.com/judge/problem/read/LIS) 일명 Longest Increasing Sequence 라는 문제인데, 주어진 수열에서 가장 긴 길이를 가질 수 있는 증가하는 부분 수열의 길이를 리턴해야 한다. 가장 먼저 1로 (가질 수 있는 최소 길이값이 길이1이므로) 값을 초기화 한 dp를 선언하고, i는 1부터 길이까지 증가시키고 j는 0부터 i까지 증가 시켜서, i번째 값이 j번째 값 보다 크면 dp[j] + 1이나 현재 값 dp[i] 중 maximum 값으로 갱신하는 것이다. 동영상 설명이 잘 되어 있어서 링..

2579. 계단 오르기(https://www.acmicpc.net/problem/2579) 문제의 요점은 연속해서 계단 3개를 밟을 수 없다는 것이다. 작은 단위로 계단이 3개 있을 때를 가정하자면 다음과 같다.1번 계단 -> 3번 계단 과 1번 계단 -> 3번 계단을 밟는 것 중 최대 값이 3번째 계단에 다다랐을 때의 최대 값이 되는 것이다. (문제에서는 무조건 마지막 계단을 밟아야 한다.) 계단이 4개 있을 때로 문제를 늘리면 1. 1번 계단 -> 3번 계단 -> 4번 계단 (dp[1] + 계단[3] + 계단[4])2. 1번 계단 -> 2번 계단 -> 4번 계단 (dp[2] + 계단[4]) 왜 1번 계단 이 dp[1]이 되고 1번 계단 -> 2번 계단이 dp[2]가 되는지는, 계단 수를 늘려서 그려보..

518. Coin Change 2(https://leetcode.com/problems/coin-change-2/#/description) amount 를 coins의 값들로 만들 수 있는 모든 경우의 수를 리턴하는 문제다. 원래는 coin들로 recursive 하게 빼주다가 0이 되면 리턴하게 하는 식으로 하려고 했는데, 빼주었던 coin들을 어떻게 가지고 있어야 할지 구현하는게 어려워서 포기했다. 결국 DP로 풀었는데, 2차원 배열로 어떻게 하려다가 잘 안되서 그냥 인터넷에서 보고 구현했다. dp의 index값은 amount 값이 되고, 그렇기에 0원을 만들 수 있는 경우의 수는 1가지 (아무것도 없는 경우) 있기 때문에 dp[0] = 1 을 해준 상태에서 시작한다. amount 5, coins = ..

1149. RGB 거리(https://www.acmicpc.net/problem/1149) dp[i][j]라는 배열을 만들어서, i는 i번째 집이고 j는 색을 의미하게 하였다. 그 값으로는 i번째 집이 j의 색을 가질 때, 가질 수 있는 최소 값을 넣었다. 정리하자면 i번째 집을 j색으로 칠할 때 + (i-1번째 집이 j색이 아닌 다른색으로 칠했던 경우의 최소 값) 인 것이다. public void problem1149(int houseCount, ArrayList n) { int[][] dp = new int[houseCount][3]; dp[0][0] = n.get(0); dp[0][1] = n.get(1); dp[0][2] = n.get(2); for (int i=1; i

1463. 1로 만들기(https://www.acmicpc.net/problem/1463) 동전 경우의 수 구하는 문제랑 비슷하다. 다만 앞에서 하는게 아니라 뒤에서 풀어야 풀린다. (다른 방법은 잘 모르겠음) 예를 들어서 8이 주어지면 8에서 만들 수 있는 수는 8-1, 8/2 두 가지이다. 이 때 나오는 수인 7, 4를 인덱스로 가지는 dp 에 1을 넣어준다. 이것이 맨 처음에 1을 넣어주는 부분이다. (초기화를 n-1하는 이유는 어떤 수 n에서 1을 만드는 가장 최댓값이 n-1이기 때문이다.) 그리고 그 다음 7부터 거꾸로 dp를 만들어 주면 된다. (인덱스) i에서 i/2, i/3, i-1에 i를 만들수 있는 값 + 1과 해당 값의 최솟값만 갱신해 주고, 목표가 1을 만드는 것이기 때문에 dp의 ..

1003. 피보나치 함수(https://www.acmicpc.net/problem/1003) 숫자를 입력받아, (피보나치 계산으로) 1과 0을 얼마나 호출하는지를 출력하는 문제이다. 케이스 범위에 따라, 이전 계산 값을 그대로 사용할 수 있게 보완하면 더 좋을듯 public void problem1003(int n) { if (n == 0) { System.out.println("1 0"); } else if (n == 1) { System.out.println("0 1"); } else if (n == 2) { System.out.println("1 1"); } else { int[][] dp = new int[n + 1][2]; dp[1][0] = 0; dp[1][1] = 1; dp[2][0] = 1..