알고리즘 문제풀이/백준
-
[백준/BOJ] N과 M (1), (2), (3), (4), (5), (6), (7), (8), (9), (10), (11)알고리즘 문제풀이/백준 2022. 9. 22. 21:50
N과 M (1) https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define lp1(i, x, n) for(int i = x; i
-
[백준/BOJ] 14620번 꽃길알고리즘 문제풀이/백준 2022. 6. 21. 00:35
https://www.acmicpc.net/problem/14620 14620번: 꽃길 2017년 4월 5일 식목일을 맞이한 진아는 나무를 심는 대신 하이테크관 앞 화단에 꽃을 심어 등교할 때 마다 꽃길을 걷고 싶었다. 진아가 가진 꽃의 씨앗은 꽃을 심고나면 정확히 1년후에 꽃이 피므 www.acmicpc.net 쉬운 DFS 문제였다. 씨앗을 3개 심을 수 있는 모든 경우의 수를 구한 후, 해당 케이스가 꽃이 피어날 수 있는지를 확인하면 된다. 배열을 여러 개 두면 쉽게 구현할 수 있다. (코드 참고) #include #define f first #define s second #define lp1(i, x, n) for(int i = x; i = answer) return false; } sum = tm..
-
[백준/BOJ] 9934번 완전 이진 트리알고리즘 문제풀이/백준 2022. 6. 9. 17:18
https://www.acmicpc.net/problem/9934 9934번: 완전 이진 트리 상근이는 슬로베니아의 도시 Donji Andrijevci를 여행하고 있다. 이 도시의 도로는 깊이가 K인 완전 이진 트리를 이루고 있다. 깊이가 K인 완전 이진 트리는 총 2K-1개의 노드로 이루어져 있다. (아래 www.acmicpc.net 중위 탐색의 결과를 완전 이진 트리로 바꿔야 하는 문제다. 특정 depth까지 left와 right을 설정해 루트 노드를 탐색하는 방법을 반복하면서 문제를 해결하는데, 이분 탐색을 재귀로 구현하는 것과 비슷하다. #include #define f first #define s second #define lp1(i, x, n) for(int i = x; i = n) retur..
-
[백준/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, ..