잡다한 IT 지식

본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다. https://github.com/ROUTINE-STUDY/Algorithm 저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다. GitHub - ROUTINE-STUDY/Algorithm: 초보 알고리즘 스터디 / 누구나 참여 가능 초보 알고리즘 스터디 / 누구나 참여 가능 :runner:. Contribute to ROUTINE-STUDY/Algorithm development by creating an account on GitHub. github.com 문의는 댓글 바람. 문제 출처 :https://www.acmicpc.net/problem/2606 [문제 설명] 간단한 그래프 탐색 문제. 1번 노드..

본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다. 저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다. 문의는 댓글 바람. 문제 출처 :https://www.acmicpc.net/problem/11724 [문제 설명] 그래프가 총 몇개인지 구하시오. [접근 방법] 노드들을 모두 입력 받은 후, 탐색을 통하여 그래프 하나를 전부 순회하면 개수를 하나 추가하는 방법으로 풀었다. 그래프를 BFS로 모두 순회하므로 시간복잡도는 O(N+M). 공간복잡도도 인접행렬로 구현할 경우 O(N^2)이라, 연결리스트로 구현해서 O(N+M)가 된다. 결론 : 시간 복잡도 O(N+M) 공간복잡도 O(N+M) [내 답안 수정하기] import java.io.BufferedReade..

본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다. 저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다. 문의는 댓글 바람. 문제 출처 : https://www.acmicpc.net/problem/18352 [문제 설명] 어느 도시로부터 특정 거리의 있는 도시들을 오름차순으로 출력하시오. [접근 방법] 시작 도시를 기준으로 BFS하여, 같은 층(같은 거리)에 있는 요소들을 반환하면 된다. 주의해야 할 점은 사이클(시작점과 끝점이 같은 경로)이 있으므로 방문 여부를 체크해줘야 한다는 것과 오름차순으로 결과를 반환해야 한다는 것. 리스트에 넣어서 퀵정렬을 통해 정렬한 후에 반환해줘도 되겠지만, 그것보다는 메모리를 추가적으로 쓰더라도 배열을 따로 만들어서 리턴해주..

본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다. 저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다. 문의는 댓글 바람. 문제 출처 : https://www.acmicpc.net/problem/5567 [문제 설명] 친구랑 친구의 친구만 초대해라. [접근 방법] 순수 트리 문제인줄 알고 골랐는데 그래프 문제였다. 트리도 그래프가 맞긴 한데; 처음엔 맵을 이용해서 풀려고 했는데, (2,1) 이런 형식으로 입력이 올 수도 있어서 그래프를 이용해 풀었다. 그래프를 2차원 배열로 구현할까도 싶었지만, 일일이 모든 노드가 연결 됐는지 파악하기 보다는(O(V^2)) 연결된 노드만 추가하는(O(V+E)) 연결리스트가 나아보여서 연결 리스트로 구현했다. 검색은 BFS ..

본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다. 저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다. 문의는 댓글 바람. 문제 출처 : https://www.acmicpc.net/problem/1388 [문제 설명] 선의 개수를 구하시오 [접근 방법] -모양이면 양옆으로 조회. |모양이면 위아래로 조회 시간복잡도는 어차피 모든 타일을 돌아야하므로 O(NM)이 될 듯. [리팩토링 전 코드] import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { publ..