자료구조22 [Java] 백준 1374번 : 강의실 https://www.acmicpc.net/problem/1374 1374번: 강의실 첫째 줄에 강의의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 줄마다 세 개의 정수가 주어지는데, 순서대로 강의 번호, 강의 시작 시간, 강의 종료 시간을 의미한다. 강의 www.acmicpc.net 💡 문제 풀이 강의실 배정 문제이다. 이 문제는 최선의 강의실 개수를 구하는 문제이다. 가장 빨리 끝나는 강의 혹은 가장 빨리 시작하는 강의를 기준으로 탐색해서 해결할 수 있다. 이번 문제에선 가장 빨리 시작하는 강의를 기준으로 해결했다. 대기 중인 강의가 우선순위 큐에 저장되고 강의의 개수만큼 탐색한다. 지금 하는 강의가 끝나고 대기 중인 다음 강의가 진행될 수 있다면 다음 강의를.. 2023. 5. 3. [Java] 백준 19637번 : IF문 좀 대신 써줘 https://www.acmicpc.net/problem/19637 19637번: IF문 좀 대신 써줘 첫 번째 줄에는 칭호의 개수 N (1 ≤ N ≤ 105)과 칭호를 출력해야 하는 캐릭터들의 개수 M (1 ≤ M ≤ 105)이 빈칸을 사이에 두고 주어진다. (1 ≤ N, M ≤ 105) 두 번째 줄부터 N개의 줄에 각 칭 www.acmicpc.net 💡 문제 풀이 기본적인 이분탐색 문제이다. 칭호와 값의 매핑을 위해서 Map을 사용했고, 그중 비교가 빠른 HashMap을 사용했다. 중복을 제외해서 Map에 넣고 이분탐색을 위해 필요한 배열을 스트림으로 정렬해서 넣었다. 이후는 이분탐색으로 찾으면 된다! 시간복잡도는 아무리 커야 O(nlogn)이다. ✔️ 느낀 점 자바로 알고리즘을 푸는 건 너무 어렵다.. 2023. 4. 26. TIL : 위상정렬 알고리즘 (21) 💻 알고리즘 📌 위상정렬 알고리즘 Cycle이 없는 방향 그래프에서 작업 순서를 구하는 알고리즘이다. 이전에 공부한 적 있으나 기록을 남겨두지 않아서 남겨두려고 한다. 💡 특징 순환하지 않는 방향 그래프에서만 가능하다. 진입 차수 (in-degree) 또는 진출 차수 (out-degree)를 이용한다. 여러 개의 답이 존재할 수 있다 O(V+E)의 시간 복잡도를 가진다. 💡 동작 원리 (진입차수 ver) 진입 차수가 0인 정점을 큐에 넣는다. 큐에서 원소를 꺼내 연결된 간선을 제거한다. 진입 차수가 0이라면 해당 정점을 큐에 삽입한다. 마지막에 Cycle의 존재 유무를 확인한다. 결과의 크기가 정점의 개수보다 작다면 Cycle이 존재하는 것이다. from collections import deque de.. 2023. 3. 3. [Python] 백준 14698번 : 전생했더니 슬라임 연구자였던 건에 대하여 (Hard) https://www.acmicpc.net/problem/14698 14698번: 전생했더니 슬라임 연구자였던 건에 대하여 (Hard) 각 테스트 케이스마다 슬라임을 끝까지 합성했을 때 청구될 비용의 최솟값을 1, 000, 000, 007로 나눈 나머지를 출력한다. 전기 에너지가 전혀 필요하지 않은 경우엔 1 을 출력한다. www.acmicpc.net 💡 문제 풀이 그리디 알고리즘 문제이다. 간단하게 작은 것부터 계산해주면 된다. 매번 정렬하면서 사용할 수 없으니까 우선순위 큐를 사용해주면 된다. ✔️ 느낀 점 heapq.heappop이 힙 구조로 되어있다는 가정 하에 0번 인덱스를 리턴하는 것인 것을 몰라서 heapify를 안 써서 계속 틀렸다. 이번 기회에 확실하게 잡고 가게 되었다. 💻 코드 imp.. 2022. 8. 24. TIL : Union-Find 알고리즘, Disjoint Set 자료구조 (6) 📚 자료구조 ✔️ Disjoint Set이란? 여집합이 없는 부분집합을 저장하고 조작하는 자료 구조. 한 마디로, 서로소 집합 자료구조 세 가지 연산을 가진다. 초기화, make-set(x) : x를 유일한 원소로 하는 새로운 set을 만든다. 합치기, union(x, y) : x가 속한 set과 y가 속한 set을 합친다. 찾기, find(x) : x가 속한 set의 루트 노드 값을 리턴한다. 💡 특징 부모 노드가 자식 노드를 가리키는 트리 구조와 다르게 분리 집합은 자식 노드가 부모 노드를 가리킨다. 💻 알고리즘 ✔️ Union-Find 알고리즘이란? 그래프 알고리즘 중 하나로 두 노드가 같은 그래프에 속하는지 판별하는 알고리즘이다. 다시 말하면, disjoint set을 표현할 때 사용하는 알고리즘.. 2022. 8. 7. [Python] 백준 1764번 : 듣보잡 https://www.acmicpc.net/problem/1764 1764번: 듣보잡 첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. www.acmicpc.net 💡 문제 풀이 자료구조 문제이다. set에 대한 개념을 알고 있는지 묻고 있다. ✔️ 느낀 점 💻 코드 import sys n, m = map(int, sys.stdin.readline().split()) a1 = set([sys.stdin.readline().strip() for _ in range(n)]) a2 = set([sys.stdin.readline().strip() for _ in .. 2022. 7. 19. 이전 1 2 3 4 다음