Problem Solving - Java
1.[BOJ] 1707 - 이분 그래프 (bfs)
[전체 코드] [문제 풀이 설명] 🔎 이분 그래프란? 일단! 이 문제를 풀기 전에, 당연히 이분 그래프가 무엇인지부터 간단하게 살펴보자. > *이분 그래프란? 인접한 정점끼리는 서로 다른 색상 -> 모든 정점을 2가지 색으로만 칠할 수 있는 그래프. 한 마디로, 이웃하고 있는 정점끼리는 같은 색상이면 안 된다. 그리고 여기서 중요한 점!! 비...
2.[BOJ] 14500 - 테트로미노
[전체 코드] [문제 풀이 설명] 문제는, 주어진 종이 위에 테트로미노를 놓을 수 있는 모든 경우의 수 중에서, 놓은 수의 합이 최대일 경우를 구하는 문제이다. 즉! 모든 경우의 수로 테트로미노를 놓아야 하므로 위 문제는 백트래킹을 사용하여 모든 경우를 보면 된다. 일단, 테트로미노는 크기가 4인 정사각형으로 모양은 다양하다. 백트래킹으로 탐색하면서...
3.[BOJ] 1261 - 알고스팟
[전체 코드] [문제 풀이 설명] 이 문제는 보기에는 쉬워 보인다. 하지만, BFS, 백트래킹 등 푸는 방법이 확고하게 생각나지 않는 문제다. 일단, 이 문제는 최단 거리를 구하는 문제는 아니다. 하지만 왜 BFS를 썼냐? Queue가 아닌 Deque의 성질을 사용하여서 BFS를 구현하였기 때문이다 일단 Deque가 뭔지 간단히 짚고 가자면, Dequ...
4.[BOJ] 15990 - 1, 2, 3, 더하기 5
[전체 코드] [문제 풀이 설명] 일단 DP (다이나믹 프로그래밍) 문제는 점화식을 찾는 것이 중요하다. 그리고 dp배열을 1차원으로 구현할지 또는 2차원으로 구현할지 잘 생각해 봐야한다. (다들 9095번 (1, 2, 3 더하기)을 풀었을 거라 예상하고 설명을 하겠다.) 위 문제의 핵심은 "단, 같은 수를 두 번 이상 연속해서 사용하면 안 된다."이다...
5.[BOJ] 15989 - 1, 2, 3, 더하기 4
[전체 코드] [문제 풀이 설명] 이 문제는 9095(1, 2, 3 더하기) 문제를 기반으로 "합을 이루고 있는 수의 순서만 다른 것은 같은 것으로 친다." 의 조건이 더해진 문제이다. n이 4인 경우를 예로 들면, > 1로 끝나는 경우: 1+1+1+1, 1+2+1, 2+1+1, 3+1 2로 끝나는 경우: 1+1+2, 2+2 3으로 끝나는 경우: 1+3...
6.[BOJ] 11053 - 가장 긴 증가하는 부분 수열
[전체 코드] [문제 풀이 설명] DP에서 유명한(?) LIS (Longest Increasing Subsequence) 문제이다. 문제 이름대로, 수열이 있으면 해당 수열에서 증가하는 부분이 가장 긴 부분 수열을 구하는 문제이다. 예제 입력 1을 보면, 수열이 [10, 20, 10, 30, 20, 50] 으로 주어졌다. > i:0) 0번 인덱스부터 ...
7.[BOJ] 11722 - 가장 긴 감소하는 부분 수열
[전체 코드] [문제 풀이 설명] 이 문제는 LDS (Longest Decreasing Subsequence)이다. LIS(11053)과 비슷하지만, 감소하는 부분 수열을 구하는 것이다. 11053과 비슷하게 풀되, for문을 순차적으로 탐방하는 것이 아닌, 역순으로 탐방하는 것이다. 이렇게 n - 1번째부터 시작해서 0번째까지 역순으로 자신보다 큰 ...