본문 바로가기

알고리즘 풀이

 (84)
[백준] 14500번: 테트로미노 - JAVA 🔗 문제 링크 BOJ 14500번: 테트로미노 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 📝 풀이 과정 모든 테트로미노를 그린 뒤 탐색마다 도형을 회전시키고 대칭시키며 구할 수도 있지만 경우의 수가 너무 많아 귀찮아서 포기하였다... 예시로 그려진 테트로미노의 모양을 잘 살펴보면 ㅜ모양을 제외하면 DFS로 표현이 가능할 것이라는 생각이 들었다. 회색으로 칠해진 부분이 현재까지 탐색한 부분이고 ⭐의 위치가 현재 위치라고 할 때, 탐색할 수 있는 방향은 파란색의 화살표로 가는 방향뿐이기 때문에 ㅜ 모양의 탐색..
[백준] 11727번: 2×n 타일링 2 - JAVA 🔗 문제 링크 BOJ 11727번: 2×n 타일링 2 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net 📝 풀이 과정 [백준] 11726번: 2×n 타일링 - JAVA과 이어지는 문제이다. 노란색으로 체크된 n - 1의 타일에 2x1 타일이 세로로 하나 붙은 형태를 가지고 있고, 파란색으로 체크된 n - 2의 타일에 2x1 타일이 가로로 2개 붙어있거나, 2x2 타일이 붙은 형태를 가지고 있다. 이전 문제에서 n - 2의 타일에 붙이는 타일은 2x1타일이 가로로 2개 붙은 형태만 가능했었는데, 타일이 추가되면서 대신 2x2타일도 가능하게 된 ..
[백준] 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 ..

티스토리툴바