devlog

출처 : https://www.acmicpc.net/problem/1113 풀이 방법경계를 판단하기가 어려웠고 높이가 1~9이기 때문에 범위가 매우 작다는 점을 이용해서 가장 작은 높이에서 가장 큰 높이 직전까지 1씩 증가해 가면서 풀이하는 방법으로 풀이했다.(한 번에 계산은 안됨) 테두리일 경우, 넘쳐나게 되므로 테두리일 땐, 높이를 증가시키면 안 된다.이를 위해 visited 값을 2로 설정한 것은 높이를 증가시키지 않았다.또한 중복해서 더해지는 경우도 방지해야 하므로 한 번 높이를 증가시킨 경우 visited값을 +1을 해주어서 중복 계산을 방지해야 한다.import java.io.*;import java.util.*;public class Main { static int n, m; st..

출처 : https://www.acmicpc.net/problem/2098 풀이 방법외판원 문제를 비트마스킹과 DP를 활용해서 풀이하는 문제이다DP를 2차원 배열로 선언한 후 dp[y][x] = y를 현재 지점 x를 현재 지점을 포함한 방문한 노드의 인덱스를 비트로 변경했을 때 값으로 설정한다. ex 11001(2진수) -> 1, 4, 5번 방문 모든 지점을 방문했을 경우는 (1 011111 = 100000 - 1 (2진수)아래와 같은 코드를 통해 i번 인덱스를 방문했는지 판단한다.if((visited & (1 0) continue; 이후에는 일반적인 dp문제와 동일하게 풀이하면 된다. import java.io.*;import java.util.*;public class Main { stat..

출처 : https://www.acmicpc.net/problem/17182 풀이 방법순열 문제라는 것을 알 수 있다.n이 10까지 밖에 되지 않으므로 방문할 순서를 정하고 최소를 구하면 된다.단순히 순열만 사용해서 구해도 되지만 플로이드 워샬을 사용해 보고 싶어서 사용해 보았다.import java.io.*;import java.nio.Buffer;import java.util.*;public class Main { static int n,k, ans; static int[][] dist; static boolean[] visited; public static void main(String[] args) throws IOException { BufferedReader ..

출처 : https://www.acmicpc.net/problem/1765 풀이 방법유니온 파인드 문제이다우선 F인 친구가 나오게 된다면, union을 한다.반면 E가 나오게 된다면 enemy에 저장을 한 후, 모든 enemy를 돌며 enemy의 enemy를 union을 해주었다.이후 집합의 수를 Set을 활용하여 세었다.import java.util.*;import java.lang.*;import java.io.*;// The main method must be in a class named "Main".class Main { static int n, m; static int[] parents; static ArrayList[] enemy; static int find(int a..

출처 : https://school.programmers.co.kr/learn/courses/30/lessons/388354?language=java 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 풀이 방법처음에는 모든 노드를 루투로 설정하고 싹 다 계산하려고 했다.하지만 시간 복잡도가 10^6 * 10^6 으로 시간이 복잡도를 만족하지 못한다.이에 다른 사람들의 풀이를 참고했다.해당 문제의 특징을 파악하는 것이 매우 중요했다. 이 문제에서 가장 중요한 부분은 어떤 노드를 루트로 잡느냐였고, 해당 노드가 (루트 -> 루트 아님), (루트 아님 -> 루트) 일 때 이렇게 변경되는 노드만 (짝홀 트리, 역짝홀 트리..

코드출처 : https://www.acmicpc.net/problem/11967 풀이 방법불 켜진 방으로만 이동이 가능하다.불이 켜진 방으로 이동한 후, 켤 수 있는 불을 모두 킨다.불을 켤 때, 주변에 방문한 곳이 있다면 해당 방도 방문할 수 있기 때문에 queue에 넣어준다.또한 방에 방문했을 때, 주변에 방문을 하지 않았지만, 불이 켜진 방이 있다면 해당 방도 queue에 넣어준다. 코드import java.util.*;import java.lang.*;import java.io.*;public class Main { public static ArrayList[][] switches; public static boolean[][] visited; public static bo..

