algoqna

https://www.acmicpc.net/problem/11437 각 정점에 대하여 정점의 정보를 저장해둔다(fillInfoOfNode) int[] infoOfNode[N][2] 선언 배열에 저장되는 것은 나의 부모 / 나의 깊이 두 정점의 깊이를 맞춘다 (matchDepth) 깊이를 맞춘 상태에서 깊이를 1개씩 내려가며 둘의 공통 조상을 찾을 때 까지 반복 https://github.com/ssjjaa-algo/AlgoAndMySQL/blob/master/src/Baekjoon/BOJ11437.java

2812번: 크게 만들기 N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 가장 큰 수가 되는 조건이 무엇인지 찾아야 한다 -> 그리디적 사고방식. 맨 앞에 있는 숫자가 최대한 클 수록 유리하다. 그러므로 그렇게 만들어야 한다. 스택 자료구조를 이용한다. 내가 있는 위치를 기준으로 다음에 들어갈 원소가 나보다 크다면 다음에 있는 원소가 기준이 되고, 다음에 있는 원소에서 이전을 검사하여 큰 값을 만날 때까지, K > 0일 때까지 이전 원소들을 빼본다. 그게 아니라면 그냥 스택에 푸쉬한다. 위의 과정을 거쳤는데 아직 K번을 다 뺀 상황이 아니라면 뒤에 붙은 원소들은 자연스럽게 작은 원소들임. 맨 뒤에서부터 K가 0..

10799번: 쇠막대기 여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다. 쇠막대기와 레이저 www.acmicpc.net 스택 성질을 이용한 문제 쇠막대기는 자신보다 긴 쇠막대기 위에만 놓일 수 있다. - 쇠막대기를 다른 쇠막대기 위에 놓는 경우 완전히 포함되도록 놓되, 끝점은 겹치지 않도록 놓는다. 각 쇠막대기를 자르는 레이저는 적어도 하나 존재한다. 레이저는 어떤 쇠막대기의 양 끝점과도 겹치지 않는다 - 열린 괄호 ' ( '가 출현하는 경우는 스택에 그대로 push한다 - 막대기를 제거할 가능성이 없기 때문에 deleteStick을 false로 설정해준다 - 닫힌 괄호 ' ) ' 가 출현하..

20040번: 사이클 게임 사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한 www.acmicpc.net Disjoint-Set (상호 배타적 집합) - 트리 이용 Union-Find 1) 상호 배타적인 부분 집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료구조 ● 0 ~ n-1 까지의 원소로 표현한 뒤, 각 1개의 원소를 포함하는 n개의 집합을 만들어야 함 = 배 kkalgo.tistory.com Disjoint-Set에 대해 모른다면 위의 링크를 참조하셔도 괜찮습니다. - 전형적인 Disjoint-Set 문제 : Union-Find 이용해서 사이클..

1. 트리의 중위 순회에서 마지막 도착지점의 값을 구한다 : endOfInorder에 저장 2. 유사 중위 순회에서 endOfInorder과 값이 같은 순간의 cnt 값을 출력한다 - 자식이 있는 경우 자기 자신으로 돌아올 때 유사 중위 순회의 조건에 의해 다시 더해줘야한다. - 생각하지 못했던 반례 * 1의 왼쪽 자식 2만 있고 2는 자식이 하나도 없는 경우, 즉 endOfInorder가 root인 경우 * 맨 처음에 바로 endOfInorder값에 도달했는지를 체크하는 것이 아닌 자식이 있는지 여부부터 체크하는 것으로 해결 import java.io.*; import java.util.*; public class Main { static StringBuilder sb = new StringBuilde..

1. 트리의 형태가 무조건 이진 트리라는 조건은 없다 2. 트리의 루트가 무조건 0번 노드라는 조건은 없다 위의 두 조건을 염두하여 풀어야 할 문제 - 부모노드를 저장할 배열 parent - 나의 자식노드를 저장할 List[] Childs - 삭제해야할 노드의 부모노드(parent[num]) 로 가서 부모노드에서 삭제해야할 노드를 자식목록에서 지운 후 bfs를 탐색한다. == child[parent[num]] 안에 있다. import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; i..

15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 1) M개의 치킨집을 배치시키므로 치킨집의개수Combination M만큼 재귀를 돌아 M개의 치킨집을 배치시킨다 2) 치킨집을 배치시켰으면 가) 모든 집들이 나) 배치시킨 치킨집들에 대하여 모든 거리를 갱신시켜 최단거리를 가지도록 한다 import java.io.*; import java.util.*; public class A047_BJ15686_치킨배달 { static int N,M; static int[][] arr; static Lis..

Union-Find 1) 상호 배타적인 부분 집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료구조 ● 0 ~ n-1 까지의 원소로 표현한 뒤, 각 1개의 원소를 포함하는 n개의 집합을 만들어야 함 = 배열 선언 2) 필수적인 세 가지 연산 ● 초기화 : n개의 원소가 집합에 포함되어 있도록 초기화 ● Union(a,b) : 원소 a와 b를 하나로 합친다 == 두 집합을 하나의 집합으로. ● find(a) : 원소 a가 속한 집합을 반환한다. 3) 트리를 이용한 상호 배타적 집합 ● 한 집합에 속하는 원소들을 '하나의 트리'로 묶는다 ● 그리하여 상호 배타적 집합은 '트리들의 집합' ● 어떤 정점 v와 u가 같은 집합인지 알고싶다? * 정점 v와 u가 '같은 루트' 를 공유하고 있나를 확인한다...