Meluu_의 코딩 공부 일지

🧫 문제 분석 ✔️ 출처인구 이동 골드4 📖 문제 랜덤 문제를 돌리다가 나왔다. 그래프 탐색 냄새가 솔솔 난다. BFS를 사용하면 될것 같다.  1. 한 나라의 좌우 상하로 인접한 다른 나라와의 인구차를 M명이라 했을 때 L 해야한다.2. 조건을 만족한 나라들과는 연합을 하여 국경선을 하루 연다. 3. 인구가 이동하며 각 나라의 인구수는 (연합 인구수 / 연합한 나라 개수) 가 되며 소수점은 버린다. 4. 이동후 연합 해지 및 모든 국경선을 닫는다.5. 인구 이동이 없을때까지 반복한다.6. 인구 이동이 며칠동안 발생했는지가 문제이다.  내가 생각한 방법1. 우선 연합가능한 나라들을 찾고, 그 나라에 연합 번호를 매기며 각 인구수를 더해놓는다. 2. 연합은 1개 이상 생길 수 있다. 3. 만약 1번 연..

🧫 문제 분석 ✔️ 출처숨바꼭질 1697번 - 백준 📖 문제🔅 문제 풀이수빈이의 위치 x동생의 위치 k수빈이는 -1, +1, *2 로 이동할 수 있고 이는 1초를 사용한다.graph를 조건에 만족하는 최대 크기로 만들어서 각 위치에 따른 초를 적을 것이다.처음 수빈이가 있는 장소는 1로 초기화한다. 너비우선탐색으로 하되 문제에서 주어진 위치에 대한 조건식을 걸어주고 (0 이동하려는 곳에 이전에 이동한 흔적이 있는지 확인하여 걸린시간이 덮어씌어지는 것을 방지한다.x-1, x+1, x*2 3번의 위치이동을 하고 graph 인덱스의 값에 현재 위치의 걸린시간 +1 초를 더해 이동한 흔적을 남긴다. 그리고 이동한 위치를 queue에 넣는다. 방문하지 않은 곳은 걸린시간이 0이다. 왜냐하면 graph를 만들..

백준 2667번 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 문제 풀이 미로 찾기와 매우 유사한 문제이다. 다른점은 단지라는 그래프의 개수와 각 단지의 집들 즉, 각 그래프의 노드들의 개수를 오름차순으로 출력하는 문제이다. 그저 그래프를 찾아내서 얼마만큼의 노드들이 연결되어 있는지만 확인하기에 BFS, DFS 둘다 사용이 가능하다. 여기서는 BFS를 사용하였다. import java.io.*; import java.util.*; public class Main { static int[][] graph; st..

백준 2606번 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하인 양의 정수이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍 www.acmicpc.net 문제 풀이 그래프에서 1번 컴퓨터(노드)를 시작점으로 연결되어있는 컴퓨터들은 모두 바이러스에 감염된 것이기에 BFS , DFS 둘다 사용하여 풀 수 있다. 이번에는 DFS를 사용하여 풀었다. 재귀호출 , Stack 두 가지 경우를 둘다 사용해보았다. import java.io.*; import java.util.*; public class Main { static int[][] graph; static boolean[] visited; static i..

백준 2178번 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 문제 풀이 BFS를 사용하여 풀었다. 시작점이 (0,0)으로 고정되어있고 각 칸과 칸 사이의 거리는 동일하고 이동할 수 있는 칸들은 서로 연결되어 있기 때문에 결국에는 미로를 그래프로써 본다면 (N,M)까지 가는 거리는 그 높이만큼이 거리라고 볼 수 있다. import java.io.*; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; import java.util.StringToken..

백준 1260번 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 문제 풀이 DFS와 BFS의 기본적인 문제 보통 DFS는 스택이나 재귀호출 BFS는 큐를 사용한다. import java.io.*; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenizer; public class Main { public static Queue card; public static void main..

백준 2164번 2164번: 카드2 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 www.acmicpc.net 문제 풀이 카드 번호 1 2 3 ... N-2 N-1 N 특정 동작 카드가 한 장 남을때까지 반복 1) 제일 위 카드를 바닥에 드랍 2) TOP 카드를 BOTTOM 카드 밑으로 이동 각 동작 후 남은 카드 개수 확인 목표 : 제일 마지막에 남는 카드를 구하기 조건 (1

백준 11047번 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 문제 풀이 import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw..

백준 1065번 1065번: 한수 어떤 양의 정수 X의 각 자리가 등차수열을 이룬다면, 그 수를 한수라고 한다. 등차수열은 연속된 두 개의 수의 차이가 일정한 수열을 말한다. N이 주어졌을 때, 1보다 크거나 같고, N보다 작거나 www.acmicpc.net 문제 풀이 import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new OutputStream..

백준 11726번 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 문제 풀이 import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(Sys..