L.O.K

https://www.acmicpc.net/problem/14675 14675번: 단절점과 단절선 프로그램의 입력은 표준 입력으로 받는다. 입력의 첫 줄에는 트리의 정점 개수 N이 주어진다. (2 ≤ N ≤ 100,000) 트리의 정점은 1번부터 n번까지 존재한다. 다음 줄부터 N-1개의 줄에 걸쳐 간선의 정 www.acmicpc.net ◎ 문제풀이 뭔가 맥이 빠지는 문제였다. 단절점과 단절선을 없애면 트리가 그래프가 두 개 나와야 한다. 단절선은 무엇을 없애든 그래프가 2개 나온다. 그러므로 무조건 yes이다. 단절점은 단절점의 자식노드가 2개 이상이면 yes이다. 그러므로 트리를 인접리스트로 구현하여 리스트의 크기가 2이상이면 yes를 출력한다. ◎ 코드 package org.example.tree;..

1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net ◎ 문제풀이 특정 노드를 삭제하면 자식 노드들도 삭제가 될 때, 리프노드의 개수를 구하는 문제이다. 풀이는 3단계로 이루어 진다. Step1) 트리를 그래프의 인접리스트 구조로 구현 각 노드의 자식노드를 List에 저장한다. 그래프의 인접리스트 방식으로 트리를 구현하는 것이다. Step2) DFS 탐색으로 노드 삭제 특정 노드를 삭제하면 자식노드와 자식의 자식노드도 삭제해야 한다. DFS탐색으로 자식의 자식까지 삭제하고 삭제 여부를 테이블 자료구조에 저장한..

5639번: 이진 검색 트리 트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다 www.acmicpc.net ◎ 문제풀이 전위순회 결과를 가지고 이진트리를 만든 후 후위순회를 하는 문제이다. 전위순회는 ROOT -> LEFT -> RIGHT 순으로 탐색한다. 그러므로 가장 위에 있는 값이 ROOT이고 다음 값은 LEFT이다. 그리고 그 다음 값은 LEFT의 LEFT이다. LEFT의 LEFT가 없다면 ROOT의 RIGHT이다. 이 구조는 객체참조구조를 이용하면 쉽게 구할 수 있다. ◎ 코드 package org.example.tree; import java...

1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net ◎ 문제풀이 위상정렬의 교과서 같은 문제이다. 문제풀이의 순서를 정해야 한다. 그러나 순서에는 우선순위가 있다. 즉, 각 문제는 위상이 서로 다르다. 문제A는 문제B 앞에 와야하고 문제C는 문제D 앞에 와야한다. 이렇듯, 정렬되는 순서에 어떠한 위상이 존재할 때, 위상정렬 알고리즘을 사용한다. [Algorithm] 위상정렬 (Topology Sort)이란? 위상정렬은 방향그래프를 한 정렬이다. 위 그래프는 작업 간 의존관계를 표현한..

https://www.acmicpc.net/problem/16500 16500번: 문자열 판별 첫째 줄에 길이가 100이하인 문자열 S가 주어진다. 둘째 줄에는 A에 포함된 문자열의 개수 N(1 ≤ N ≤ 100)이 주어진다. 셋째 줄부터 N개의 줄에는 A에 포함된 단어가 한 줄에 하나씩 주어진다. A에 www.acmicpc.net ◎문제 풀이 문자열 s가 주어질 때, 주어진 여러 개의 문자열 조합으로 s를 만들 수 있는지를 묻는 문제이다. 조합을 만드는 문제는 재귀호출로 풀면된다. 적절한 가지치기 조건을 두어 DFS 탐색을 하면 문제를 풀 수 있다. ◎코드 import java.util.Scanner; //BOJ165000 문자열 판별 ( 백트래킹 ) public class Main { public s..

