자바
-
Q. 11403 자바 : 경로 찾기코딩테스트/백준_Java 2023. 4. 5. 09:31
Q. 11403 자바 : 경로 찾기 문제 : boj.kr/11403 실버 1 난이도의 문제이다. 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로 존재 여부를 구하라는 내용이다. 그래프 탐색 강의를 듣고 예제 문제를 푸는 도중이었는데 이 문제는 List를 그래프 탐색이라고 되어 있어서 List를 사용해서 풀었지만, 만약 이를 몰랐다면 입력이 격자형 그래프로 주어져서 격자형 그래프로 풀었을 것 같다. 문제를 이해하는데 시간이 좀 걸렸다.. 입력이 아래와 같이 주어졌을 때 3 0 1 0 0 0 1 1 0 0 출력이 아래와 같다. 1 1 1 1 1 1 1 1 1 즉 정점이 0, 1, 2가 있다면 입력을 간선으로 바꾸면 0 -> 1, 1 -> 2, 2 -> 0..
-
Q. 20366 자바 : 같이 눈사람 만들래?코딩테스트/백준_Java 2023. 3. 27. 22:27
문제 :boj.kr/20366 골드 3 난이도의 문제이다. 투 포인터 강의를 듣고나서, 투 포인터 유형의 다른 문제들을 찾아보다가 발견한 문제이다. 처음에 문제를 봤을 때는 어떻게 접근해야 할 지 감이 안잡혔었는데, 감이 안잡혀서 검색을 했더니, 세 용액 문제와 비슷한, 네 용액 문제로 풀면 된다는 내용이 있길래 그 내용만 보고 추측해서 풀었더니 다행히 풀렸다.(다른 블로그 코드 참고x) 문제를 보면 하나의 눈사람은 두 개의 눈덩이로 구성되고 눈덩이가 주어지면, 두 눈사람의 키 차이가 가장 작은 값을 구하라는 문제이다. 1. 투 포인터 알고리즘을 이용해 값을 조정하려면, 눈덩이들이 정렬된 상태여야 하므로 먼저 정렬을 해준다. - O(N log N) 2. 네 개의 값을 뽑아야 하므로 먼저 두 개의 값을 선..