ds7 [Python] 백준 1043번 : 거짓말 (빅뱅 거짓말 아님ㅋ) https://www.acmicpc.net/problem/1043 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 💡 문제 풀이 분리 집합 문제이다. 사실 유니온&파인드 알고리즘으로 해결하고 싶었는데 자료구조로 푸는 게 더 적절해 보였다. 진실을 알고 있는 사람들과 각 파티에 참석하는 사람들을 입력받은 다음에 처리를 해줘야 한다. 이 문제에서 가장 중요한 것은 이미 거짓말을 들은 사람이 다른 파티에서 진실을 알고 있는 사람과 만날 경우이다. 따라서 진실을 알고있는 사람과 같이 있는 모든 사람들을 진실을 알고있는 그룹에 .. 2022. 9. 1. [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. [C++] 백준 11286번 : 절댓값 힙 https://www.acmicpc.net/problem/11286 11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 문제 풀이 우선순위 큐의 힙 구조를 이용해서 빠르게 정렬을 하는 것이 포인트이다! 절댓값과 일반 값 모두 따져야 해서 pair 구조를 이용했고 내부적으로 정리하기 위해서 구조체를 구현했다! 느낀 점 그렇게 어렵지 않은 문제인데 오랜만에 코딩을 하다 보니까 많이 버벅거렸다. 꾸준히 계속 연습해야겠다. 코드 #include #include #include using namespa.. 2022. 1. 18. [C++] 백준 1158번 : 요세푸스 문제 https://www.acmicpc.net/problem/1158 1158번: 요세푸스 문제 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000) www.acmicpc.net 문제 풀이 https://codinghejow.tistory.com/91와 같은 문제이다! 느낀 점 이번에 코테 준비를 하면서 다시 풀어봤던 문제이다. 이번에 한번 정리함으로써 큐에 대한 이해도가 확실하게 향상된 것 같다. 코드 #include #include using namespace std; int n, k; queue q; void func(int n, int k) { for (int i = 1; i 2021. 9. 24. 이전 1 2 다음