알고리즘 문제풀이/백준
-
[백준/BOJ] 10942번 팰린드롬? (C++)알고리즘 문제풀이/백준 2021. 1. 21. 16:10
www.acmicpc.net/problem/10942 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net 어려운 DP문제였습니다. (다시 풀기) 일반적으로 팰린드롬인지 확인하는 과정은 맨 앞과 맨 뒤, 두번째와 뒤에서 두번째, 세번째와 뒤에서 세번째 이런식으로 문자가 같은지 확인하므로 O(N)의 시간 복잡도가 소요됩니다. 그런데 여기서 수열의 크기가 최대 2,000이고 질문의 개수가 최대 1,000,000 이기 때문에, O(N*M) = 2,000,000,000 으로 시간초과가 발생할 수 있습니다. 따라서 DP로 접근하여 문제를 해결해야합니다. 질문마다 ..
-
[백준/BOJ] 2667번 단지번호붙이기 (C++)알고리즘 문제풀이/백준 2021. 1. 20. 01:05
www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 전형적인 BFS 유형의 문제입니다. 2583번과 거의 동일한 문제였습니다. #include #include #include #include using namespace std; int n; int map[26][26]; int dx[4] = {1, 0, -1, 0}; int dy[4] = {0, 1, 0, -1}; int BFS(int sx, int sy) { int cnt = 1; queue q; q.push(..
-
[백준/BOJ] 2583번 영역 구하기 (C++)알고리즘 문제풀이/백준 2021. 1. 19. 23:33
www.acmicpc.net/problem/2583 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net BFS의 유형의 문제입니다. (0, 0)이 왼쪽 아래부터 시작이라는 것에 주의해야합니다. 2차원 배열을 사용해야하므로 (0, 0)을 왼쪽 위에 두고 문제를 풀어야합니다. 그 이후에는 전형적인 BFS 문제입니다. #include #include #include #include using namespace std; int m, n, k; int map[101][101]; int dx[4] = {..
-
[백준/BOJ] 11060번 점프점프 (C++)알고리즘 문제풀이/백준 2021. 1. 19. 19:14
www.acmicpc.net/problem/11060 11060번: 점프 점프 재환이가 1×N 크기의 미로에 갇혀있다. 미로는 1×1 크기의 칸으로 이루어져 있고, 각 칸에는 정수가 하나 쓰여 있다. i번째 칸에 쓰여 있는 수를 Ai라고 했을 때, 재환이는 Ai이하만큼 오른쪽으로 www.acmicpc.net DP 유형의 문제입니다. dp 배열을 임의의 큰 값 2147000000으로 초기화해주고, 0번째 인덱스는 0으로 초기화합니다. 그런 다음 0번에서 n-1번 인덱스 각각 최대 1번부터 a[i]번 까지 움직여보면 되는 문제입니다. #include using namespace std; int a[1001], dp[1001]; int main(void) { ios_base::sync_with_stdio(fa..
-
[백준/BOJ] 11048번 이동하기 (C++)알고리즘 문제풀이/백준 2021. 1. 18. 18:19
www.acmicpc.net/problem/11048 11048번: 이동하기 준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다. 준규는 www.acmicpc.net DFS + DP 유형의 문제입니다. DFS를 통해 (0, 0) 에서 시작해서 아래로 한칸, 오른쪽으로 한칸, 대각선으로 한칸 3방향으로 방문 가능한 경로로 (n-1, m-1) 에 도착하게 되고, 다시 (0, 0)으로 돌아오면서 현재 dp의 값과 DFS의 최대값을 누적해가며 답을 구합니다. #include #include using namespace std; int n, m; int map[1001..
-
[백준/BOJ] 16964번 DFS 스페셜 저지 (C++)알고리즘 문제풀이/백준 2021. 1. 15. 16:43
www.acmicpc.net/problem/16964 16964번: DFS 스페셜 저지 첫째 줄에 정점의 수 N(2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에는 트리의 간선 정보가 주어진다. 마지막 줄에는 DFS 방문 순서가 주어진다. DFS 방문 순서는 항상 N개의 정수로 이루 www.acmicpc.net DFS 유형의 문제입니다. (다시 풀기) 입력값으로 받는 DFS의 진행 순서에 맞게끔 각각의 노드에 인접한 노드들을 내림차순으로 정렬하는 것이 포인트였던 문제였습니다. #include #include #include using namespace std; vector graph[100001]; bool visit[100001]; vector order(100001), answe..
-
[백준/BOJ] 7569번 토마토 (C++)알고리즘 문제풀이/백준 2021. 1. 14. 19:31
www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net BFS 유형의 문제입니다. 7576번 문제가 3차원으로 바뀐 문제입니다. #include #include #include #include using namespace std; int m, n, h; int map[101][101][101]; int visit[101][101][101]; int dz[6] = {1, -1, 0, 0, 0, 0}; int dx[6] = {0, 0, 1, -1..
-
[백준/BOJ] 1012번 유기농 배추 (C++)알고리즘 문제풀이/백준 2021. 1. 14. 18:21
www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 전형적인 BFS 유형의 문제였습니다. 세로의 길이를 먼저 입력받는 것을 주의 #include #include #include #include using namespace std; int map[51][51]; int dx[4] = {1, 0, -1, 0}; int dy[4] = {0, 1, 0, -1}; void BFS(int sx, int sy, int m, int n) { queue q; q.push({ sx, sy }..