반갑습니다!

1915번: 가장 큰 정사각형 boj.kr 풀이 이 문제는 동적 계획법을 사용해야한다. 이 문제의 핵심 아이디어는 위에서부터 탐색하면서 최대 크기의 정사각형을 갱신하는 것이다. 즉 dp[i][j] = (j, i)에서의 최대 정사각형의 길이가 된다. (수학에서 사용하는 좌표계를 기준으로 x, y 순으로 좌표를 표현했음을 참고할 것) 배열을 board[][]라고 하겠다. 그러면 board[i][j]가 1인 곳은 변의 길이가 1인 정사각형이다. 변의 길이가 2인 정사각형은 board[i][j], board[i-1][j], board[i][j-1], board[i-1][j-1]이 모두 1이어야 한다. 이 문제의 풀이는 여기서 힌트를 얻을 수 있다. 아래의 예시를 보면서 좀 더 알아보자. (0, 0 ~ 3, 0)..

17472번: 다리 만들기 2 boj.kr 풀이 [프로그래머스] 지형 이동과 유사한 문제인데 개인적으로 조금 더 까다로웠다. 상당히 구현할 것이 많은 문제이다. 해당 문제는 완전탐색으로도 해결할 수 있다고 한다. 아래의 코드는 MST를 사용해서 해결하였다. 이 문제에서 MST를 만들어서 문제를 해결하려면 크게 3단계로 나누어서 풀어야한다. 섬들 라벨링 하기 섬들 간의 거리 구하기 MST 생성하기 우선 섬 라벨링은 BFS 알고리즘을 통해 할 수 있었다. visited[][] 배열을 선언해 중복 방문을 막아주었다. // 섬들을 구분하기 위해 bfs 알고리즘 사용 void bfs(int x, int y, int idx) { queue q; q.push({ x, y }); visited[y][x] = idx; ..

6497번: 전력난 boj.kr 풀이 MST로 풀 수 있는 문제이다. 문제는 도시에서 절약할 수 있는 최대 액수를 구하는 것이고 이는 최소 액수로 가로등을 키는 문제라고 생각할 수 있다. 따라서 kruskal 알고리즘을 통해 가로등을 키는데 필요한 비용을 계산하고, 전체 비용에서 빼주면 된다. 코드 C++ Python3

4386번: 별자리 만들기 boj.kr 풀이 MST 알고리즘 기초 문제이다. 입력 값으로 주어지는 간선이 없기 때문에 별들 사이의 모든 간선을 구한 뒤 kruskal 알고리즘을 사용해 MST를 생성해주고 소수 둘 째 자리에서 반올림해주면 어렵지 않게 해결할 수 있다. 코드 C++

14921번: 용액 합성하기 boj.kr 풀이 투 포인터 알고리즘을 사용해서 해결했다. 기존의 방식과 조금 변형해서 사용했는데, 시작 인덱스를 0, 끝 인덱스를 n-1로 두었다. 그리고 두 인덱스가 가리키는 용액을 섞어서 0에 가장 가까운 조합을 찾아주었다. 이 때 0에 가장 가깝다는 것은 절대값이 가장 작다는 의미이므로 절댓값 함수 abs()를 사용했다. 코드 C++