본문 바로가기

분류 전체보기229

9575번: 백준 - 행운의 수(Java) 본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다. 저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다. 문의는 댓글 바람. 문제 출처 : https://www.acmicpc.net/problem/9575 [문제 설명] 3개의 배열이 주어지고 각 배열에서 숫자를 하나씩 뽑아 더했을 때 합을 구한다. 그 합이 5와 8로만 이루어졌으면 이 숫자는 행운의 숫자다. 행운의 숫자의 총 개수를 구하시오. [접근 방법] 제약 조건 수열 크기는 50을 넘지 않고, 원소는 30,000보다 작거나 같은 양의 정수 1125,000 문제에선 중복된 숫자는 같은 걸로 처리함. 2. 중복을 처리할 수 있는 방법들 2.1 해시셋 2.2 배열을 이용하여 방문처리 만족하는 원소 개수(행운.. 2022. 1. 21.
백준 - 연결 요소의 개수(Java) 본 알고리즘 풀이는 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.. 2022. 1. 20.
백준 - 특정 거리의 도시 찾기 본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다. 저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다. 문의는 댓글 바람. 문제 출처 : https://www.acmicpc.net/problem/18352 [문제 설명] 어느 도시로부터 특정 거리의 있는 도시들을 오름차순으로 출력하시오. [접근 방법] 시작 도시를 기준으로 BFS하여, 같은 층(같은 거리)에 있는 요소들을 반환하면 된다. 주의해야 할 점은 사이클(시작점과 끝점이 같은 경로)이 있으므로 방문 여부를 체크해줘야 한다는 것과 오름차순으로 결과를 반환해야 한다는 것. 리스트에 넣어서 퀵정렬을 통해 정렬한 후에 반환해줘도 되겠지만, 그것보다는 메모리를 추가적으로 쓰더라도 배열을 따로 만들어서 리턴해주.. 2022. 1. 20.
백준 - 결혼식(Java BFS) 본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다. 저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다. 문의는 댓글 바람. 문제 출처 : https://www.acmicpc.net/problem/5567 [문제 설명] 친구랑 친구의 친구만 초대해라. [접근 방법] 순수 트리 문제인줄 알고 골랐는데 그래프 문제였다. 트리도 그래프가 맞긴 한데; 처음엔 맵을 이용해서 풀려고 했는데, (2,1) 이런 형식으로 입력이 올 수도 있어서 그래프를 이용해 풀었다. 그래프를 2차원 배열로 구현할까도 싶었지만, 일일이 모든 노드가 연결 됐는지 파악하기 보다는(O(V^2)) 연결된 노드만 추가하는(O(V+E)) 연결리스트가 나아보여서 연결 리스트로 구현했다. 검색은 BFS .. 2022. 1. 19.
백준 - 바닥 장식(Java) 본 알고리즘 풀이는 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.. 2022. 1. 19.
알고리즘 기본 - 에라토스테네스의 체 참고 블로그 https://firework-ham.tistory.com/8 [JAVA] 소수 구하는 알고리즘 : 에라토스테네스의 체 소수 구하는 알고리즘으로 유명한 에라토스테네스의 체입니다. 고대 그리스의 수학자 에라토스테네스가 만들어 낸 소수를 찾는 방법으로 코딩 알고리즘에서 소수를 구할 때도 이 방법을 사용 firework-ham.tistory.com 에라토스테네스의 체는 kks 블로그에서 이름만 보고 지레 겁먹어서 미뤘던 카테고리다. 그러다 소수 구하기 알고리즘을 보다가 우연히 발견했는데 생각보다 간단하다. 결국 소수를 구한 다음에 그 배수들을 소수에서 제외하는 방식. 자바로 구현해봤는데 구현 난이도도 굉장히 쉬웠다. import java.io.IOException; import java.util... 2022. 1. 19.

티스토리툴바