알고리즘36 [Algorithm] Dijkstra 알고스팟 (백준), nextLine() 주의사항 - 에이젠 https://www.acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net 공략 다익스트라 알고리즘 문제 입니다. 정답률은 41퍼센트 정도로 어렵지 않게 풀 수 있는 문제입니다. 하지만 이전에 풀어본 다익스트라 문제와 다른 부분이 있기에 생각을 하게 만드는 문제였습니다. 그동안 노드들을 인접리스트를 사용해 쉽게 나타내었지만 이문제는 각각의 노드들이 2차원배열 요소이기 때문에 자료구조를 다르게 사용해야 합니다. 우선 Info class의 기존에 idx.. 2022. 8. 30. [Algorithm] Dijkstra 특정한 최단경로 (백준) - 에이젠 https://www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 공략 이전에 풀었던 최소비용 구하기 문제와 같은 다익스트라 알고리즘 문제 입니다. 공략법은 거의 같습니다만 추가로 생각해야할 부분이 서로 다른 두 개의 노드( V1 , V2) 를 무조건 통과해야한다는 조건이 생겼다는 것이죠. 예전에 BFS문제를 풀면서 각 두 경로의 길이를 비교해서 풀었던 기억이 있었기에 V1 -> V2과 V2 -> V1 각각의 경로 길.. 2022. 8. 26. [Algorithm] Dijkstra 파티(파티) - 에이젠 https://www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 처음 다익스트라 공략 방법을 그대로 사용. 다만 단방향의 Edge에서 왕복을 해야한다는 내용이 추가된 문제. 다익스트라 알고리즘을 두번 사용하여 왕복하는 시간을 알아내었음. import java.util.*; class Main { static Scanner sc = new Scanner(System.in); static class Edge { int to ; int.. 2022. 8. 24. [Algorithm] Dijkstra 최소비용 구하기 - 에이젠 https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 문제 N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 M개의 버스가 있다. 우리는 A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화 시키려고 한다. A번째 도시에서 B번째 도시까지 가는데 드는 최소비용을 출력하여라. 도시의 번호는 1부터 N까지이다. 입력 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄.. 2022. 8. 23. [Algorithm] 6월 27일 알고리즘 연습 -에이젠 Lv. 1 숫자 문자열과 영단어 - 성공 0를 빠뜨리는 실수. String.replace()를 적용한 문자열을 따로 할당을 안 하는 실수. class Solution { public int solution(String s) { int answer = 0; String arr = s; arr = arr.replace("one","1"); arr = arr.replace("two","2"); arr = arr.replace("three","3"); arr = arr.replace("four","4"); arr = arr.replace("five","5"); arr = arr.replace("six","6"); arr = arr.replace("seven", "7"); arr = arr.replace("eig.. 2022. 6. 27. [Algorithm] 6월 24일 알고리즘 연습 - 에이젠 내풀이(1) : 효율성테스트를 통과하지 못함. 수많은 사람들의 점수를 일일이 검사하면서 비효율 발생 -> 참고한 코드를 통해 이분탐색을 통해 해결하는 것을 확인. 듣기로 이문제가 LEVEL2중 상위권 문제라고 많이 언급하는 것 같다. 이 이상의 수준은 두개 이상의 알고리즘을 사용하는 경우가 많을 것같다. class Solution { public int[] solution(String[] info, String[] query) { int[] answer = {}; answer = new int[query.length]; ArrayList arr = new ArrayList(); //생성 for(String str : info){ String[] input = str.split(" "); //사람 생성 /.. 2022. 6. 24. [Algorithm] 6월23일 알고리즘 연습 - 에이젠 Lv. 2 단체사진 찍기 참고한 풀이 class Solution { private int answer = 0; private String[] friends = {"A", "C", "F", "J", "M", "N", "R", "T"}; public int solution(int n, String[] data) { boolean[] isVisited = new boolean[8]; dfs("", isVisited, data); System.out.println(answer); return answer; } private void dfs(String names, boolean[] isVisited, String[] datas) { if (names.length() == 7) { if (check(names, .. 2022. 6. 23. 이전 1 2 3 4 5 6 다음 728x90
