잡다한 IT 지식

본 알고리즘 풀이는 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..

참고 블로그 https://firework-ham.tistory.com/8 [JAVA] 소수 구하는 알고리즘 : 에라토스테네스의 체 소수 구하는 알고리즘으로 유명한 에라토스테네스의 체입니다. 고대 그리스의 수학자 에라토스테네스가 만들어 낸 소수를 찾는 방법으로 코딩 알고리즘에서 소수를 구할 때도 이 방법을 사용 firework-ham.tistory.com 에라토스테네스의 체는 kks 블로그에서 이름만 보고 지레 겁먹어서 미뤘던 카테고리다. 그러다 소수 구하기 알고리즘을 보다가 우연히 발견했는데 생각보다 간단하다. 결국 소수를 구한 다음에 그 배수들을 소수에서 제외하는 방식. 자바로 구현해봤는데 구현 난이도도 굉장히 쉬웠다. import java.io.IOException; import java.util...