공부 기록용 블로그

배열로 입력받고, BFS로 탐색한다. 처음엔 어라,,어떻게 카운트하지? 싶었는데 그냥 방문하면서 배열에 더해가면 된다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 import java.awt.*; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; public class Main { static int N,M; s..

https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 이 문제는 뇌에 힘을 줘서 좌표 생각을 잘 해야 한다. 가로길이 M, 세로길이 N인데 for문을 돌리거나 Queue에 넣을 때 잘 넣어보자 좌표는 1. arr[x][y] 2. arr[y][x] 이걸 보고 참고하자. 나는 2번이 더 익숙해서 2번으로 풀었다. DFS로도 풀어보고, BFS로도 풀어봤다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24..

https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 일단 배열로 입력 받는다. 그리고 배열을 돌면서 visit배열을 확인하여 아직 방문하지 않았으면 방문해서, 인접해있는 배열들을 전부 방문하면서 연결된 집을 센다. 좌우,위아래 연결되어있는 집을 찾는거니까 각 연결된 집을 어떤식으로 찾을지 고민해야하는데 각각 (x,y)라고 하고 현재 위치가 (0,0)에 있다고 가정하면 (0,1) (-1,0) (0,0) (1,0) (0,-1) 왼쪽 오른쪽 위 아래 좌표..

https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net dfs랑 bfs 둘 다 풀어봤다. 시간을 줄이기 위해서 BufferedReader쓰고 StringTokenizer로 받아줬고, 방문체크 잘 해주고 답 출력할 때 자기 컴퓨터는 빼고 계산해야하니까 1 빼주면 된다! 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39..

https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 1. 배열을 이용해서 푼 DFS 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 import java.io.BufferedReader; import java...

DP문제..! 다이나믹 프로그래밍 문제인데, 큰 문제를 작은 문제로 나눌 수 있고, 부분 문제가 반복적으로 해결된다. DP를 구현하는 방법은 상향식과 하향식이 있는데, 상향식은 작은 문제를 하나씩 해결하면서 먼저 계산했던 문제를 이용해서 다음 문제도 해결하는 것이고, 하향식은 미리 한번에 계산해서 메모리에 저장해놓고, 같은 문제를 호출하면 바로 결과를 가져오는건데 이런걸 메모이제이션이라고 한다. 0일때는 0이 1, 1이 0 1일때는 0이 0, 1이 1 2일때는 0이 1, 1이 1 3일때는 0이 1, 1이 2 4일때는 0이 2, 1이 3 . . . 이런식으로 이어지는데, 잘 보면 여기에 규칙이 있다. 2이후부터는 각각 전과, 전전 값을 더하면 값이 나온다는 것이다. 그러니까 2일때 0은 0일때 0이 나온 ..

666이 연속으로 나오는 수를 찾으면 되는데, 가장 작은 수를 차례로 찾는거니까 숫자를 하나씩 증가시켜가면서 숫자 안에 연속된 666이 있는지 확인한다. 처음엔 한 자리씩 검사하면서 어떻게 연속된 666을 체크하지..? 싶었는데 그냥 한 자리씩 지워주면서 1000으로 나눴을 때 나머지가 666이면 연속된 666을 발견한거다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; public class Main { publ..

체스판의 크기가 8*8이고, 맨 윗칸이 첫번째가 흰색인 경우/맨 윗칸이 첫번째가 검은색인 경우로 나누어 생각했다. 일단 최악의 경우는 전부 바꾸게 되어 64가 될 것이고, find함수로 첫번째가 B가 될 경우와 W가 될 경우를 나누어서 생각해보았다. 그렇게 받은 N x M 체스판을 전부 검사해보면 끝~! 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamRead..

하나씩 입력받아서 이중for문을 돌리면서 키와 몸무게가 둘 다 비교 대상보다 크면 순위를 올리는 식으로 계산한다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; public class Main { public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(n..

브루트포스 문제니까, 일단 다 탐색해야하는구나~하고 접근 가장 작은 생성자를 찾는거니까 작은 수부터 계산해준다. 그리고 입력 방식을 다르게 두 번 풀어봤다. 1.Scanner 이용 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 import java.util.*; public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); int N = in.nextInt(); int result = 0; for(int i=1;i