전체 글
백준 16953 - A -> B
[문제 바로가기] 1. 유형 BFS 2. 풀이 뒤에 1이 붙는 경우, 2를 곱하는 경우를 모두 탐색해 줍니다. 2차원 배열 BFS에서 4방향을 완전 탐색을 하는 경우와 비슷합니다. 여기서 주의할 점은 인풋값이 십억이므로, 뒤에 1을 붙이는 경우는 int타입을 초과할 가능성이 있습니다. 그래서 long타입을 사용합니다. 3. 코드 import java.io.*; import java.util.*; public class Main{ static int N, M; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); Strin..
백준 5883 - 아이폰 9S
[문제 바로가기] 1. 유형 구현 2. 풀이 N이 1000이어서, O(N^2)으로 충분히 풀이 가능. 예제1을 보면 지울 수 있는 숫자 후보는 2,3,5,7 입니다. 위 숫자를 지운 상태에서 N번 탐색하는 식으로 구해주면 됩니다. 중복 체크를 해주기 위해 HashSet에 입력값을 넣어요. 이전값과 비교해가면서 가장 긴 숫자를 찾아요. 3. 코드 import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader bf = new BufferedReader(new InputStreamReader(System.in)); StringTokeni..
백준 17393 - 다이나믹롤러
[문제 바로가기] 1. 유형 이분탐색 2. 풀이 3. 풀이 import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader bf = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(bf.readLine()); int N = Integer.valueOf(st.nextToken()); long arr[] = new long[N]; long arr2[] = new long[N]; st = new StringTokeniz..
백준 - 좋은 단어
1. 유형 스택 2. 풀이 간단한 스택문제입니다. 3. 코드 import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader bf = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(bf.readLine()); int N = stoi(st.nextToken()); int cnt= 0 ; while(N-->0) { st = new StringTokenizer(bf.readLine()); char[] c = st.ne..
백준 21608 - 상어 초등학교
[문제 바로가기] 1. 유형 구현 2. 문제 분석 21년 상반기 문제입니다. SDI를 지원했을 때 오전 타임 1번으로 나온 문제라서 반갑네요. 유형은 우선순위 큐를 사용해야 하고, 기준을 잘 설정해야 해요. 주변에 친구가 많은 칸을 선택, 주변에 빈칸이 많은곳선택 -> 행번호오름차순->열번호 오름차순 저 같은 경우엔 람다식+배열을 많이 써요. 코테 칠 때 클래스를 만들고 Comparable을 구현한 후 컬렉션에 넣으면 시간이 많이 소요됩니다. 나머지 조건 쉽습니다. 4방향을 탐색해주면서 주변에 친구가 있으면 카운트를 증가시켜요. 친구 여부는 Set으로 판단해줬습니다. 4방향 탐색하면서 빈칸이 있으면 빈칸 수 를 증가시켜주고 우선순위 큐에 삽입하면 됩니다. 설계 총 N^2을 탐색 -> 빈칸중에서 -> 친구..
프로그래머스 - 9주차 위클리 챌린지- 전력망을 둘로 나누기
[문제 바로가기] 1. 유형 트리, union-find 2. 풀이 2-1. 해설 처음 접근법은 2가지 묶음으로 나눠야 합니다. 그러기 위해서 저는 Union-find를 사용했습니다. 시뮬레이션을 돌려봅시다. 예제1번에서 처럼 4-7간선을 지워봅시다. 그리고 union-find를 돌리면, 아래 그림처럼 배열이 초기화 될거에요. 그럼 1의 개수와 7의 개수의 차이를 구하면 끝! 이것을 간선의 수 만큼 반복해서 최소값을 구해줍니다. 3. 코드 import java.util.*; class Solution { static int p[], MIN=987654321; public int solution(int n, int[][] wires) { int answer = -1; for(int i=0; i
백준 1780 - 종이의 개수
[문제 바로가기] 1. 유형 분할 정복 2. 접근법 2-1. 해설 분할 정복으로 푸는 문제 입니다. 전체 사각형을 기준으로 잡고, 세부 사각형이 모두 같은지 판단해 줍니다. [그림1]과 같은 사각형이 있다고 가정하겠습니다. 길이가 3일 때, 모두 같은지를 판단 합니다. 0과 1이 같이 있으니 분할 정복을 시도합니다. 위의 코드를 따르면 [그림2] 처럼 나올겁니다. 이제 위의 코드를 계속 반복하면 끝! 2-2. 설계 전체가 같은 값 일 수 있으니 체크 -> DFS(큰변, 작은변, 좌표)를 호출 -> 작은 사각형이 동일 한지 여부에 따라 종이의 수 증가. 3. 코드 import java.io.*; import java.util.*; public class Main { static int N, grid[][]..
백준 2665 - 미로만들기
[문제 바로가기] 1. 유형 BFS 2. 문제 풀이 2-1. 해설 BFS에서 파생된 문제 중 하나인 벽 뚫기 문제입니다. 만약 이 문제를 DFS 그냥 정말 탐색하게 된다면 시간 초과가 날 것입니다. 따라서 이 문제는 우선순위 큐를 사용한 BFS로 풀어야 합니다. 벽을 몇 번 뚫을지 딱 정해주지 않았습니다. 그래서 만나는 벽을 모두 큐에 넣어주면서 탐색해 줘야 합니다. 우선순위 큐의 정렬 기준은 적게 벽을 통과한 횟수입니다. 벽을 뚫지 않은 길을 먼저 탐색하는 거죠. 마지막 좌표에 도달했으면 벽을 파괴한 횟수 출력. 끝! 핵심코드. Queue pq = new PriorityQueue((a,b) ->{return a[2]-b[2];}); 3. 코드 import java.io.*; import java.uti..
백준 1005 - ACM Craft
[문제 바로가기] 1. 유형 위상 정렬, 동적 프로그래밍 2. 문제 접근 2-1. 설계 기본적인 위상 정렬 템플릿을 사용하고, 거기다가 DP를 추가한 문제입니다. 2-2. 풀이법 1. 가장 처음에 차수(해당 노드에 들어 노는 선분 수)를 초기화합니다. 2. 차수가 0인 것만 큐에 넣습니다 3. 큐에서 하나씩 꺼내면서 연결된 노드를 탐색합니다. 그리고 차수를 하나씩 감소시키고, 해당 노드까지의 누적 가중치를 갱신합니다. 3-1. 만약 차수가 0이 되면 큐에 집어넣습니다. 4. 3번을 큐가 빌 때까지 반복합니다. 끝. 3. 코드 import java.io.*; import java.util.*; public class Main { public static void main(String[] args) thro..
백준 17265 - 나의 인생에는 수학과
[문제 바로가기] 1. 유형 DFS 2. 문제 설명 N이 5이기 때문에 총 경우의 수 N*N*2로 충분히 시간내에 들어오는 것이 가능합니다. 일반적인 현재 좌표가 숫자인지 기호인지에 따라 조건문으로 분기합니다. 그리고 일반적인 DFS템플릿을 사용하면 됩니다. 3. 코드 import java.io.*; import java.util.*; //나의 인생에는 수학과 함계 public class Main { static char[][] mat; static int D[][] = { { 0, 1 }, { 1, 0 } }, N, MAXVAL = -Integer.MAX_VALUE, MINVAL = Integer.MAX_VALUE; public static void main(String[] args) throws IO..