박카스러버

https://www.acmicpc.net/problem/2098 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 저는 해당 문제를 비트마스킹과 DP를 이용하여 문제를 해결하였습니다. 브루트 포스같은 경우 N이 16이기 때문에 시간복잡도가 16!이기 때문에 시간초과가 날 것이라 생각하였습니다. 비트마스킹을 통해 지금까지 거쳐간 경로를 표현하고 dp는 dp[현재 어떤 지점에 있는지][비트마스킹으로 표현한 경로]로 하였습니다. package BOJ.ETC; import jav..

저는 책을 읽다보니 TDD에 관심을 가지게 되었습니다. 해당 책에서는 실험을 통해 TDD에 대한 얘기를 했고 TDD 미적용시 30분 정도 걸리는 코드를 TDD를 적용시켰을 때 대략 10%정도 빠르게 작업이 완료되었다고 한다. 그래서 저도 TDD를 적용시켜보고자 자료를 찾아보던 중 DDD START!의 저자이신 최범균님의 TDD 유튜브를 찾게 되었습니다. (밑에 해당 유튜브의 링크를 걸어놨습니다.) 이제부터 작성하는 글은 해당 유튜브의 내용을 요약이니 유튜브를 직접 보시는 것을 강력히 추천드립니다. 최범균님께서 예시를 들어 실제로 TDD를 적용했을 때 어떻게 개발이 진행되는지를 라이브 코딩으로 보여주십니다. 😀 테스트 코드의 필요성 수동 테스트 - 검증 범위 누락 발생하기 쉽다. - 예외 상항 검증하기 어..

https://www.acmicpc.net/problem/1026 1026번: 보물 첫째 줄에 N이 주어진다. 둘째 줄에는 A에 있는 N개의 수가 순서대로 주어지고, 셋째 줄에는 B에 있는 수가 순서대로 주어진다. N은 50보다 작거나 같은 자연수이고, A와 B의 각 원소는 100보다 작거 www.acmicpc.net 저는 해당 문제를 A,B 배열을 소팅하여 A는 낮은 숫자부터 B는 높은 숫자부터 곱하여 곱의 최소를 구하였습니다. 시간 복잡도 : O(nlog(n)) package BOJ.Greedy; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays; import java.util.Collecti..

https://www.acmicpc.net/problem/16437 16437번: 양 구출 작전 2, 3, 5번에 사는 모든 양들은 1번 섬으로 갈 수 있지만 7번 섬에 사는 양들은 1번 섬으로 가기 위하여 6번 섬을 거쳐야 하는데 6번 섬에 사는 늑대들의 수가 7번 섬에 사는 양들의 수보다 많으므로 www.acmicpc.net 저는 해당 문제를 DFS를 이용해 문제를 해결하였습니다. 처음에는 BFS를 통해 문제를 해결하려 하였지만, 시간초과를 피할 수 없었습니다. 각각의 양에서 경로를 이동하는 로직이였는데 이럴 경우 중복되는 노드를 여러번 방문할 수 있어 시간초과가 나오는 것 같습니다. 그래서 dfs를 통해 문제를 해결하였습니다. dfs를 사용하면 한 노드에 한 번만 방문해서 문제를 해결할 수 있었습니..

https://www.acmicpc.net/problem/6118 6118번: 숨바꼭질 재서기는 수혀니와 교외 농장에서 숨바꼭질을 하고 있다. 농장에는 헛간이 많이 널려있고 재서기는 그 중에 하나에 숨어야 한다. 헛간의 개수는 N(2

