알고리즘 문제풀이
-
[백준/BOJ] 2529번 부등호알고리즘 문제풀이/백준 2022. 5. 29. 21:55
https://www.acmicpc.net/problem/2529 2529번: 부등호 여러분은 제시된 부등호 관계를 만족하는 k+1 자리의 최대, 최소 정수를 첫째 줄과 둘째 줄에 각각 출력해야 한다. 단 아래 예(1)과 같이 첫 자리가 0인 경우도 정수에 포함되어야 한다. 모든 입력 www.acmicpc.net 시간복잡도가 9! 이므로 완전탐색으로 충분히 해결할 수 있다. 따라서 모든 순열을 구한 후, 조건에 만족하는 처음 값(최소값)과 마지막 값(최대값)을 출력하였다. #include #define f first #define s second #define lp1(i, x, n) for(int i = x; i selected[i + 1]) { flag = false; break; } } else if..
-
[백준/BOJ] 14497번 주난의 난알고리즘 문제풀이/백준 2022. 5. 22. 16:38
https://www.acmicpc.net/problem/14497 14497번: 주난의 난(難) 주난이는 크게 화가 났다. 책상 서랍 안에 몰래 먹으려고 숨겨둔 초코바가 사라졌기 때문이다. 주난이는 미쳐 날뛰기 시작했다. 사실, 진짜로 뛰기 시작했다. ‘쿵... 쿵...’ 주난이는 점프의 파 www.acmicpc.net 초기 코드 #include #define f first #define s second #define lp1(i, x, n) for(int i = x; i m >> _x1 >> _y1 >> _x2 >> _y2; _x1--, _y1--, _x2--, _y2--; for(int i = 0; i > area[i]..
-
[백준/BOJ] 2589번 보물섬알고리즘 문제풀이/백준 2022. 5. 5. 02:05
https://www.acmicpc.net/problem/2589 2589번: 보물섬 첫째 줄에는 보물 지도의 세로의 크기와 가로의 크기가 빈칸을 사이에 두고 주어진다. 이어 L과 W로 표시된 보물 지도가 아래의 예와 같이 주어지며, 각 문자 사이에는 빈 칸이 없다. 보물 지도의 www.acmicpc.net 처음엔 다음과 같이 접근하였다. 1. 지도에서 2개의 육지를 뽑는 모든 조합을 구한다. 2. 조합에서 두 육지 사이의 거리가 가장 긴 경우를 DFS로 구한다. 3. DFS에서 선택된 2개의 육지 사이에 도달하는 최단 시간을 BFS로 구한다. 그러나 위와 같은 방법으로 문제를 접근하면 250C2 * 50 * 50 * 4 = 311,250,000로 시간초과 발생 (멍청하게 50C2로 계산해서 망했다 ㅋ)..
-
[백준/BOJ] 17825번 주사위 윷놀이알고리즘 문제풀이/백준 2022. 5. 3. 00:41
https://www.acmicpc.net/problem/17825 17825번: 주사위 윷놀이 주사위 윷놀이는 다음과 같은 게임판에서 하는 게임이다. 처음에는 시작 칸에 말 4개가 있다. 말은 게임판에 그려진 화살표의 방향대로만 이동할 수 있다. 말이 파란색 칸에서 이동을 시작하면 www.acmicpc.net 빡센 완탐문제(짱 어렵당), 완벽히 풀 수 있을 때까지 반복해볼 것 #include using namespace std; typedef long long ll; const int dx[] = {-1, 0, 1, 0}; const int dy[] = {0, 1, 0, -1}; int t, n, m, k, sx, sy, ex, ey, x, y, answer, root; // a : 주사위 입력값, m..
-
[백준/BOJ] 1189번 컴백홈알고리즘 문제풀이/백준 2022. 4. 30. 01:11
https://www.acmicpc.net/problem/1189 1189번: 컴백홈 첫 줄에 정수 R(1 ≤ R ≤ 5), C(1 ≤ C ≤ 5), K(1 ≤ K ≤ R×C)가 공백으로 구분되어 주어진다. 두 번째부터 R+1번째 줄까지는 R×C 맵의 정보를 나타내는 '.'과 'T'로 구성된 길이가 C인 문자열이 주어진다 www.acmicpc.net 백트래킹을 이용하여 경로의 모든 경우의 수를 구한 후, 거리가 K인 개수를 구하는 문제이다. (DFS 구현시, 반환값이 있는 형태로 만드는 연습이 필요한 것 같다.) #include using namespace std; typedef long long ll; const int dx[] = {-1, 0, 1, 0}; const int dy[] = {0, 1, ..
-
[백준/BOJ] 1068번 트리알고리즘 문제풀이/백준 2022. 4. 25. 23:13
https://www.acmicpc.net/problem/1068 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 인접 리스트를 이용해 트리를 구현한 후, DFS 탐색을 하면서 리프노드에 도달하면 1을 리턴하고, 리프 노드의 수를 각 노드를 거쳐 루트까지 누적해가면 된다. 이때, 루트 노드를 제거하는 경우를 예외처리 해줘야 한다.
-
[백준/BOJ] 2636번 치즈알고리즘 문제풀이/백준 2022. 4. 24. 18:00
https://www.acmicpc.net/problem/2636 2636번: 치즈 아래 과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(에서 네모 칸에 X친 부분)에는 치즈가 놓 www.acmicpc.net (0,0)부터 차례대로 BFS 탐색을 한다. 탐색 도중 값이 1인 지역을 만난다면, 해당 지역은 가장 바깥부분을 의미한다. 따라서 해당 지역을 0으로 바꿔주고, 큐에는 넣지 않는다. 이렇게 하면 BFS 탐색을 할 때마다, 치즈 안쪽의 구멍을 신경쓰지 않아도 공기에 노출된 겉표면만을 제거할 수 있다. #include using namespace std; typedef long long ll; const int dx[]..
-
[백준/BOJ] 1051번 숫자 정사각형 (C++)알고리즘 문제풀이/백준 2021. 11. 16. 17:34
https://www.acmicpc.net/problem/1051 1051번: 숫자 정사각형 N×M크기의 직사각형이 있다. 각 칸에는 한 자리 숫자가 적혀 있다. 이 직사각형에서 꼭짓점에 쓰여 있는 수가 모두 같은 가장 큰 정사각형을 찾는 프로그램을 작성하시오. 이때, 정사각형은 행 www.acmicpc.net 문제의 이해가 좀 어려웠는데, 난이도는 쉬운 문제였다. 꼭지점의 값이 모두 같은 가장 큰 정사각형의 넓이를 찾는 완전 탐색(브루트 포스) 문제였다. #include #include using namespace std; int map[51][51]; int main(void) { freopen("input.txt", "rt", stdin); ios_base::sync_with_stdio(false)..