IT_공부하자

문제 : https://www.acmicpc.net/problem/2263  접근 :    - 인오더와 포스트오더를 저장한다.   - 포스트오더의 마지막 값은 root 노드 이므로 해당 값을 프리오더에 저장하고, 인오더에서 노드의 값을 기점으로 좌우를 나눈다.   - 인오더에서 좌우를 나눈거와 동일한 길이만큼 포스트오더에서 좌우로 나눈다.   - 좌측 나눈 sub 트리에서 위에 과정을 동일하게 반복하고, 오른쪽에 대해서도 동일하게 시행한다.   -결과 값을 출력한다.         코드 구현 :  import java.io.*;public class Main { private static StringBuilder sb; private static int[] in_order_idx; pri..

문제 : https://www.acmicpc.net/problem/17609  접근 :   - 좌측 끝과 우측 끝에 포인터를 두고 양쪽에서 1씩 감소시키면서 일치하는지 판단한다.   - 만약 다르다면 현재 좌측+1, 우측 포인터 위치에서 다시 한번 검사를 실시한다.   - 또한, 현재 좌측, 우측-1 포인터 위치에 대해서도 검사를 실시하고 둘 중 작은 값을 결과로 출력한다.  코드 구현 : import java.io.*;public class Main { private static int checkPal(String str, int s, int e, int rm_cnt){ if (rm_cnt >= 2) return 2; while (s

문제 : https://www.acmicpc.net/problem/12904  접근 :    - 2번째 입력받은 문자열을 deq에 넣는다.   - reverse 가 false 인 경우 마지막 문자를 뽑아 A 이면 다음으로 진행, B 이면 reverse를 ture 로 반전   - reverse 가 true 인 경우 첫번째 문자를 뽑아 A 이면 다음으로 진행, B 이면 reverse를 false 로 반전   - 1번째 입력 받은 문자열과 deq의 길이가 같아질때 까지 반복실행   - 만약 길이가 같아지면 reverse 가 true 이면 반전하여 동일한지 비교, 만약 false 이면 그대로 같은지 비교한다.    코드 구현 : import java.io.*;import java.util.*;public cla..

https://www.acmicpc.net/problem/1167문제 : https://www.acmicpc.net/problem/1967  접근 :    - root 노드에서부터 리프노드까지 탐색을 진행하여 가장 긴 길이의 리프 노드를 찾는다.   - 찾은 리프 노드에서 부터 가장 먼 노드까지 길이를 계산한 후 결과를 출력한다.   코드 구현 :  import java.io.*;import java.util.*;public class Main { private static Map> graph; private static Node end; static class Node{ int idx; int weight; public Node(int idx, in..

문제 : https://www.acmicpc.net/problem/4803  접근 :    - m 만큼 입력을 받아 그래프를 연결한다.  - 1부터 n 까지 root node라고 가정하고 반복문을 진행한다. 만약 graph에 해당 node 정보가 없다면 단일 노드로서 트리로 존재한다고 판단한다.   - 그래프를 순회하면서 노드의 갯수를 확인하고 노드 수 = (간선수 / 2) + 1 이면 사이클이 없으므로 트리로 카운트 한다.   -  0 0 입력이 들어올 때까지 수행하고 해당 결과에 알맞은 문자열을 출력한다.   코드 구현 :  import java.io.*;import java.util.*;public class Main { private static BufferedReader br; // ..

문제 : https://www.acmicpc.net/problem/1068 접근 :    - 입력 받은 수를 배열에 넣는다.   - 지워야할 수를 저장한 후, 입력 받은 배열로 그래프를 만든다.  - 만약 배열의 인덱스나 배열의 값이 지워야할 수 이라면 그래프로 만들지 않고 다음 수로 넘어간다.  - root 와 지워야할 수가 같다면 0을 출력, 다르면 root 부터 리프노드의 수를 DFS 로 계산한다.  - 탐색이 끝나면 리프노드 수를 출력한다.  코드 구현 :  import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.H..

문제 : https://www.acmicpc.net/problem/11725  접근 :    - 입력되는 정보로 그래프를 작성   - 루트가 1 이므로 DFS를 통하여 1부터 인접한 노드의 부모 노드를 현재 수로 등록한다.   - 만약 인접 노드가 자신의 부모 노드일 경우 DFS를 실행하지 않는다.   - 부모 노드를 모두 등록하면 2부터 자신의 부모 노드를 출력한다.    코드 구현 :  import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;public class Main { private static ArrayList[] adj; pri..

문제 :https://school.programmers.co.kr/learn/courses/30/lessons/42884  접근 :   - 끝을 기준으로 최소힙에 넣는다.  - 한개 씩 차례대로 빼면서 다음의 시작 지점이 이전의 끝지점보다 큰 경우 끝지점을 갱신하고 정답에 1을 추가한다.  - 끝까지 진행 후 결과값을 출력한다.    코드 구현 :   import java.util.Collections;import java.util.PriorityQueue;class Solution { private static class Car implements Comparable{ int route_in; int route_out; public Car(int route_i..

문제 :https://www.acmicpc.net/problem/2688  접근 :   - n = 1,  dp[1] = 10, before = {0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}  - n = 2, dp[2] = 10 - 0 + 10 - 1 + 9 - 1 + · · · + 2 - 1 , before = {0, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1}  - n = 3, dp[3] = 55 - 0 + 55 - 10 + 45 - 9 + · · · + 2 - 1, before = {0, 55, 45,  36, 28, 21, 15, 10, 6, 3, 1} 즉 dp[n] = dp[n-1] - before[0] + (dp[n-1] - before[0]) - before[1] + ..

문제 : https://www.acmicpc.net/problem/9465  접근 :   - 위쪽을 뜯는 경우와 아래쪽을 뜯는 경우를 나눠서 생각한다.  - 가로의 위치가 0 과 1 인 경우에는 나올 수 있는 최대값을 dp에 저장한다.  - 가로의 위치가 2 이상인 경우에는 위쪽과 아래쪽을 나눠서 현재 위치까지 도달했을 때, 가능한 최대값을 dp에 저장한다.  - 가로로 진행할 때, 항상 위쪽과 아래쪽을 나누어 더 큰 값으로 ans 값을 갱신한다.  - n-1 까지 진행한 후, ans 값을 출력한다.       코드구현 :  import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;public clas..