출처 : https://www.acmicpc.net/problem/18234 풀이 방법pi는 wi보다 항상 크다.라는 조건에 의해 그리디로 풀이할 수 있음을 파악했다.pi는 당근을 뽑지 않으면 계속해서 누적되다가 해당 당근을 뽑게 된다면 누적된 pi와 wi만큼 맛을 얻을 수 있다.이를 통해 T일 전까지 가장 큰 pi를 계속 누적을 하다 마지막에 뽑는 것이 가장 많은 맛을 얻을 수 있다는 것을 알 수 있다. 또한 pi는 wi보다 항상 크다라는 조건에 의해, 만약 T가 6이고 당근이 3종류라면 6, 5, 4일 차에만 당근을 뽑아 먹고, 1, 2, 3일 차에는 당근을 안 뽑아 먹는 것이 더 크다는 조건을 알 수 있다. (만약 뽑게 된다면, wi가 중간에 포함되어야 하기 때문에 안 뽑고 Pi만큼 얻는게 더 좋다..

출처 : https://www.acmicpc.net/problem/17398 풀이 방법풀이의 방법만 안다면 구현은 간단한 문제였다. 간선을 하나씩 끊어 가면서 이때 나누어진 두 집합의 노드의 수를 계산하는 문제이다.만약 간선을 끊을 때마다, 끊어진 두 노드에서 bfs 또는 dfs를 수행해서 각 집합의 노드의 수를 계산하게 된다면 시간 복잡도가 초과된다.그렇게 때문에 nlogn 이하의 시간 복잡도를 가지는 알고리즘을 생각해 내야 했다. 지금 까지 공부하며 시간 복잡도를 줄였던 방법에 대해 생각해 보았다. 1. 노드기준이 아닌 엣지 기준으로 생각해 보기2. 방향 간선에선 간선의 방향을 바꾸어 보기3. 순서를 역으로 생각해 보기 등등 생각이 났지만, 이 문제에 적용할 수 있는 방법은 역으로 생각하기였다. 1...

출처 : https://www.acmicpc.net/problem/7812 풀이 방법처음엔 문제의 케이스가 여러 번 주어진다는 것을 보지 못하고 O(n^2)으로 풀이할 수 있어서 풀이했지만, 케이스가 여러 개 주어지므로 시간 초과가 발생한다. 즉 O(n)만에 풀이를 해야한다. 항상 트리 문제를 풀이할 땐, 문제가 풀리지 않는다면 노드를 기준이 아닌 엣지를 기준으로 생각해 보아야 한다.A가 중앙일 때와 B가 중앙일 때를 비교해 보면 A와 B를 연결하는 엣지의 더해지는 횟수만 변경되고 나머지 엣지는 유지된다.이 점에 초점을 맞추어서 고민을 해보았다. 정답은 서브트리와 관련이 있었다.A에서 B로 이동할 때 A-B엣지가 더해지는 수는 (B 쪽 엣지를 끊고 난 후 A의 자식 수) - (A쪽 엣지를 끊고 난 후 B..

출처 : https://www.acmicpc.net/problem/12865 풀이 방법,이번 문제는 0-1 배낭 문제(0-1 Knapsack Problem)로, 1차원 DP를 활용하여 최적의 해결법을 찾는다.DP 배열을 사용하여 주어진 무게 제한 내에서 최대 가치를 찾는 방식으로 풀이하였다. 1. DP 배열 정의• dp[j] → 무게 j일 때 배낭에 담을 수 있는 최대 가치를 저장• 초기값은 0으로 설정2. 각 물건을 순회하며 DP 테이블 갱신• 현재 물건을 넣을 수 있는 최대 무게부터 역순으로 탐색 (이전 값이 유지되도록)• 현재 가방을 선택하는 경우 vs. 선택하지 않는 경우를 비교하여 dp 갱신 dp[j] = max(dp[j], dp[j - weight] + value) import java.io...