true-false

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)); ..

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[]..

https://www.acmicpc.net/problem/11779 23% 시간초과로 어리둥절했던 문제이다.분명 다익스트라로 잘 구현했는데 시간초과가 발생했다. 문제는 아래 핵심이라고 주석메모를 해놓은 부분이다. 다익스트라를 구현 할 때 가중치가 작은 순으로 PQ에 담기는데,큐에서 꺼낸 노드의 누적 비용(cur.w)이 해당 노드의 dist[cur.v]와 다를 수 있는 경우가 발생한다는 것이다.언제? 간선의 수(m)가 많아질수록, 즉 복잡한 그래프일수록 발생할 가능성이 높아진다. 간선의 수가 적을 때만 테스트 해보니 간과했던 부분이었다. 더보기왜 이런 상황이 발생하는지 설명하겠습니다:PriorityQueue 특성: 다익스트라 알고리즘에서 우선순위 큐는 가장 짧은 거리를 가진 노드를 먼저 꺼냅니다. 하지만 ..

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..

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 ..

구현 + 백트래킹 문제인데 구현하느라 엄청 애를 먹었다.. 문제 풀이하면서 슈도코드 작성한 걸 보면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, -..

이번 문제는 플로이드-워셜 알고리즘에 대해 먼저 이해하고 풀어야한다! 플로이드-워셜(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..

풀이 시간  - 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..

https://www.acmicpc.net/problem/1655  우선 문제를 풀기 전 최대힙과 최소힙 자료구조 개념을 알고 가면 좋을 문제이다.https://true-false.tistory.com/12  처음 문제를 봤을 땐 간단한 거 치고 티어가 낮지 않아서 조금 의아했다.그 마음으로 ArrayList를 작성해서 풀었는데 역시나 시간초과가 발생하더라..import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.Comparator;public class b1655_가운데를말해요 { public static void ..

https://www.acmicpc.net/problem/12865  문제 설명이 문제는 전형적인 배낭 문제(Knapsack Problem)로, 다이나믹 프로그래밍(DP)을 사용하여 해결할 수 있다.주어진 물품들을 배낭에 넣을 때, 배낭이 담을 수 있는 최대 무게를 초과하지 않으면서 물품들의 가치 합을 최대화하는 문제이다. 다이나믹 프로그래밍의 기본 개념다이나믹 프로그래밍은 복잡한 문제를 작은 부분 문제로 나누어 해결하는 방법이다.각 부분 문제는 한 번만 풀고, 그 결과를 재사용하여 전체 문제를 해결한다.이번 배낭 문제가 딱 이런류이다. 예로, 최대 적재량이 8kg인 배낭에 여러 물건들(weight[])을 담아 최대 가치를 구하고자 한다.각각 가치가 3, 4이고, 무게가 3, 4인 1, 2번 물건을 담은..