Algorithm10 BOJ_트리의 독립집합 [DFS, DP] 트리의 독립집합 2 초128 MB77383809283448.511%문제https://www.acmicpc.net/problem/2213그래프 G(V, E)에서 정점의 부분 집합 S에 속한 모든 정점쌍이 서로 인접하지 않으면 (정점쌍을 잇는 간선이 없으면) S를 독립 집합(independent set)이라고 한다. 독립 집합의 크기는 정점에 가중치가 주어져 있지 않을 경우는 독립 집합에 속한 정점의 수를 말하고, 정점에 가중치가 주어져 있으면 독립 집합에 속한 정점의 가중치의 합으로 정의한다. 독립 집합이 공집합일 때 그 크기는 0이라고 하자. 크기가 최대인 독립 집합을 최대 독립 집합이라고 한다. 문제는 일반적인 그래프가 아니라 트리(연결되어 있고 사이클이 없는 그래프)와 각 정점의 가중치가 양의 정수로.. 2024. 11. 9. BOJ - 점프2253 [DP] Java 하반기 코딩테스트를 치루며, DP 관련해서 문제가 자주 출제되었다고 생각한다. 어떤 회사의 코딩테스트인지는 밝히지 못하겠지만, 해당 문제와 비슷하게 풀었던 문제가 기억나서 글을 작성하였다. 추가로 해당 문제를 풀이한 언어로 Java 코드는 없었고, 대부분 파이썬과 C++로만 정리되어 있어, 풀이에 어려움을 겪을 분들에게 정답을 공유하고자 작성했다. 정답 풀이는 아래 Github 링크에 있고, 개인적으로 고민하며 해결함을 바랬기에 제 코드 위주로 구조적인 힌트만 간략하게 작성하였다. https://github.com/himJJong/codingtest_study/blob/master/24_11_04/boj_%EC%A0%90%ED%94%84.java codingtest_study/24_11_04/boj_점프.. 2024. 11. 4. 알고리즘 기록 Github Link https://github.com/himJJong/codingtest_study (2024_01 ~ 2024_10) GitHub - himJJong/codingtest_studyContribute to himJJong/codingtest_study development by creating an account on GitHub.github.com https://github.com/himJJong/Eggorithm_Study/tree/himJJong/himJJong%20-%20Java (2022_07 ~ 2024_01) Eggorithm_Study/himJJong - Java at himJJong · himJJong/Eggorithm_Study알고리즘 스터디 🧑🏻💻. Contribute to hi.. 2024. 10. 1. codeTree - Grid Compression [Hard] https://www.codetree.ai/missions/8/problems/count-number-of-points-2?&utm_source=clipboard&utm_medium=text 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요.www.codetree.ai 처음보는 개념의 문제라서, 작성해보고자 한다. 비슷한 유형의 코테 문제도 많이 봤던 것 같아 자세하게 이해하고 넘어가보자!!! Pair 클래스는 해당 x,y 지점을 담을 것이고, Tuple 클래스는 직사각형의 왼쪽 아래와 오른쪽 위 지점을 담을 것이다. 신기했던 것은 nums라고 만들어진 TreeSet에 해당 좌표 x,.. 2024. 8. 16. codeTree - PriortyQueue [Hard] https://www.codetree.ai/missions/8/problems/sum-of-kth-smallest-pair?&utm_source=clipboard&utm_medium=text 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요.www.codetree.ai 배운점 : arr1, arr2 배열의 원소들을 정렬해서 미리 배열의 원소들의 합을 구할 때 최소를 구하고자 한다. 이해가 안되었던 로직은 아래와 같다. pq는 두 배열 원소의 합 쌍을 기준으로 오름차순 정렬한 PriorityQueue이다. 1. k번째의 최솟값을 구해야 하므로 for 문을 k-1까지 진행하며, pq.. 2024. 8. 16. codeTree - TreeSet [easy] https://www.codetree.ai/missions/8/problems/small-but-big-number?&utm_source=clipboard&utm_medium=text 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요.www.codetree.ai 배운것: TreeSet의 floor, ceiling 메서드를 통해 정렬된 값들 중 원하는 범위를 찾아낼 수 있었다. 2024. 8. 16. Kruskal vs Prim 신장 트리란? 그래프의 모든 정점과 간선의 부분 집합으로 구성되는 트리를 말합니다. 사이클이 안 생기는 조건 안에서 간선의 개수를 정점 - 1개로 골라 만드는 것으로, 정점 - 1의 수가 간선의 수가 되는 트리입니다. 최소 비용 신장 트리란? 신장 트리 중에서 간선들의 합이 최소인 트리입니다. 또한 무향 가중 그래프에서 만들어질 수 있고 사이클이 발생되지 않으며 비용의 합이 최소인 트리입니다. 최소 비용 신장 트리의 특징 무방향 가중치 그래프입니다. 가중치의 합이 최소입니다. 정점 n개에서 n - 1개의 간선을 가지는 트리입니다. 사이클이 포함되서는 안됩니다. 최소 비용 신장 트리의 사용 도로망, 통신망, 유통망 등 여러 분야에서 비용을 최소로 해야하는 경우에 유용하게 사용됩니다. 최소 비용 신장 트리를.. 2023. 12. 2. Comparable, Comparator 인터페이스 백준 문제풀이를 진행하는데 있어 정렬에 조건을 줄 때, 아직 미흡한 이해 때문에 구글링을 번복하고 있다. 그렇기에 이번 기회에 확실하게 개념을 잡고 활용해보고자 정리하게 되었다. Comparable 인터페이스를 사용하려면 compareTo 메소드를 구현해야하는 것, Comparator 인터페이스를 쓰려면 compare 메소드를 구현해야 하는 점이 서로의 차이점이다. 보통 두 인터페이스는 "객체를 비교할 수 있도록 만든다." 라고 생각하는 것이 편하다. 하지만 왜 객체를 비교할 수 있도록 생각하라는 것일까? 우리는 원시 타입의 실수 변수 경우 부등호로 쉽게 비교할 수 있기 떄문이다. 하지만 새로운 클래스 객체를 만들어 비교하고자 한다면 본질적으로 객체는 사용자가 기준을 정해주지 않는 이상 어떤 객체가 더 .. 2023. 4. 15. 글을 쓰기에 앞서서 위 카테고리를 이제 생성에 대해 많은 시간을 고민했다. 이유는 아직 부족한 코테의 실력과 더불어 알고리즘에 대한 이해가 충분히 풍부하지 않았기 때문이다. 물론 지금도 훌륭한 적용을 바탕으로 문제를 해결하지는 못하지만, 현재 시점부터는 문제를 푸는 것 이외에 다양한 관점에서 여러 방면으로 접근해보고 더 꼼꼼한 공부를 해보고 싶었기에 시작하게 된 것이다. 코테 준비를 위해 1년 기간동안 알고리즘 스터디를 동기들과 꾸준하게 하고 있는데, 이는 4명이서 매주 4문제씩 백준 홈페이지에서 문제를 선정하고 있다. 문제에 대한 이해와 관점은 다른 경우가 많았기에 현재는 각자 Pr을 올려 코드 리뷰를 개인적으로 진행하고 있다. 깃허브 링크는 아래에 있으니 참고해도 좋을 것 같다. https://github.com/lco.. 2023. 4. 13. 이진 트리와 순회 방법 이진 트리(Binary Tree)는 각 노드가 최대 두 개의 자식 노드를 가지는 트리 자료구조입니다. 이진 트리는 많은 알고리즘에서 사용되며, 특히 검색 알고리즘에서 자주 사용됩니다. 이진 트리는 각 노드(Node)가 데이터와 두 개의 포인터(left, right)를 가지며, 이 포인터를 통해 자식 노드를 가리킵니다. 트리의 가장 위쪽에 위치한 노드를 루트 노드(Root Node)라고 하며, 가장 아래쪽에 있는 노드를 리프 노드(Leaf Node)라고 합니다. 이진 트리는 여러 가지 방법으로 순회할 수 있습니다. 대표적인 순회 방법으로는 전위 순회(Preorder Traversal), 중위 순회(Inorder Traversal), 후위 순회(Postorder Traversal)가 있습니다.다음은 이진 트.. 2023. 4. 13. 이전 1 다음
