Algorithm/문제코드6 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. 이전 1 다음
