목록전체 글 (60)

쫑쫑이의 블로그

백준 1068 트리 Java [DFS]

https://www.acmicpc.net/problem/1068 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 예제에 없는 조건만 찾으면 빨리 해결할 수 있다 먼저 루트가 0번 인덱스가 고정이 아니다 어떤 노드의 자식 노드가 제거됐을 때 남은 자식 노드가 없으면 리프 노드가 된다 입력값을 이용하여 먼저 root를 찾아주고 인덱스별 자식 노드를 children에 담아주었다 이 때 삭제될 노드는 자식 노드로 넣어주지 않았다 3번 예제가 루트 노드와 삭제 노드가 같은 경우인데 이런 경우에는 큐에 값을 넣지..
알고리즘/백준 2022. 11. 28. 03:35
백준 11000 강의실 배정 Java [우선순위 큐]

https://www.acmicpc.net/problem/11000 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109) www.acmicpc.net 우선순위 큐를 2개 만들어 한 우선순위큐는 예제의 첫번째 값을 오름차순으로 하여 만들고 이 큐의 size가 0이 될 때 까지 반복문을 돌려 큐의 peek값보다 작거나 같은 끝나는 시간 값 큐에 있는 값들을 모두 빼고, 강의실 카운트에서 뺀다 하나씩 꺼내고 끝나는 시간 값을 다른 우선순위큐에 오름차순으로 하여 넣고, 강의실 카운트를 더한 후 강의실 최대값과 비교하여 갱신한다 import java.awt.*; import java.io.*; imp..
알고리즘/백준 2022. 11. 27. 00:09
백준 7662 이중 우선순위 큐 Java [우선순위 큐]

https://www.acmicpc.net/problem/7662 7662번: 이중 우선순위 큐 입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 Q에 적 www.acmicpc.net 중복되는 값들을 카운트할 HashMap과 오름차순 우선순위 큐, 내림차순 우선순위 큐를 만들어 입력 값이 I 일때 중복되는 값이 HashMap에 없으면 양쪽 큐에 다 넣고 중복되는 값이 HashMap에 있으면 value를 1 증가한다 입력 값이 D 일때 HashMap에 peek 값이 있고 value가 1보다 크면 value를 1 빼고 value가 1이면 HashMap에서 제거하고, 큐에서도 p..
알고리즘/백준 2022. 11. 26. 02:25
백준 1516 게임 개발 Java [위상정렬, DP]

https://www.acmicpc.net/problem/1516 1516번: 게임 개발 첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. 건물의 번호는 1부 www.acmicpc.net 위상정렬을 사용하여 먼저 지어야하는 건물 갯수만큼 가중치를 주고, 건물이 완성될 때마다 그 다음 지을 수 있는 건물의 시간 값을 최대값을 비교하여 넣어주고, 가중치가 0이 되면 건물 완성 큐에 넣는다 예제를 예시로 하면 가중치는 [0, 0, 1, 1, 2, 1]이 된다 (0번 인덱스는 사용안함) 가중치가 0인 값을 큐에 넣으면 1번만 큐에 들어간다 1 다음에 지을 수 있는 건물은 2, ..
알고리즘/백준 2022. 11. 25. 01:14
백준 11085 군사 이동 Java [분리집합 Union find]

https://www.acmicpc.net/problem/11085 11085번: 군사 이동 전쟁 당시 Baekjoon World의 국왕은 Cube World를 공격할 작전을 세운 적이 있습니다. Baekjoon World와 Cube World는 p개의 지점과 w개의 길로 표현됩니다. 모든 길은 양방향이며, 각 길마다 너비가 존재하여 www.acmicpc.net 백준 월드에서 큐브 월드를 공격한다는 말은 백준 월드 수도 c와 큐브 월드 수도 v가 하나의 집합에 속해야한다는 뜻이다 경로 상에 있는 길 중 너비가 가장 좁은 길의 너비를 최대화하는 경로를 택한다는 말은 큰 길만 골라간 것과 같다 즉, c와 v가 하나의 집합이 될 때까지 너비 기준 최대 우선순위 큐로 입력값을 큐에서 하나씩 꺼내서 서로 연결되지..
알고리즘/백준 2022. 11. 24. 02:58
백준 1976 여행 가자 Java [분리집합, Union find]

https://www.acmicpc.net/problem/1976 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net 분리 집합 문제로 여행 계획에 있는 모든 도시들이 하나의 집합에 속해 공통 부모를 가지고 있는지 확인하면 된다 입력에서 1이 나온 부분을 i번째 도시와 j번째 도시를 부모가 같게 만든다 i번째 도시의 i보다 작은 숫자의 도시들은 이전에 중복 체크되니까 j의 시작을 i + 1로 하면 시간을 절반으로 단축할 수 있다 예제의 경우 그림에 빨간 선으로 표현한 것처럼 3번만 확인하면 된다 import ja..
알고리즘/백준 2022. 11. 23. 00:53
이전 Prev 1 2 3 4 5 6 ··· 10 Next 다음