알고리즘35 백준 9376 탈옥 https://www.acmicpc.net/problem/9376 9376번: 탈옥 문제 상근이는 감옥에서 죄수 두 명을 탈옥시켜야 한다. 이 감옥은 1층짜리 건물이고, 상근이는 방금 평면도를 얻었다. 평면도에는 모든 벽과 문이 나타나있고, 탈옥시켜야 하는 죄수의 위치도 � www.acmicpc.net 이 문제는 공부 삼아 블로그를 참고해서 풀었다 (https://stack07142.tistory.com/145 님 블로그) 정말 혼자서는 생각도 못 해낼 방법인 듯... 많이 배웠다! 기본 기본적으로 이 문제에서 가중치는 연 문의 개수이다 (Pos 객체의 door변수로 체크) visit 배열을 방문/미방문이 아니라 몇 개의 문을 열어 해당 지점에 도착했는지를 기록한다 더 적은 가중치(연 문의 수)로 해당 .. 2020. 5. 21. 백준 1062 가르침 알고리즘 k-5개만 고르면 된다 모든 단어가 "anta"로 시작하고 "tica"로 끝나므로 {'a', 'n', 't', 'i', 'c'}는 무조건 알고 있어야 한다 나머지 알파벳 중 k-5개를 마저 뽑아서 시뮬레이션(?)을 돌리면 된다 나는 무조건 알야야 하는 알파벳(origin)과 뽑을 알파벳(pick)으로 나눠서 체크해줬다 배운 것 1. List의 contains()메소드 리스트에 해당 요소가 있는지 알려준다 2. 문자열 처리 for(int i=0; i 2020. 5. 21. SWEA 2112 보호필름 백트래킹 가지치기를 잘 해야 시간초과가 나지 않는다 한 열이 실패하면 그 경우는 무조건 실패다 → return false 한 열에서 k개 이상이 되면 그 열은 성공이다 → continue loop 해서 다음 열 탐색으로 넘어가자 0개부터 개수를 늘려가며 투여하므로 앞에서 답이 나왔다면 (ans≠-1) break하고 출력한다 알고리즘 1. 어떤 행에 약품을 투여할지 조합으로 정한다 (0개 ~h-1개) - h-1개까지 해서 안 되면 h개 투여해야하는 거니까 예외처리로 출력해준다 - 새로운 dfs마다 memcpy를 해준다 2. 0개부터 개수를 늘려가며 투여하므로 앞에서 답이 나왔다면 (ans≠-1) break하고 출력한다 3. 조합을 돌리면서 재귀 전 insert, 재귀 후 delete로 약품 투여를 처리해준.. 2020. 5. 20. Kruskal Kruskal MST를 만드는 알고리즘 중 하나이다 간선이 많을 때 사용하면 Prim 알고리즘보다 성능이 좋다 수도 코드 1.Edge 클래스 생성 & edgeList 생성 2.union-find 메서드들 생성 findSet, isSameParent, union 3.makeSet 4.간선의 가중치 기준 오름차순 정렬 5.모든 간선을 탐색하며 다른 집합에 속하면 sum갱신 & union 자바로 구현한 Kruskal public class Kruskal { static class Edge implements Comparable{ int a, b, cost; public Edge(int a, int b, int cost) { super(); this.a = a; this.b = b; this.cost = cos.. 2020. 5. 19. 이전 1 2 3 4 5 ··· 9 다음