본문 바로가기

알고리즘 문제 풀이207

백준 - 결혼식(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.
백준 - 경비원 본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다. 저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다. 문의는 댓글 바람. 문제 출처 : https://www.acmicpc.net/problem/2564 [문제 설명] 상점까지 모서리를 따라 가는 최소거리의 합 [접근 방법] 문제를 보자마자 떠오른 건 BFS였는데 읽어보니까 모서리를 따라서 가야한다는 조건이 있다. 처음엔 단순히 X좌표 Y좌표끼리 연산을 하면 모든 경우의 수를 처리할 수 있을 줄 알았는데 맞은 편에 있을 때만 성립한다는 걸 알았다. 따라서, 맞은 편에 있을 때와 나머지 경우의 수로 나눠서 풀어야 한다. 이 문제를 풀면서 아쉬웠던 점이, 맞은 편에 있는 조건을 하드코딩으로 짰다는 게 아쉽다. .. 2022. 1. 17.
백준 - 랜선 자르기(Java) 본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다. 저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다. 문의는 댓글 바람. 문제 출처 : https://www.acmicpc.net/problem/1654 [문제 설명] 전형적인 이분탐색을 이용하는 문제 [접근 방법] 딱 봐도 이분탐색이라 자신 있게 접근했다가, 부족함을 알게해준 문제. https://st-lab.tistory.com/269 [백준] 1654번 : 랜선 자르기 - JAVA [자바] https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000.. 2022. 1. 17.
백준 - 계란으로 계란치기 (Java) 본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다. 저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다. 문의는 댓글 바람. 문제 출처 : https://www.acmicpc.net/problem/16987 [문제 설명] 문제가 너무 거창하고 길어서 헤메기 좋은 문제입니다. 특히 2번 조건과 3번 조건이 엄청 헷갈렸습니다. 3번 같은 경우 아직도 헷갈립니다. 잡론은 각설하고 문제의 유형은 완전탐색으로 모든 경우의 수를 만드는 것입니다. 시간복잡도는 계란의 개수^계란의 개수라 언뜻 보면 시간 초과가 날것처럼 보이지만 계란의 개수가 최대 8개이므로 8^8 => 2^24으로 16,777,216 => 1600만밖에 되지 않습니다. import java.io.*; i.. 2022. 1. 17.

티스토리툴바