devlog

[프로그래머스] 수레 움직이기 C++

출처 : https://school.programmers.co.kr/learn/courses/30/lessons/250134 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr풀이 방법주의할 점 dfs 백트레킹백트레킹에서 전역 변수를 최대한 덜 사용하고 문제를 최대한 분리하기 위해 함수의 인자로 넘길 것 최대 크기가 4x4 밖에 안되므로 완전 탐색 + 백트레킹으로 생각해 볼 수 있다. 조건에 맞게 서로 교차되는 경우, 같은 곳에 이동하는 경우, 방문한 곳에 다시 방문하는 경우를 하나씩 잘 구별해 주면 된다. 또한 공이 도착하지 않은 경우에만 이동시켜주어야 한다. 이 부분에서 크게 실수를 했다.if (g_ma..

[백준] 히스토그램에서 가장 큰 직사각형 (c++) 분할 정복

출처 : https://www.acmicpc.net/problem/6549 풀이 방법대표적인 분할 정복의 문제이다.왼쪽에서 가장 큰 사각형, 오른쪽에서 가장 큰 사각형, 경계 지역 사각형을 포함하는 사각형 중 가장 큰 사각형을 찾으면 된다.  가장 중요한 부분은 경계 지역을 포함하는 사각형의 최대 크기이다.주의 히스토 그램이 위와 같을 때 파란색 부분과 검은색 부분도 while문을 사용해 다 계산을 해주어야 한다. 기저 조건으로 start == end, end - start == 1인 경우로 설정했다. 실수한 점 넓이는 long long을 사용했다. 하지만 밑변과, 높이는 int이였다.long long width = height * (end - start)위와 같이 식을 작성했는데 연산 순서가 int끼리..

[백준] 텀 프로젝트 (c++) dfs

출처 : https://www.acmicpc.net/problem/9466 풀이 방법 사이클을 찾는 문제이다.사이클을 찾기 위해서, group을 만들고 dfs로 탐색을 했다.group을 저장하기 위해 visited 배열을 사용했고, 해당 그룹에서의 사이클 원소 개수를 저장하기 위해 cnt_arr를 사용했다.만약 visited가 0이라면 자신이 그룹의 시작으로 설정하고 탐색을 한다. 그러다 다음 원소가 자신의 그룹가 같다면 사이클이 완성되었다는 뜻이고, 그룹 중에서 몇 번째로 방문한 원소인지를 통해 사이클의 원소 개수를 구할 수 있었다. 풀이 #include #include #include using namespace std;int t, n;int visited[100001];int cnt_arr[1000..