728x90
728x90
공부할 내용 서로소 집합 신장 트리 크루스칼 알고리즘 위상 정렬 공부 방법 기타 그래프 이론 - 동빈나 영상 시청 및 정리 이것이 코딩테스트다 책 참고 추천문제 풀기 (블로그에 문제 풀이를 게시하지는 않겠음) 위상 정렬 사이클이 없는 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것을 의미한다. 예시) 선수과목을 고려한 학습 순서 설정 위 세 과목을 모두 듣기 위한 적절한 학습 순서는? 자료구조 -> 알고리즘 -> 고급 알고리즘 (O) 자료구조 -> 고급 알고리즘 -> 알고리즘 (X) 진입차수와 진출차수 진입차수(Indegree): 특정한 노드로 들어오는 간선의 개수 진출차수(Outdegree): 특정한 노드에서 나가는 간선의 개수 위상 정렬 알고리즘 큐를 이용하는 위상 정렬 알고..
공부할 내용 서로소 집합 신장 트리 크루스칼 알고리즘 위상 정렬 (해당 주제는 앞에서 정리했기 때문에 따로 정리하지 않아도 된다.) 공부 방법 기타 그래프 이론 - 동빈나 영상 시청 및 정리 이것이 코딩테스트다 책 참고 추천문제 풀기 (블로그에 문제 풀이를 게시하지는 않겠음) 신장 트리 그래프에서 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 의미한다. 모든 노드가 포함되어 서로 연결되면서 사이클이 존재하지 않는다는 조건은 트리의 조건이기도 하다. 원본 그래프에 존재하는 간선을 모두 활용하지 않고 일부 간선만 활용하여 모든 노드가 포함되어있는 하나의 부분 그래프를 만드는 것이다. 신장트리는 모든 노드가 다 연결되어있지만, 일부 간선을 사용하지 않아도 괜찮다는 점에서 실제 문제 상황에서도 이..
오늘은 최대공약수 알고리즘을 구현 및 사용하는 방법에 대해 알아보자! GCD는 Greatest Common Divisor로 최대 공약수이다. 최대공약수는 두 수의 공통 약수중 최댓값을 말합니다. (약수는 나누어서 0 이 되는 수를 말한다) 이렇게 나누어서 0 이 되는 수중 공통적으로 들어가 있으며, 최댓값을 찾는 것입니다. 자바에서는 BigInteger 클래스에 최대공약수를 구할 수 있는 gcd() 함수를 제공합니다. 함수를 이용해서 구하는 방법과 직접 함수를 만드는 방법에 대해 알아 본다. 1. BigInteger 내장 함수를 사용 private static int gcdThing(int a, int b) { BigInteger b1 = BigInteger.valueOf(a); BigInteger b2..
참고: https://gorakgarak.tistory.com/522 순열(Permutation) 알고리즘 1,2,3 와 같은 숫자들이이 있다. 이것을 중복하지 않고 순서를 끌어내는 방법을 생각해보자 1-2-3 1-3-2 2-1-3 2-3-1 3-1-2 3-2-1 여섯가지 방법이 존재한다. 이제 숫자 네개인 1,2,3,4를 한번 섞어본다. 1-2-3-4.. gorakgarak.tistory.com 프로그래머스의 코딩 테스트 문제 중에서 완적 탐색 기법 lever2 단계인 '소수 찾기'를 풀다가 '순열'의 개념이 필요하게 되었다. 직접 구현해보려고 했으나, 쉽지않아서 구글링을 통해서 학습하였다. (알고리즘이 직관적으로 이해하기가 쉽지 않아 꽤 오랜 시간 손 코딩을 하면서 따라가며 이해하였다) 참고: htt..