본문 바로가기

99클럽29

[Day10]JAVA- 백준 특정 거리의 도시 찾기 (18352번) https://www.acmicpc.net/problem/18352  백준 18352번 문제를 풀기위해서는 BFS 에 대해서 알아야 한다. BFS 에 대해서 잘 알고 있으면 어려운 문제는 아니지만 , 함정이 있다! 문제를 꼼꼼히 읽어야 한다.BFS,DFS 문제를 많이 풀다보면은 어느정도 문제를 읽다보면 어떠한 알고리즘을 사용해야겠다 감이 잡힌다. 그래서 대강 문제를 읽보 바로 풀어버리는 실수를 하게 되는것이다. 이 문제에서 포인트는 단방향의 도로인것과 , 도시의 번호를 오름차순으로 출력하는 것이다.보통을 노드 사이는 양방향인 경우가 많아 아래와 같이 선언해 주는 경우가 많다. graph.get(u).add(v);grpah.get(v).add(u); 단방향은 한방향으로만 선언해 줘야 한다!graph.get.. 2024. 11. 6.
[Day09]JAVA- 백준 나이트의 이동 (7562번) https://www.acmicpc.net/problem/7562  백준 7562번 문제를 풀기위해서는 BFS 를 활용해야한다.  사실 DFS는 문제를 풀기위한 수식의 일뿐 문제를 이해하고 어떤 방식으로 체크판에 나이트가 움직이는 지를 파악하는게 중요하다. 체스판에서 나이트가 움직일 수 있는 경우는 총 8가지 이다.  체크판을 벗어나지 않으면서 이동 할 수 있는 모든 경우를 구하여 그 중 나이트가 이동하고자 하는 판 까지의 이동만 계산하면 된다.   행 , 열 을 구분하여 이동할 수 있도록 배열에 8가지 경우를 담은 배열을 생성한다. static int x[] = {-2, -2, -1, 1, 2, 2, 1, -1};static int y[] = {-1, 1, 2, 2, 1, -1, -2, -2}; 이동한.. 2024. 11. 5.
[Day08]JAVA- 백준 촌수계산(DFS) https://www.acmicpc.net/problem/2644   촌수계산 문제를 풀기 위해서는 DFS , BFS 와 같은 탐색방법을 알고 있어야한다.  입력값 을 노드로 그려보면 아래와 같은 모양이다. 9 7 3 7 1 2 1 3 2 7 2 8 2 9 4 5 4 6  쉽게 말해 두 노드 사이의 간선의 개수 를 센다고 생각하면 쉽다.  * DFS(깊이 우선탐색) 활용 방식 기본적인 DFS 방식을 활용하면 되지만 주의해야할 점이 있다! 처음에는 result 배열에 각 시작 노드와의 간선의 개수를 저장하도록 했다.int count=1;public static void DFS(int y) { Stack stack = new Stack(); stack.push(y); .. 2024. 11. 4.
[Day07]JAVA- 프로그래머스 모음사전 https://school.programmers.co.kr/learn/courses/30/lessons/84512 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr프로그래머스 모음사전 문제를 풀기 위해서는 완전탐색에 대해서 알아야 한다.  완전탐색이란모든 경우의 수를 시도하는 방법으로 입력 값의 범위가 작은 경우에 주로 사용된다.  더보기* 완전탐색 알고리즘 - 단순 Brute-Force  : 단순히 반복문과 조건문으로 모든 경우를 만들어 답을 구하는 방법 - 비트 마스트(Bitmask) : 나올 수 있는 모든 경우의 수가 각각의 원소가 포함되거나 , 포함되지 않은 두 가지 선택으로 구성되는 경우 - 재귀.. 2024. 11. 4.
[Day06]JAVA- 백준 2805번 나무자르기 https://www.acmicpc.net/problem/2805 백준 2805번을 풀기 위해서는 이분탐색을 활용해야한다.  문제는 이분탐색 유형 중 간단한 편인다. 절단기의 최대 높이를 구하면 되는 것이다.  - N : 나무의 수 - M :  집에 가져가고자 하는 나무의 길- mid : 절단기의 높이 나무들의 높이는  입력 받은 나무의 수(N) 으로 배열을 생성해준다 .int[] tree = new int[N]; 범위를 지정할때 left : 0 , right 는 입력받은 나무의 최대 높이로 지정해 주면 된다. for(int i=0;i 원하는 나무의 길이만큼 딱 맞아 떨어지는 경우도 있지만 아닌 경우도 생각해서 자른 나무의 길이의 합은 M 보다 크거나 같아야 한다.  - tot : 잘린 나무들의 길이 합.. 2024. 11. 2.

티스토리툴바