알고리즘95 백준 [자바 java] 1717번 : 집합의 표현 https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 초기에 $n+1$개의 집합 $\{0\}, \{1\}, \{2\}, \dots , \{n\}$이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다. 집합을 표현하는 프로그램을 작 www.acmicpc.net 이 문제는 유니온파인드를 사용하여 풀었다. 옛날에는 유니온파인드가 복잡하고 별로라고 생각했는데, 난이도가 올라갈수록 집합문제에 이 알고리즘을 안쓰면 시간초과, 메모리초과 없이 문제를 풀 수가 없다. 처음에는 find함수에서 return할 때 재귀로 받은 값을 union[k]에 넣는 것을 생략했는데, 이랬더니 시간초과가 났다. 앞으로는 귀찮다고 생략하지 말자. .. 2023. 7. 13. 백준 [자바 java] 11279 : 최대 힙 https://www.acmicpc.net/problem/11279 11279번: 최대 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 문제 설명 수들을 입력받고, 0을 입력받을 때마다 이제까지 입력받았던 수 중 가장 큰 수를 출력하고 poll한다. 이외의 수를 받으면 힙에 수를 offer한다. 풀이 설명 우선순위큐를 하나 생성한다. 이 때 Collections.reverseOrder()을 이용하여 내림차순화 된 우선순위큐로 만들어준다. 수를 입력받고 이게 0이면 우선순위큐에서 poll하고 값을 string.. 2023. 7. 13. 백준 [자바 java] 1927 : 최소 힙 https://www.acmicpc.net/problem/1927 1927번: 최소 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 문제설명 수들을 입력받고, 0을 입력받을 때마다 이제까지 입력받았던 수 중 가장 작은 수를 출력하고 poll한다. 이외의 수를 받으면 힙에 수를 offer한다. 문제풀이 우선순위큐를 하나 생성한다 수를 입력받고 이게 0이면 우선순위큐에서 poll하고 값을 stringBuilder에 저장(비어있으면 0 저장) 아니라면 이를 우선순위 큐에 저장 풀이코드 import java.uti.. 2023. 7. 13. 백준 [자바 java] 10845 : 큐 https://www.acmicpc.net/problem/10845 10845번: 큐 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 문제설명 앞서 작성했던 스택과 비슷한 문제이다. https://ethereal-coder.tistory.com/41 백준 [자바 java] 10828 : 스택 https://www.acmicpc.net/problem/10828 10828번: 스택 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는.. 2023. 7. 12. 백준 [자바 java] 10828 : 스택 https://www.acmicpc.net/problem/10828 10828번: 스택 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 문제 설명 첫번째 줄에 문장들의 갯수가 주어지고 문장이 의미하는 대로 stack에 수를 push하고 pop하는 등의 과정을 수행한다. 문제 풀이 n에 문장의 수를 입력받는다. Integer형식인 stack를 하나 만든다. stringTokneizer을 이용하여 문자열을 입력받는다. 문자열이 push일 경우 스택에 넣을 값을 입력받고 이를 push한다. pop, peek등의 문자열.. 2023. 7. 12. 백준 [자바 java] 11000 : 강의실 배정 https://www.acmicpc.net/problem/11000 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109) www.acmicpc.net 문제설명 n이 주어지고, n개의 강의들이 모두 강의가 가능하게 하도록 준비해야하는 최소 강의실 수를 구하는 문제이다. 풀이설명 처음에는 강의실을 2차원 배열에 입력받고, 시작시간을 기준으로 오름차순 한 후, visit 한 배열이 없을 때까지 배열을 처음부터 끝까지 반복해서 확인하는 방법으로 풀었는데, 시간초과가 나왔다. 문제에 사용된 알고리즘을 확인 한 결과, 우선순위 큐를 사용해야 한다는 것을 알게 되었다. 기존 방법과 같이 시작시간을 기준으.. 2023. 7. 11. 이전 1 ··· 10 11 12 13 14 15 16 다음
