알고리즘 문제풀이
-
[백준/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..
-
[프로그래머스/Level 2] 단체사진 찍기 (C++)알고리즘 문제풀이/프로그래머스 2021. 1. 15. 16:46
programmers.co.kr/learn/courses/30/lessons/1835 코딩테스트 연습 - 단체사진 찍기 단체사진 찍기 가을을 맞아 카카오프렌즈는 단체로 소풍을 떠났다. 즐거운 시간을 보내고 마지막에 단체사진을 찍기 위해 카메라 앞에 일렬로 나란히 섰다. 그런데 각자가 원하는 배치가 모두 programmers.co.kr 새롭게 알게된 점 distance() 함수를 통해 iterator 사이의 크기를 반환할 수 있다. #include #include #include using namespace std; bool isPossible(int dis, char op, int target) { if(op == '=') return dis == target; else if(op == '>') retu..
-
[백준/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 }..
-
[백준/BOJ] 16940번 BFS 스페셜 저지알고리즘 문제풀이/백준 2021. 1. 14. 17:29
www.acmicpc.net/problem/16940 16940번: BFS 스페셜 저지 올바른 순서는 1, 2, 3, 4와 1, 3, 2, 4가 있다. www.acmicpc.net 처음보는 유형의 BFS 문제였습니다. (다시 풀기) 양방향 그래프를 만들고, 마지막 줄의 BFS의 방문순서를 큐에 저장합니다. 현재 정점과 인접한 정점들을 BFS 탐색하기 전에, set에 넣어주어 아까 큐에 저장했던 방문순서의 front 값이 set에 저장되어있는지 확인하는 것이 포인트입니다. #include #include #include #include using namespace std; vector graph[100001]; queue input; // 입력으로 받은 방문 순서가 저장된 큐 bool visit[10000..