1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net ◎ 문제풀이 카드 묶음을 비교하여 하나로 만들 때, 비교횟수의 최솟값을 구하는 문제이다. 비교횟수가 최소가 되려면 카드묶음이 큰 거를 가장 마지막에 비교해야 한다. 그리고 두 개의 카드묶음을 하나로 합치면 또 하나의 카드 묶음이 만들어진다. 비교횟수가 최소가 되려면 새로 생성된 카드묶음을 포함한 가장 개수가 적은 카드묶음 두 개를 합쳐야 한다. 다시말하여, 새로운 카드묶음이 추가될 때 마다 카드묶음 자료구조에서 매번 최솟값을 구해야 한다는 의미다...

1781번: 컵라면 상욱 조교는 동호에게 N개의 문제를 주고서, 각각의 문제를 풀었을 때 컵라면을 몇 개 줄 것인지 제시 하였다. 하지만 동호의 찌를듯한 자신감에 소심한 상욱 조교는 각각의 문제에 대해 데드라 www.acmicpc.net ◎ 문제풀이 문제마다 데드라인이 정해져 있을 때, 컵라면을 최대로 몇 개까지 받을 수 있는지를 구하는 문제이다. 이 문제는 그리디 풀이에 HeapQueue를 떠올리면 간단히 풀리는 문제이다. ( 나는 떠올리지 못했다.. ) 단위시간이 1씩 늘어가면 컵라면을 받을 수 있는 개수도 바뀐다. 시간의 변화에 따른 최적해를 구해야 하므로 그리디로 접근해야 한다. 단위시간 1을 하루로 생각해보자. 한 문제를 푸는데 하루가 걸린다. 데드라인이 2일이라면 이틀 안에 풀면 된다. 최적해..

2655번: 가장높은탑쌓기 첫째 줄에는 입력될 벽돌의 수가 주어진다. 입력으로 주어지는 벽돌의 수는 최대 100개이다. 둘째 줄부터는 각 줄에 한 개의 벽돌에 관한 정보인 벽돌 밑면의 넓이, 벽돌의 높이 그리고 무게가 차 www.acmicpc.net ◎ 문제풀이 벽돌이 100개 이하로 주어질 때, 벽돌을 쌓아 올릴 수 있는 최대 높이를 구하는 문제이다. 이 문제가 까다로운 이유는 두 개의 조건을 고려해야 하기 때문이다. 1) 밑면의 넓이 2) 무게 이런 경우, 밑면의 넓이로 정렬해준 다음 무게로 DP 풀이를 하면 된다. 먼저, N개의 벽돌을 밑면의 넓이가 작은 순서대로 오름차순 정렬을 한다. 그리고 밑면의 넓이가 작은 것부터 하나씩 DP 테이블을 만들 것이다. DP테이블은 N번째 블록을 가장 밑으로 하는..

1939번: 중량제한 첫째 줄에 N, M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1 ≤ A, B ≤ N), C(1 ≤ C ≤ 1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 www.acmicpc.net ◎ 문제풀이 공장1에서 공장2로 한번에 이동가능한 최대중량을 구하는 문제이다. BinarySearch와 BFS를 모두 떠올려야 하는 고난도 문제였다. 처음 이 문제를 접했을 때, DFS가 떠올랐다. 공장1에서 공장2까지 가는 모든 경로를 완전탐색해야 한다고 생각했기 때문이다. 그러나 DFS로 풀면 시간초과가 난다. visited[bridge.nextNode] = true; // 역행방지 dfs(bridg..

1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net ◎ 문제풀이 다익스트라 알고리즘 문제로 알려져 있는데, 문제를 보니 플로이드 워셜 알고리즘이 더 어울린다고 생각했다. 시작점이 정해져 있지 않았고 모든 노드를 기준으로 하기 때문이다. 플로이드 워셜은 삼중for문을 구현하므로 시간초과를 조심해야 하는데, 시간제한이 1초이고 n이 1000이하라 삼중for문을 돌리면 얼추 시간초과가 걸리지 않는다고 생각했다. [Algorithm] 플로이드-워셜(Floyd-Warshall) 알고리즘이란?..