Algorithm/BOJ 썸네일형 리스트형 <BOJ> 1717 자바 (집합의표현) + 유니온파인드 https://www.acmicpc.net/problem/1717 import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer;//https://www.acmicpc.net/problem/1717public class 유니온파인드1_집합의표현 { static int[] parent; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); .. 더보기 <BOJ> 1753자바 (최단경로) https://www.acmicpc.net/problem/1753 풀이 코드import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.PriorityQueue;import java.util.StringTokenizer;//https://www.acmicpc.net/problem/1753public class Main { private static int E; private static int V; private static int K; private static ArrayList[] AL; private static int[].. 더보기 <BOJ> 11779 자바 (최소비용 구하기2) https://www.acmicpc.net/problem/11779 23% 시간초과로 어리둥절했던 문제이다.분명 다익스트라로 잘 구현했는데 시간초과가 발생했다. 문제는 아래 핵심이라고 주석메모를 해놓은 부분이다. 다익스트라를 구현 할 때 가중치가 작은 순으로 PQ에 담기는데,큐에서 꺼낸 노드의 누적 비용(cur.w)이 해당 노드의 dist[cur.v]와 다를 수 있는 경우가 발생한다는 것이다.언제? 간선의 수(m)가 많아질수록, 즉 복잡한 그래프일수록 발생할 가능성이 높아진다. 간선의 수가 적을 때만 테스트 해보니 간과했던 부분이었다. 더보기왜 이런 상황이 발생하는지 설명하겠습니다:PriorityQueue 특성: 다익스트라 알고리즘에서 우선순위 큐는 가장 짧은 거리를 가진 노드를 먼저 꺼냅니다. 하지만 .. 더보기 <BOJ> 21608 자바 (상어초등학교) https://www.acmicpc.net/problem/21608 PQ를 활용한 구현문제이다.1시간 정도 소요되었고 디버깅 한번으로 통과한 문제. import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.PriorityQueue;import java.util.StringTokenizer;public class b21608_상어초등학교 { private static class Student implements Comparable { int y; int x; int like; int blank; public Stude.. 더보기 <BOJ> 19238 자바 (스타트택시 1%, 6% 주의!) https://www.acmicpc.net/problem/19238 정확히 어떤 테스트케이스인지는 모르겠으나 1%와 6%에서 너무 괴롭혔다. 1. 문제 조건에 성립하기 위해선 direction 순서도 상/좌/우/하 로 설정해주는 것이 좋다.2. 맵을 그릴 때 0이 빈칸, 1이 벽으로 주어지기 때문에, 승객 및 도착지 번호는 2부터 시작하도록 한다.3. 승객을 찾는 findGuest() 에서 PQ를 사용하되, 주의할 점이 있다.(이부분에서 6%의 벽을 넘었다..)- while(큐가 빌때까지) 4방향을 돌면서 승객을 발견하는 경우는 PQ 모두 담은 뒤- PQ의 첫번째 요소를 리턴하는 방식으로 구현을 해준다.4. PQ에서 얻어낸 승객 정보를 바탕으로 도착지를 찾고, count를 해준다. 풀이코드import .. 더보기 <BOJ> 19236 자바 (청소년상어) 구현 + 백트래킹 문제인데 구현하느라 엄청 애를 먹었다.. 문제 풀이하면서 슈도코드 작성한 걸 보면1. 물고기 이동- 1~16순으로 이동 . 이동 가능: 빈칸 & 다른물고기 . 이동 불가능: 상어 & 경로밖 + 반시계 회전: 나머지 연산 이용 2. 상어이동 - 여러칸 이동가능, 따라서 반복문 안에서 최대 3번 DFS 3. 1,2 반복 후 max 출력 풀이코드import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer;public class Main { static int max = -1; static int[] dy = {-1, -.. 더보기 <BOJ> 1956 자바 (운동) 이번 문제는 플로이드-워셜 알고리즘에 대해 먼저 이해하고 풀어야한다! 플로이드-워셜(floyd-warshall)정의플로이드-워셜 알고리즘은 그래프에서 모든 쌍의 최단거리를 구하는 알고리즘입니다. 이 알고리즘은 동적 계획법을 사용하여 모든 노드 쌍 사이의 최단 경로를 효율적으로 찾을 수 있습니true-false.tistory.com DFS 풀이 코드(1% 시간초과)import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.StringTokenizer;public class 운동 { private static ArrayLi.. 더보기 <BOJ> 16946 자바 (벽부수고 이동하기4) 풀이 시간 - 1H 초과 풀이 과정 - 맵을 돌면서 벽이면 마주치면 BFS - visited 배열 초기화 - 다시 1번 과정 반복 1차 풀이 코드 (시간 초과)package algorithms.src.단기간성장;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.LinkedList;import java.util.Queue;import java.util.StringTokenizer;public class b16946_벽부수고이동하기4 { private static int N,M; private static int[][] map; private sta.. 더보기 이전 1 2 3 다음
