전체 글

알고리즘 문제보다 수학 문제 같았다. 문제 풀이 방법에는 두 가지가 있다. 첫 번째는 규칙을 찾아 푸는 방법이고 두 번째는 기울기를 이용해서 푸는 방법이다. 나는 규칙을 찾아가면서 풀었지만 기울기를 이용한 방법이 더 간편해 보인다. 입력값이 int로 주어지고 w와 h값이 각각 1억 이하의 자연수이기 때문에 사용할 수 없는 사각형 계산을 하면서 인티저 오버플로가 발생할 수 있다. 따라서 입력값을 전부 long으로 형 변환 후 계산했다. 또한 최대 공약수가 1억을 넘을수는 없기 때문에 int로 선언했다. 최대 공약수를 구하는 방법도 세 가지가 있는데 첫 번째는 w와 h를 BigInteger로 변환하고 BigInteger에 내장된 gcd를 사용하는 방법 두 번째는 재귀를 이용한 유클리드 호제법 세 번째는 반복..

문제를 보고 처음에 아주 신이 났었다. 딱히 생각하지 않고 바로 풀 수 있는 BFS문제였기 때문이다. 문제를 제대로 읽지 않고 10분도 안돼서 코드 작성을 마쳤고 테스트를 돌리는데 몇 개의 케이스를 제외하고서 모두 틀렸고 심지어 런타임 에러도 났다. 30분 넘게 고민을 해도 답이 나오지 않았고 1시간이 다 돼서야 n과 m의 크기가 가변적이라는 걸 발견했다. 문제 예시에서 5X5 배열만을 이야기해서 모든 변수를 5로 고정하고 풀었으니 당연히 틀릴만했던 거다. 저번에도 이런 경우가 꽤 있었는데 오늘은 정말 허탈했다.... 문제를 제대로 읽자.... 최종 코드 import java.util.Arrays; import java.util.LinkedList; import java.util.Queue; class ..

문제 이름은 평범한 배낭이지만 전혀 평범하지 않다고 느꼈다. 한참을 고민하다가 검색을 했지만 너무 어려웠다. 대표적인 DP 문제라고 하는데 knapsack 알고리즘을 이용해서 풀어야 한다. 입력값을 w 배열과 v 배열에 삽입하고 각 무게와 가치를 계산해서 dp배열에 가치의 최댓값을 넣어주면 된다. 가장 이해하기 어려웠던 부분은 아래의 코드인데 dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]); 이전에 계산했던 가치, 남은 무게의 가치 + 현재 가치 중 큰 값을 저장하는 부분이다. j - w[i] 는 j의 무게에서 현재 아이템의 무게를 뺀 값이다. 이 값은 dp[i-1][j - w[i]] 에 이미 저장되어 있고 이 값에 현재 아이템의 가치를 더한..

문제의 그림부터 DP 문제라고 알려주고 있었다. 꽤나 많은 문제들을 풀면서 이제 문제를 보면 어떤 유형인지 대충 어떻게 설계를 해야 하는지는 알 수 있다. 다만 실제로 구현하는것은 아직도 조금 힘들다. 입력값을 배열로 만들고 마지막 배열의 값을 dp 배열에 복사하는 것이 첫 번째이다. 그리고 정점의 노드부터 재귀를 통해 내려온다. 마지막 노드에 도착하면 왼쪽과 오른쪽의 값 중 큰 값을 선택하고 배열의 값과 더해 dp의 값이 된다. 이런 식으로 모든 노드를 순회하면 dp[0][0] 값이 최댓값이 되어 출력하면 된다. 최종 코드 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; pu..

문제를 읽고 전형적인 DFS / BFS 문제라고 생각했다. 다만 DFS / BFS를 구현하는 부분이 조금 막혔다. 그래서 모든 경우의 수를 나누어 먼저 풀어보았고 BFS를 이용해서 다시 풀어 보았다. 모든 경우의 수를 나눈 방법은 BFS를 이용했을 때보다 시간이 훨씬 적게 걸렸다. 다만 코드의 길이가 좀 길고 거리가 2인 확인과 대각선 확인의 로직이 복잡해 장단점이 있는 것 같다. 최종 코드 (모든 경우) class Solution { public int[] solution(String[][] places) { int[] answer = new int[5]; for (int i = 0; i < places.length; i++) { String[] temp = places[i]; boolean check..

문제가 쉬운 듯하면서도 이해가 자꾸 되지 않아서 꽤 시간을 썼다. 부분 수열이 무엇인지 알아야 하고 LIS 알고리즘을 코드로 구현해야 한다. 한 번에 점화식이 떠오르지 않고 한 단계씩 생각해봐야 해서 힘들었다. 최종 코드 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.*; public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine(..

지금까지 풀어본 문제 중에 난이도가 가장 높았던 문제라고 생각한다. 지금까지 알고 있었던 지식을 총동원해야 풀 수 있는 문제였다. 정렬과 조합에 대해서 알아야 하고, 중간중간 생각해야 할 조건이 많아서 어렵게 느낀 것 같다. 특히 처음에 orders 배열을 정렬하지 않으면 기본 케이스 2개만 통과하고 점수는 하나도 얻을 수 없다. 만약 실제 시험이였다면 이 한 문제에 시간을 거의 다 쓰고. 처음 정렬의 하지않아 0 솔을 했을 것 같은 느낌이다.... 최종 코드 import java.util.*; class Solution { static HashMap stringMap; public String[] solution(String[] orders, int[] course) { // 1. orders의 값을 ..

처음 시도는 완전 탐색으로 시도했지만 50%에서 시간 초과가 나왔다. N의 값이 1000 이하니 완전 탐색을 이용하면 시간 초과가 나오는 게 당연한 결과였다. 다른 방법을 생각해봤지만 떠오르지 않아서 검색을 통해 힌트를 참고했다. 처음에는 이 문제가 왜 DP를 이용하는지 이해가 잘 안되었다. 점화식도 떠오르지 않았고, 지금까지 풀었던 문제들과는 조금 달라서 그렇게 생각한 것 같다. 풀이 방법은 R, G, B를 0, 1, 2로 대응시키고 다음 집의 색상을 봐야 한다. 예를 들어 첫 번째 집이 0이라면 다음 집은 1 또는 2가 되어야 한다. 1과 2중에서 더 작은 값을 더해 n까지 배열을 만들면 된다. 마지막으로 배열의 세 값 중 가장 작은 값을 출력하면 된다. DP로 풀 수 있는 문제지만 이전 집의 색상과..

다른 문제를 풀면서 투 포인터 알고리즘에 대해 알게 되었고 대표적인 문제를 풀어 보았다. 실버 4 문제라 기본적인 투 포인터 개념만 이해한다면 바로 풀 수 있는 문제이다. 투 포인터 알고리즘은 연속되고 길이가 가변적인 부분 배열을 만들어 특정 조건을 만족시키는 알고리즘이다. 배열을 반복적으로 탐색할때 2중 for문을 이용한다면 시간 복잡도가 O(n^2) 나온다. 그러나 투포인터 알고리즘을 이용한다면 시간 복잡도를 O(n)까지 줄일 수 있다. 투 포인터 알고리즘의 방식은 두 가지가 있다. 1. 시작점과 끝점이 배열의 시작점에서 같이 시작하는 것 2. 정렬된 배열 안에서 시작점과 끝점이 각각 배열의 시작점과 끝점에서 시작하는 것 이 문제는 첫 번째 방식으로 접근하여 풀었다. 간단하면서도 강력한 알고리즘이라 ..