농부공학자

https://programmers.co.kr/learn/courses/30/lessons/43165 코딩테스트 연습 - 타겟 넘버 n개의 음이 아닌 정수들이 있습니다. 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 programmers.co.kr 깊이/너비 우선 탐색 유형에 있는 문제이다. 문제를 보면 4 1 2 1 에서 +4,-4, +1-1, +2-2, +1-1을 모두 탐색해야 하므로 완전 탐색으로 살펴봐야 한다는 것은 알겠다. 여기서 조합을 어떻게 해야하냐가 문제인데 이렇게 풀었다...... 코드 class Solution { public static int answer = 0..

https://www.acmicpc.net/problem/1010 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다. www.acmicpc.net 다리 안겹치게 짓는거... N 0) return dp[m][n]; // 재활용 if(m == n || n == 0) return dp[m][n] = 1; return dp[m][n] = bridge(m - 1, n - 1) + bridge(m - 1, n); // n+1 C r+1 = n C r + n C r+1 } } https://st-lab.tistory.com/194 : 설명 잘된 블로그

https://www.acmicpc.net/problem/2644 2644번: 촌수계산 사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어 www.acmicpc.net BFS씀 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokeniz..

https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net BFS로 풀었다. 코드 package Baek; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenizer; public class Baek11725 {..

https://www.acmicpc.net/problem/7562 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net BFS로 풀었다. 걍 전형적인.. 문제이다.... dx[], dy[]의 범위에만 신경써주면 됨 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue; import java.util.Strin..

https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net BFS로 풀어야하는 문제이다. 풀이 방법은 문제에 나온 순서만 살펴보면 위 그림처럼 나올 것이다. next == K 인지 확인하고 맞다면 check[temp] 를 출력하면 된다. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java...

https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 얘도 토마토네? 백준 7576번이랑 배열만 다른 문제이다.. https://ticssfm.tistory.com/80?category=970752 [BaekJoon] 백준 7576번 _ 토마토 for JAVA _ BFS 알고리즘 https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. ..

https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net BFS로 풀었다. 중요한 점은... 1에서 0으로 옮겨가서 숫자를 바꾸는 식으로 짰는데 1이 여러개 있을 수 있으므로 BFS() 함수를 돌릴 때 x,y 좌표를 Queue에 넣으면 계산이 한번에 되어버린다. 뭔말이냐면 이렇게 (0, 0)에서 0(안익은) 을 쭉 훑어서 4까지 가버린다. 그래서 이미 map[][] 배열을 쭉 훑어서 1인 x,y 좌표를 queue에 넣어놓고 함수를 실행시..

https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net BFS 연습하려고 들어갔다. 정답률이 50프로가 넘길래 만만하게 보고 들어갔는데 1도 모르겠어서~ 다른분꺼 참고함 (https://yongku.tistory.com/entry/%EB%B0%B1%EC%A4%80-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%B0%B1%EC%A4%80-14502%EB%B2%88-%EC%97%B0%EA%B5%AC%EC%86%8C-%EC%9E%90%EB%B..

https://www.acmicpc.net/problem/2583 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net DFS로 풀었음 탐색 문제는 다 비슷비슷 한 것 같다. 보자마자 DFS 아니면 BFS를 써야겠다 싶은.... 쉬운 문제만 푸는건가? 뭐 암튼.. 여기서 주의할점은.... 문제에 그려진 배열로 생각하면 안된다는거랑... 입력에 주어지는 숫자대로 배열을 만들면 안된다는...것이다. 우선 문제에 그림이 이렇게 그려져있는데 우리는 배열을 만들 때 (0,0)이 왼쪽 위에 가게 하므로 이..