전체 글53 [SEWA 1249번 보급로] 오늘의 문제는 보급로이다. 처음엔 무조건 완전탐색! 이 문제를 보고 BFS를 사용해야겠다는 생각을 했다.하지만 단지 방문처리조건 하나만으로 목적지 도착시 값이 최소로 걸린 시간이라 보장할 수 있을까?결론은 아니다. 문제에 제시된 예시만 확인해도 아닌 경우가 많다는 것을 알 수 있다. 그렇다면 어떤 방법을 통해서 이를 해결할 수 있을까? 나는 좌표마다 방문처리와 현재까지의 최소 시간을 저장해 비교하는 방법으로 해결했다. 코드는 다음과 같다.( 코드가 너무 커보인다면 "Ctrl + 스크롤 내리기" 하면 잘보여요 ! )( 초기화는 "Ctrl + 0" / 다시 확대는 "Ctrl + 스크롤 올리기" )import java.util.*;import java.io.*;public class Solution { .. 2024. 7. 10. [백준 12865번 평범한 배낭] 오늘의 문제는 평범한 배낭이다. 처음엔 무조건 완전탐색! 첫 접근은 재귀함수를 해당 물품을 챙겼을 때, 물품의 수와 버틸 수 있는 무게를 확인하고챙기고 or 챙기지 않고 진행하는 방법으로 구현하였다. ( 코드가 너무 커 보인다면 "Ctrl + 스크롤 내리기" 하면 잘 보여요! )( 초기화는 "Ctrl + 0" / 다시 확대는 "Ctrl + 스크롤 올리기" )import java.util.*;import java.io.*;public class Main { static int N, K, info[][], max; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedRe.. 2024. 7. 2. [백준 13265번 색칠하기] 오늘의 문제는 "색칠하기"이다. 처음엔 무조건 완전탐색! 2가지 색으로 색칠이 가능한지 확인하는 문제이고, 입력이 두 동그라미(노드)를 연결하는 내용이라 생각하였다 !각 동그라미(노드)들을 연결시켜놓고 상태(색)을 저장해주는 식으로 구현한다면 문제를 풀 수 있을것이라 생각했다.동그라미의 개수 n의 범위와 직선의 개수 m의 범위를 확인했을 때, 시간초과를 고려하지 않아도 될 것 같았다. 그래서 작성하기 시작한 코드는 아래와 같다 !( 코드가 너무 커보인다면 "Ctrl + 스크롤 내리기" 하면 잘보여요 ! )( 초기화는 "Ctrl + 0" / 다시 확대는 "Ctrl + 스크롤 올리기" )import java.util.*;import java.io.*;public class Main { static A.. 2024. 6. 1. [백준 5582번 공통 부분 문자열] 오늘의 문제는 "공통부분 문자열"이다. 처음엔 무조건 완전탐색! 각 문자열에 다중 for 문을 적용하여 선택되는 문자열들이 같은지 비교하며 그 수를 세준다.하지만 한 문자열은 최대 4000자까지 가능하고 두 문자열 모두, 모든 길이의 부분 문자열을 구한다면 시간초과를 피할 수 없다. 그리하여 생각한 첫 방법은..!A문자열만 모든 부분 문자열을 확인하며 B문자열에 포함되는지 확인한다면..?import java.util.*;import java.io.*;public class Main { public static void main (String [] args) throws IOException { BufferedReader br = new BufferedReader(new Input.. 2024. 5. 31. 2178 미로탐색 돌아온 알고리즘 ! 오늘의 문제는 미로탐색이다. 문제에 나와있듯 (1, 1)에서 출발하여 (N, M)의 위치에 도착했을 때까지 ! 지나야 하는 " 최소 칸의 수 " 를 구하는 문제이다.DFS를 통해서 모든 경우를 구하고 (N, M)까지 도달하는데 지난 수들을 비교해주는 방법도 답은 나오겠지만 최소 칸의 수를 구하는데는 BFS 가 더 효과적일 것이라 생각하고 BFS로 풀었다 ! 코드는 다음과 같다. 눈여겨 볼것 " 왜 2차배열의 크기를 [N][M]이 아닌 [N+2][M+2]로 했는가 ! "import java.util.*;import java.io.*;public class Main{ static int N, M, map[][], ans; // 행의 수, 열의 수, 입력받는 수들을 넣어줄 2차원 배.. 2023. 10. 28. 11725 트리의 부모찾기 처음 봤을 때의 느낌 : 어.... 어라..?새로운 문제를 접하고 어떻게 공략할지 생각하는게 너무 오랜만이라 그런지 처음엔 뇌정지가 왔다..ㅎ하지만 다시 멘탈을 잡고 차근차근 읽으며 어느 타이밍에 부모노드를 식별해야하는지 생각해냈다.아직 bfs의 흐름에 대해서 아주 자연스러울 정도로 친해지진 못했다는 생각을 했다...더 많은 문제를 풀어봐야겠다는 생각을 하며 ..!!! 코드는 다음과 같다.import java.util.*;import java.io.*;public class Main { static boolean visited[]; //방문처리를 해줄 visited배열 ! static int N, ans[]; //노드의 갯수, 정답을 적을 배열 ! static List list[]; public.. 2023. 10. 21. 2606 바이러스 저번 문제는 DFS와 BFS 였다 ! 그 이후로 풀어본 문제는 바이러스 !이 문제는 저번 문제를 제대로 풀었다면 사실상 같은 수준이기 때문에 쉽게 풀 수 있다. 문제는 위와 같다.여러 덩어리(?).. 묶음의 컴퓨터들이 있고 1번 컴퓨터가 감염됬을 때, 관련 묶음 컴퓨터가 모두 감염되면 몇 개의 컴퓨터가 감염됬는지 구하는 문제이다 ! 내 기준 이 문제의 함정은...! 바로1번 컴퓨터 이후로 감염되는 컴퓨터의 수를 구하는 것이므로 1번 컴퓨터는 세지않는것 ..! 코드는 다음과 같다.import java.util.*;import java.io.*;public class Main { static int N, M, cnt; // 컴퓨터의 수, 간선( 연결을 표시하는 선 )의 수, 감염된 컴퓨터를 세줄 cnt이다.. 2023. 10. 21. 1260 DFS와 BFS 한동안 쉬었던 알고리즘을 다시 시작했다...한 때에는 익숙했던 것들이지만 몇개월만에 DFS/BFS 조차도 헷갈리는 상태였다.DFS와 BFS의 기본을 찾기위해서 ..! 선택한 문제이다 ㅎ import java.util.*;import java.io.*;public class Main { static boolean visited[]; // 해당 숫자에 다녀갔는지 확인하는 boolean 배열 ! static List [] list; public static void main (String [] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer s.. 2023. 10. 21. 1676 팩토리얼 0의 개수 숫자를 처음부터 주어진 최대값인 500까지 모두 곱해서는 절대 이 문제를 풀지 못한다 ㅎ그래서 어떻게 해야 이 문제를 풀 수 있을까를 고민하던 찰나 0의 개수는 결국 2와 5가 필요한 10이 몇개 만들어지냐 라는 점을 발견 ! 그럼 0부터 N까지 중에 2와 5가 쌍으로 몇개나 있는지 확인을 해보았다.import java.io.*;public class Main { public static void main (String [] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); //N을 받아준다 int N = Integer.parseInt(br.readLine().. 2023. 6. 6. 이전 1 2 3 4 5 6 다음
