백준
-
최소신장트리: 백준 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 / 백준 2178 미로 탐색PS 2022. 6. 11. 16:32
모각코 PS스터디 그래프 탐색 두 번째 문제인 '미로 탐색'입니다. 문제의 제약조건을 보면서 어떤 알고리즘으로 접근하면 좋을지 힌트를 얻을 수 있기도 하죠? 표본 수가 적고, 시간 제한이나 메모리가 상대적으로 넉넉하고, 좌표나 맵 같은 것이 주어지면 그래프가 떠오르는 것 같습니다. 그리고 각 탐색로의 길이를 비교하거나, 특히 가장 빠른 탐색 경로를 찾아야 하는 경우에는 BFS를 선택하는 편이 '대개' 유리하겠죠. 모든 경로를 다 들어가보고 길이를 기록해뒀다가 제일 짧은 길이를 리턴하는 것보다, 모든 경로를 동시에 진행하다가 한 경로가 끝에 다다르면 나머지를 더이상 탐색하지 않고 리턴하는게, 탐색 횟수가 훨씬 적을 거니까요. 이번 문제가 그런 스타일의 문제였습니다. 문제와 풀이..
-
모각코PS / 백준 1260 DFS와 BFSPS 2022. 6. 11. 16:08
모각코 PS스터디 지난주는 너무 바빠서 PS스터디 포스팅을 못 올렸네요. 백트래킹이었는데, 나중에라도 시간이 나면 올려보려고 합니다. 이번주 5주차 PS스터디 문제 주제는 그래프 탐색이었습니다. 세 문제 모두 DFS/BFS 문제였어요. 한 문제 씩 보면서 그래프 탐색에 대한 공부 방법, 주의점, 그리고 잡담 같은걸 좀 해볼게요. 그래프 탐색 문제는 흔히 '템플릿'이라고 하는 코딩스타일이 존재하죠. 조금만 구글링 해봐도 수두룩해요. 물론 제 블로그에도 있고요 ㅋㅋ. 그걸 보고 바로 원리를 이해할 수 있다면 좋겠지만 이해가 안된다면, 템플릿을 외워서라도 문제를 풀어보면서 익숙해지는 것도 좋은 방법 같습니다. 푸는데에 성공했다면 IDE로 옮겨서 디버깅을 실행해두고 한 스텝씩 따라가며 공부하는 거..
-
모각코PS / 백준 17478 재귀함수가 뭔가요?PS 2022. 5. 25. 16:09
모각코 PS스터디 백준 문제들을 보다보면 가끔가다 재미용 문제(?)가 있죠. 이 문제도 약간 그런 느낌입니다. 부트캠프 커리큘럼이 재귀를 배울 차례라, 알고리즘을 정해주신 대장님께서 넣어주신 것 같아요. 웃으면서 재밌게 풀었습니다. ㅎㅎ 문제와 풀이 문제 링크 : 백준 17478번 - 재귀함수가 뭔가요? 👇펼쳐서 코드와 해설 읽기 설명할 로직이랄게 없죠?...ㅎㅎ 더 정리할 수 있을 것 같은데 재귀 은근 머리아파서... 대강 풀고 끝내자! 하고 대강 풀어버렸습니다. (...) import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); ..
-
모각코 PS / 백준 1475 방 번호PS 2022. 5. 25. 15:57
모각코 PS스터디 이번주는 지난주와 비슷한 난이도의 문제가 선정되었습니다. 아직 2번 문제까지밖에 못봤는데 오늘 남는 시간에 나머지도 얼른 풀어봐야겠어요. 그 전에, 먼저 풀어놓은 문제들부터 포스팅으로 남겨보려고 합니다. 문제와 풀이 문제 링크 : 백준 1475번 - 방 번호 👇펼쳐서 코드와 해설 읽기 로직의 흐름은 이렇습니다. 09까지의 숫자세트를 저장할 배열 변수 set을 만들어놓습니다. 입력받은 숫자열(int)의 길이를 체크해서, 길이만큼 for문을 돌 건데요. 한 바퀴 돌 때마다 앞에서부터 숫자 하나씩 가져옵니다. 가져온 숫자가 숫자세트에 존재하는지 체크합니다. 있으면 숫자세트의 잔여 개수를 하나 줄입니다. 줄일 잔여 수가 없으면 숫자세트를 하나 추가(09까지 하나씩 증가)하고 난 뒤에 잔여개수를..
-
모각코 PS스터디 / 백준 1783 병든 나이트PS 2022. 5. 21. 16:44
모각코 PS스터디 왜인지 모르겠는데 PS는 하고 나서 포스팅 하는 걸 자꾸 까먹는다. 이번주 스터디 한 세 문제를 차례로 포스팅해보려고 한다. 문제와 풀이 문제 링크 : 백준 1783번 - 병든 나이트 👇펼쳐서 코드와 해설 읽기 이 문제도 역시 그리디(greedy) 카테고리의 문제다. 얼핏 보면 탐색 같지만, 표본 수(2,000,000,000)를 보면 탐색으로 했을 때 무조건 타임아웃이 날 거란 걸 생각해볼 수 있다. 충족할 조건은 2가지다. 이동횟수를 최대화할 것. 이동방식을 충족할 것. (밟은 발판 갯수가 5개 이상 시에만) 나이트의 이동경로는 다음 네가지다 2U 1R 1U 2R 1D 2R 2D 1R 네 가지 이동을 완수하는 케이스를 먼저 생각해보기로 했다. 네 가지 이동을 완수하고 나서도 시작점에 ..
-
모각코 PS스터디 / 백준 2875 "대회 or 인턴"PS 2022. 5. 21. 16:43
모각코 PS스터디 왜인지 모르겠는데 PS는 하고 나서 포스팅 하는 걸 자꾸 까먹는다. 이번주 스터디 한 세 문제를 차례로 포스팅해보려고 한다. 문제와 풀이 문제 링크 : 백준 2875번 - 대회 or 인턴 👇펼쳐서 코드와 해설 읽기 그리디(greedy) 카테고리의 문제다. 팀을 만드는 데에는 여자2와 남자1이 필요하고, 인턴은 아무나 1이 필요하다. 일단 팀이 많은게 좋다고 하니까, 가능한 팀을 최대한 구성해 놓고, 그다음에 인턴갈 인원을 차출한다. 인턴 갈 사람수가 부족하면 팀을 깨야하는데, 한팀씩 깨서 부족한 만큼만 팀을 깨야 한다. 그리고 결과를 출력해주면 된다. import java.util.Scanner; public class Main { public static void main(String..