박카스러버

https://www.acmicpc.net/problem/17616 17616번: 등수 찾기 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에 세 정수 N, M, X가 공백을 사이에 두고 주어진다. (2 ≤ N ≤ 105, 1 ≤ M ≤ min(N(N-1)/2, 5×105), 1 ≤ X ≤ N) . 다음 M 줄에는 각각 두 정수 A, B가 주어 www.acmicpc.net 저는 bfs를 이용해 문제를 해결하였습니다. 저는 x에게 이긴 사람의 수와 진 사람의 수를 각각 bfs를 이용해 찾았습니다. x의 등수는 ( x에게 진 사람 수 + 1 ) ~ ( 전체 사람 수 - x에게 이긴 사람 수 ) 입니다. package BOJ.bfs; import java.io.BufferedReader; import jav..

https://www.acmicpc.net/problem/17836 17836번: 공주님을 구해라! 용사는 마왕이 숨겨놓은 공주님을 구하기 위해 (N, M) 크기의 성 입구 (1,1)으로 들어왔다. 마왕은 용사가 공주를 찾지 못하도록 성의 여러 군데 마법 벽을 세워놓았다. 용사는 현재의 가지고 있는 www.acmicpc.net 저는 BFS를 이용해 문제를 해결하였습니다. BFS를 이용해 경로를 탐색하고, 만약 칼을 줍는다면 해당 노드에서 파생되는 노드들은 BFS조건에서 벽인지 확인하는 과정을 없앴습니다. 방문 배열도 칼을 가지고 있는지 없는지를 나눠서 체크하였습니다. package BOJ.bfs; import java.io.BufferedReader; import java.io.InputStreamRea..

https://www.acmicpc.net/problem/16401 16401번: 과자 나눠주기 첫째 줄에 조카의 수 M (1 ≤ M ≤ 1,000,000), 과자의 수 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 과자 N개의 길이 L1, L2, ..., LN이 공백으로 구분되어 주어진다. 과자의 길이는 (1 ≤ L1, L2, ..., LN ≤ 1, www.acmicpc.net 저는 이분탐색을 통해 문제를 해결하였습니다. 저는 mid값으로 몇개의 과자를 만들 수 있는지를 체크하고 이 개수가 사람의 수보다 큰지를 확인하여 크다면 start = mid +1 작다면 end = mid - 1 로 하여 최대로 길게 줄 수 있는 과자 길이를 찾았습니다. 시간복잡도 : O(n(log(n)*m)) (..

저는 TDD를 공부하던 중 TDD를 이용하여 알고리즘 문제를 풀면 괜찮지 않을까?라는 생각을 하게 되었습니다. 시간은 조금 더 걸리겠지만, TDD의 장점인 내 코드에 대한 피드백이 빠르기 때문에 즉각적으로 제가 잘못 작성한 코드를 알 수 있을 것이라는 기대감을 품고 시작하였습니다. 결론부터 말씀드리자면 TDD를 알고리즘 문제에 적용시키는 것은 추천드리지 않습니다. 2164번 소스코드 더보기 package BOJ; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue; import java.util.function.Function; public clas..

https://www.acmicpc.net/problem/12919 12919번: A와 B 2 수빈이는 A와 B로만 이루어진 영어 단어 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다. 이런 사실에 놀란 수빈 www.acmicpc.net 저는 해당 문제를 BFS를 이용해 문제를 해결하였습니다. 문제 그대로 s문자열부터 시작해서 두가지 명령을 하면서 t와 같은지를 BFS하게 되면 시간 초과가 나오게 됩니다. 그래서 저는 역으로 t부터 시작해 s와 같은지를 BFS를 하였습니다. 역으로 하게 되면 맨 앞글자가 'B'일때는 두번째 연산, 마지막 글자가 'A'일때는 첫번째 연산의 역을 하면 되기 때..

https://www.acmicpc.net/problem/2169 2169번: 로봇 조종하기 첫째 줄에 N, M(1≤N, M≤1,000)이 주어진다. 다음 N개의 줄에는 M개의 수로 배열이 주어진다. 배열의 각 수는 절댓값이 100을 넘지 않는 정수이다. 이 값은 그 지역의 가치를 나타낸다. www.acmicpc.net 저는 해당 문제를 DP를 이용하여 문제를 해결하였습니다. 해당 좌표를 오는 방향에 따라서 다르게 고려해야 하기 때문에 일반적인 DP랑 다르게 방향까지 고려하여 DP를 작성하였습니다. ( DP[y좌표][x좌표][이 좌표로 오기 전의 방향] ) 또 다음 방향을 정할 때 왼쪽방향이였다면 오른쪽으로는 못 가게 오른쪽이라면 왼쪽으로는 못 가게 구현하였습니다. package BOJ.DP; impor..

https://www.acmicpc.net/problem/1240 1240번: 노드사이의 거리 N(2≤N≤1,000)개의 노드로 이루어진 트리가 주어지고 M(M≤1,000)개의 두 노드 쌍을 입력받을 때 두 노드 사이의 거리를 출력하라. www.acmicpc.net 저는 해당 문제를 BFS를 이용해 문제를 해결하였습니다. BFS를 이용해 a 지점에서 출발하여 b지점으로 도달하는데 까지의 weight를 구하였습니다. package BOJ.DFS; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.LinkedList; import java.util.List; im..

https://programmers.co.kr/learn/courses/30/lessons/1844 코딩테스트 연습 - 게임 맵 최단거리 [[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,1],[0,0,0,0,1]] 11 [[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,0],[0,0,0,0,1]] -1 programmers.co.kr 저는 해당 문제를 BFS를 이용해 문제를 해결하였습니다. 저는 개인적으로 변수 변수를 통해 벽이나 빈 곳을 표현하는 것이 가독성 측면에서 조금 더 좋은 것 같습니다. import java.util.*; class Solution { private static final int NO_ANSWER = -1; pr..

https://programmers.co.kr/learn/courses/30/lessons/17678 코딩테스트 연습 - [1차] 셔틀버스 10 60 45 ["23:59","23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59"] "18:00" programmers.co.kr 저는 해당 문제를 문자열의 시간을 int타입의 분으로 변경하여 문제를 해결하였습니다. 먼저 입력의 시간을 모두 분으로 변경하였습니다. 그리고 각각의 버스 시간 전에 도착하는 사람을 구하고 이게 m보다 커지게 되거나 도착한 사람이 버스 시간보다 늦게오면 ..

https://programmers.co.kr/learn/courses/30/lessons/67260 코딩테스트 연습 - 동굴 탐험 9 [[0,1],[0,3],[0,7],[8,1],[3,6],[1,2],[4,7],[7,5]] [[8,5],[6,7],[4,1]] true 9 [[8,1],[0,1],[1,2],[0,7],[4,7],[0,3],[7,5],[3,6]] [[4,1],[5,2]] true 9 [[0,1],[0,3],[0,7],[8,1],[3,6],[1,2],[4,7],[7,5]] [[4,1],[8,7],[6,5]] false programmers.co.kr 저는 해당 문제를 BFS를 이용하여 문제를 해결하였습니다. 먼저 먼저 방을 방문해야 갈 수 있는 곳은 isLocked를 통해 표시하여 BFS때 ..