전체 글
-
[백준 2644번] 촌수 계산 (Java 풀이)Algorithm/DFS 2022. 5. 23. 21:13
백준알고리즘 2644번 : 촌수 계산 (Solved.ac 난이도 Gold5) https://www.acmicpc.net/problem/2644 2644번: 촌수계산 사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어 www.acmicpc.net 촌수를 이동함에 따라 count를 해주어야하는 부분에서 약간 헤멨다. 특이사항이 있다면, 일반적인 dfs와는 달리 한번 check한 LinkedList에 대해서는 다시 확인을 할 필요가 없다는 점이다. 그렇게 해도 되는 이유는 문제에서 '각 사람의 부모는 최대 한 명만 주어진다.'라고 명시되어 있기 때..
-
[백준 11725번] 트리의 부모 찾기 (Java 풀이)Algorithm/DFS 2022. 5. 17. 18:34
백준알고리즘 11725번 : 트리의 부모 찾기 (Solved.ac 난이도 Silver2) https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net DFS와 BFS 모두를 이용해서 풀 수 있는 문제였다. LinkedList 타입의 배열을 정의하는 것이 문제 해결에 도움이 많이 되었다. 아직 DFS 및 BFS에 익숙치않아 2가지버전 모두 사용해서 풀어보았다. 실제 소스의 차이는 그리 크지 않다. method를 재귀로 할 것인지, while문을 낀 queue로 할 것인지의 차이정도? 속도 차이도 유의미하게 크지는 않았다...
-
[백준 14502번] 연구소(자바)Algorithm/BFS 2022. 5. 14. 18:07
백준알고리즘 14502번 : 연구소 (Solved.ac 난이도 Gold5) https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 벽을 세우는 경우의 수만큼 BFS를 돌려보는 방식으로 풀 수 있었다. 우리는 배열에서 0을 갖고있는 위치 3군데를 1로 바꾸어 벽으로 만들 수 있다. 3중 for문을 돌려서 0 3개를 1로 바꾼 뒤, BFS를 적용하여 바이러스를 침투시켜본다. 그 후에 남은 0의 개수를 count하면 해당 case의 안전 영역 크기를 도출할 수 있다. ..
-
[백준 7576번] 토마토 (자바)Algorithm/BFS 2022. 5. 13. 21:46
백준알고리즘 7576번 : 토마토 (Solved.ac 난이도 Gold5) https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 전형적인 BFS문제이다만.. 나는 DFS로 몇 번 시도해보고서야 완전 틀린 해석이었다는 걸 깨달았다. DFS로 하게되었을 때의 문제점이라면, 각 구역마다 한번의 탐색으로 끝내도 될 것을 계속 접근하여 비효율적으로 만드는 것이다. 잘 익은 토마토를 기준으로 너비 우선탐색으로 뻗어나가면, 애초에 검증이 많이 필요..
-
[백준 2473번] 세 용액 (Java 풀이)Algorithm/정렬(Sort) 2022. 5. 6. 20:27
백준알고리즘 2473번 : 세 용액 (Solved.ac 난이도 Gold4) https://www.acmicpc.net/problem/2473 2473번: 세 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 www.acmicpc.net 숫자 3개를 선택하여 가장 절대값이 가장 작은 숫자를 만드는 조합을 출력하는 문제이다. 두개라면 two pointer를 사용하여 풀 수 있을꺼라 생각하였는데, 고민하다가 하나를 고정하는 대신 나머지 2개를 투 포인터로 fix하는 방법은 어떨까 생각해보았다. 물론 내가 작성한 logic은 중복으로 탐색하..
-
[백준 7453번] 합이 0인 네 정수 (Java 풀이)Algorithm/정렬(Sort) 2022. 4. 29. 13:07
백준알고리즘 7453번 : 합이 0인 네 정수 (Solved.ac 난이도 Gold2) https://www.acmicpc.net/problem/7453 7453번: 합이 0인 네 정수 첫째 줄에 배열의 크기 n (1 ≤ n ≤ 4000)이 주어진다. 다음 n개 줄에는 A, B, C, D에 포함되는 정수가 공백으로 구분되어져서 주어진다. 배열에 들어있는 정수의 절댓값은 최대 228이다. www.acmicpc.net 첫번째로 간과한 부분은 12초가 꽤 러프하다고 생각하여 단순 계산으로 시도해본 것이고, 두번째로 간과한 부분은 속도를 높이기 위해 투 포인터 방식을 사용했으나 동일한 연산에 대하여 곱셈이 아니라 덧셈으로 count를 해준 것이다. 예를들어 AxB 배열에 13이 3개, CxD 배열에 -13이 3개..
-
[백준 2193번] 이친수 (자바)Algorithm/Dynamic Programming(DP, 동적 프로그래밍) 2022. 4. 20. 20:05
백준알고리즘 2193번 : 이친수 (Solved.ac 난이도 Silver3) https://www.acmicpc.net/problem/2193 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 규칙을 찾고나면 어렵지 않게 풀 수 있는 문제같다. 그리고 규칙을 찾는 방법은 작은 경우에서부터 하나씩 크기를 늘리면서 앞전 경우와 연결되는 연속성을 발견하는 것이다. 예를 들어 3자리 숫자일때와 4자리 숫자일때를통ㅇ해 규칙을 찾아보자. 3자리 숫자일때는 100, 101로 총 2가지 경우의 수가 있다. 4자리 ..
-
[백준 11727번] 2×n타일링2 (자바)Algorithm/Greedy Algorithm 2022. 4. 16. 18:35
백준알고리즘 11727번 : 2Xn 타일링 2 (Solved.ac 난이도 Silver3) https://www.acmicpc.net/problem/11727 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net 2xn 타일링1 문제를 풀었으면 이 문제도 어렵지 않게 풀수 있을 것 같다. 역시 dp 알고리즘의 기본은 쪼개기다. 다만 이번에는 2xn 타일링1 문제때와는 달리 '2x1 막대가 오는 경우와 1x2 막대가 오는 경우'로 나누지 않고 '2x1 막대가 오는 경우와 2x1 막대가 오지 않는 경우'로 나눠주었다. 이렇게 나눈 이유는 이번 문제에는..