ps
-
최소신장트리: 백준 9372 상근이의 여행PS 2022. 7. 23. 14:38
최소신장트리: 백준 9372 상근이의 여행 간단한 팁을 하나 남겨보고자 포스팅을 합니다. 제목에 쓰여있듯이 신장트리(spanning tree)라는 것에 대한 이야기예요. 문제와 풀이 문제 링크 : 백준 9372 - 상근이의 여행 👇펼쳐서 코드와 해설 읽기 문제를 보면 즉시 BFS로 풀어야겠다는 생각이 들죠. 최소신장트리에 대해서 모르는 상태였기 때문에 저도 그랬습니다. 신장 트리란 모든 정점을 포함하고 있는 그래프를 말합니다. 그리고 모든 정점을 가장 짧은 경로로 연결하는 그래프를 최소 신장 트리라고 합니다. 물론 몇가지 제약이 있지만 일단 개념은 그렇습니다(무향 그래프에서 가중치나 비용이 특별히 없을 때). 최소신장트리가 그려질 때에는 한 그래프에서 여러 형태로 존재할 수 있고, Self loop는 불..
-
모각코PS / 백준 2110 공유기 설치PS 2022. 6. 22. 15:01
모각코 PS스터디 지난주 알고리즘 스터디 내용 중 대표적인 한 문제를 정리해보려고 합니다. 늘 그렇듯 문제는 알고리즘 대장님께서 선정해주셨습니다.😃 문제와 풀이 문제 링크 : 백준 2110번 - 공유기 설치 👇펼쳐서 코드와 해설 읽기 진짜 할 말이 많은데... 일단 넋두리 & 이분탐색 tip은 마무리로 넘겨두고... 로직의 흐름 부터 보시죠. 로직의 흐름은 이렇습니다. 표본 수가 매우 큽니다. 대강 눈으로만 봐도 판단 횟수가 10억 * 20만이니까, 그리디로는 택도 없습니다. logN의 시간 복잡도로, 대강 열댓번 정도의 탐색으로 끝내야할 것 같습니다. 이를 위해 이분탐색으로 풀 것입니다. 정확히는 파라메트릭 서치를 적용할 거에요. 지금 궁금한 건 거리죠. 최소 거리와 최대 거리를 탐색 범위로 두면 됩니..
-
동전 교환 알고리즘: 주어진 화폐로 특정 금액 만드는 경우의 수 구하기PS 2022. 6. 2. 17:37
동전 교환 알고리즘 문제 : 경우의 수 구하기 동전 교환 알고리즘 문제는 다이나믹 프로그래밍 영역에서 다양한 바리에이션으로 출제되는 문제입니다(저도 몰랐어요. 이번에 DP 공부하면서 알게되었습니다. 코린이라서...). 아래에 해설할 문제는 '몇 종류의 화폐가 주어지고, 이 화폐들을 조합해서 특정 금액을 만들 수 있는 경우의 수'를 구하는 유형의 문제입니다. 해설을 보시고 DP에 익숙해져서 또 다른 동전 교환 알고리즘 문제와 DP 문제들도 쉽게 풀 수 있게 되면 좋겠습니다! 해설 영상 영상이 좀 많이 길어요. 왜냐면 제가 겨우겨우 이해를 했기 때문에... 저와 같이 이해가 느리신 분이 계시면 도움이 되시라고 최대한 자세하게, 반복하면서 설명을 해서 그렇습니다. 중간 중간 멈춰가면서 생각해보시..
-
PS미세먼지 팁: 정수 자릿수 구할 때 Math.log10() + 1?PS 2022. 5. 24. 17:36
미먼Tip : 정수 자릿수 구하는 법 (Math.log10() + 1 말고) '숫자 자릿수 구하기'라고 구글링 하면, int cnt = Math.log10(자릿수 구할 숫자) + 1를 쓰라고 많이들 알려주세요. 그렇게 해도 가능합니다. 하지만 다른 방법은 없을까요? 의문 자릿수를 구하다가 한 가지 의문이 들었어요. 보통 자릿수는 int형으로 필요해서 구하게 되는데요. 넘겨주는 숫자의 타입도 int형이고요. 자릿수 구할 값을 -> Math.log10()에 넘겨주고 -> int값으로 리턴을 받는건데 그렇게 되면 데이터의 타입이 int -> double -> int로 두 번 오토박싱이 일어날 거란 생각이 들었습니다. 그래서 이런 생각이 들었어요. int cnt = String.valueOf(자릿..