본문 바로가기

코딩일기/알고리즘75

[백준 14502번 : 골드 5] 연구소 (BFS,DFS,완전 탐색 / Java) 이번 문제는 솔직히 조금 어려웠다. 일단 벽을 언제 어떻게 설치해야되는지 감이 잡히질 않아 답을 보게 되었다. 문제를 살펴보자. 문제 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크기가 N×M인 직사각형으로 나타낼 수 있으며, 직사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다. 일부 칸은 바이러스가 존재하며, 이 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다. 새로 세울 수 있는 벽의 개수는 3개이며, 꼭 3개를 세워야 한다. 예를 들어, 아래와 같이 연구소가 생긴 경우를 살펴보자.. 2021. 8. 5.
[백준 1789 : 실버5] 수들의 합 ( 그리디 / Java ) 이번 문제는 내가 문제 이해를 잘 못해서 답을 풀지 못해 답을 보고 이해하고 나니 매우 쉬운 문제였다. 문제를 살펴보자. 문제 서로 다른 N개의 자연수의 합이 S라고 한다. S를 알 때, 자연수 N의 최댓값은 얼마일까? 입력 첫째 줄에 자연수 S(1 ≤ S ≤ 4,294,967,295)가 주어진다. 출력 첫째 줄에 자연수 N의 최댓값을 출력한다. 문제 접근 방법 N개의 자연수의 합 S를 만들기 위해 필요한 N의 최대값을 구해라 이게 무슨 소리냐면 S가 55라고 치면 55가 나올수 있는 방법은 1+54이 될수 있고 1+2+53 이 될수 있다. 하지만 이렇게 되면 N의 값은 2또는 3이 된다. 따라서 최대값이 될수 없다. 그래서 우리가 N의 최대값을 구하려면 최대한 많은 수를 더해야 한다. 최대한 많은 수를.. 2021. 8. 5.
[백준 1932번 : 실버1] 정수 삼각형 ( DP / Java ) 이번 문제는 DP 문제에서 약간의 응용이 섞인것 같았다. 하지만 기본적인 DP를 알고 있다면 충분히 풀수 있는 문제 같다. 문제를 살펴보자. 문제 위 그림은 크기가 5인 정수 삼각형의 한 모습이다. 맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다. 삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는 모두 정수이며, 범위는 0 이상 9999 이하이다. 입력 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 .. 2021. 8. 5.
[백준 11724번 : 실버2] 연결 요소의 개수 ( DFS / Java) 이번 문제는 기본적인 DFS 문제였다. 문제를 살펴보자. 문제 방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다. 출력 첫째 줄에 연결 요소의 개수를 출력한다. 문제 접근 방법 이번 문제는 연결되어 있는 리스트의 개수를 구하는것이여서 DFS를 통해 연결되어 있는것들만 접근을 했다. DFS가 뭔지 모르겠다면 아래 링크를 통해서 보고오면 이해가 빠를것이다. https://wpione.. 2021. 8. 5.

티스토리툴바