알고리즘 문제분석(35)
-
[백트래킹] 백준 18290 NM과 K(1)
https://www.acmicpc.net/problem/18290 18290번: NM과 K (1) 크기가 N×M인 격자판의 각 칸에 정수가 하나씩 들어있다. 이 격자판에서 칸 K개를 선택할 것이고, 선택한 칸에 들어있는 수를 모두 더한 값의 최댓값을 구하려고 한다. 단, 선택한 두 칸이 인접 www.acmicpc.net 수행시간 : 1시간 / 난이도 : 실버 1 DFS를 통한 재귀 + 재귀를 돌때마다 좌표를 통한 체크 이 2가지만 구현 할 수 있으면, 쉽게 풀리는 문제이다. 재귀를 도는 조건은 visited가 false 임과 동시에 선택한 칸들이 인접하면 안되므로 조합느낌으로 백트래킹을 구현하고, 백트래킹 내부 조건으로 인접했는지 아닌지를 판단해주면 되는 문제였다. #include #include us..
2021.06.24 -
[BFS] 백준 16928 뱀과 사다리 게임
https://www.acmicpc.net/problem/16928 16928번: 뱀과 사다리 게임 첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으 www.acmicpc.net 수행시간 : 45분 / 난이도 : 실버 1 전형적인 것 같으면서도 살짝 응용이 필요한 그래프 탐색문제. 내 로직은 다음과 같다. 1. visited배열의 차원수 결정 (지도가 1차원이다) 2. BFS 함수안에서 for문을 돌때 주사위 만큼 돌아야되므로 i를 6까지로 설정해주기 3. 뱀과 사다리의 좌표를 이용해서 BFS 구현하기 #include #inc..
2021.06.24 -
[구현&시뮬레이션] 백준 15686 치킨배달
https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 수행시간 : 1시간 40분 / 난이도 : 골드 5 처음 문제를 읽고, 어? 할만한데? 하다가 그대로 1시간이 지나가버린 문제였다... 일반 완탐 + 구현 형식이 아니다. 만약 하나를 골라서 탐색을 했는데 그 값이 다음 값보다 좋은 값이 아니라면? 다시 돌아가서 복구해주고 다음 것을 탐색하는, 즉 백트래킹 자료구조가 필요했다. 요즘은 로직을 짜는 것에 시간을 더 투자하려고하는데..
2021.06.24 -
[이분탐색] 백준 2805 나무자르기
https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 수행시간 : 약 50분 / 난이도 : 실버 3 이분탐색을 어떤식으로 응용할 수 있냐? 라는 질문에 가장 좋은 예로 들수 있는 문제라고 생각한다. 처참한 정답률은 이 문제의 난이도가 생각보다 어렵다는 것을 알 수 있게 해준다. 이 문제의 핵심 아이디어는 초기 MAX값을 나무길이의 가능한 MAX 값으로 설정, 초기 MIN 값을 1로 설정 후 이분 탐색을 통해 자..
2021.06.24 -
[투포인터] 백준 2470 두 용액
https://www.acmicpc.net/problem/2470 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net 수행시간 : 1시간 / 난이도 : 골드 5 처음 풀어보는 투포인터라는 자료구조 문제였다. 문제를 풀면서 느낀 투포인터는 start값과 end값을 조절하면서 값을 비교해주기에 start에 포인터하나 end에 포인터하나 즉 2개의 포인터를 통해서 값을 찾아나가는 알고리즘이었다. B-search와 비슷한 맥략을 가진 자료구조지만, 항상 벡터의 인덱스를 가지고 조절을 하..
2021.06.24 -
[BFS] 백준 2583 영역 구하기
www.acmicpc.net/problem/2583 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net 수행 시간 : 1시간 난이도에 비해 상당히 까다로웠던 문제. 우리가 아는 배열이나 벡터는 좌표가 아래로 뻗어나가는데 문제에서는 위로 뻗어나가고 그것도 모눈종이라서 좌표가 하나씩 밀리므로 새로운 temp 벡터를 선언하여 bfs를 돌린 값을 저장시키는 방식으로 구현하였다. #include #include #include #include using namespace std; int n, m, k;..
2021.04.05