https://www.acmicpc.net/problem/2617 2617번: 구슬 찾기 모양은 같으나, 무게가 모두 다른 N개의 구슬이 있다. N은 홀수이며, 구슬에는 번호가 1,2,...,N으로 붙어 있다. 이 구슬 중에서 무게가 전체의 중간인 (무게 순서로 (N+1)/2번째) 구슬을 찾기 위해서 www.acmicpc.net 저는 해당 문제를 단방향 인접 리스트를 통해 포현하였습니다. 이를 통해 그래프 탐색하면서 해당 구슬보다 몇개가 더 무거운지 , 몇개가 더 가벼운 지를 찾았습니다. 이 두개의 값이 (n/2+1) 보다 큰지를 확인하였습니다. 해당 구슬보다 가벼운 것들의 개수나 무거운 것들의 개수 둘 중 하나라도 (n/2+1) 보다 커진다면 중간 무게의 구슬이 될 수 없기 때문에 이보다 커진다면 결과..

https://www.acmicpc.net/problem/15971 15971번: 두 로봇 2018년 강원도에서 새로운 동굴이 발견되었다. 이 동굴에는 총 N개의 넓은 방이 존재하며 좁은 통로로 서로 연결되어 있는 것으로 밝혀졌다. N개의 방은 1번부터 N번까지의 번호를 붙여 1번 방, 2번 www.acmicpc.net 저는 해당 문제를 BFS를 이용해 문제를 해결하였습니다. 처음에는 robot1과 robot2의 위치를 bfs로 하여 시간초과가 나왔습니다. 문제를 다시 읽어보니 robot1에서 bfs를 진행하고 robot2까지 최단거리에서 그 중 가중치가 가장 큰 edge를 빼주면 되는 것이였습니다. package BOJ; import java.io.BufferedReader; import java.io..

https://www.acmicpc.net/problem/2406 2406번: 안정적인 네트워크 첫째 줄에 두 정수 n(1 ≤ n ≤ 1,000), m(0 ≤ m ≤ 10,000)이 주어진다. n은 컴퓨터의 개수이며, m은 연결되어 있는 지사 컴퓨터들의 쌍의 개수이다. 다음 m개의 줄에는 두 정수 x, y가 주어진다. 이는 서 www.acmicpc.net 저는 해당 문제를 프림알고리즘을 이용하여 문제를 해결하였습니다. 저는 직접 연결되어 있는 경우 해당 가중치를 모두 0으로 변경하였습니다. 본사는 지사 컴퓨터와 모두 연결되어 있기 때문에 본사는 프림에서 제외하고 진행하였습니다. 본사를 제외한 지사 컴퓨터들이 MST라면 본사와의 연결이 끊겨도 다른 지사를 통해서 연결되기 때문입니다. 프림 알고리즘을 진행하..

https://www.acmicpc.net/problem/2623 2623번: 음악프로그램 첫째 줄에는 가수의 수 N과 보조 PD의 수 M이 주어진다. 가수는 번호 1, 2,…,N 으로 표시한다. 둘째 줄부터 각 보조 PD가 정한 순서들이 한 줄에 하나씩 나온다. 각 줄의 맨 앞에는 보조 PD가 담당한 www.acmicpc.net 저는 해당 문제를 위상정렬을 통해 해결하였습니다. 위상정렬을 통해 사이클이 존재하는지도 확인할 수 있기 때문에 사이클이 존재한다면 0을 리턴하도록 하였습니다. 시간복잡도 : O(V + E) package BOJ; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.LinkedList;..

https://www.acmicpc.net/problem/9344 9344번: 도로 어떤 나라에는 1부터 N까지 이름 붙여진 N개의 도시가 있다. 한 엔지니어는 모든 도시를 연결하는 도로를 건설하고자 한다. 즉, 모든 도시에 대해 항상 다른 어떤 도시로든 이동할 수 있어야 한다 www.acmicpc.net 저는 크루스칼을 통해서 해당 문제를 해결하였습니다. 저는 n^2에 비해 길의 수가 많이 작아서 크루스칼이 더 유리할 것이라 판단하였습니다. 크루스칼을 하면서 pq가 크루스칼에 포함되는지를 판단하여 포함된다면 true 그렇지 않다면 false를 리턴하여 문제를 해결하였습니다. 시간복잡도 : O(nlog(n)) package BOJ; import java.io.BufferedReader; import ja..