본문 바로가기

전체보기

 (126)
[백준] 11726번: 2×n 타일링 - JAVA 🔗 문제 링크 BOJ 11726번: 2×n 타일링 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 📝 풀이 과정 문제를 보고 경우의 수를 하나씩 그려보기로 했다. n = 4까지 그리고 난 뒤 확인해보면 일정한 패턴이 반복됨을 알 수 있었다. 노란색으로 체크된 n - 1의 타일에 세로 타일이 하나 추가된 모습이고, 파란색으로 체크된 n - 2의 타일에 가로 타일이 두 개 추가된 형태를가지고 있다. 따라서, $dp[n] = dp[n-1] + dp[n-2]$라는 점화식을 가지게 된다. 💡 mod 연산을 한 결과값을 출력해야 할 때에는 반..
[백준] 11724번: 연결 요소의 개수 - JAVA 🔗 문제 링크 BOJ 11724번: 연결 요소의 개수 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net 📝 풀이 과정 BFS와 DFS 모두 풀이가 가능하지만 DFS로 문제를 풀어보았다. 반복문을 돌며, 만약 방문한 요소가 아닐 경우 해당 칸을 시작으로 하여 DFS를 시작한다. 방문하며 visit을 true로 변경하여 다시 방문하지 않도록 방문처리를 해주고 해당 요소에 연결되어 있고 방문하지 않았다면 재귀를 통해 DFS를 돌린다. 더이상 방문할 요소가 ..
[백준] 11723번: 집합 - JAVA 🔗 문제 링크 BOJ 11723번: 집합 11723번: 집합 첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다. 둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다. www.acmicpc.net 📝 풀이 과정 입력 범위(1
[백준] 11403번: 경로 찾기 - JAVA 🔗 문제 링크 BOJ 11403번: 경로 찾기 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net 📝 풀이 과정 모든 정점에서 다른 정점까지 도달할 수 있는지 탐색할 수 있는지를 판별하는 문제이다. 따라서, 플로이드 와샬 알고리즘을 생각해 볼 수 있는데, 문제에서 N의 범위가 100이하으므로 $O(N^3)$인 플로이드 와샬을 써도 괜찮은 문제이다. k, i, j를 3중 반복문을 통해 탐색하며, 만약 i -> k로 갈 수 있고 k -> j로도 갈 수 있다면, i -> j로 가는 경우가 가능하기 때문에 true로 값을 변경해준다. 💻 코드 import java..
[백준] 1074번: Z - JAVA 🔗 문제 링크 BOJ 1074번:Z 1074번: Z 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. 만약, N > 1이 라서 www.acmicpc.net 📝 풀이 과정 N = 2일 때의 탐색 모형이다. 처음 큰 $2^2$ x $2^2$의 사각형을 4등분으로 분할한 뒤 Z모양으로 탐색하고, $2^1$ x $2^1$을 Z모향으로 탐색을 하게 되면 위와 같은 그림이 나오게 된다. 처음 문제를 봤을 때, 단순 분할 + 재귀 문제라고 생각하고 모든 칸을 방문하며 count 했고, 실패했다... 시간 복잡도를 잘 따지지 않아 생겼던 문제인데, N의 범위는 1
[백준] 11399번: ATM - JAVA 🔗 문제 링크 BOJ 11399번: ATM 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net 📝 풀이 과정 사람들이 번호 순서대로 줄을 선 상태이고, [3, 1, 4, 3, 2]의 인출시간이 걸린다고 했을 때, 아래만큼의 시간이 각각 소요되게 된다. 0번 : 3= 3 1번 : 3 + 1= 4 2번 : 3 + 1 + 4= 8 3번 : 3 + 1 + 4 + 3= 11 4번 : 3 + 1 + 4 + 3 + 2= 13 -------------------------------------- 총 인출 시간 : 3 + 4 + 8 + 11 + 13 = 39 ..
[백준] 11286번: 절댓값 힙 - JAVA 🔗 문제 링크 BOJ 11286번: 절댓값 힙 11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 📝 풀이 과정 [백준] 11279번: 최대 힙과 정렬부분만 다른 문제이다. 우선 순위는 절대값이 작은 순 → 숫자가 작은 순으로 제거해야 하기 때문에 PriorityQueue를 사용해 Comparator의 compare를 오버라이딩하여 Queue에서 올바른 순서로 나올 수 있게 만들어 주었다. PriorityQueue que = new PriorityQueue((o1, o2) -> Math.abs..
[백준] 11279번: 최대 힙 - JAVA 🔗 문제 링크 BOJ 11279번: 최대 힙 11279번: 최대 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 www.acmicpc.net 📝 풀이 과정 힙을 직접 구현해도 좋겠지만, Java에 있는 PriorityQueue를 사용해 문제를 해결하기로 했다.(List로 문제를 풀 수도 있지만, n개의 숫자를 출력할 때마다 정렬하면 $O(n^2\log n)$으로 시간초과 발생) PriorityQueue는 add와 poll 모두 O(log n)으로 $O(n\log n)$만에 문제를 해결할 수 있다. PriorityQueue는 기본적으로 오름..

티스토리툴바